How to Search on
Encrypted Data
SENY KAMARA
MICROSOFT RESEARCH
Encryption
Gen(1k) ⟾ K
Enc(K, m)⟾ c
Dec(K, c) ⟾ m
Alice
Eve
Bob
Secure Communiation
2
Encryption
Gen(1k) ⟾ K
Enc(K, m)⟾ c
Dec(K, c) ⟾ m
Alice Eve
Secure Storage
3
Encryption
Gen(1k) ⟾ K
Enc(K, m)⟾ c
Dec(K, c) ⟾ m
Alice Eve
Secure Cloud Storage
4
Encrypted Search
5
Encrypted Search 6
EncK
EncKEncK
Two Simple Solutions 7
?
Large comm.
complexity
id2
Large local
storage
Q: can we do better?
Enc
Enc
Enc Enc
More Advanced Solutions
Multi-Party Computation
[Yao82, Goldreich-Micali-Wigderson87]
Oblivious RAM
[Goldreich-Ostrovsky92]
Searchable symmetric encryption
[Song-Wagner-Perrig01]
Functional encryption
[Boneh-di Crescenzo-Ostrovsky-Persiano06]
Property-preserving encryption
[Bellare-Boldyreva-O’Neill06]
Fully-homomorphic encryption
[Gentry09]
8
Encrypted Search 9
EncKEncK
EncK
w
L1
L2
Encrypted Search 10
Size of EDB
Search
time
Rounds of interaction
Storage leakage
Query leakage
Property-Preserving Encryption
Encryption that supports public tests
Examples:
Deterministic encryption
[Bellare-Boldyreva-O’Neill06]
Order-preserving encryption
[Agrawal-Kiernan-Srikant-Xu04, Boldyreva-Chenette-Lee–O’Neill09]
Orthogonality-preserving encryption
[Pandey-Rouselakis12]
11
Deterministic Encryption
[Bellare-Boldyreva-O’Neill06]
Gen(1k) ⟾ K = 〈K1, K2〉
DET(K, w)⟾
〈FK2(w), FK1(FK2(w))⊕w 〉
12
W1
DETKDETKW2DETKW3
EncK
EncK