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

[Andrey Jivsov <[e-mail]>]

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.

( I know that e.g. NIST documents recommend a private key to be as you Mike
wrote, e.g. 256 bits for P-256)

Thank you.

On Wed, Oct 21, 2020 at 1:14 PM Mike Hamburg <[e-mail]> wrote:

> Hello again Mike,
>
> In general, secrets for discrete log systems have to be at least
> twice the security level, due to collision-based attacks such as
> Pollard rho, baby-step-giant-step, etc.
>
> This is also why P-1 must be divisible by a prime that’s at least
> 2*lambda bits, where lambda is the desired security level.
> Otherwise the Pohlig-Hellman attack breaks the system.
>
> Cheers,
> — Mike
> ...
>