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

[Ian Goldberg <[e-mail]>]

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