Re: Encryption provably free of trapdoors



daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner) writes:

Unruh wrote:
daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner) writes:
reason why proving P != NP seems to be hard is because we don't know
how to prove meaningful lower bounds on the computational complexity of

Upper bounds. NP is worst case scenario. There are lots of travelling
salesman routes which are trivial and can be solved in time linear in the
size of the route. Ie, the lower bound is certainly polynomial.

Huh? I don't understand what you are trying to say. I don't think you
are making any sense. It is _lower_ bounds on computational complexity
that are relevant to provably secure crypto, not _upper_ bounds.

Uh, did you read the rest of the post? That is what I said. However as far
as NP=P is concerned it is upper bounds NP is a worst case scenario.



Let me try to elaborate on my point, since obviously I didn't get
it across. The reason that it is hard to prove the existence of an
algorithm in NP that cannot be solved in polynomial time is that we
do not know how to prove super-polynomial lower bounds on running time.
In fact, we are almost totally clueless about how to prove any non-trivial
lower bounds about problems in NP.

Upper bounds. the travelling salesman problem has a trivial lower bound--
linear in the cities visited. Consider the graph with each point connected
only to two other points. The path from A to B is trivial for all A and B.


Here's a pop quiz for you: What do you think is the best known lower bound
on the time to solve a TSP instance of size n? Place your best guess.

For specific TSP it is O(1). For arbitrary graphs it is of course more
difficult. What one wants is the least upper bound. Ie, T(TSP(n)) < Polynom(n)
would prove it was polynomial in n.


I don't know for sure, because I don't follow the theory literature very
closely, but I know what my guess is. I bet the answer is Omega(n)
-- the trivial lower bound that any algorithm has to read the entire
input. Now to prove that the TSP is not in P, you have to improve that
tremendously. Today I don't think anyone has a clue how to prove even a
Omega(n^2) lower bound on the time to solve a TSP instance (I believe),
let alone proving a super-polynomial time bound. Of course, I imagine
most computer scientists would expect that there is no way to solve the
TSP in O(n) time -- but I don't think anyone knows how to prove that,
let alone that there is no way to solve it in O(n^2) time, or O(n^100)
time, or O(poly(n)) time.

I think the following should be required reading for anyone who wants
to expound on this issue:
http://www.iacr.org/publications/dl/massey96/massey96.html
Check out particularly slides #12 and #16. The talk notes that, at the
time of the talk, the world record for lower bounds on the difficulty of
inverting a one-way permutation is that there is a particular function
f:{0,1}^n->{0,1}^n so that inverting f has complexity at least 3n-3.
Note that this is only a factor of three better than the trivial lower
bound of n (which comes by noticing that any inverter has to examine
all the bits of its input). This is a far, far cry from an 2^n lower
bound on the time to invert f (which is what we might expect if f were
a cryptographic one-way hash for which there is no attack better than
brute force).

Later on, the talk examines the ratio the time to invert f and the
time to compute f. At the time, the world record best known result
was a function f where inverting provably takes twice as long as
computing f in the forward direction. Yet for our current hash functions,
inverting is conjectured to be exponentially harder (say, takes 2^200
times as much computing power) as computing the hash.

In summary, we have n-bit hash functions where it is conjectured that
inverting them would take at least 2^n time, but no one has been able
to find any function where inverting provably takes more than 3n-3 time.
That's an enormous gap between conjectured and proven complexity, and
it illustrates just how weak the known tools for proving lower bounds
are. This may be the common cause behind why both proving P!=NP is hard
and finding provably secure crypto is hard. Our failure to prove P!=NP
and our failure to find provably secure crypto might be just two different
symptoms of the same underlying ignorance.

interesting problems. The underlying reason why creating a provably
secure encryption algorithm seems to be hard is because we don't know
how to prove meaningful lower bounds on the computational complexity of
interesting problems. See the connection?

In encryption lower bounds are far more useful.

Umm, that's what I said.

Yes. And in NP it is the worst case that is important. You could have a
problem in which all examples are linear except for some extremely rare
instances (Prob(difficult)=1/2^N) but those difficult instances are not
polynomial (but verifying solution of course is polynomial). this would be
in NP-P despite the fact that almost all instances are trivial (and thus
totally useless for crypto).

Ie, the demands on th e funtion for crypto are almost exactly the opposite
of the requirement for NP.

For crypto all you need is that the decryption with zero info be much much
harder than the encryption. If the problem is N^(10^100) it is pleanty good
enough for crypto. It is polynomial.


And there are many problems which may be exponential for small inputs and
become linear for large.

Out of curiousity, which problems were you thinking of?
As an example:
The decryption of a file of length N encrypted with AES with key
of length N fed through MD5
(Of course AES might be more easily decrypted than exponential in the
length of the key if the key is less than 128 bits, but let me take the
standard lore.)




(This is a question, not an argument. It wouldn't change the argument
I'm making, but I'm honestly curious.)
.



Relevant Pages

  • Re: Encryption provably free of trapdoors
    ... It is _lower_ bounds on computational complexity ... do not know how to prove super-polynomial lower bounds on running time. ... inverting a one-way permutation is that there is a particular function ... times as much computing power) as computing the hash. ...
    (sci.crypt)
  • Re: Union of set of intervals
    ... We can easily distinguish the lower bounds from upper bounds in t by values ... Now, starting from the far left, draw the graph of a horizontal line on the ... whenever it descends back to zero from above. ...
    (comp.soft-sys.matlab)
  • Re: Random numbers generation with variable bound
    ... > I need to create a vector of N random numbers xthat satisfies the following constraints: ... > sum x= s ... > Note that the lower and the upper bounds are different for each i. ... I found randfixedsum function but the upper and lower bounds have to be the same for each number. ...
    (comp.soft-sys.matlab)
  • Re: Random numbers generation with variable bound
    ... > I need to create a vector of N random numbers xthat satisfies the following constraints: ... > sum x= s ... > Note that the lower and the upper bounds are different for each i. ... I found randfixedsum function but the upper and lower bounds have to be the same for each number. ...
    (comp.soft-sys.matlab)
  • Re: Standard query: Bounds of allocatable components from derived-type constructors?
    ... It is not specific to lower bounds or to assumed shape arrays. ... have matching lower and upper bounds. ... to temporary arrays (for expressions) and to called routines. ...
    (comp.lang.fortran)