# Introduction to Programming - Stanford University Online Cryptography Course Dan Boneh Public key encryption from Diffie-Hellman The ElGamal Public-key System Dan Boneh Recap: public key encryption: (Gen, E, D) Gen pk m E sk

c c D m Dan Boneh Recap: public-key encryption applications Key exchange (e.g. in HTTPS) Encryption in non-interactive settings: Secure Email: Bob has Alices pub-key and sends her an email Encrypted File Systems read write

Bob E(pkA, KF) E(kF, File) E(pkB, KF) skA Alice File Dan Boneh Recap: public-key encryption applications Key exchange (e.g. in HTTPS) Encryption in non-interactive settings: Secure Email: Bob has Alices pub-key and sends her an email Encrypted File Systems Key escrow: data recovery without Bobs key Escrow Service

write Bob E(pkescrow, KF) E(kF, File) E(pkB, KF) skescrow Dan Boneh Constructions This week: two families of public-key encryption schemes Previous lecture: based on trapdoor functions (such as RSA) Schemes: ISO standard, OAEP+, This lecture: based on the Diffie-Hellman protocol Schemes: ElGamal encryption and variants (e.g. used in GPG) Security goals:

chosen ciphertext security Dan Boneh Review: the Diffie-Hellman protocol Fix a finite cyclic group G (e.g G = (Zp)* ) Fix a generator g in G (1977) of order n (i.e. G = {1, g, g2, g3, , gn-1 } ) Alice Bob choose random a in {1,,n} choose random b in {1,,n}

A = ga B = gb a B = b a (g ) = kAB = g ab = ( ga ) b

= Ab Dan Boneh ElGamal: converting to pub-key enc. Fix a finite cyclic group G (e.g G = (Zp)* ) Fix a generator g in G (1984) of order n (i.e. G = {1, g, g2, g3, , gn-1} ) Alice Bob Treat as a publicchoose key random b in {1,,n}

choose random a in {1,,n} A = ga ct = [ B = gb , compute gab = Ab , derive symmetric key k , encrypt message m with k ] Dan Boneh

ElGamal: converting to pub-key enc. Fix a finite cyclic group G (e.g G = (Zp)* ) Fix a generator g in G (1984) of order n (i.e. G = {1, g, g2, g3, , gn-1} ) Alice Bob Treat as a publicchoose key random b in {1,,n} choose random a in {1,,n} A = ga

To decrypt: ct = compute gab = Ba , derive k, and decrypt [ B = gb , compute gab = Ab , derive symmetric key k , encrypt message m with k ] Dan Boneh The ElGamal system (a modern view)

G: finite cyclic group of order n (Es, Ds) : symmetric auth. encryption defined over (K,M,C) H: G2 K a hash function K a hash function We construct a pub-key enc. system (Gen, E, D): Key generation Gen: choose random generator g in G output sk = a , and random a in Zn pk = (g, h=ga ) Dan Boneh The ElGamal system (a modern view) G: finite cyclic group of order n

(Es, Ds) : symmetric auth. encryption defined over (K,M,C) H: G2 K a hash function K a hash function E( pk=(g,h), m) : R Zn , u Z gb , v Z hb b Z k Z H(u,v) , c Z Es(k, m) output (u, c) D( sk=a, (u,c) ) : v Z ua k Z H(u,v) , m Z Ds(k, c) output m Dan Boneh ElGamal performance E( pk=(g,h), m) : b Z Zn , u Z gb , v Z hb Encryption:

2 exp. Can pre-compute D( sk=a, (u,c) ) : v Z ua (fixed basis) [ g(2^i) , h(2^i) for i=1,,log2 n ] 3x speed-up (or more) Decryption: 1 exp. (variable basis) Dan Boneh

Next step: why is this system chosen ciphertext secure? under what assumptions? End of Segment Dan Boneh Online Cryptography Course Dan Boneh Public key encryption from Diffie-Hellman ElGamal Security Dan Boneh

