Unidirectional Updatable Encryption and Proxy Re-Encryption
P
e
i
h
a
n
M
i
a
o
S
i
k
h
a
r
P
a
t
r
a
n
a
b
i
s
G
a
v
e
n
W
a
t
s
o
n
Unidirectional Updatable Encryption and
Proxy Re-Encryption from DDH
●
Key management is fundamental to
any secure deployment of
cryptography
●
Key rotation is best practice and
mandated by standards such as
PCI-DSS
●
Securely performing key rotation
and associated updates is a
challenging task
Key Management and Key Rotation
U
p
d
a
t
a
b
l
e
E
n
c
r
y
p
t
i
o
n
(
U
E
)
P
r
o
x
y
R
e
-
E
n
c
r
y
p
t
i
o
n
(
P
R
E
)
K
2
What is Proxy Re-Encryption (PRE)?
D
e
l
e
g
a
t
e
d
e
c
r
y
p
t
i
o
n
a
b
i
l
i
t
y
t
o
s
o
m
e
o
n
e
e
l
s
e
Alice
Proxy
Bob
r
k
3
What is Updatable Encryption (UE)?
D
e
l
e
g
a
t
e
S
t
o
r
a
g
e
a
n
d
K
e
y
R
o
t
a
t
i
o
n
t
o
s
o
m
e
o
n
e
e
l
s
e
Client
Server
C
e
C
e+1
4
P
u
b
l
i
c
k
e
y
–
P
r
o
x
y
R
e
-
E
n
c
r
y
p
t
i
o
n
S
y
m
m
e
t
r
i
c
K
e
y
–
U
p
d
a
t
a
b
l
e
E
n
c
r
y
p
t
i
o
n
Re-encryption Schemes
(
p
k
,
s
k
)
←
K
e
y
G
e
n
(
1
n
)
c
←
E
n
c
(
p
k
,
m
)
m
←
D
e
c
(
s
k
,
c
)
r
k
←
R
e
K
e
y
G
e
n
(
p
k
s
,
s
k
s
,
p
k
d
,
(
s
k
d
)
)
c
’
←
R
e
E
n
c
(
r
k
,
c
)
k
←
K
e
y
G
e
n
(
1
n
)
c
←
E
n
c
(
k
,
m
)
m
←
D
e
c
(
k
,
c
)
k
e
+
1
,
Δ
←
N
e
x
t
(
k
e
)
c
’
←
U
p
d
a
t
e
(
Δ
,
c
)
5
Directionality of PRE
●
PRE Key Updates:
○
Bidirectional
- takes as input both secret keys
○
Unidirectional
- takes as input source secret and destination public key
●
UE Key Updates, even more variations…
C
i
p
h
e
r
t
e
x
t
U
p
d
a
t
e
s
&
K
e
y
U
p
d
a
t
e
s
6
Directionality of UE
C
i
p
h
e
r
t
e
x
t
U
p
d
a
t
e
c
a
n
b
e
B
i
d
i
r
e
c
t
i
o
n
a
l
a
n
d
U
n
i
d
i
r
e
c
t
i
o
n
a
l
M
o
r
e
I
m
p
o
r
t
a
n
t
l
y
h
o
w
a
b
o
u
t
K
e
y
U
p
d
a
t
e
s
:
B
i
d
i
r
e
c
t
i
o
n
a
l
Given
Δ
and
k
c
a
n
d
e
r
i
v
e
o
t
h
e
r
k
e
y
U
n
i
d
i
r
e
c
t
i
o
n
a
l
(
F
o
r
w
a
r
d
L
e
a
k
)
Given
Δ
i+1
and
k
i
c
a
n
d
e
r
i
v
e
k
i
+
1
U
n
i
d
i
r
e
c
t
i
o
n
a
l
(
B
a
c
k
w
a
r
d
s
L
e
a
k
)
Given
Δ
i+1
and
k
i+1
c
a
n
d
e
r
i
v
e
k
i
N
o
D
i
r
e
c
t
i
o
n
a
l
Given
Δ
and
k
c
a
n
n
o
t
d
e
r
i
v
e
o
t
h
e
r
k
e
y
The next talk formally proves equivalence of these
I
n
t
u
i
t
i
o
n
:
S
i
m
p
l
y
u
p
d
a
t
e
c
i
p
h
e
r
t
e
x
t
&
d
e
c
r
y
p
t
u
s
i
n
g
k
i
+
1
7
Building Unidirectional Schemes
●
Prior work shows that constructing unidirectional schemes is hard
●
For PRE schemes either:
○
Only support one re-encryption
○
Or need stronger assumptions (FHE, iO, LWE)
●
For UE,
○
Similar is true (LWE, iO, SXDH)
C
a
n
w
e
c
o
n
s
t
r
u
c
t
u
n
i
d
i
r
e
c
t
i
o
n
a
l
U
E
/
P
R
E
s
c
h
e
m
e
s
f
r
o
m
D
D
H
?
8
Let’s Focus on Updatable Encryption
Security Notions - High-level (Oracles)
E
n
c
r
y
p
t
N
e
x
t
C
h
a
l
l
e
n
g
e
U
p
d
a
t
e
C
o
r
r
u
p
t
Encrypt a message
Let’s explore different notions…
Move to the next epoch
Update a ciphertext to the current epoch (honest re-encryption)
Obtain secret key or update token from a prior epoch
9
CPA notion - IND-ENC:
Let’s Focus on Updatable Encryption
Security Notions - High-level (Notions/Challenges)
E
n
c
(
k
,
m
0
)
E
n
c
(
k
,
m
1
)
(
m
0
,
m
1
)
R
e
E
n
c
(
∆
,
c
0
)
R
e
E
n
c
(
∆
,
c
1
)
(
c
0
,
c
1
)
E
n
c
(
k
,
m
)
R
e
E
n
c
(
∆
,
c
)
(
m
,
c
)
?
?
?
Post-Compromise notion - IND-UPD:
Combined notion - IND-UE
10
Building Unidirectional UE - A first attempt
Consider the following:
c
e
=
E
n
c
(
k
e
,
m
)
∆
e
+
1
=
E
n
c
(
k
e
+
1
,
k
e
)
c
e
+
1
=
E
n
c
(
k
e
,
m
)
,
E
n
c
(
k
e
+
1
,
k
e
)
A
t
t
a
c
k
:
C
o
r
r
u
p
t
p
r
i
o
r
e
p
o
c
h
e
a
n
d
d
e
c
r
y
p
t
f
i
r
s
t
e
l
e
m
e
n
t
o
f
a
n
y
c
i
p
h
e
r
t
e
x
t
I
s
s
u
e
:
M
e
m
o
r
y
o
f
p
r
i
o
r
k
e
y
s
m
a
i
n
t
a
i
n
e
d
a
c
r
o
s
s
a
l
l
c
i
p
h
e
r
t
e
x
t
s
Update
c
e
+
2
=
E
n
c
(
k
e
,
m
)
,
E
n
c
(
k
e
+
1
,
k
e
)
,
E
n
c
(
k
e
+
2
,
k
e
+
1
)
c
e
+
3
=
E
n
c
(
k
e
,
m
)
,
E
n
c
(
k
e
+
1
,
k
e
)
,
E
n
c
(
k
e
+
2
,
k
e
+
1
)
,
E
n
c
(
k
e
+
3
,
k
e
+
2
)
∆
e
+
2
=
E
n
c
(
k
e
+
2
,
k
e
+
1
)
∆
e
+
3
=
E
n
c
(
k
e
+
3
,
k
e
+
2
)
11
●
KPHE - Key and Plaintext Homomorphic Encryption
Consider a new building Block
●
A generalization of the circular secure encryption scheme of [BHHO08]
●
Most importantly, can be constructed from DDH
(
s
k
,
p
k
)
=
K
e
y
G
e
n
(
1
n
)
c
=
E
n
c
(
p
k
,
m
)
m
=
D
e
c
(
s
k
,
c
)
(
p
k
’
,
c
’
)
=
E
v
a
l
(
p
k
,
c
,
𝛑
𝛑
k
,
𝛑
𝛑
m
)
12
Building Unidirectional UE from KPHE
C
o
n
s
i
d
e
r
t
h
e
f
o
l
l
o
w
i
n
g
:
(
l
e
t
k
e
=
(
p
k
e
,
s
k
e
)
o
f
a
K
P
H
E
s
c
h
e
m
e
)
c
e
=
E
n
c
(
p
k
e
,
m
)
∆
e
+
1
=
E
n
c
(
p
k
e
+
1
,
s
k
e
)
c
e
+
1
=
E
n
c
(
p
k
e
’
,
m
)
,
E
n
c
(
p
k
e
+
1
,
s
k
e
’
)
Pick Random Permutation π
Eval(pk
e
, c
e
, π, id)
Eval(pk
e+1
,
∆
e+1
, id, π)
∆
e
+
2
=
E
n
c
(
p
k
e
+
2
,
s
k
e
+
1
)
c
e
+
2
=
E
n
c
(
p
k
e
’
,
m
)
,
E
n
c
(
p
k
e
+
1
’
,
s
k
e
’
)
,
E
n
c
(
p
k
e
+
2
,
s
k
e
+
1
’
)
P
i
c
k
N
e
w
R
a
n
d
o
m
P
e
r
m
u
t
a
t
i
o
n
π
’
a
n
d
p
e
r
f
o
r
m
E
v
a
l
s
A
v
o
i
d
s
i
s
s
u
e
o
f
p
r
e
v
i
o
u
s
s
c
h
e
m
e
:
N
o
m
e
m
o
r
y
o
f
p
r
i
o
r
e
p
o
c
h
k
e
y
s
a
n
d
N
o
k
e
y
s
s
h
a
r
e
d
a
c
r
o
s
s
c
i
p
h
e
r
t
e
x
t
s
13
Extensions and Security
●
This scheme achieves IND-ENC security
●
Extend to achieve IND-UPD/IND-UE by hiding the number of re-encryptions
○
A
c
i
p
h
e
r
t
e
x
t
i
n
e
p
o
c
h
e
m
u
s
t
a
l
w
a
y
s
h
a
v
e
e
c
i
p
h
e
r
t
e
x
t
e
l
e
m
e
n
t
s
●
Similar constructions hold for PRE
○
Security analysis is slightly more involved due to move complex re-encryption graph
14
The challenge of ciphertext expansion
O
p
e
n
p
r
o
b
l
e
m
–
D
D
H
-
b
a
s
e
d
c
o
n
s
t
r
u
c
t
i
o
n
w
i
t
h
o
u
t
l
i
n
e
a
r
r
e
-
e
n
c
r
y
p
t
i
o
n
g
r
o
w
t
h
T
h
e
o
r
y
p
e
r
s
p
e
c
t
i
v
e
:
First Unidirectional UE and (multihop) PRE constructions from DDH
P
r
a
c
t
i
c
a
l
p
e
r
s
p
e
c
t
i
v
e
:
Fix max ciphertext length based on needs (e.g. 1 re-encrypt per year for 10 years)
C
r
i
t
i
q
u
i
n
g
o
u
r
a
p
p
r
o
a
c
h
–
c
i
p
h
e
r
t
e
x
t
s
g
r
o
w
l
i
n
e
a
r
l
y
w
i
t
h
r
e
-
e
n
c
r
y
p
t
i
o
n
15
Question?
Thanks for listening
https://ia.cr/2022/311
K
K
16
Unidirectional updatable encryption and proxy re-encryption are key concepts in secure cryptography deployments. Key management and rotation are essential for secure encryption schemes such as Proxy Re-Encryption (PRE) and Updatable Encryption (UE). PRE allows delegation of decryption abilities, while UE delegates storage and key rotation tasks. Different directionality characteristics and schemes are discussed, highlighting the challenges and considerations in implementing secure cryptographic protocols.
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
Unidirectional Updatable Encryption and Proxy Re-Encryption from DDH Peihan Miao Sikhar Patranabis Gaven Watson
Key Management and Key Rotation Key management is fundamental to any secure deployment of cryptography Proxy Re-Encryption (PRE) Key rotation is best practice and mandated by standards such as PCI-DSS K Securely performing key rotation and associated updates is a challenging task Updatable Encryption (UE) 2
What is Proxy Re-Encryption (PRE)? Delegate decryption ability to someone else Alice Proxy Bob rk 3
What is Updatable Encryption (UE)? Delegate Storage and Key Rotation to someone else Ce Client Server Ce+1 4
Re-encryption Schemes Public key Proxy Re-Encryption Symmetric Key Updatable Encryption (pk,sk) KeyGen(1n) k KeyGen(1n) c Enc(pk, m) c Enc(k, m) m Dec(sk, c) m Dec(k, c) ke+1, Next(ke ) rk ReKeyGen(pks, sks, pkd, (skd)) c Update( , c) c ReEnc(rk, c) 5
Directionality of PRE Bidirectional vs Unidirectional Ciphertext Updates & Key Updates PRE Key Updates: Bidirectional - takes as input both secret keys Unidirectional - takes as input source secret and destination public key UE Key Updates, even more variations 6
Directionality of UE Ciphertext Update can be Bidirectional and Unidirectional More Importantly how about Key Updates: Unidirectional (Forward Leak) Given i+1and ki can derive ki+1 Unidirectional (Backwards Leak) Given i+1and ki+1 can derive ki Bidirectional Given and k can derive other key No Directional Given and k cannot derive other key The next talk formally proves equivalence of these Intuition: Simply update ciphertext & decrypt using ki+1 7
Building Unidirectional Schemes Prior work shows that constructing unidirectional schemes is hard For PRE schemes either: Only support one re-encryption Or need stronger assumptions (FHE, iO, LWE) For UE, Similar is true (LWE, iO, SXDH) Can we construct unidirectional UE/PRE schemes from DDH? 8
Security Notions - High-level (Oracles) Let s Focus on Updatable Encryption Encrypt Encrypt a message Next Move to the next epoch Update Update a ciphertext to the current epoch (honest re-encryption) Corrupt Obtain secret key or update token from a prior epoch Challenge Let s explore different notions 9
Security Notions - High-level (Notions/Challenges) Let s Focus on Updatable Encryption CPA notion - IND-ENC: (m0,m1 ) Enc(k, m0 ) Enc(k, m1 ) ? Post-Compromise notion - IND-UPD: (c0,c1 ) ReEnc( , c0 ) ReEnc( , c1 ) ? Combined notion - IND-UE (m,c) Enc(k, m) ? ReEnc( , c) 10
Building Unidirectional UE - A first attempt Consider the following: e+1= Enc(ke+1, ke) e+2= Enc(ke+2, ke+1) e+3= Enc(ke+3, ke+2) ce= Enc(ke, m) Update ce+1= Enc(ke, m) , Enc(ke+1, ke) ce+2= Enc(ke, m) , Enc(ke+1, ke), Enc(ke+2, ke+1) ce+3= Enc(ke, m) , Enc(ke+1, ke), Enc(ke+2, ke+1) , Enc(ke+3, ke+2) Attack: Corrupt prior epoch e and decrypt first element of any ciphertext Issue: Memory of prior keys maintained across all ciphertexts 11
Consider a new building Block KPHE - Key and Plaintext Homomorphic Encryption (sk,pk) = KeyGen(1n) c = Enc(pk, m) m = Dec(sk, c) (pk ,c ) = Eval(pk, c, ? ?k, ? ?m) A generalization of the circular secure encryption scheme of [BHHO08] Most importantly, can be constructed from DDH 12
Building Unidirectional UE from KPHE Consider the following: (let ke= (pke, ske) of a KPHE scheme) ce= Enc(pke, m) e+1= Enc(pke+1, ske) Pick Random Permutation Eval(pke, ce, , id) Eval(pke+1, e+1, id, ) ce+1= Enc(pke , m) , Enc(pke+1, ske ) e+2= Enc(pke+2, ske+1) Pick New Random Permutation and perform Evals Avoids issue of previous scheme: No memory of prior epoch keys and No keys shared across ciphertexts ce+2= Enc(pke , m) , Enc(pke+1 , ske ) , Enc(pke+2 , ske+1 ) 13
Extensions and Security This scheme achieves IND-ENC security Extend to achieve IND-UPD/IND-UE by hiding the number of re-encryptions A ciphertext in epoch e must always have e ciphertext elements Similar constructions hold for PRE Security analysis is slightly more involved due to move complex re-encryption graph 14
The challenge of ciphertext expansion Critiquing our approach ciphertexts grow linearly with re-encryption Theory perspective: First Unidirectional UE and (multihop) PRE constructions from DDH Practical perspective: Fix max ciphertext length based on needs (e.g. 1 re-encrypt per year for 10 years) Open problem DDH-based construction without linear re-encryption growth 15
Thanks for listening K K https://ia.cr/2022/311 Question? 16
