[Cryptography] State of sin (was Re: What to put in a new cryptography course)

[Jerry Leichter]

>> What you asked for is not a crypto algorithm whose complexity is X^20, what you asked for is a *proof* that there exists no algorithm that computes the same function in less than X^20.  Such a proof is a very different beastie than an algorithm.  (It’s actually even worse than that, because to prove security, proving that there is no equivalent algorithm is not enough.  You have to prove that there does not even exist a *probabilistic approximation* to the algorithm that runs in <X^20.)
> 
> That is basically what I understood I was asking for. If we could find such a proof, we could construct a crypto system that was provably strong even if it turned out that P=NP. 
There are plenty of proofs around of complexity of algorithms, starting with the familiar "sorting is O(n log n)".  (Which is good but also illustrates a significant point:  Sorting *where the only operation available is order comparison of pairs* requires O(n log n) comparisons.  Radix sort of O(n) - ignoring the dependency on key size.)

It's probably not hard to construct an artificial problem specifically so that you can prove it requires O(n^20) operations.  (He says glibly....)  Natural problems (*not* in the Razborov/Rudich sense of a natural proof, just problems that have arisen naturally rather than being constructed for a particular purpose) with proven lower bounds tend to be bounded by fairly low-degree polynomials.  O(n^2) is reasonably common; there are probably some O(n^3) algorithms around.  I don't off-hand know of any natural problems with a known higher bound, but they may be out there.

One could probably construct cryptosystems from some of these problems.  There are three issues, though:
1.  The results are worst case.  There could easily be many "easy" instances, and it may be as difficult as solving the particular instance to determine if it's "easy" or not.  Some of the results on the difficulty of approximations might lead to a way around this.
2.  Even if we can avoid the easy instances, you really need to know more than that the problem is O(n^2) - you need the constant in order to know what actual n's meet particular security specs.  This is known in a few instances - actually, for sorting using comparison, we can give the exact value by counting arguments - and not known in others.
3.  Even if you have the exact complexity, for low-degree polynomials you'd need such large values of n that the whole thing may fall apart.

Still, it's an interesting question as to whether one can construct a practical algorithm this way.  Here's one that *almost* works:  You can construct a permutation and its inverse in linear time.  But given a permutation, computing its inverse is equivalent to sorting, so is O(n log n).  So you can get an asymmetric key system by publishing the permutation, encrypting by applying it, and decrypting using the inverse (the private key).  This only gives you a log n advantage over an attacker so n would have to be immense - and of course that doesn't really work because of radix sort.
                                                        -- Jerry