Computational Diffie-Hellman Assumption G: finite cyclic group of order n Comp. DH (CDH) assumption holds in G if: g, ga , gb gab for all efficient algs. A: [ Pr A(g, ga, gb ) = gab ] < negligible where g Z {generators of G} ,

a, b Z Zn Dan Boneh Hash Diffie-Hellman Assumption G: finite cyclic group of order n , H: G2 K a hash function K a hash function Def: Hash-DH (HDH) assumption holds for (G, H) if: (g, ga, gb , H(gb,gab) ) p where g Z {generators of G} , (g,

g a, gb , R ) a, b Z Zn , R Z K H acts as an extractor: strange distribution on G2 uniform on K uniform on K Dan Boneh Suppose K = {0,1}128 and H: G2 K a hash function K only outputs strings in K that begin with 0 ( i.e. for all x,y: msb(H(x,y))=0 ) Can Hash-DH hold for (G, H) ? Yes, for some groups G No, Hash-DH is easy to break in this case

Yes, Hash-DH is always true for such H ElGamal is sem. secure under Hash-DH KeyGen: output g Z {generators of G} , pk = (g, h=ga) , E( pk=(g,h), m) : b Z Zn a Z Zn sk = a D( sk=a, (u,c) ) : k Z H(gb,hb) , c Z Es(k, m)

k Z H(u,ua) , m Z Ds(k, c) output (gb, c) output m Dan Boneh ElGamal is sem. secure under Hash-DH pk = (g,ga) m0 , m 1 chal. pk,sk adv. A gb, Es(H(), m0) (gb , gab) p

pk = (g,ga) m0 , m 1 chal. pk,sk g , Es(H(), m1) p b1 kK chal. p b1 pk,sk

gb, Es(k, m0) p adv. A b (gb , gab) chal. pk = (g,ga) m0 , m 1 pk,sk kK pk = (g,ga)

m0 , m 1 gb, Es(k, m1) adv. A b1 adv. A b1 Dan Boneh ElGamal chosen ciphertext security? To prove chosen ciphertext security need stronger assumption Interactive Diffie-Hellman (IDH) in group G: Chal. g Z{gen} a,b ZZn g, h=ga, u=gb

Adv. A (u1,v1) 1 0 if (u1)a = v1 otherwise v wins if v=gab IDH holds in G if: efficient A: Pr[ A outputs gefficient A: Pr[ A outputs gab] < negligible Dan Boneh ElGamal chosen ciphertext security? Security Theorem: If IDH holds in the group G,

(Es, Ds) provides auth. enc. and H: G2 K a hash function K is a random oracle then ElGamal is CCAro secure. Questions: (1) can we prove CCA security based on CDH? (2) can we prove CCA security without random oracles? Dan Boneh End of Segment Dan Boneh Online Cryptography Course Dan Boneh Public key encryption from Diffie-Hellman

ElGamal Variants With Better Security Dan Boneh Review: ElGamal encryption KeyGen: output g Z {generators of G} , pk = (g, h=ga) , E( pk=(g,h), m) : b Z Zn a Z Zn sk = a D( sk=a, (u,c) ) :

k Z H(gb,hb) , c Z Es(k, m) k Z H(u,ua) , m Z Ds(k, c) output (gb, c) output m Dan Boneh ElGamal chosen ciphertext security Security Theorem: If IDH holds in the group G, (Es, Ds) provides auth. enc. and H: G2 K a hash function K is a random oracle then ElGamal is CCAro secure. Can we prove CCA security based on CDH (g, ga , gb

gab ) ? Option 1: use group G where CDH = IDH (a.k.a bilinear group) Option 2: change the ElGamal system Dan Boneh Variants: twin ElGamal KeyGen: output g Z {generators of G} , pk = (g, h1=ga1, h2=ga2) , E( pk=(g,h1,h2), m) : b Z Zn [CKS08]

a1, a2 Z Zn sk = (a1, a2) D( sk=(a1,a2), (u,c) ) : k Z H(gb, h1b, h2b) k Z H(u, ua1, ua2) c Z Es(k, m) m Z Ds(k, c) output (gb, c) output m Dan Boneh Chosen ciphertext security Security Theorem:

If CDH holds in the group G, (Es, Ds) provides auth. enc. and H: G3 K a hash function K is a random oracle then twin ElGamal is CCAro secure. Cost: one more exponentiation during enc/dec Is it worth it? No one knows Dan Boneh ElGamal security w/o random oracles? Can we prove CCA security without random oracles? Option 1: use Hash-DH assumption in bilinear groups Special elliptic curve with more structure [CHK04 + BB04] Option 2: use Decision-DH assumption in any group [CS98] Dan Boneh

Further Reading The Decision Diffie-Hellman problem. Universal hash proofs and a paradigm for chosen ciphertext secure public key encryption. R. Cramer and V. Shoup, Eurocrypt 2002 Chosen-ciphertext security from Identity-Based Encryption. D. Boneh, R. Canetti, S. Halevi, and J. Katz, SICOMP 2007 The Twin Diffie-Hellman problem and applications. D. Cash, E. Kiltz, V. Shoup, Eurocrypt 2008

Efficient chosen-ciphertext security via extractable hash proofs. H. Wee, Crypto 2010 D. Boneh, ANTS 3, 1998 Dan Boneh Online Cryptography Course Dan Boneh Public key encryption from Diffie-Hellman A Unifying Theme Dan Boneh

One-way functions (informal) A function f: X K a hash function Y is one-way if There is an efficient algorithm to evaluate f(), but), but Inverting f is hard: for all efficient A and x Z X : Pr[ A(f(x)) ] < negligible Functions that are not one-way: f(x) = x, f(x) = 0 Dan Boneh

