<!DOCTYPE html>

<html>

  <head>

    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

  </head>

  <body>

    <p><br>

    </p>

    <div class="moz-cite-prefix">On 7/24/24 21:50, Seth David Schoen

      wrote:<br>

    </div>

    <blockquote type="cite" cite="mid:ZqHZo5TnjlM8mUuC@demorgan"><span

      style="white-space: pre-wrap"></span><span

      style="white-space: pre-wrap">

</span>

      <pre class="moz-quote-pre" wrap="">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.)

</pre>

    </blockquote>

    <p>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. <br>

    </p>

    <p>In either case I believe that attacks on elliptic-curve systems

      are exponential, although the exponent is somewhat less than two.</p>

    <p>Bear</p>

    <p><br>

    </p>

  </body>

</html>