<html> <head> <meta http-equiv="content-type" content="text/html; charset=ISO-8859-1"> </head> <body bgcolor="#FFFFFF" text="#000000"> Hey Curves folk, There's been some flak thrown up at "verifiably random" curves recently, and I'm wondering if there's any interest in doing it right. Of course, it's not obvious at all that random curves should have any quality which is better than, say, the Microsoft "2^NIST - minimal such that 3 mod 4" curves. But if anyone cares about the random case, CRYPTO would be the place to generate the curves. I would suggest a procedure like the following. It's a rough sketch and I'd like to hear suggestions. <ul> <li> At the CRYPTO rump session, we will generate a seed.</li> <ul> <li>The process will be explained with handout cards that have an explanation, and hash values of documentation and verification (at least) scripts that we will distribute over the internet, presumably before and after. This commits us to the procedure. The hash values will be written in large font, so that they can be photographed. </li> <li>Human-powered entropy sources that can be photographed will be used to create the seed. A half-dozen Boggle boards are an easy choice, as are dice or Bananagrams tiles. They will be shaken by members of the audience. </li> <li>Audience takes photographs of the seed with the handouts behind them. The hash values will be visible in the photographs along with the seed, because they are in large font. </li> <ul> <li>At least one photo should be taken with a film camera, preferably a Polaroid; or we should print out some photos on the spot. </li> </ul> <li>The seed will be entered into a console connected to an EC2 or similar cluster.</li> <li>The exact format in which the seed will be entered must be specified ahead of time.</li> <ul> <li>Eg, the Boggle boards will be entered left to right. Each board will be entered left-to-right, then top-to-bottom like English text. Rotation will be ignored. The letters will be capitalized as on the board (with Qu entered like that if it so reads on the tile). </li> </ul> </ul> <li>The cluster will find suitable Edwards curves.</li> <ul> <li>The field orders will have bit-lengths 160, 192, 224, 256, 384 and 512, or possibly some subset of these. </li> <li>The prime will be generated by computing a truncated hash of the seed, "-", the desired bitlength, "-p-", and a counter. The counter will be in decimal and will count from 1. This string will not be null-terminated. We will set the high bit and the low two bits of the candidate modulus, so that the prime must be of the correct length and must be 3 mod 4. For each bit length, the least positive counter which results in a prime will be used. </li> <li>An untwisted Edwards curve will be generated by the truncated hash seed-bitlength-d-counter. The least positive counter which results in a curve that meets the SafeCurves criteria (with this spec considered to provide rigidity) with cofactor exactly 4 will be used. It will take perhaps a couple hundred core hours to find all the curves. </li> <li>The generation script will generate a certificate that the curve was correct, and for why smaller counters were rejected. For the primes this will consist of a base which causes Miller-Rabin to fail. For the curves it will consist of a point of order 8, or order less than 1/4 the Hasse-Weil bound on the curve, or composite order inside 1/4 the Hasse-Weil bound of the curve. This might take a comparable amount of time to key generation.</li> <ul> <li>I don't know how to check all the SafeCurves criteria. The ones which aren't about orders hold with high probability, but we should still check them. </li> </ul> </ul> <li>If we want to generate prime-order short Weierstrass curves, that can be done as well.</li> <ul> <li>The primes should probably be the same as for Edwards, to simplify implementation. </li> <li>I would suggest a4 = -3 for performance, since there is an isomorphic curve to this with reasonable probability anyway.</li> <li>We would hash "-a-" instead of "-d-". </li> <li>Obviously we would have to ignore the "it must be an Edwards curve" criteria in the SafeCurves spec. </li> </ul> <li>If we rent enough cores, we can probably hand out the results at the end of the rump session. Otherwise, the next day. </li> <li>Later, people can verify that the curves were randomly generated.</li> <ul> <li>They will have the words and photographs from the rump session audience, showing the hash of the documentation and the verification script, and the seed. </li> <li>They will have the documentation, the verification script, and the ability to verify the certificate based on the seed.</li> <li>The verification script should run in minutes at most.</li> </ul> <li>If this procedure fails in a way that preserves its entropy and binding properties, it will still be considered valid. If it fails in a way that fails to preserve either property, it is not valid. </li> </ul> Is anyone interested in doing this? Or should we just forget about random options, or use Brainpool? I have versions of some of the scripts for special primes, and it shouldn't be that hard to modify them. Cheers, -- Mike </body> </html>