Ex. 1: generic one-way functions Let f: X K a hash function Y be a secure PRG (where |Y| |X| ) |X| ) (e.g. f built using det. counter mode) Lemma: f a secure PRG uniform on K f is one-way Proof sketch: A inverts f uniform on K B(y) = is a distinguisher Generic: no special properties. Difficult to use for key exchange. Dan Boneh Ex 2: The DLOG one-way function Fix a finite cyclic group G (e.g G = (Zp)* )

(i.e. G = {1, g, g2, g3, , gn-1} ) g: a random generator in G Define: f: Zn K a hash function G as Lemma: Dlog hard in G Properties: of order n f(x) = gx G G uniform on K f is one-way

f(x), f(y) uniform on K f(x+y) = f(x) ), but f(y) uniform on K key-exchange and public-key encryption Dan Boneh Ex. 3: The RSA one-way function choose random primes p,q 1024 bits. Set N=pq. choose integers e , d s.t. ed = 1 (mod d = 1 (mod (N) ) Define: Lemma: f: as f(x) = x e in f is one-way under the RSA assumption

Properties: f(x), buty) = f(x) ), but f(y) and f has a trapdoor Dan Boneh Summary Public key encryption: made possible by one-way functions with special properties homomorphic properties and trapdoors Dan Boneh End of Segment

Dan Boneh Online Cryptography Course Dan Boneh Farewell (for now) Dan Boneh Quick Review: primitives CTR PRG GGM PRF, PRP

key exchange Trapdoor Functions public key encryption CMAC, HMAC PMAC MAC Collision resistance Diffie-Hellman groups Dan Boneh

Remaining Core Topics (part II) Digital signatures and certificates Authenticated key exchange User authentication: passwords, one-time passwords, challenge-response Privacy mechanisms Zero-knowledge protocols Dan Boneh Many more topics to cover Elliptic Curve Crypto Quantum computing New key management paradigms: identity based encryption and functional encryption Anonymous digital cash Private voting and auction systems Computing on ciphertexts: fully homomorphic encryption Lattice-based crypto Two party and multi-party computation

Dan Boneh Final Words Be careful when using crypto: A tremendous tool, but if incorrectly implemented: system will work, but may be easily attacked Make sure to have others review your designs and code Dont invent your own ciphers or modes Dan Boneh End of part I Dan Boneh