[Cryptography] Is there a public-key algorithm whose best-known attack is exponential-time?

[Ray Dillinger]

On 7/24/24 21:50, Seth David Schoen wrote:
> Is Merkle's conjecture actually literally correct, so far as we know?
> That is, is there any public-key cryptosystem where the computational
> work for an attacker, in the best known attack, is actually exponential?
> (I assume that the encryption operation should be polynomial-time, so
> not some algorithm where encryption is exponential-time and naive
> decryption is also exponential-time, just with a bigger exponent.)

To be clear, are you asking about computational work for the attacker as 
a factor of key size, or as a factor of the computational work required 
to do encryption? The difference is occasionally important.

In either case I believe that attacks on elliptic-curve systems are 
exponential, although the exponent is somewhat less than two.

Bear

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20240913/0b9a3562/attachment.htm>