[betterunix]

Keep in mind that theoretical constructions of symmetric ciphers are nowhere near as fast as practical constructions like AES. The real issue is that no public-key algorithms are known other than those that are based on theoretical constructions.

Also, our knowledge of complexity theory is not sufficient to show that cryptography is even possible. I suspect that improvements in our knowledge of complexity theory will greatly improve our cryptographic primitives, in both security and efficiency.

[marshray]

Keep in mind that theoretical constructions of symmetric ciphers are nowhere near as fast as practical constructions like AES.

What I hear you saying is "AES was designed with a practical implementation in mind, whereas asymmetric constructions were more 'discovered' from theoretical work that's often unweildy when reduced to practice". This about right?

The real issue is that no public-key algorithms are known other than those that are based on theoretical constructions.

I dunno. http://en.wikipedia.org/wiki/Merkle%27s_Puzzles always seemed pretty down-to-Earth to me, but they're inefficient as heck too. :-)

[betterunix]

While it is true that AES was designed with practicality in mind, that is not what the difference between a theoretical construction and a practical construction is about. The theory of cryptography is based on complexity-theoretic arguments (or in some cases, information-theoretic arguments) about cryptographic constructions, essentially showing that any algorithm that can be used to violate some security property of the system can be used to solve some hard problem. For example, in the case of the Goldwasser-Micali system, any chosen plaintext attack can be used to solve the quadratic residuosity problem efficiently. On the other hand, there is no such proof for AES; the evidence in favor of the security of AES is heuristic, based on a combination of statistical tests, resistance to known attacks on block ciphers, and other measures that have been developed over the past few decades.

This is not to say that AES should not be trusted. AES is a fine cipher, it is efficient, and unless someone can show us a practical attack the heuristic evidence is pretty strong.

Now, as for Merkle puzzles, that system is not considered secure by cryptographic standards. A cryptographic construction is not secure unless it requires the adversary to do work that is exponential in some parameter in the system (the security parameter), while parties that know some secret (such a key) only do work that is polynomial in all parameters of the system. In the case of RSA, for example, parties that are aware of the secret key must do work that is cubic in the security parameter, while the adversary must do work that is exponential in the cube root of the security parameter. Whether such systems actually exist is still an open question, as it turns out; a positive answer to this question would imply that P does not equal NP. Cryptographers generally assume certain truths about complexity theory, beyond the P vs. NP problem, and cryptography research has actually opened new areas of complexity theory that are based on such assumptions (such as the notion of knowledge complexity, which emerged from the work on zero knowledge proof systems).

[marshray]

Thanks for explaining all this.

The reason I brought up Merkle puzzles is because they depend on a symmetric cipher or one-way hash function, giving them one foot in that first category.