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.
* At the CRYPTO rump session, we will generate a seed.
o 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.
o 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.
o 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.
+ At least one photo should be taken with a film camera,
preferably a Polaroid; or we should print out some photos on
the spot.
o The seed will be entered into a console connected to an EC2 or
similar cluster.
o The exact format in which the seed will be entered must be
specified ahead of time.
+ 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).
* The cluster will find suitable Edwards curves.
o The field orders will have bit-lengths 160, 192, 224, 256, 384
and 512, or possibly some subset of these.
o 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.
o 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.
o 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.
+ 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.
* If we want to generate prime-order short Weierstrass curves, that
can be done as well.
o The primes should probably be the same as for Edwards, to
simplify implementation.
o I would suggest a4 = -3 for performance, since there is an
isomorphic curve to this with reasonable probability anyway.
o We would hash "-a-" instead of "-d-".
o Obviously we would have to ignore the "it must be an Edwards
curve" criteria in the SafeCurves spec.
* If we rent enough cores, we can probably hand out the results at the
end of the rump session. Otherwise, the next day.
* Later, people can verify that the curves were randomly generated.
o 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.
o They will have the documentation, the verification script, and
the ability to verify the certificate based on the seed.
o The verification script should run in minutes at most.
* 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.
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
_______________________________________________
Curves mailing list
[email protected]
https://moderncrypto.org/mailman/listinfo/curves
