[Cryptography] List of Proven Secure Ciphers / Hashes

[Lodewijk andré de la porte]

ITT: Lodewijk trolls (fellow?) cryptonerds by mentioning P=NP. Sorry about
glossing over so much that it seems legit but is actually false in many
ways of looking at the situation.

The constant time argument is cheating; a large enough constant always
exceeds there result of a function ( when working in |R ). Although I
definitely agree that one needn't something NP hard to work as crypto.
Mixing functions like AES or hashes are quite different from asymetric
crypto, asymetric crypto has sterner demands on key shortness and
computational time. (Someone glossed over the fact that larger keys are
much much slower to compute, which (atm) really does become a problem
exponentially fast ;) )

> Assumption 1: We are talking about asymptotic security (as a function of
> key length), not concrete security. Why? Because if you care about concrete
> security, then P and NP are irrelevant since, as a previous person noted,
> any scheme with some fixed key length k can be broken in *constant* time
> 2^k.


The last part depends on how the break works. By crawling 2^k you've found
all possible inputs, not the one you actually meant. Especially when
stacking algorithms that makes a huge difference.


> Let's let n -- a parameter! -- denote the length of the key.

Now N correlates with both "security factor" and computational time


> Assumption 2: Encryption runs in time polynomial in n.
> You can question this assumption, and in fact it might be meaningful to
> allow encryption to run in time  n^{log n}. But this is the assumption I am
> making.


> Assumption 3: You want security to hold against all polynomial-time
> adversaries.
> You can question this assumption, and in fact it might be meaningful to
> only require security for adversaries running in time n^10 (but not those
> running in time n^11). But this is the assumption I am making.


Well said. Adversaries are usually not theoretical. But we're usually
looking for multiple orders of excess safety, against attackers 1000-10,000
times faster (than current known best) over long periods of time. It's
still also cheating, of course, because polynomials can grow pretty fast
too.


> We must also fix a notion of security. For concreteness, let's use the
> notion of CPA-security (i.e., security against chosen-plaintext attacks);
> see the Katz-Lindell textbook for formal definitions. CPA-security, as
> defined there, already incorporates Assumptions 1, 2, and 3.
> Now, what I claim is:
> If P=NP, then no public-key or symmetric-key encryption scheme is
> CPA-secure.


I think that the assumptions (esp 3) are too strong for grarpamp purposes.
I'll look at the CPA-secure definition later, but I suspect it is also too
strong. Then again, what secure meant was not really specified anyway.

NP just isn't the hardest class of problems out there.


I think I was confusing NP with NP-hard, but this is probably the strongest
counter argument out there! Haven't heard of crypto with decryption in
NP-hard but not in NP (would love to be pointed at it, if it's out there!).

Getting back to grarpamp:
formally proofed secure crypto besides the one time XOR?

There's proofs with the right assertions, which is all proofs usually are.
OTP still assumes a good source of randomness (which can be impossible).
Most others a hard problem (notable discrete log, prime factorization, such
things). Some (symmetric crypto) merely attempt to mix data such that it
doesn't turn homogenous (remains high in entropy/uses the output space
optimally) but also mixes thoroughly (all input (bits) is (are) represented
in all the output (bits)) without there being any determinable relationship
between in and output. We've gotten quite good at symetric, given that AES
looks a lot like DES but still nobody really found a problem with it
(biclique isn't that big a deal). AES is also ridiculously fast for how
good the encryption is. Asymmetric is still quite hard, given basically
everyone is worried basically everything out there. We all stick our heads
in the sand when someone mentions quantum computing.

What would proving AES even mean? Did anyone ever prove a cipher to be
secure? I guess you could construct a symetric cipher from asymetric
crypto, copypaste proof that asserts the security of the underlying problem
(and probably P!=NP) and call it a day.

Thanks for participating guys, you actually make me feel guilty not
studying this stuff harder and more formally correctly.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140907/fe0654d3/attachment.html>