Cryptography(By Dan Boneh)

lecture1: introduction

introduce to cryptography

Secure multi-party computation:

Outsourcing computation:

Zero knowledge:

Three steps in cryptography:

history of symmetric cipher:

Symmetric ciphers:

1 Substitution cipher:

e.g. Caesar Cipher:

how to break:

2 Vigener cipher:

how to break:

• know the key length:

  

• not know the key length:

  assume key = 1,2,3, …, n

3 Rotor Machines:

4 Data Encryption Standard:

Discrete Probability:

Probability distribution：

Events：

The union bound:

Random Variables:

The uniform random variable:

Randomized algorithms:

Independence:

An important property of XOR:

The birthday paradox:

Cipher definition:

Lecture2: Stream Ciphers

1 The One Time Pad:

Information Theoretic Security:(Shannon 1949) (Perfect secrecy)

Stream Ciphers:

PRG must be unpredicable:

Negligible and Non-negligible:

e.g.

Attack on OTP and stream cipher

Attack1: two time pad(used twice):

Attack2: no integrity(OTP is malleable)

2 RC4:

3 CSS:

4 eStream:

PRG Security Def.

Statistical tests:

Advantage:

e.g.

Secure PRGs: crypto def.

unpredictable:

Computationally indistinguishable:

Sematic security:

e.g.

e.g.

Stream ciphers are semantically secure:

Lecture3: Block ciphers

introduction to block ciphers:

PRF：

PRP：

Secure PRFs:

Secure PRP:

PRF => PRG

DES(The data encryption standard)

Feistel Network:

Security of DES:

Exhaustive Search for block cipher key:

DES challenge:

Strengthening DES against ex. search:

More attack:

1 side channel attacks:

2 Fault attack:

(make sure correctness before output ciphertext)

3 Linear and differential attacks:

4 Quantum attacks:

AES:

Substitution-Permutation network:

Attacks to AES:

more block ciphers:

PRF from PRG:

PRP from PRF:

Lecture4: using block ciphers

PRF Switching Lemma:

One-time key

Incorrect use of a PRP:

Many-time key:

Semantic Security for many-time key:

Ciphers insecure under CPA:

solution1: randomized encryption:

solution2: Nonce-based Encryption:

Modes of operation:

Cipher block chain(CBC):

CBC’: nonce-based CBC

CBC technicality: padding:

Randize counter mode:

nonce ctr-mode:

Lecture5: Message integrity:

MACs(Message Authentication Code):

Security:

Mac based on PRFs:

Security:

CBC-MAC(ECBC, CMAC):

Security:

NMAC(Nested MAC):

Security:

MAC Padding:

CMAC(NIST standard):

A parallel MAC(PMAC):

Security:

One-time MAC:

Carter-Wegman MAC(Many-time MAC):

HMAC:

Collision resistance:

Attack for Collision resistance:

Generic attack:

The birthday paradox:

The Merkle-Damgard iterated construction:

(if no space for PB, add another block)

collision resistance:

compression function from a block cipher:

HMAC construction:

Timing attack on MAC verification:

Lecture6: Authenticated Encryption:

Sample tampering attacks:

reading someone else’s data:

attack using network access:

Definition of authenticated encryption:

goals:

ciphertext integrity:

authenticated encryption:

implication:

authenticity:

against chosen ciphertext attack:

example of ciphertext attack:

chosen ciphertext security:

authenticated encryption => CCA:

Construct from ciphers and MACs:

Combing MAC and ENC(CCA):

Standards:

OCB： direct construction from a PRP:

Performance:

Case study:

TLS:

Bugs in older versions:

Attacks:

Padding attack:

solution:

Attacking non-atomic decryption:

leture7: Odds and ends

Key derivation:

one key to many key:

source key is uniform:

source key is not uniform:

e.g.,

Deterministic encryption:

Constructions:

Synthetic IV (SIV):

Just use PRP:

Tweakable encryption:

trivial construction:

XTS constraction:

Format preserving encryption:

lecture8: Key exchange

Key management:

key exchange without online TTP:

Merkel puzzles:

Diffie-Helloman protocol:

Public-key encryption:

Lecture9: Number Theory:

Notation:

GCD:

Modular inversion:

Fermat’s theorem:

Euler’s generalization of Fermat:

Modular e’th roots:

Quadratic residue:

Representing bignums:

Arithmetic:

Exponentiation:

Intractable problems:

discrete logarithm:

Lecture10: Public Key Encryption（RSA-based）

Construction:

Trapdoor functions(TDF):

public-key encryption from TDFs

Incorrect use:

RSA trapdoor function:

RSA assumption:

RSA public-key encryption:

Textbook RSA is insecure:

PKCS1:

Is RSA a one-way permutation?

RSA in practice:

Lecture11: Public Key Encryption（Diffie-Hellman-based）

ElGamal:

Security:

Variants of ElGamal:

Twin ElGamal:

A Unifying Theme:

One-way function: