Cryptography: Week One
Course goals - how crypto primitives work and how to use them correctly and reason about security.
Always use a public encryption algorithm, never use a proprietary one. Remember the keys are secret, the algorithms are public. Proprietary algorithms are often vulnerable.
Cryptography is not something you should try to invent yourself. Use the standards for primitives, which have been reviewed by hundreds of people.
First half of the course will cover symmetric key encryption, second half will cover public key encryption.
In symmetric we can distinguish between single use keys (one time keys), used eg in email encryption, and multi-use keys (used in eg file encryption). The latter needs more machinery to make secure.
What is Cryptography?
The core of cryptography is secure communication that consists of two parts:
Secure key establishment
Secure communication with the key, ensuring confidentiality and integrity
Crypto can do much more:
Digital signature. Analagous to handwritten signature - always the same signature in handwriting. But in digital, if an attacker has my signature they can just copy it. How do we do digital signatures? It has to be a function of the content being signed.
Anonymous communication. We can use a mix net, using a sequence of proxies to disguise who is being talked to. But bidirectional communication is still possible.
On top of anonymous communication we can build other anonymous services, like anonymous cash.
Other examples include elections and private auctions. Both examples of the problem of secure multi-party computation. Where the users have an input that is secret to themselves, but they want to compute a function over all the inputs. They want to reveal the value of the function, without any other information being revealed.
We could do that with a trusted authority, but that requires a trusted authority.
There is a theorem in crypto which states that any computation that can be done with trusted authority can also be done without.
Here the parties talk to each other with a protocol, with no central authority, but at the end of the communication the result of the function is revealed, and nothing else.
Some crypto schemes are just magic.
example: privately outsourcing computation. For example Alice can enter a search query, and there are encryption schemes such that it can be sent to google, and google can compute it, without knowing the value of the query. It will send the encrypted results, and Alice can then derypt it. Google doesn’t know the content of the search or the results, but can use its algorithms. This is just theoretical at the moment beyond simple computations.
Another example: Zero-knowledge. Alice can prove that she knows the prime factors of N to Bob, without Bob knowing the factors themselves.
Modern crypto is a rigorous science, and every concept we describe follows three steps:
Precisely specify the threat model. What can an attacker do, and what are their goals?
Propose a construction
Prove that breaking the construction under threat model will solve an underlying hard problem, so if the problem is hard that proves the attacker can’t break the construction.
Discrete Probability Crash Course
Stream Ciphers Part One (Boneh)