Re: [Cfrg] Your Secret is Too Short (was: Is Diffie-Hellman Better Than We Think?)

Thanks to an anonymous reply, I see this
https://eprint.iacr.org/2010/615.pdf, sec. 2, which is a good description
of the enhanced algorithm that takes advantage of a short exponent (The
Gaudry-Schost Algorithm). It's similar to Pollard-Rho algorithm, but its
not the the same, and the link below is not an accurate description of this
algorithm. In particular, this later algorithm is structured to contain the
"walk" within the small set corresponding to small exponents, which doesn't
happen with the Pollar-Rho algorithm.

Looks like a private key expanded from 128 bits into 256 is needed as a
mitigation e.g. if you must use a 128-bit secret with e.g. P-256.

Thank you.

On Thu, Oct 22, 2020 at 3:12 PM Andrey Jivsov <crypto@brainhub.org> wrote:

> Hm, this was my original question. When the generator is in a large
> subgroup/group, I don't see how the algorithm on Wikipedia page benefits
> from the limited range of the secret exponent.
>
> I can further enhance my question by saying that instead of using x in
> [1,sqrt(group_order)] the secrets are derived with a KDF(128-bit key, x),
> where KDF's output is 256 bits (mod group order), so that they are
> unpredictable values. However, I don't even see why this is needed.
>
> It seems that the page is written for a small 128-bit subgroup (for a
> 256-bit curve).
>
> On Wed, Oct 21, 2020 at 7:15 PM Ian Goldberg <iang@uwaterloo.ca> wrote:
>
>> On Wed, Oct 21, 2020 at 06:20:33PM -0700, Andrey Jivsov wrote:
>> > Is the Pollar-Rho algorithm able to take advantage of the exponent size
>> > that is about the size of the security parameter?
>> >
>> > Let's consider ECDLP for P-256 or Curve25519. Does private x for public
>> > Q=xG need to be ~256 bits? I would appreciate pointers on how does
>> > Pollard-Rho can take advantage of x~2^128 for P-256 of Curve25519.
>>
>> If you choose x ~ 2^128 and Q=xG, Pollard's kangaroo (aka Pollard's
>> lambda) algorithm can break that in ~2^64 time.
>>
>> https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm
>>
>> > ( I know that e.g. NIST documents recommend a private key to be as you
>> Mike
>> > wrote, e.g. 256 bits for P-256)
>>
>> As well it should.  Is there a standard that suggests choosing a 128-bit
>> x?
>>
>> --
>> Ian Goldberg
>> Canada Research Chair in Privacy Enhancing Technologies
>> Professor, Cheriton School of Computer Science
>> University of Waterloo
>>
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>