research-article

Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives

Authors:

Olga OhrimenkoAuthors Info & Claims

CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

Pages 1465 - 1482

https://doi.org/10.1145/3133956.3133980

Published: 30 October 2017 Publication History

Abstract

Using dynamic Searchable Symmetric Encryption, a user with limited storage resources can securely outsource a database to an untrusted server, in such a way that the database can still be searched and updated efficiently. For these schemes, it would be desirable that updates do not reveal any information a priori about the modifications they carry out, and that deleted results remain inaccessible to the server a posteriori. If the first property, called forward privacy, has been the main motivation of recent works, the second one, 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 for different flavors of backward privacy, we present several schemes achieving both forward and backward privacy, with various efficiency trade-offs.

Our constructions crucially rely on primitives such as constrained pseudo-random functions and puncturable encryption schemes. Using these advanced cryptographic primitives allows for a fine-grained control of the power of the adversary, preventing her from evaluating functions on selected inputs, or decrypting specific ciphertexts. In turn, this high degree of control allows our SSE constructions to achieve the stronger forms of privacy outlined above. As an example, we present a framework to construct forward-private schemes from range-constrained pseudo-random functions.

Finally, we provide experimental results for implementations of our schemes, and study their practical efficiency.

Supplemental Material

MP4 File

Download
2837.52 MB

References

[1]

Aranha, D.F. and Gouvêa, C.P.L. RELIC is an Efficient LIbrary for Cryptography. https://github.com/relic-toolkit/relic.

[2]

Boneh, D. and Boyen, X. Efficient selective-ID secure identity based encryption without random oracles. In: C. Cachin and J. Camenisch (eds.), EUROCRYPT 2004, LNCS, vol. 3027, pp. 223--238. Springer, Heidelberg (May 2004).

[3]

Boyle, E., Goldwasser, S., and Ivan, I. Functional signatures and pseudorandom functions. In: H. Krawczyk (ed.), PKC 2014, LNCS, vol. 8383, pp. 501--519. Springer, Heidelberg (Mar. 2014).

Digital Library

[4]

Boneh, D. and Lipton, R.J. A revocable backup system. In: Proceedings of the 6th USENIX Security Symposium, San Jose, CA, USA, July 22-25, 1996. USENIX Association (1996). prefixhttps://www.usenix.org/conference/6th-usenix-security-symposium/revocable-backup-system.

Digital Library

[5]

Barreto, P.S.L.M. and Naehrig, M. Pairing-friendly elliptic curves of prime order. In: B. Preneel and S. Tavares (eds.), SAC 2005, LNCS, vol. 3897, pp. 319--331. Springer, Heidelberg (Aug. 2006).

Digital Library

[6]

Bost, R. ∑oφoς: Forward secure searchable encryption. In: E.R. Weippl, S. Katzenbeisser, C. Kruegel, A.C. Myers, and S. Halevi (eds.), ACM CCS 16, pp. 1143--1154. ACM Press (Oct. 2016).

[7]

Bost, R. Implementation of ∑oφoς, Diana and Janus (2017). prefixhttps://github.com/OpenSSE/opensse-schemes.

[8]

Bajaj, S. and Sion, R. HIFS: history independence for file systems. In: A.R. Sadeghi, V.D. Gligor, and M. Yung (eds.), ACM CCS 13, pp. 1285--1296. ACM Press (Nov. 2013).

Digital Library

[9]

Boneh, D. and Waters, B. Constrained pseudorandom functions and their applications. In: K. Sako and P. Sarkar (eds.), ASIACRYPT 2013, Part II, LNCS, vol. 8270, pp. 280--300. Springer, Heidelberg (Dec. 2013).

[10]

Canetti, R. and Chen, Y. Constraint-hiding constrained prfs for nc1 from lwe. In: EUROCRYPT 2017, LNCS. Springer, Heidelberg (2017).

[11]

Curtmola, R., Garay, J.A., Kamara, S., and Ostrovsky, R. Searchable symmetric encryption: improved definitions and efficient constructions. In: A. Juels, R.N. Wright, and S. Vimercati (eds.), ACM CCS 06, pp. 79--88. ACM Press (Oct. / Nov. 2006).

Digital Library

[12]

Cash, D., Grubbs, P., Perry, J., and Ristenpart, T. Leakage-abuse attacks against searchable encryption. In: I. Ray, N. Li, and C. Kruegel: (eds.), ACM CCS 15, pp. 668--679. ACM Press (Oct. 2015).

