Overview of Public Key Encryption Schemes by Dan Boneh
Public key encryption
from Diffie-Hellman
The ElGamal
Public-key System
Online Cryptography Course Dan Boneh
Recap: public key encryption:
(Gen, E, D)
E
D
pk
m
c
c
m
sk
Gen
Recap: public-key encryption applications
Key exchange (e.g. in HTTPS)
Encryption in non-interactive settings:
•
Secure Email: Bob has Alice’s pub-key and sends her an email
•
Encrypted File Systems
File
sk
A
Recap: public-key encryption applications
Key exchange (e.g. in HTTPS)
Encryption in non-interactive settings:
•
Secure Email: Bob has Alice’s pub-key and sends her an email
•
Encrypted File Systems
•
Key escrow: data recovery without Bob’s key
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
Review: the Diffie-Hellman protocol
(1977)
Fix a finite cyclic group G
(
e.g G = (Z
p
)
*
)
of order n
Fix a generator g in G
(
i.e. G = {1, g, g2
, g
3
, … , g
n-1
}
)
Alice
Bob
choose random
a
in {1,…,n}choose random
b
in {1,…,n}k
AB
=
g
ab
=
(
g
a
)
b
=
A
b
B
a
=
(
g
b
)
a
=
A = g
a
B = g
b
ElGamal: converting to pub-key enc.
(1984)
Fix a finite cyclic group G
(
e.g G = (Z
p
)
*
)
of order n
Fix a generator g in G
(
i.e. G = {1, g, g2
, g
3
, … , g
n-1
}
)
Alice
Bob
choose random
a
in {1,…,n}choose random
b
in {1,…,n}A = g
a
B = g
b
Treat as a
public key
ElGamal: converting to pub-key enc.
(1984)
Fix a finite cyclic group G
(
e.g G = (Z
p
)
*
)
of order n
Fix a generator g in G
(
i.e. G = {1, g, g2
, g
3
, … , g
n-1
}
)
Alice
Bob
choose random
a
in {1,…,n}choose random
b
in {1,…,n}A = g
a
B = g
b
Treat as a
public key
To decrypt:
compute g
ab
= B
a
,
derive k, and decrypt
The ElGamal system (a modern view)
•
G: finite cyclic group of order n
•
(E
s
, D
s
) : symmetric auth. encryption defined over (K,M,C)
•
H: G
2
⟶
K a hash function
We construct a pub-key enc. system (Gen, E, D):
•
Key generation Gen:
–
choose random generator g in G and random a in Z
n
–
output sk = a , pk = (g, h=g
a
)
The ElGamal system
(a modern view)
E
(
pk=(g,h), m
)
:
b
⟵
Z
n
, u
⟵
g
b
, v
⟵
h
b
k
⟵
H(u,v) , c
⟵
E
s
(k, m)
output (u, c)
D
(
sk=a, (u,c)
)
:
v
⟵
u
a
k
⟵
H(u,v) , m
⟵
D
s
(k, c)
output m
•
G: finite cyclic group of order n
•
(E
s
, D
s
) : symmetric auth. encryption defined over (K,M,C)
•
H: G
2
⟶
K a hash function
R
ElGamal performance
Encryption
: 2 exp. (fixed basis)
–
Can pre-compute
[
g
(2^i)
, h
(2^i)
for i=1,…,log
2
n
]
–
3x speed-up (or more)
Decryption
: 1 exp. (variable basis)
E( pk=(g,h), m)
:
b
⟵
Z
n
, u
⟵
g
b
, v
⟵
h
b
D( sk=a, (u,c) )
:
v
⟵
u
a
End of Segment
Next step:
why is this system chosen ciphertext secure?
under what assumptions?
Public key encryption
from Diffie-Hellman
ElGamal Security
Online Cryptography Course Dan Boneh
Computational Diffie-Hellman Assumption
G: finite cyclic group of order n
Comp. DH (CDH) assumption holds in G if: g, g
a
, g
b
⇏
g
ab
for all efficient algs. A:
Pr
[
A(g,
g
a
, g
b
) = g
ab
]
< negligible
where g
⟵
{generators of G
}
, a, b
⟵
Z
n
Hash Diffie-Hellman Assumption
G: finite cyclic group of order n , H: G
2
⟶
K a hash function
Def
: Hash-DH (HDH) assumption holds for (G, H) if:
(
g,
g
a
, g
b
, H(
g
b
,
g
ab
)
)
≈
p
(
g,
g
a
, g
b
, R
)
where g
⟵
{generators of G
}
, a, b
⟵
Z
n
,
R
⟵
K
H acts as an extractor: strange distribution on G
2
⇒
uniform on K
Suppose K = {0,1}128
and
H: G
2
⟶
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
:
g
⟵
{generators of G} , a
⟵
Z
n
output pk = (g, h=g
a
) , sk = a
D( sk=a, (u,c) )
:
k
⟵
H(u,u
a
) , m
⟵
D
s
(k, c)
output m
E( pk=(g,h), m)
:
b
⟵
Z
n
k
⟵
H(g
b
,h
b
) , c
⟵
E
s
(k, m)
output (g
b
, c)
ElGamal is sem. secure under Hash-DH
≈
p
≈
p
≈
p
(g
b
, g
ab
)
(g
b
, g
ab
)
≈
p
ElGamal chosen ciphertext security?
To prove chosen ciphertext security need stronger assumption
Interactive Diffie-Hellman
(IDH) in group G:
IDH holds in G if:
∀
efficient A: Pr[ A outputs g
ab
] < negligible
Chal.
Adv. A
g
⟵
{gen}a,b
⟵
Z
n
g, h=
g
a
, u=g
b
ElGamal chosen ciphertext security?
Security Theorem
:
If
IDH
holds in the group G,
(E
s
, D
s
)
provides auth. enc.
and
H:
G
2
⟶
K is a “random oracle”
then
ElGamal
is CCA
ro
secure.
Questions:
(1) can we prove CCA security based on CDH?
(2) can we prove CCA security without random oracles?
End of Segment
Public key encryption
from Diffie-Hellman
ElGamal Variants
With Better Security
Online Cryptography Course Dan Boneh
Review: ElGamal encryption
KeyGen
:
g
⟵
{generators of G} , a
⟵
Z
n
output pk = (g, h=g
a
) , sk = a
D( sk=a, (u,c) )
:
k
⟵
H(u,u
a
) , m
⟵
D
s
(k, c)
output m
E( pk=(g,h), m)
:
b
⟵
Z
n
k
⟵
H(g
b
,h
b
) , c
⟵
E
s
(k, m)
output (g
b
, c)
ElGamal chosen ciphertext security
Security Theorem
:
If
IDH
holds in the group G,
(E
s
, D
s
)
provides auth. enc.
and
H:
G
2
⟶
K is a “random oracle”
then
ElGamal
is CCA
ro
secure.
Can we prove CCA security based on CDH (g, g
a
, g
b
↛
g
ab
) ?
•
Option 1: use group G where CDH = IDH (a.k.a bilinear group)
•
Option 2: change the ElGamal system
Variants: twin ElGamal
[CKS’08]
KeyGen
:
g
⟵
{generators of G} , a1, a2
⟵
Z
n
output pk = (g, h
1
=g
a1
, h
2
=g
a2
) , sk = (a1, a2)
D
(
sk=(a1,a2), (u,c)
)
:
k
⟵
H(u, u
a1
, u
a2
)
m
⟵
D
s
(k, c)
output m
E
(
pk=(g,h
1
,h
2
), m
)
:
b
⟵
Z
n
k
⟵
H(g
b
, h
1
b
,
h
2
b
)
c
⟵
E
s
(k, m)
output (g
b
, c)
Chosen ciphertext security
Security Theorem
:
If
CDH
holds in the group G,
(E
s
, D
s
)
provides auth. enc.
and
H:
G
3
⟶
K is a “random oracle”
then
twin
ElGamal
is CCA
ro
secure.
Cost: one more exponentiation during enc/dec
–
Is it worth it? No one knows …
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 [CHK’04 + BB’04]
•
Option 2: use Decision-DH assumption in any group
[CS’98]
Further Reading
•
The Decision Diffie-Hellman problem. D. Boneh, ANTS 3, 1998
•
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
Public key encryption
from Diffie-Hellman
A Unifying Theme
Online Cryptography Course Dan Boneh
One-way functions
(informal)
A function f: X
⟶
Y is one-way if
•
There is an efficient algorithm to evaluate f(
⋅
), but
•
Inverting f is hard:
for all efficient A and x
⟵
X :
Pr
[
A
(
f(x)
)
]
< negligible
Functions that are not one-way: f(x) = x, f(x) = 0
Ex. 1: generic one-way functions
Let f: X
⟶
Y be a secure PRG (where |Y|
≫
|X| )
(e.g. f built using det. counter mode)
Lemma
: f a secure PRG
⇒
f is one-way
Proof sketch:
A inverts f
⇒
B(y) = is a distinguisher
Generic: no special properties. Difficult to use for key exchange.
Ex 2: The DLOG one-way function
Fix a finite cyclic group G
(
e.g G = (Z
p
)
*
)
of order n
g: a random generator in G
(
i.e. G = {1, g, g2
, g
3
, … , g
n-1
}
)
Define
: f: Z
n
⟶
G as f(x) = g
x
∈
G
Lemma
: Dlog hard in G
⇒
f is one-way
Properties
: f(x), f(y)
⇒
f(x+y) = f(x)
⋅
f(y)
⇒
key-exchange and public-key encryption
Ex. 3: The RSA one-way function
•
choose random primes p,q
1024 bits. Set
N=pq
.
•
choose integers
e , d
s.t.
e
⋅
d = 1 (mod
(N) )
Define
: f: as f(x) = x
e
in
Lemma
: f is one-way under the RSA assumption
Properties
: f(x
⋅
y) = f(x)
⋅
f(y) and
f has a trapdoor
Summary
Public key encryption:
made possible by one-way functions
with special properties
homomorphic properties and trapdoors
End of Segment
Farewell
(for now)
Online Cryptography Course Dan Boneh
Quick Review: primitives
PRG
PRF, PRP
MAC
GGM
CTR
CMAC, HMAC
PMAC
Collision
resistance
key
exchange
Trapdoor
Functions
public key
encryption
Diffie-Hellman
groups
Quick Review: primitives
To protect non-secret data
:
(data integrity)
–
using small read-only storage: use collision resistant hash
–
no read-only space: use MAC … requires secret key
To protect sensitive data
: only use authenticated encryption
(eavesdropping security by itself is insufficient)
Session setup
:
•
Interactive settings: use authenticated key-exchange protocol
•
When no-interaction allowed: use public-key encryption
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
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
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
Don’t invent your own ciphers or modes
End of part I
This content provides insights into public key encryption schemes such as Diffie-Hellman and ElGamal, as presented by cryptography expert Dan Boneh. Topics covered include key exchange, secure email, encryption applications, constructions, and a review of the Diffie-Hellman protocol. The material delves into the theoretical foundations and practical applications of these encryption systems, highlighting their security goals and implementation scenarios.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
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 sk pk m c c m E D Dan Boneh
Recap: public-key encryption applications Key exchange (e.g. in HTTPS) Encryption in non-interactive settings: Secure Email: Bob has Alice s pub-key and sends her an email Encrypted File Systems skA read write Alice E(pkA, KF) File Bob E(kF, File) E(pkB, KF) Dan Boneh
Recap: public-key encryption applications Key exchange (e.g. in HTTPS) Encryption in non-interactive settings: Secure Email: Bob has Alice s pub-key and sends her an email Encrypted File Systems Key escrow: data recovery without Bob s key Escrow Service skescrow write E(pkescrow, KF) Bob E(kF, File) E(pkB, KF) 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 (1977) Fix a finite cyclic group G (e.g G = (Zp)* ) of order n Fix a generator g in G (i.e. G = {1, g, g2, g3, , gn-1 } ) Alice Bob choose random ain {1, ,n} choose random bin {1, ,n} A = ga B = gb = (ga)b=Ab Ba= (gb)a= kAB = gab Dan Boneh
ElGamal: converting to pub-key enc. (1984) Fix a finite cyclic group G (e.g G = (Zp)* ) of order n Fix a generator g in G (i.e. G = {1, g, g2, g3, , gn-1} ) Alice Bob Treat as a choose random ain {1, ,n} choose random bin {1, ,n} public key A = ga compute gab = Ab , derive symmetric key k , ct =[ , ] encrypt message m with k B = gb Dan Boneh
ElGamal: converting to pub-key enc. (1984) Fix a finite cyclic group G (e.g G = (Zp)* ) of order n Fix a generator g in G (i.e. G = {1, g, g2, g3, , gn-1} ) Alice Bob Treat as a choose random ain {1, ,n} choose random bin {1, ,n} public key A = ga compute gab = Ab , derive symmetric key k , ct =[ , ] encrypt message m with k To decrypt: compute gab = Ba , derive k, and decrypt B = gb 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 We construct a pub-key enc. system (Gen, E, D): Key generation Gen: choose random generator g in G and random a in Zn output sk = a , 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 E( pk=(g,h), m) : b Zn , u gb , v hb k H(u,v) , c Es(k, m) output (u, c) D( sk=a, (u,c) ) : v ua k H(u,v) , m Ds(k, c) output m R Dan Boneh
ElGamal performance E( pk=(g,h), m) : b Zn , u gb , v hb D( sk=a, (u,c) ) : v ua Encryption: 2 exp. (fixed basis) Can pre-compute [ 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 {generators of G} , a, b Zn Dan Boneh
Hash Diffie-Hellman Assumption G: finite cyclic group of order n , H: G2 K a hash function Def: Hash-DH (HDH) assumption holds for (G, H) if: (g, ga, gb , H(gb,gab) ) p (g, ga, gb , R ) where g {generators of G} , a, b Zn , R K H acts as an extractor: strange distribution on G2 uniform on K Dan Boneh
Suppose K = {0,1}128 and H: G2 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: g {generators of G} , a Zn output pk = (g, h=ga) , sk = a E( pk=(g,h), m) : b Zn D( sk=a, (u,c) ) : k H(gb,hb) , c Es(k, m) k H(u,ua) , m Ds(k, c) output (gb, c) output m Dan Boneh
ElGamal is sem. secure under Hash-DH pk = (g,ga) pk = (g,ga) chal. adv. A chal. adv. A m0 , m1 m0 , m1 p pk,sk pk,sk gb, Es(H(), m0) gb, Es(k, m0) k K b 1 b 1 (gb , gab) p p pk = (g,ga) pk = (g,ga) chal. adv. A chal. adv. A m0 , m1 m0 , m1 p pk,sk pk,sk gb, Es(H(), m1) gb, Es(k, m1) k K b 1 b 1 (gb , gab) Dan Boneh
ElGamal chosen ciphertext security? To prove chosen ciphertext security need stronger assumption Interactive Diffie-Hellman (IDH) in group G: g, h=ga, u=gb Chal. Adv. A (u1,v1) g {gen} a,b Zn v if (u1)a = v1 1 0 otherwise wins if v=gab IDH holds in G if: efficient 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 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: g {generators of G} , a Zn output pk = (g, h=ga) , sk = a E( pk=(g,h), m) : b Zn D( sk=a, (u,c) ) : k H(gb,hb) , c Es(k, m) k H(u,ua) , m 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 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 [CKS08] KeyGen: g {generators of G} , a1, a2 Zn output pk = (g, h1=ga1, h2=ga2) , sk = (a1, a2) E( pk=(g,h1,h2), m) : b Zn D( sk=(a1,a2), (u,c) ) : k H(u, ua1, ua2) k H(gb, h1b,h2b) m Ds(k, c) c Es(k, m) 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 is a random oracle then twinElGamal 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 [CHK 04 + BB 04] Option 2: use Decision-DH assumption in any group [CS 98] Dan Boneh
Further Reading The Decision Diffie-Hellman problem. D. Boneh, ANTS 3, 1998 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 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 Y is one-way if There is an efficient algorithm to evaluate f( ), but Inverting f is hard: for all efficient A and x 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 Y be a secure PRG (where |Y| |X| ) (e.g. f built using det. counter mode) Lemma: f a secure PRG f is one-way Proof sketch: A inverts f 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)* ) of order n g: a random generator in G (i.e. G = {1, g, g2, g3, , gn-1} ) Define: f: Zn G as f(x) = gx G Lemma: Dlog hard in G f is one-way Properties: f(x), f(y) f(x+y) = f(x) f(y) 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. e d = 1 (mod (N) ) Define: f: as f(x) = xe in Lemma: f is one-way under the RSA assumption Properties: f(x y) = f(x) 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 CMAC, HMAC PMAC PRF, PRP MAC PRG GGM Collision resistance key exchange Diffie-Hellman groups Trapdoor Functions public key encryption 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 Don t invent your own ciphers or modes Dan Boneh
End of part I Dan Boneh
