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

[Viktor Dukhovni]

On Thu, Jul 25, 2024 at 03:38:12PM -0700, Jon Callas wrote:

> > On Jul 24, 2024, at 21:50, Seth David Schoen <schoen at loyalty.org> 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.)
> 
> (3) One of the advantages that ECC has over the integers is that its
> strength is similar to symmetric-land, where it's half the number of
> bits.

Which seems meet's the OP's search for an exponential-time *best-known*
attack, though of course the asymptotic behaviour is hardly relevevant
when actual protocols work with specific curves, what matters is that
the best known attacks aren't much better than brute-force search
through the keyspace, which is impractical for the chosen curves.

> (4) The whole appeal of quantum computers, Shor's Algorithm, and the
> rest is that they turn an exponential thing into a polynomial one.

Worth emphasising, a *specific* problem gets a theoretical quantum
polynomial-time algorithm, where it previously had only ~exponential
classical algorithms.  There is no generic exponential->polynomial
improvement.

> (5) It's a peeve of mine that there's this grand, sweeping assumption
> that polynomial means easy, and exponential means hard. This is not
> true. For example, there's a polynomial function to test if an integer
> is prime, but we don't use it. When it was discovered, it was k^17
> (where k is number of bits) and as I remember, continued work has
> gotten it down to k^13. As it turns out, k^13 is just really not
> useful for k in the range of 1000 or more. So we don't use it. It
> doesn't matter that it's polynomial because a polynomial of order 13
> is to an engineer close enough to exponential for government work, as
> they say. In fact, there's a lot of concern about Shor's algorithm
> that while it turns factoring into a cubic, that's not good enough.

The degree was originally 6, but is now 6:

    https://en.wikipedia.org/wiki/AKS_primality_test#History_and_running_time

but, AFAIK, it is still not in practice advantageous over alternatives.

> Similarly, I can trivially construct an exponential function that might as well be linear. Here goes:
> 
> f(x) = (e/c)^(x/c)

Not quite that, because you'd then need `c < e`.  I think you meant:

    (e^(x/C))/C

which, though exponential, can grow arbitrarily slowly over an interval
of interest.

-- 
    Viktor.