Digital Library

[13]

Cash, D., Jarecki, S., Jutla, C.S., Krawczyk, H., Rosu, M.C., and Steiner, M. Highly-scalable searchable symmetric encryption with support for Boolean queries. In: R. Canetti and J.A. Garay (eds.), CRYPTO 2013, Part I, LNCS, vol. 8042, pp. 353--373. Springer, Heidelberg (Aug. 2013).

[14]

Cash, D., Jaeger, J., Jarecki, S., Jutla, C.S., Krawczyk, H., Rosu, M.C., and Steiner, M. Dynamic searchable encryption in very-large databases: Data structures and implementation. In: NDSS 2014. The Internet Society (Feb. 2014).

[15]

Chase, M. and Kamara, S. Structured encryption and controlled disclosure. In: M. Abe (ed.), ASIACRYPT 2010, LNCS, vol. 6477, pp. 577--594. Springer, Heidelberg (Dec. 2010).

[16]

Cash, D. and Tessaro, S. The locality of searchable symmetric encryption. In: P.Q. Nguyen and E. Oswald (eds.), EUROCRYPT 2014, LNCS, vol. 8441, pp. 351--368. Springer, Heidelberg (May 2014).

[17]

RocksDBFacebook, Inc. RocksDB: A Persistent Key-Value Store for Flash and RAM Storage. http://rocksdb.org.

[18]

Goldreich, O., Goldwasser, S., and Micali, S. How to construct random functions (extended abstract). In: 25th FOCS, pp. 464--479. IEEE Computer Society Press (Oct. 1984).

[19]

Green, M.D. and Miers, I. Forward secure asynchronous messaging from puncturable encryption. In: 2015 IEEE Symposium on Security and Privacy, pp. 305--320. IEEE Computer Society Press (May 2015).

Digital Library

[20]

Garg, S., Mohassel, P., and Papamanthou, C. TWORAM: Efficient oblivious RAM in two rounds with applications to searchable encryption. In: M. Robshaw and J. Katz (eds.), CRYPTO 2016, Part III, LNCS, vol. 9816, pp. 563--592. Springer, Heidelberg (Aug. 2016).

Digital Library

[21]

Goldreich, O. and Ostrovsky, R. Software protection and simulation on oblivious RAMs. Journal of the ACM (JACM), vol. 43(3):(1996), pp. 431--473.

Digital Library

[22]

Galbraith, S., Paterson, K., and Smart, N. Pairings for cryptographers. Cryptology ePrint Archive, Report 2006/165 (2006). http://eprint.iacr.org/2006/165.

[23]

Hohenberger, S., Koppula, V., and Waters, B. Adaptively secure puncturable pseudorandom functions in the standard model. In: T. Iwata and J.H. Cheon (eds.), ASIACRYPT 2015, Part I, LNCS, vol. 9452, pp. 79--102. Springer, Heidelberg (Nov. / Dec. 2015).

Digital Library

[24]

Kamara, S. and Moataz, T. Boolean searchable symmetric encryption with worst-case sub-linear. In: EUROCRYPT 2017, LNCS. Springer, Heidelberg (2017).

[25]

Kamara, S. and Papamanthou, C. Parallel and dynamic searchable symmetric encryption. In: A.R. Sadeghi (ed.), FC 2013, LNCS, vol. 7859, pp. 258--274. Springer, Heidelberg (Apr. 2013).

[26]

Kamara, S., Papamanthou, C., and Roeder, T. Dynamic searchable symmetric encryption. In: T. Yu, G. Danezis, and V.D. Gligor (eds.), ACM CCS 12, pp. 965--976. ACM Press (Oct. 2012).

Digital Library

[27]

Kiayias, A., Papadopoulos, S., Triandopoulos, N., and Zacharias, T. Delegatable pseudorandom functions and applications. In: A.R. Sadeghi, V.D. Gligor, and M. Yung (eds.), ACM CCS 13, pp. 669--684. ACM Press (Nov. 2013).

Digital Library

[28]

Miers, I. Libforwardsec. Forward secure encryption for asynchronous messaging. https://github.com/imichaelmiers/libforwardsec.

[29]

Meng, X., Kamara, S., Nissim, K., and Kollios, G. GRECS: Graph encryption for approximate shortest distance queries. In: I. Ray, N. Li, and C. Kruegel: (eds.), ACM CCS 15, pp. 504--517. ACM Press (Oct. 2015).

