[Cryptography] hard natural problems

[Jerry Leichter]

> 
>> 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.
> 
> They're out there, and they're a lot harder than n^3.  There is such
> a thing as /deterministic chaos/ which is the physics equivalent of
> an exponentially-hard algorithm....
I'm not sure how to treat the complexity of these things.  The chaotic systems that are usually studied have very simple, low-complexity forward computations. But ... they are generally defined over the *reals*.  The extreme sensitivity to initial values is present in the real computations.

What exactly happens when you use finite precision arithmetic to compute these functions isn't at all clear (though of course we do it all the time).  You're layering another level of fuzziness on a problem that was fuzzy (no, not in the technical sense) on top.

FP arithmetic has "one-way" functions even without chaos.  Here's a classic example:  Given the interest rate, the number of periods, and the initial loan of a fixed-rate mortgage, computing the monthly payment is trivial.  But suppose you want to determine the interest rate that will result in a given monthly payment.  This turns out to be the solution to a high-degree polynomial (the degree is the number of periods) that's extremely ill-conditioned.  It's impractical to solve it.  (You can, of course, simply run the forward problem repeatedly to search for approximate solutions.  Newton-Raphson may help.)

Can one turn computations over some computable approximation to the reals (you don't have to use floating point - fixed precision might work; a more interesting approach is rationals with bignum numerators and and denominators, or maybe continued fractions) into a usable cryptosystem?  I vaguely recall proposals for such a thing many years back, but I don't know of any practical designs.

I also don't know what the proper measures of complexity/difficulty are in this domain.  Counting operations - when an operation might be an arithmetic operation on bignums whose lengths grow as the problem proceeds - won't cut it.

                                                       -- Jerry