Article

Dynamic Searchable Symmetric Encryption with Forward and Stronger Backward Privacy

Authors:

Josef PieprzykAuthors Info & Claims

Computer Security – ESORICS 2019: 24th European Symposium on Research in Computer Security, Luxembourg, September 23–27, 2019, Proceedings, Part II

Pages 283 - 303

https://doi.org/10.1007/978-3-030-29962-0_14

Published: 23 September 2019 Publication History

Abstract

Dynamic Searchable Symmetric Encryption (DSSE) enables a client to perform updates and searches on encrypted data which makes it very useful in practice. To protect DSSE from the leakage of updates (leading to break query or data privacy), two new security notions, forward and backward privacy, have been proposed recently. Although extensive attention has been paid to forward privacy, this is not the case for backward privacy. Backward privacy, first formally introduced by Bost et al., is classified into three types from weak to strong, exactly Type-III to Type-I. To the best of our knowledge, however, no practical DSSE schemes without trusted hardware (e.g. SGX) have been proposed so far, in terms of the strong backward privacy and constant roundtrips between the client and the server.

In this work, we present a new DSSE scheme by leveraging simple symmetric encryption with homomorphic addition and bitmap index. The new scheme can achieve both forward and backward privacy with one roundtrip. In particular, the backward privacy we achieve in our scheme (denoted by Type-I) is stronger than Type-I. Moreover, our scheme is very practical as it involves only lightweight cryptographic operations. To make it scalable for supporting billions of files, we further extend it to a multi-block setting. Finally, we give the corresponding security proofs and experimental evaluation which demonstrate both security and practicality of our schemes, respectively.

References

[1]

Amjad, G., Kamara, S., Moataz, T.: Forward and backward private searchable encryption with SGX. In: Proceedings of the 12th European Workshop on Systems Security, p. 4. ACM (2019)

[2]

Bost, R.: oo: forward secure searchable encryption. In: CCS 2016, pp. 1143–1154. ACM (2016)

[3]

Bost, R., Minaud, B., Ohrimenko, O.: Forward and backward private searchable encryption from constrained cryptographic primitives. In: CCS 2017, pp. 1465–1482. ACM (2017)

[4]

Cash, D., Grubbs, P., Perry, J., Ristenpart, T.: Leakage-abuse attacks against searchable encryption. In: CCS 2015, pp. 668–679. ACM (2015)

[5]

Cash, D., et al.: Dynamic searchable encryption in very-large databases: data structures and implementation. In: NDSS 2014, vol. 14, pp. 23–26. Citeseer (2014)

[6]

Cash D, Jarecki S, Jutla C, Krawczyk H, Roşu M-C, and Steiner M Canetti R and Garay JA Highly-scalable searchable symmetric encryption with support for Boolean queries Advances in Cryptology – CRYPTO 2013 2013 Heidelberg Springer 353-373

[7]

Castelluccia, C., Mykletun, E., Tsudik, G.: Efficient aggregation of encrypted data in wireless sensor networks. In: 3rd Intlernational Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Sensor Networks, Italy (2005)

[8]

Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. In: CCS 2006, pp. 79–88. ACM (2006)

[9]

Faber S, Jarecki S, Krawczyk H, Nguyen Q, Rosu M, and Steiner M Pernul G, Ryan PYA, and Weippl E Rich queries on encrypted data: beyond exact matches Computer Security – ESORICS 2015 2015 Cham Springer 123-145

[10]

Fuhry B, Bahmani R, Brasser F, Hahn F, Kerschbaum F, and Sadeghi A-R Livraga G and Zhu S HardIDX: practical and secure index with SGX Data and Applications Security and Privacy XXXI 2017 Cham Springer 386-408

[11]

Garg S, Mohassel P, and Papamanthou C Robshaw M and Katz J TWORAM: efficient oblivious RAM in two rounds with applications to searchable encryption Advances in Cryptology – CRYPTO 2016 2016 Heidelberg Springer 563-592

Digital Library

[12]

Ghareh Chamani, J., Papadopoulos, D., Papamanthou, C., Jalili, R.: New constructions for forward and backward private symmetric searchable encryption. In: CCS 2018, pp. 1038–1055. ACM (2018)

[13]

Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: CCS 2012, pp. 965–976. ACM (2012)

[14]

Paillier P Stern J Public-key cryptosystems based on composite degree residuosity classes Advances in Cryptology — EUROCRYPT 1999 1999 Heidelberg Springer 223-238

[15]

Sharma, V.: Bitmap index vs. b-tree index: Which and when? Oracle Technical Network (2005). http://www.oracle.com/technetwork/articles/sharma-indexes-093638.html

[16]

Song, D.X., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: S&P 2000, pp. 44–55. IEEE (2000)

[17]

Stefanov, E., Papamanthou, C., Shi, E.: Practical dynamic searchable encryption with small leakage. In: NDSS 2014, vol. 71, pp. 72–75 (2014)

[18]

Sun S-F, Liu JK, Sakzad A, Steinfeld R, and Yuen TH Askoxylakis I, Ioannidis S, Katsikas S, and Meadows C An efficient non-interactive multi-client searchable encryption with support for Boolean queries Computer Security – ESORICS 2016 2016 Cham Springer 154-172

[19]

