[curves] Any interest in random curves?

[Mike Hamburg]

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20140625/7d793be8/attachment.html>