Provable Lower Bounds for some Algorithmic Problems?

Question

Are there any problems for which we have known lower bounds?

For example, for comparison based sorting, we know you need $\Omega(n \log n)$ comparisons. Edit: I'm aware that this requires restricting the algorithm to comparisons. I couldn't think of any lower bound in an unrestricted model, but I'm mostly interested in lower bounds for unrestricted computations.

My motivation for this is: while we don't know how to prove that one-way functions exist, maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it. Even a problem with $\Omega(n^7)$ could suffice to build somewhat practical cryptography: $c \cdot (2^{128})^{\frac{1}{7}} \approx c\cdot319557$ bits (for some constant $c$) would be required to obtain the same security level as a 128 bit key.

Does this question make sense? If not, where do I go amiss? Do my calculations make any sense?

Answer 1

maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it. Even a problem with $\Omega(n^7)$ could suffice to build somewhat practical cryptography: $c⋅(2128)17≈c⋅319557$ bits (for some constant $c$) would be required to obtain the same security level as a 128 bit key.

Some people have tried thinking about this. The relevant name is "fine-grained cryptography". You can show things like what you allude to --- some polynomial "gap" in the complexity of honest parties vs adversarial ones. One of Ralph Merkle's early cryptosystems (the "Merkle Puzzles") was actually of this form. It was arguably the earliest publicly-known (GCHQ had something earlier I believe) public-key cryptosystem, but only in the aformentioned "fine-grained" sense. Here, you still need to make some hardness assumption --- in particular you need a random oracle. But you get public-key cryptography from a random oracle, although only with a polynomial computation gap.

If you're ok with even weaker crypto, you can remove additional assumptions to get "fully provable" results. In particular, you can get are things like "There exists a circuit, computable in $AC^0$, whose inverse is not" (so an OWF for $AC^0$). See the introduction of this paper for references.

For example, for comparison based sorting, we know you need $\Omega(n \log n)$ comparisons.

This is a good example, as it's an example of lower bounds we know how to prove. In general, we only know [1] how to prove lower bounds on restricted models of computation. Examples include:

• The decision tree complexity of a problem (the $\Omega(n \log n)$ lower bound on comparisons for sorting is of this form)
• The communication complexity of a problem (I've seen this show up in a time/space tradeoff paper in cryptography before)
• Lower bounds in the generic group model

There are other lower bounds of course that are applicable within cryptography (I have work in progress which uses some sphere packing lower bounds, for example), but they are much more specialized.

[1] One can prove lower bounds on specific problems which are conjectured to be hard in the Turing machine model of computation, but they are very weak. In particular, I think our best lower bounds on 3-SAT are only linear (with a constant of like $4$ or something).

Answer 2

maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it

Even that limited goal is beyond what we can prove. People have done studies on tiny functions (functions small enough that exhaustive search is possible); the difference between evaluating the function forward and backwards was surprisingly small. One would hope that the difference becomes wider once the size of the function increases; however we can't prove it.

Does this question make sense?

Yes, it does (although, depending on how you define things, the $c \cdot 319557$ may be the time required to evaluate in the forward direction, rather than the number of bits); we just don't know the answer.

Now, the obvious question may be, if we can prove that comparison based sorting takes $\Omega(n \log n)$ operations, why can't we do anything analogous with inverting functions? Well, with the comparison based sorting proof, the only information we allow the sorting algorithm about the relative order of elements is to call the Oracle, which returns a single bit each time. And, we can prove that any sorting algorithm with that restriction must call the Oracle $\Omega(n \log n)$ times (because it needs to distinguish between $n!$ different sort orders), and hence must take at least $\Omega(n \log n)$ time. However, that proof is valid only if we restrict the program in that way; sorting algorithms that don't abide by that restriction (e.g. radix sorting or interpolation sorting) can go faster. And (the point I'm really trying to make) when we ask for a function to be inverted by any means, we don't require the program to use any sort of Oracle to get the information we need, hence the type of proof we used for comparison based sorting doesn't work.