[Cryptography] hard natural problems

[John Denker]

On 07/15/2016 04:29 PM, Jerry Leichter wrote:

> Natural problems [....]

> 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.
 *) Weather forecasting certainly counts as a natural problem.
  It is subject to the famous /butterfly effect/.
 *) Even a system as simple as a double-jointed pendulum exhibits
  chaos.  That means it is exponentially sensitive to tiny details
  in the initial conditions.  Here's an animated gif, and some
  discussion:
     https://en.wikipedia.org/wiki/Chaos_theory
 *) Et cetera.

Chaotic systems tend to be super-sensitive to things we can control
(which would be good for encryption/decryption) but are also super-
sensitive to things we cannot control (which is usually not so good).
That's why you don't hear about them much in discussions of codes
and ciphers.  Even so,
  -- Chaotic behavior helps if you're building a RNG.
  -- An example is using glitter to make tamper-resistant seals
   (but beware that people often ask seals to do more than they
   could possibly do).
  -- One may speculate about building an analog computer that
   uses chaos for encryption/decryption.  I reckon this would
   require noise control on a level comparable to a quantum
   computer, i.e. not practical, but it's amusing to think about.