Re: [Cfrg] Prime 630*(427!+1)+1 for classic DH?

[Dan Brown <[e-mail]>]

Good points!  Responses inline below (between <<< >>> sorry if that's awkward.)

-----Original Message-----
From: Cfrg [mailto:[e-mail]] On Behalf Of Anna (Amy) Johnston

With a prime like this (and with the knowledge that q is prime), a better way (non-probabilistic) is to use Pocklington's theorem.  Two exponentiations with the right base and you've proved primality.  q can also be checked for primality with Pocklington's, but it takes a larger number of much smaller exponentiations.

<<<
Sounds right.  Primality proofs are good checks before deployment.  I felt they were not needed to tentatively discuss the merits.
>>>

The SNFS reduces the computation cost of the sieve, but as larger base fields become the norm (at least 2048 bits), the linear algebra, not the sieve will be the problem (see iacr e-print 2017/067, page 8, as well as other discrete logarithm records in the past -- all shift work away from the linear algebra to the sieve).  This means that back doors are not as big a concern.

<<< 
I was extrapolating (too much?) from Fried et al. ia.cr/2016/961, especially this from the Section 6.3 Lessons:

"Both from this perspective, and from our more modern one, dismissing
the risk of trapdoored primes in real usage appears to have been a mistake, as
the apparent difficulties encountered by the trapdoor designer in 1992 turn out
to be easily circumvented."

My extrapolation is that for even for very large keysizes, let's not dismiss the possibility of a trapdoor, so let's use some kind of additional countermeasure.  I'm not alone in this, since other fixed DH prime in IETF RFCs are derived from pi, etc. I agree that it may, in the end, be overly cautious, but it seems to have little cost. 
>>>

If sieving attacks are the main concern, then regularly changing  the primes used would be a bigger boost to security.  Fixed primes, uses everywhere, mean that the huge cost of the sieve and solving the system of equations have an even bigger payoff.  Changing primes regularly minimizes an attackers gain from any possible sieve attack -- SNFS, more general, or other index calculus attacks which may be developed. 

<<< 
Yes, you're essentially right about variable primes. I totally forgot to compare to them.  Prime 630*(427!+1)+1 should only be compared to other fixed DH primes. At the moment, I don't remember the usual tradeoffs between fixed and variable classic DH primes ..., but I recall that some like fixed DH primes. 

Hmm, I think variable DH primes compare less favorably to 630*(427!+1)+1 on the issue of the den Boer reduction.  I rather like the original den Boer reduction between DHP and DLP, and nearly optimizing it forces one to a special prime, which might as well (???) be fixed.  I do realize that there are reasonable alternatives to den Boer.  Most simply, just assume that DHP hard.  Use a Maurer-Wolf reduction, or rely on Boneh-Lipton's results about the conjectural existence of such reductions.  I just see the den Boer reduction as simpler, but maybe that's being too sentimental.

Side joke: for those that really like to see vitanums pi and e in their primes (not to mention sqrt(2)), look up Stirling's formula to find them in 630*(427!+1)+1.
>>>