Digital Library

[30]

Miers, I. and Mohassel, P. IO-DSSE: Scaling dynamic searchable encryption to millions of indexes by improving locality. In: NDSS 2017. The Internet Society (2017).

[31]

Naveed, M. The fallacy of composition of oblivious RAM and searchable encryption. Cryptology ePrint Archive, Report 2015/668 (2015). http://eprint.iacr.org/2015/668.

[32]

Naor, M. and Teague, V. Anti-presistence: History independent data structures. In: 33rd ACM STOC, pp. 492--501. ACM Press (Jul. 2001).

Digital Library

[33]

Ostrovsky, R., Sahai, A., and Waters, B. Attribute-based encryption with non-monotonic access structures. In: P. Ning, S.D.C. di Vimercati, and P.F. Syverson (eds.), ACM CCS 07, pp. 195--203. ACM Press (Oct. 2007).

Digital Library

[34]

Poddar, R., Boelter, T., and Popa, R.A. Arx: A strongly encrypted database system. Cryptology ePrint Archive, Report 2016/591 (2016). http://eprint.iacr.org/2016/591.

[35]

Preneel, B., Govaerts, R., and Vandewalle, J. Hash functions based on block ciphers: A synthetic approach. In: D.R. Stinson (ed.), CRYPTO'93, LNCS, vol. 773, pp. 368--378. Springer, Heidelberg (Aug. 1994).

[36]

Roche, D.S., Aviv, A.J., and Choi, S.G. A practical oblivious map data structure with secure deletion and history independence. In: 2016 IEEE Symposium on Security and Privacy, pp. 178--197. IEEE Computer Society Press (May 2016).

[37]

Reardon, J., Capkun, S., and Basin, D. Data node encrypted file system: Efficient secure deletion for flash memory. In: Presented as part of the 21st USENIX Security Symposium (USENIX Security 12), pp. 333--348. USENIX, Bellevue, WA (2012). prefixhttps://www.usenix.org/conference/usenixsecurity12/technical-sessions/presentation/reardon.

[38]

Stefanov, E., Papamanthou, C., and Shi, E. Practical dynamic searchable encryption with small leakage. In: NDSS 2014. The Internet Society (Feb. 2014).

[39]

Song, D.X., Wagner, D., and Perrig, A. Practical techniques for searches on encrypted data. In: 2000 IEEE Symposium on Security and Privacy, pp. 44--55. IEEE Computer Society Press (May 2000).

Digital Library

[40]

Zhang, Y., Katz, J., and Papamanthou, C. All your queries are belong to us: The power of file-injection attacks on searchable encryption. In: 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10-12, 2016., pp. 707--720 (2016).

Digital Library

Cited By

Das BDatta NMajumder ASamajder S(2025)Fault-tolerant Verifiable Dynamic SSE with Forward and Backward PrivacyIACR Communications in Cryptology10.62056/ayl5w4fe-31:4Online publication date: 13-Jan-2025
https://doi.org/10.62056/ayl5w4fe-3
Lv SHuang YLi XLi TGuo LChen XLiu Z(2025)LUNA: Efficient Backward-Private Dynamic Symmetric Searchable Encryption Scheme With Secure Deletion in Encrypted DatabaseIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.332923437:4(1961-1974)Online publication date: Apr-2025
https://doi.org/10.1109/TKDE.2023.3329234
Liu HXu LLiu XMei LXu C(2025)Query Correlation Attack Against Searchable Symmetric Encryption With Supporting for Conjunctive QueriesIEEE Transactions on Information Forensics and Security10.1109/TIFS.2025.353069220(1924-1936)Online publication date: 2025
https://doi.org/10.1109/TIFS.2025.3530692
Show More Cited By

Index Terms

Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives
1. Security and privacy

Recommendations

Practical Backward-Secure Searchable Encryption from Symmetric Puncturable Encryption
CCS '18: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security

Symmetric Searchable Encryption (SSE) has received wide attention due to its practical application in searching on encrypted data. Beyond search, data addition and deletion are also supported in dynamic SSE schemes. Unfortunately, these update ...
Forward and Backward Private Searchable Encryption with SGX
EuroSec '19: Proceedings of the 12th European Workshop on Systems Security

Symmetric Searchable Encryption (SSE) schemes enable users to search over encrypted data hosted on an untrusted server. Recently, there has been a lot of interest in forward and backward private SSE. The notion of forward privacy guarantees that updates ...
Efficient backward private searchable encryption

Dynamic Searchable Symmetric Encryption (DSSE), apart from providing support for search operation, allows a client to perform update operations on outsourced database efficiently. Two security properties, viz., forward privacy and backward privacy are ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

October 2017

2682 pages

ISBN:9781450349468

DOI:10.1145/3133956

General Chair:
Bhavani Thuraisingham
The University of Texas at Dallas, USA
,
Program Chairs:
David Evans
University of Virginia
,
Tal Malkin
Columbia University
,
Dongyan Xu
Purdue University

Copyright © 2017 ACM.

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 October 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

EPSRC

Conference

CCS '17

Sponsor:

SIGSAC

CCS '17: 2017 ACM SIGSAC Conference on Computer and Communications Security

October 30 - November 3, 2017

Texas, Dallas, USA

Acceptance Rates

CCS '17 Paper Acceptance Rate 151 of 836 submissions, 18%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

297
Total Citations
View Citations
1,901
Total Downloads

Downloads (Last 12 months)173
Downloads (Last 6 weeks)19

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Das BDatta NMajumder ASamajder S(2025)Fault-tolerant Verifiable Dynamic SSE with Forward and Backward PrivacyIACR Communications in Cryptology10.62056/ayl5w4fe-31:4Online publication date: 13-Jan-2025
https://doi.org/10.62056/ayl5w4fe-3
Lv SHuang YLi XLi TGuo LChen XLiu Z(2025)LUNA: Efficient Backward-Private Dynamic Symmetric Searchable Encryption Scheme With Secure Deletion in Encrypted DatabaseIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.332923437:4(1961-1974)Online publication date: Apr-2025
https://doi.org/10.1109/TKDE.2023.3329234
Liu HXu LLiu XMei LXu C(2025)Query Correlation Attack Against Searchable Symmetric Encryption With Supporting for Conjunctive QueriesIEEE Transactions on Information Forensics and Security10.1109/TIFS.2025.353069220(1924-1936)Online publication date: 2025
https://doi.org/10.1109/TIFS.2025.3530692
Long ZZhang KLi JWu PNing J(2025)Verifiable and Privacy-Enhanced Authorized Keyword Search for Mobile Cloud StorageIEEE Internet of Things Journal10.1109/JIOT.2024.349504212:6(7348-7359)Online publication date: 15-Mar-2025
https://doi.org/10.1109/JIOT.2024.3495042
Zhao CDu RHe KChen JLi JLiu XNing J(2025)Efficient Verifiable Dynamic Searchable Symmetric Encryption With Forward and Backward SecurityIEEE Internet of Things Journal10.1109/JIOT.2024.347077212:3(2633-2645)Online publication date: 1-Feb-2025
https://doi.org/10.1109/JIOT.2024.3470772
Wu PShen JCao ZDong X(2025)MMKFB: multi-client and multi-keyword searchable symmetric encryption with forward and backward privacyFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-024-3390-z19:3Online publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1007/s11704-024-3390-z
Peng TGong BSun P(2025)Toward privacy-preserving verifiable DSSE for attribute-based cloud computing systemThe Journal of Supercomputing10.1007/s11227-024-06912-181:2Online publication date: 22-Jan-2025
https://doi.org/10.1007/s11227-024-06912-1
Zou ZGao RLi XWang XZhang X(2025)A Dynamic Symmetric Searchable Encryption Scheme for Rapid Conjunctive QueriesAlgorithms and Architectures for Parallel Processing10.1007/978-981-96-1545-2_15(249-269)Online publication date: 13-Feb-2025
https://doi.org/10.1007/978-981-96-1545-2_15
Wu JDu KWang JSun SWang YLi YTian WWang Y(2025)Compressed Cookies: Practical Wildcard Symmetric Searchable Encryption with Optimized StorageProvable and Practical Security10.1007/978-981-96-0954-3_6(106-126)Online publication date: 1-Feb-2025
https://doi.org/10.1007/978-981-96-0954-3_6
Chung-Nguyen HYuan DCui S(2025)Verifiable Conjunctive Searchable Symmetric Encryption with Result Pattern HidingProvable and Practical Security10.1007/978-981-96-0954-3_5(85-105)Online publication date: 1-Feb-2025
https://doi.org/10.1007/978-981-96-0954-3_5
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten