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

[Jon Callas]

> On Jul 24, 2024, at 21:50, Seth David Schoen <schoen at loyalty.org> wrote:
> 
> I'm working on a project which, among other things, had me read Merkle
> (1978), where the conclusion states
> 
>> This paper has thus far dealt with a method which is O(N↑2). If an
>> exponential method were possible, it would offer such significant
>> advantages over traditional techniques that it would almost surely
>> supplant them in short order. The problem appears to offer enough leverage
>> age that it can be attacked, as witness the current solution, and an
>> exponential solution would offer significant practical advantages over
>> traditional techniques. The problem merits serious consideration. The
>> author will make the following conjecture: An exponential method is
>> possible. The reader is invited to consider the problem.
> 
> This is to say that the straightforward attack on Merkle's Puzzles,
> the system introduced there, is O(n²), and Merkle, realizing that this
> is not that great for practical use, conjectures that there is a
> public-key cryptosystem where the time complexity of an attack (without
> knowledge of the private key) will be exponential instead of quadratic.
> 
> I first thought "well, he was right ... RSA!" (which he cites in an
> "Addenda" section); then a moment later I thought "wait, no, the time
> complexity of the best-known attack is subexponential".  As highlighted
> by Eric Hughes's song about the general number field sieve's complexity.
> 
> 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.)

I'm not quite sure of what Merkle is saying, but let me blither a bit.

(1) In the symmetric space, we know that well-designed ciphers have a brute-force work factor proportional to to the number of bits. (Hash functions have a work factor of n/2 bits, block ciphers are n but might be n/2ish if birthday bounds is an issue, etc.)

(2) Public key ciphers we use now over the integers are constrained by the density of prime numbers in that part of the number line. Thus we hand wave that 3K RSA or DH has 128 bits of strength and to get 256 bits of strength you need somewhere in the 8K to 16K range and it's squishy precisely because of issues related to these.

(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. This is part of why ECC didn't take off until it became common to want over 128 bits of security. (Other parts include intellectual property nonsense, as well as engineering considerations as to how to do the math. Let us not forget that Edwards did not discover Edwards Curves until 2007, and a lot of our comfort today is related to those curves and their engineering properties.) So this appears that part of the answer might be yes, assuming we understand the question (which I'm not sure we do).

(4) The whole appeal of quantum computers, Shor's Algorithm, and the rest is that they turn an exponential thing into a polynomial one. Thus, one might conclude that the question needs to apply only to PQ algorithms. I don't know. 

(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.

Similarly, I can trivially construct an exponential function that might as well be linear. Here goes:

f(x) = (e/c)^(x/c)

This is just e^x massaged by the constant c, which I give the value of 2^256. And in the real world, we can approximate a very small number to the power of a very small number as being that small number to the zero power, or 1. Yeah, let's just #define f(x) to be 1 and move on.

Yeah, I'm being a smart ass here. The point is that if you are a function theorist, this matters. If you code computers in this spacetime continuum, there are plenty of polynomials that might as well be vertical lines, and plenty of exponentials that might as well be horizontal lines. This is just like noting that when I build a house I do not need to take into account that my little section of a sphere is not flat, nor do I need to take relativity into account. I can just YOLO it with the principles that f=ma and you can't push a rope.

(6) Yes, I believe that you can just pretend Merkle is right and it's not going to bite you in the ass, even though I really don't understand the question as much as I'd like to. Of course -- you're the one whose ass might get bitten, not me. 

In cryptography we cover up a lot of lack of rigor and lots of uncertainty all the time and it works well enough. Rigorous math breaks down all the time with engineering (remember padding?) and there's lots of hinky math that seems to work in the real world. We make up things like IND-XYZ all the time, and they are all a way that serious intellectuals say, "I think that's good enough" without blushing.

	Jon