Encrypted Data Deletion for Cloud Storage Servers
Software with
Certified Deletion
B
y
J
a
m
e
s
B
a
r
t
u
s
e
k
,
V
i
p
u
l
G
o
y
a
l
,
D
a
k
s
h
i
t
a
K
h
u
r
a
n
a
,
G
i
u
l
i
o
M
a
l
a
v
o
l
t
a
,
J
u
s
t
i
n
R
a
i
z
e
s
,
a
n
d
B
h
a
s
k
a
r
R
o
b
e
r
t
s
Private Cloud Storage
Server
User
b
classical
ciphertext
Private Cloud Storage
User
Server
Private Cloud Storage
●
D
a
t
a
b
i
s
r
e
c
o
v
e
r
a
b
l
e
i
f
:
○
Secret key is leaked
○
Encryption scheme is broken
b
User
Server
●
D
a
t
a
b
i
s
r
e
c
o
v
e
r
a
b
l
e
i
f
:
○
Secret key is leaked
○
Encryption scheme is broken
User
Server
Private Cloud Storage
b
Private Cloud Storage with Certified
Deletion
●
D
a
t
a
b
i
s
r
e
c
o
v
e
r
a
b
l
e
i
f
:
○
Secret key is leaked
○
Encryption scheme is broken
Quantum ciphertext
User
Server
“please delete my data”
Private Cloud Storage with Certified
Deletion
●
D
a
t
a
b
i
s
r
e
c
o
v
e
r
a
b
l
e
i
f
:
○
Secret key is leaked
○
Encryption scheme is broken
●
b
i
s
s
t
a
t
i
s
t
i
c
a
l
l
y
h
i
d
d
e
n
,
e
v
e
n
g
i
v
e
n
t
h
e
k
e
y
Destructive
measurement
“please delete my data”
User
Before This Work
•
[BI20], [HMNY21], [BK23]: encryption with certified deletion
•
The server can:
•
Store data
•
Delete data
•
Nothing else
This Work
•
W
e
s
h
o
w
h
o
w
t
o
c
o
m
p
u
t
e
o
n
e
n
c
r
y
p
t
e
d
d
a
t
a
a
n
d
t
h
e
n
p
r
o
v
a
b
l
y
d
e
l
e
t
e
i
t
.
•
Generic compiler allows repeated partial access to data
•
Can be applied to a wide variety of primitives
•
Before deletion: Computational hiding
•
After deletion: Statistical hiding
Motivating Applications
Blind Delegation with Certified Deletion
“Please delete my data”
QPT
f
f
The client asks the server to compute a function f on encrypted data and then
asks them to delete the data.
f
f(b)
f(b)
Construction uses post-quantum FHE and SNARGs for P
Motivation for Obfuscation with Certified
Deletion: Subscription Software
Subscription
Software, Inc.
January
February
March
User
Differing Inputs Obfuscation (diO)
Adversary
Subscription
Software, Inc.
𝚷
b
Is it b’?
Given 𝚷
0
and 𝚷
1
, it is hard to find a y* such that 𝚷
0
(y*) ≠ 𝚷
1
(y*)
diO with Certified Deletion
Adversary
Subscription
Software, Inc.
𝚷
b
Is it b’?
“
T
h
e
y
d
i
f
f
e
r
a
t
y
*
”
Given 𝚷
0
and 𝚷
1
, it is hard to find a y* such that 𝚷
0
(y*) ≠ 𝚷
1
(y*)
Other Applications
Other Applications
Quantum Techniques
Two Bases
Computational Basis (C)
Hadamard Basis (H)
QFT
QFT
Destructive Measurements
•
Measuring in one basis destroys information about the other basis.
Measure
in H
Basis
with prob. (1/2)
with prob. (1/2)
Measure
in H
Basis
with prob. (1/2)
with prob. (1/2)
Certified Deletion from Prior Work
•
Encode data
in the computational basis
•
Add checks in the Hadamard basis
•
Verification key
vk
tracks where and what the checks are
•
To delete, the server measures
|𝜓⟩
in the Hadamard basis
Certified Deletion from Prior Work
H
Issue: Malleability
•
Adversary can guess a single data index and flip it
f
(
1
1
1
1
)
•
Now it can evaluate instead of
•
If the result is revealed, this leaks information
•
N
e
e
d
a
m
e
t
h
o
d
t
o
v
e
r
i
f
y
t
h
a
t
t
h
e
c
i
p
h
e
r
t
e
x
t
i
s
o
r
i
g
i
n
a
l
•
Giving an oracle that checks the data positions is
insecure [L10]
Second Attempt
•
[VZ21, CLLZ21]
co(S) is a group of unique
coset representatives
Subspace Coset States [VZ21, CLLZ21]
Subspace Coset States
•
We can publish oracles to check membership in the subspace
cosets
•
Secure because the oracles hide some information about the
subspace
Subspace Hiding
|S
v,w
⟩
Random super-coset
T+u ⊃ S+v
Subspace-hiding(S)
Enc(b ⊕Parity(v))
Certified Deletion with Coset States
(Simplified)
Adversary
cert
𝜌
b
S
e
c
u
r
i
t
y
:
I
f
c
e
r
t
∊
S
⊥
+
w
,
t
h
e
n
𝜌
𝜌
0
a
n
d
𝜌
𝜌
1
a
r
e
s
t
a
t
i
s
t
i
c
a
l
l
y
c
l
o
s
e
How to Use It for Obfuscation with
Certified Deletion (Simplified)
Thank you for listening!
For more details, see our paper on eprint or ask us.
Explore the concept of software with certified deletion for private cloud storage servers. Discover how data recoverability is influenced by secret key leaks and encryption scheme vulnerabilities. Learn about techniques for computing on encrypted data and ensuring provable deletion, with a focus on computational and statistical hiding. Delve into motivating applications like blind delegation and obfuscation with certified deletion in interactive and non-interactive settings.
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
Software with Certified Deletion By James Bartusek, Vipul Goyal, Dakshita Khurana, Giulio Malavolta, Justin Raizes, and Bhaskar Roberts
Private Cloud Storage Server User
Private Cloud Storage Server User classical ciphertext b
Private Cloud Storage Server User b Data b is recoverable if: Secret key is leaked Encryption scheme is broken
Private Cloud Storage Server User Data b is recoverable if: Secret key is leaked Encryption scheme is broken
Private Cloud Storage with Certified Deletion User Server Quantum ciphertext please delete my data b Data b is recoverable if: Secret key is leaked Encryption scheme is broken
Private Cloud Storage with Certified Deletion User please delete my data Destructive measurement Data b is recoverable if: Secret key is leaked Encryption scheme is broken b is statistically hidden, even given the key
Before This Work [BI20], [HMNY21], [BK23]: encryption with certified deletion The server can: Store data Delete data Nothing else
This Work We show how to compute on encrypted data and then provably delete it. Generic compiler allows repeated partial access to data Can be applied to a wide variety of primitives Before deletion: Computational hiding After deletion: Statistical hiding
Motivating Applications Interactive setting: Blind Delegation with Certified Deletion First construction with security against a malicious server Assumes LWE Non-interactive setting: Obfuscation with Certified Deletion Assumes indistinguishability obfuscation and OWFs
Blind Delegation with Certified Deletion The client asks the server to compute a function f on encrypted data and then asks them to delete the data. f f(b) f(b) f f QPT Please delete my data f(b) f(b) Construction uses post-quantum FHE and SNARGs for P
Motivation for Obfuscation with Certified Deletion: Subscription Software Subscription Software, Inc. User January February March
Differing Inputs Obfuscation (diO) Given ?0and ?1, it is hard to find a y* such that ?0(y*) ?1(y*) ?b Subscription Software, Inc. Adversary Is it b ?
diO with Certified Deletion Given ?0and ?1, it is hard to find a y* such that ?0(y*) ?1(y*) ?b Subscription Software, Inc. Adversary They differ at y* Is it b ?
Other Applications Strong Secure Software Leasing If an adversary returns an authenticated copy of the program, they cannot continue to evaluate a local pirated copy. Regular definition [AL21]: the pirated copy cannot be honestly evaluated. Cryptosystems with Revocable Keys Adversary gets a temporary decryption key. After deleting it, new ciphertexts have semantic security. Can be applied to PKE, Functional Encryption, more.
Other Applications Publicly Verifiable Certified Deletion Anyone can check the certificate of deletion Follow-up work has reduced the assumptions from iO to OWFs [KNY23, BKMPW23]
Two Bases Computational Basis (C) Hadamard Basis (H) QFT QFT
Destructive Measurements Measuring in one basis destroys information about the other basis. with prob. (1/2) Measure in H Basis with prob. (1/2) with prob. (1/2) Measure in H Basis with prob. (1/2)
Certified Deletion from Prior Work Encode data in the computational basis Add checks in the Hadamard basis Verification key vk tracks where and what the checks are data = 0 1 1 1 vk = * + * |? = |0 |+ |1 |+ |1 |1 | |+ + * * +
Certified Deletion from Prior Work To delete, the server measures |? in the Hadamard basis |? + + + + H cert: + + + + vk = * + * |? = |0 |+ |1 |+ |1 |1 | |+ + * * +
Issue: Malleability Adversary can guess a single data index and flip it |? = |0 |+ |1 |+ |1 |1 |- |+ |? = |1 |+ |1 |+ |1 |1 |- |+ f(1111) f(0111) Now it can evaluate instead of If the result is revealed, this leaks information Need a method to verify that the ciphertext is original Giving an oracle that checks the data positions is insecure [L10]
Second Attempt co(S) is a group of unique coset representatives [VZ21, CLLZ21]
Subspace Coset States We can publish oracles to check membership in the subspace cosets Secure because the oracles hide some information about the subspace
Subspace Hiding ? ? {? ? : random superspace ? ?} Example: a membership oracle for S Even using iO [Zha19]
Certified Deletion with Coset States (Simplified) |Sv,w cert ?b Random super-coset T+u S+v Subspace-hiding(S) Enc(b Parity(v)) Adversary Security: If cert S +w, then ?0and ?1are statistically close
How to Use It for Obfuscation with Certified Deletion (Simplified) Obfuscated Program Hardcoded: S Random superspace ? + ? ? + ? Parity(v) Correct v if y ? + ?. Hard to find y ? + ?\S + ? Input: input ?, vector ? 1. If y ? + ?: 2. Compute v using S and y 3. Use v to decode 4. Output (x) Correct if ? is correct.
Thank you for listening! For more details, see our paper on eprint or ask us.
