Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives. / Bost, Raphael; Minaud, Brice; Ohrimenko, Olga.
Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security: CCS '17. Association for Computing Machinery (ACM), 2017. p. 1465-1482.Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Standard
Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives. / Bost, Raphael; Minaud, Brice; Ohrimenko, Olga.
Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security: CCS '17. Association for Computing Machinery (ACM), 2017. p. 1465-1482.Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Harvard
APA
Vancouver
Author
BibTeX
}
RIS
TY - GEN
T1 - Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives
AU - Bost, Raphael
AU - Minaud, Brice
AU - Ohrimenko, Olga
PY - 2017/10/30
Y1 - 2017/10/30
N2 - Using dynamic Searchable Symmetric Encryption, a user with limited storage resources can securely outsource a database to an untrusted server, so that the database can still be searched and updated efficiently. For such dynamic schemes, it would be desirable that updates do not reveal any information a priori on the modifications, and that deleted results remain unaccessible to the server a posteriori. If the first property, called forward privacy, has been the main motivation of recent works, the second one, the backward privacy, has been overlooked.In this paper, we study for the first time the notion of backward privacy for searchable encryption. After giving formal definitions of different flavors of backward privacy, we present several schemes achieving both forward and backward privacy, with different efficiency tradeoffs.To design these schemes, we used constrained pseudo-random functions and puncturable encryption. These evolved cryptographic primitives allows for a finer-grained control of the power of the adversary, preventing him from evaluating functions on some inputs, or from decrypting some ciphertexts. For example, we present a framework to construct forward private schemes from range-constrained pseudo-random functions.Finally, we implemented these schemes and we study their practical efficiency.
AB - Using dynamic Searchable Symmetric Encryption, a user with limited storage resources can securely outsource a database to an untrusted server, so that the database can still be searched and updated efficiently. For such dynamic schemes, it would be desirable that updates do not reveal any information a priori on the modifications, and that deleted results remain unaccessible to the server a posteriori. If the first property, called forward privacy, has been the main motivation of recent works, the second one, the backward privacy, has been overlooked.In this paper, we study for the first time the notion of backward privacy for searchable encryption. After giving formal definitions of different flavors of backward privacy, we present several schemes achieving both forward and backward privacy, with different efficiency tradeoffs.To design these schemes, we used constrained pseudo-random functions and puncturable encryption. These evolved cryptographic primitives allows for a finer-grained control of the power of the adversary, preventing him from evaluating functions on some inputs, or from decrypting some ciphertexts. For example, we present a framework to construct forward private schemes from range-constrained pseudo-random functions.Finally, we implemented these schemes and we study their practical efficiency.
KW - Cryptog
KW - Searchable Encryption
U2 - 10.1145/3133956.3133980
DO - 10.1145/3133956.3133980
M3 - Conference contribution
SP - 1465
EP - 1482
BT - Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security
PB - Association for Computing Machinery (ACM)
ER -