0. Introduction
Classical Cryptography
The “art” of writing or solving codes - Oxford
- Art focusing on ensuring private communication between two parties.
- Two parties share secret information in advance. (symmetric key encryption)
Symmetric Ciphers
Some notations first:
is the plaintext space (messages) is the key space is the ciphertext space is the encryption algorithm (sometimes ) is the decryption algorithm (sometimes )
In a symmetric cipher, a key
Caesar Cipher (ROT)
Let
, where is the Kleene star. (Caesar used ) for each letter of . for each letter of .
This scheme is not safe since we can try all
An Improved Attack Method
Guessing the key and checking the plaintext is hard to automate, since computers don’t know what sentences make sense.1 In some cases, the message may be invalid in normal English, while the plaintext characters follow the same distribution.
Let
Now, let
and choose
Substitution Cipher
Let
is the set of all permutations on . for each letter of . for each letter of .
Note that
Also, we could try
Vigenère Cipher
A stronger version of Caesar cipher, where the key is a string of length
We can guess the key length
Modern Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of adversarial behavior.3
- Modern cryptography developed into more of a science.
- Schemes are developed and analyzed rigorously and systematically.
- Goal is to give a rigorous proof that some scheme is secure.
- Formally define concepts and make appropriate assumptions.
- Covers much broader scope than just encryption/decryption.
- Data integrity, authentication, zero-knowledge proofs, etc.
Principles of Modern Cryptography
Formal Definitions
For the proper design and analysis of cryptographic primitives, we must formally define what security is. Through a formal definition, we can understand what threats are possible and how much security is desired. Also, definitions enable us to evaluate and analyze the schemes, according to the definitions.
Precise Assumptions
Proofs of security are built on precise assumptions, such as the questions in computational complexity theory. For example, many proofs require that
Proof of Security
We must provide rigorous proof that the scheme is indeed secure under the assumptions made. With a rigorous proof, we can be sure that some scheme is secure.
Goals
- Data privacy: Messages should be read only by the sender and the receiver.
- Data integrity: Messages should not be modified by any adversaries.
- Data authenticity: Messages should really be from the sender.
Advanced Cryptography
- Cryptography beyond encryption and signatures, that also protect the computation itself, not just data.
- Several techniques such as
- Zero-knowledge proofs
- Secure multi-party computation
- Homomorphic encryption
- Differential privacy
We need advanced cryptography since our private information is being used in return for services, such as maps, health services. These data should be protected!