Sun, S.F., et al.: Practical backward-secure searchable encryption from symmetric puncturable encryption. In: CCS 2018, pp. 763–780. ACM (2018)

[20]

Wang, X.S., et al.: Oblivious data structures. In: CCS 2014, pp. 215–226. ACM (2014)

[21]

Zhang, Y., Katz, J., Papamanthou, C.: All your queries are belong to us: the power of file-injection attacks on searchable encryption. In: USENIX Security Symposium, pp. 707–720 (2016)

[22]

Zuo, C., Macindoe, J., Yang, S., Steinfeld, R., Liu, J.K.: Trusted Boolean search on cloud using searchable symmetric encryption. In: Trustcom 2016, pp. 113–120. IEEE (2016)

[23]

Zuo C, Sun S-F, Liu JK, Shao J, and Pieprzyk J Lopez J, Zhou J, and Soriano M Dynamic searchable symmetric encryption schemes supporting range queries with forward (and backward) security Computer Security 2018 Cham Springer 228-246

Digital Library

Cited By

Routray KShukla SBera PGanesan DLane NShi W(2024)Multi-Client Searchable Encryption with Granular Access Control for Cloud-Assisted IoTProceedings of the 30th Annual International Conference on Mobile Computing and Networking10.1145/3636534.3697438(1620-1622)Online publication date: 4-Dec-2024
https://dl.acm.org/doi/10.1145/3636534.3697438
Tang SLiu JLuo XJiang PGai KXu LZhu L(2023)Blockchain-Empowered Search Over Encrypted Data With Forward and Backward PrivacyProceedings of the 5th ACM International Symposium on Blockchain and Secure Critical Infrastructure10.1145/3594556.3594605(34-43)Online publication date: 10-Jul-2023
https://dl.acm.org/doi/10.1145/3594556.3594605
Lu HChen JZhang K(2021)Verifiable Dynamic Searchable Symmetric Encryption with Forward Privacy in Cloud-Assisted E-Healthcare SystemsAlgorithms and Architectures for Parallel Processing10.1007/978-3-030-95384-3_40(645-659)Online publication date: 3-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-030-95384-3_40
Show More Cited By

Index Terms

Dynamic Searchable Symmetric Encryption with Forward and Stronger Backward Privacy
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data layout
        Data encryption
2. Security and privacy

Index terms have been assigned to the content through auto-classification.

Recommendations

Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives
CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

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 ...
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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Computer Security – ESORICS 2019: 24th European Symposium on Research in Computer Security, Luxembourg, September 23–27, 2019, Proceedings, Part II

Sep 2019

639 pages

ISBN:978-3-030-29961-3

DOI:10.1007/978-3-030-29962-0

Editors:
Kazue Sako
NEC Corporation, Kawasaki, Japan
,
Steve Schneider
University of Surrey, Guildford, UK
,
Peter Y. A. Ryan
University of Luxembourg, Esch-sur-Alzette, Luxembourg

© Springer Nature Switzerland AG 2019.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 23 September 2019

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Routray KShukla SBera PGanesan DLane NShi W(2024)Multi-Client Searchable Encryption with Granular Access Control for Cloud-Assisted IoTProceedings of the 30th Annual International Conference on Mobile Computing and Networking10.1145/3636534.3697438(1620-1622)Online publication date: 4-Dec-2024
https://dl.acm.org/doi/10.1145/3636534.3697438
Tang SLiu JLuo XJiang PGai KXu LZhu L(2023)Blockchain-Empowered Search Over Encrypted Data With Forward and Backward PrivacyProceedings of the 5th ACM International Symposium on Blockchain and Secure Critical Infrastructure10.1145/3594556.3594605(34-43)Online publication date: 10-Jul-2023
https://dl.acm.org/doi/10.1145/3594556.3594605
Lu HChen JZhang K(2021)Verifiable Dynamic Searchable Symmetric Encryption with Forward Privacy in Cloud-Assisted E-Healthcare SystemsAlgorithms and Architectures for Parallel Processing10.1007/978-3-030-95384-3_40(645-659)Online publication date: 3-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-030-95384-3_40
Aaraj NMarcolla CZhu X(2021)Exipnos: An Efficient Verifiable Dynamic Symmetric Searchable Encryption Scheme with Forward and Backward PrivacyProgress in Cryptology – INDOCRYPT 202110.1007/978-3-030-92518-5_22(487-509)Online publication date: 12-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-030-92518-5_22
Qin BCui HZheng XZheng D(2021)Improved Security Model for Public-Key Authenticated Encryption with Keyword SearchProvable and Practical Security10.1007/978-3-030-90402-9_2(19-38)Online publication date: 5-Nov-2021
https://dl.acm.org/doi/10.1007/978-3-030-90402-9_2
Chen TXu PWang WZheng YSusilo WJin H(2021)Bestie: Very Practical Searchable Encryption with Forward and Backward SecurityComputer Security – ESORICS 202110.1007/978-3-030-88428-4_1(3-23)Online publication date: 4-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-88428-4_1
Vo VLai SYuan XSun SNepal SLiu J(2020)Accelerating Forward and Backward Private Searchable Encryption Using Trusted ExecutionApplied Cryptography and Network Security10.1007/978-3-030-57878-7_5(83-103)Online publication date: 19-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-57878-7_5

View Options

View options

Figures

Tables

Media

View Table of Conten