[Cryptography] List of Proven Secure Ciphers / Hashes

[R. Hirschfeld]

> From: Jerry Leichter <leichter at lrw.com>
> Date: Mon, 8 Sep 2014 13:21:54 -0400
> 
> On Sep 8, 2014, at 12:17 AM, R. Hirschfeld <ray at unipay.nl> wrote:
> >> Suppose S(x,k) is AES(x || R, k), where R is a random bit string of the same length as x.  (This is a simplified version of the randomness you need to add to get semantic security anyway.)  You can try all the keys you like, but you're unlikely to every get back a value that equals y.
> > 
> > Since you have access to nondeterminism anyway, why not just go ahead
> > and guess R too while you're at it?
> R can be arbitrarily large.  In fact, I deliberately made it so in my example:  It's the same size as the message.  Why bother guessing R?  Why not just guess the message?

I think you misunderstood my point, although maybe I misunderstood
yours.  Let me go through it more carefully.  If you still think I'm
off-base, let's take the discussion off-list so as not to bother
everybody else.

The OP wrote something vague about symmetric crypto being in NP if
known-plaintext attacks are allowed, and you replied that this was
meaningless.  I attempted to formalize what I conjectured he meant
(although perhaps he meant nothing of the sort!), namely that you can
recognize plaintext/ciphertext pairs in nondeterministic polynomial
time, i.e., for poly-time S, {<x,y> | exists k: S(x.k) = y} is in NP.
This seems obvious.

You replied with the "Suppose ..." statement above.  I thought your
concern was that in addition to the key there might be a random IV,
and my point was that you could just guess that too and the set
remains in NP.

But I guess you meant something different.  Can you explain?

> Again, if you want to talk about formal matters, you have to do it formally and exactly.  I mentioned in an earlier post that you need to watch out what "n" is ... which is exactly what's gone wrong here:  The size of the search space is arbitrarily larger than the security parameter.  That won't do.

Why not?  If the goal is, given <x,y>, to check whether S(x,k)=y for
some k, then you can guess up to a length polynomial in |<x,y>|.  In
the case you suppose, tacking on a random bit string the same length
as x, it's linear.  In what way has this gone wrong?

It seems our wires are seriously crossed.  I also don't understand
your comment about why not just guess the message.  There's no need to
do so because you're given it (it's x, the known plaintext).

Ray