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

[Dan Brown <[e-mail]>]

​in the case of ECC, See
https://eprint.iacr.org/2015/605
For recent work in this area.

Sent with BlackBerry Work (www.blackberry.com)
________________________________
From: Andrey Jivsov <[e-mail]>
Sent: Oct 21, 2020 9:21 PM
To: Mike Hamburg <[e-mail]>
Cc: Michael D'Errico <[e-mail]>; IRTF CFRG <[e-mail]>
Subject: Re: [Cfrg] Your Secret is Too Short (was: Is Diffie-Hellman Better Than We Think?)

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]<mailto:[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
...

----------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.