7.Cryptographic primitives and protocols

Cryptographic primitives

Much of the theoretical work in cryptography concerns cryptographic primitives — algorithms with basic cryptographic properties — and their relationship to other cryptographic problems. More complicated cryptographic tools are then built from these basic primitives. Complex functionality in an application must be built in using combinations of these algorithms and assorted protocols. Such combinations are called cryptosystems and it is they which users actually encounter. Examples include PGP and its variants, ssh, SSL/TLS, all PKIs, digital signatures, etc For example, a one-way function is a function intended to be easy to compute but hard to invert.

But note that, in a very general sense, for any cryptographic application to be secure (if based on computational feasibility assumptions), one-way functions must exist. However, if one-way functions exist, this implies that P ? NP. Since the P versus NP problem is currently unsolved, it is not known if one-way functions really do exist. For instance, if one-way functions exist, then secure pseudorandom generators and secure pseudorandom functions exist.
Other cryptographic primitives include the encryption algorithms themselves, one-way permutations, trapdoor permutations, etc.

Cryptographic protocols

In many cases, cryptographic techniques involve back and forth communication among two or more parties in space (e.g., between the home office and a branch office) or across time (e.g., cryptographically protected backup data). The term cryptographic protocol captures this general idea.

Cryptographic protocols have been developed for a wide range of problems, including relatively simple ones like interactive proof systems, secret sharing, and zero-knowledge proofs, and much more complex ones like electronic cash and secure multiparty computation.

When the security of a good cryptographic system fails, it is rare that the vulnerability leading to the breach will have been in a quality cryptographic primitive. Instead, weaknesses are often mistakes in the protocol design (often due to inadequate design procedures, or less than thoroughly informed designers), in the implementation (e.g., a software bug), in a failure of the assumptions on which the design was based (e.g., proper training of those who will be using the system), or some other human error.

Many cryptographic protocols have been designed and analyzed using ad hoc methods, but they rarely have any proof of security, leaving aside the effects of humans in their operations. Methods for formally analyzing the security of protocols, based on techniques from mathematical logic (see for example BAN logic), and more recently from concrete security principles, have been the subject of research for the past few decades.Unfortunately, to date these tools have been cumbersome and are not widely used for complex designs.

The study of how best to implement and integrate cryptography in applications is itself a distinct field, see: cryptographic engineering and security engineering.