On Tue, May 6, 2014 at 5:28 AM, Johannes Merkle <[email protected]> wrote: > > To be more specific: If a new attack emerges on curves defined over > Pseudo-Mersenne (or other special) primes, having 32 > bits of extra security against Pollard's Rho might not buy us much. > Admittedly, there is no indication of such attacks, > but since we don't have any clue about what attacks might evolve, the most > conservative choice is to avoid simplified > structures, in particular, if these structures had already been exploited by > attacks in other circumstances (yes, I'm > talking about the specialized NFS).
Hi Johannes, I'm not qualified to assess this, so I'll look to people like Bernstein, Lange, Hamburg, etc. Bernstein and Lange don't seem to think that's important [1]: "Special primes help index calculus, but the point of ECC has always been to avoid index calculus. All of the SafeCurves requirements can be met by special primes." Mike agrees that random primes might protect against future cryptanalysis, but points out they bring a substantial cost [2]: "a random field would be at least twice as slow". If that's true, I think you'd expect a random-prime curve to be about the same speed as a curve 1.3x the size (2 ^ 1/2.6). So a 384-bit random-prime curve would be about as slow as a fast-prime 500-bit curve, but would have a nominal security level of 192 bits instead of 250. So I guess this is a tradeoff between different strategies for adding margin against cryptanalysis? Do you think 2x slower is accurate? (Or do you have performance numbers on Brainpool or similar curves I could add to the spreadsheet [3])? Trevor [1] http://safecurves.cr.yp.to/field.html [2] http://www.ietf.org/mail-archive/web/cfrg/current/msg03961.html [3] https://docs.google.com/a/trevp.net/spreadsheet/ccc?key=0Aiexaz_YjIpddFJuWlNZaDBvVTRFSjVYZDdjakxoRkE&usp=sharing#gid=0 _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
