{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T11:01:48Z","timestamp":1777806108219,"version":"3.51.4"},"reference-count":44,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2020,1,21]],"date-time":"2020-01-21T00:00:00Z","timestamp":1579564800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer Security"],"published-print":{"date-parts":[[2020,3,17]]},"abstract":"<jats:p>Dynamic Searchable Symmetric Encryption ([Formula: see text]), 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 desirable from a [Formula: see text] scheme. The former captures that the newly updated entries cannot be related to previous search queries and the latter ensures that search queries should not leak matching entries after they have been deleted. These security properties are formalized in terms of the information leakage that can be incurred by the respective constructions. Existing backward private constructions either have a non-optimal communication overhead or they make use of heavy cryptographic primitives. Our main contribution consists of two efficient backward private schemes [Formula: see text] and [Formula: see text] that aim to achieve practical efficiency by using light weight symmetric cryptographic components only. In the process, we also revisit the existing definitions of information leakage for backward privacy [Bost et al. (In ACM CCS ( 2017 ) 1465\u20131482 ACM Press)] and propose a relaxed formulation. [Formula: see text] is the first construction to achieve backward privacy in the general setting with optimal communication complexity. Our second construction, [Formula: see text], is the first single round-trip scheme achieving backward privacy in a restricted setting with optimal communication complexity using light weight symmetric cryptographic primitives. The prototype implementations of our schemes depict the practicability of the proposed constructions and indicate that the cost of achieving backward privacy over forward privacy is substantially small. The performance results also show that the proposed constructions outperform the currently most efficient scheme achieving backward privacy.<\/jats:p>","DOI":"10.3233\/jcs-191322","type":"journal-article","created":{"date-parts":[[2020,1,21]],"date-time":"2020-01-21T12:37:53Z","timestamp":1579610273000},"page":"229-267","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":7,"title":["Efficient backward private searchable encryption"],"prefix":"10.1177","volume":"28","author":[{"given":"Sanjit","family":"Chatterjee","sequence":"first","affiliation":[{"name":"Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India. E-mails:\u00a0,\u00a0,\u00a0"}]},{"given":"Shravan Kumar","family":"Parshuram Puria","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India. E-mails:\u00a0,\u00a0,\u00a0"}]},{"given":"Akash","family":"Shah","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India. E-mails:\u00a0,\u00a0,\u00a0"}]}],"member":"179","published-online":{"date-parts":[[2020,1,21]]},"reference":[{"key":"ref001","first-page":"24","volume":"2017","author":"Abdelraheem M.A.","year":"2017","journal-title":"IACR Cryptology ePrint Archive"},{"key":"ref002","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare and P.\u00a0Rogaway, The security of triple encryption and a framework for code-based game-playing proofs, in: EUROCRYPT, LNCS, Vol.\u00a04004, Springer, 2006, pp.\u00a0409\u2013426.","DOI":"10.1007\/11761679_25"},{"key":"ref003","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh and B.\u00a0Waters, Constrained pseudorandom functions and their applications, in: ASIACRYPT, LNCS, Vol.\u00a08270, Springer, 2013, pp.\u00a0280\u2013300.","DOI":"10.1007\/978-3-642-42045-0_15"},{"key":"ref004","doi-asserted-by":"crossref","unstructured":"R.\u00a0Bost, \u03a3o\n                      \u03c6\n                      o\n                      \u03c2\n                      : Forward secure searchable encryption, in: ACM CCS, ACM Press, 2016, pp.\u00a01143\u20131154.","DOI":"10.1145\/2976749.2978303"},{"key":"ref005","unstructured":"R.\u00a0Bost, Searchable encryption: New constructions of encrypted databases, PhD thesis, 2018."},{"key":"ref006","doi-asserted-by":"crossref","unstructured":"R.\u00a0Bost, B.\u00a0Minaud and O.\u00a0Ohrimenko, Forward and backward private searchable encryption from constrained cryptographic primitives, in: ACM CCS, ACM Press, 2017, pp.\u00a01465\u20131482.","DOI":"10.1145\/3133956.3133980"},{"key":"ref007","doi-asserted-by":"crossref","unstructured":"E.\u00a0Boyle, S.\u00a0Goldwasser and I.\u00a0Ivan, Functional signatures and pseudorandom functions, in: PKC, LNCS, Vol.\u00a08383, Springer, 2014, pp.\u00a0501\u2013519.","DOI":"10.1007\/978-3-642-54631-0_29"},{"key":"ref008","doi-asserted-by":"crossref","unstructured":"D.\u00a0Cash, P.\u00a0Grubbs, J.\u00a0Perry and T.\u00a0Ristenpart, Leakage-abuse attacks against searchable encryption, in: ACM CCS, ACM Press, 2015, pp.\u00a0668\u2013679.","DOI":"10.1145\/2810103.2813700"},{"key":"ref009","doi-asserted-by":"crossref","unstructured":"D.\u00a0Cash, J.\u00a0Jaeger, S.\u00a0Jarecki, C.S.\u00a0Jutla, H.\u00a0Krawczyk, M.\u00a0Rosu and M.\u00a0Steiner, Dynamic searchable encryption in very-large databases: Data structures and implementation, in: NDSS, The Internet Society, 2014.","DOI":"10.14722\/ndss.2014.23264"},{"key":"ref010","doi-asserted-by":"crossref","unstructured":"D.\u00a0Cash, S.\u00a0Jarecki, C.\u00a0Jutla, H.\u00a0Krawczyk, M.C.\u00a0Ro\u015fu and M.\u00a0Steiner, Highly-scalable searchable symmetric encryption with support for Boolean queries, in: CRYPTO, LNCS, Vol.\u00a08042, Springer, 2013, pp.\u00a0353\u2013373.","DOI":"10.1007\/978-3-642-40041-4_20"},{"key":"ref011","unstructured":"G.\u00a0Chamani, SSE, https:\/\/github.com\/jgharehchamani\/SSE (Accessed: 2019-10-08)."},{"key":"ref012","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Chang and M.\u00a0Mitzenmacher, Privacy preserving keyword searches on remote encrypted data, in: ACNS, Lecture Notes in Computer Science, Vol.\u00a03531, 2005, pp.\u00a0442\u2013455.","DOI":"10.1007\/11496137_30"},{"key":"ref013","doi-asserted-by":"crossref","unstructured":"M.\u00a0Chase and S.\u00a0Kamara, Structured encryption and controlled disclosure, in: ASIACRYPT, LNCS, Vol.\u00a06477, Springer, 2010, pp.\u00a0577\u2013594.","DOI":"10.1007\/978-3-642-17373-8_33"},{"key":"ref014","doi-asserted-by":"crossref","unstructured":"R.\u00a0Curtmola, J.A.\u00a0Garay, S.\u00a0Kamara and R.\u00a0Ostrovsky, Searchable symmetric encryption: Improved definitions and efficient constructions, in: ACM CCS, ACM Press, 2006, pp.\u00a079\u201388.","DOI":"10.1145\/1180405.1180417"},{"key":"ref015","unstructured":"Enron Email dataset, https:\/\/www.cs.cmu.edu\/~enron\/ (Accessed: 2018-05-14)."},{"key":"ref016","doi-asserted-by":"publisher","DOI":"10.1515\/popets-2018-0002"},{"key":"ref017","doi-asserted-by":"crossref","unstructured":"S.\u00a0Faber, S.\u00a0Jarecki, H.\u00a0Krawczyk, Q.\u00a0Nguyen, M.\u00a0Rosu and M.\u00a0Steiner, Rich queries on encrypted data: Beyond exact matches, in: ESORICS, LNCS, Vol.\u00a09327, Springer, 2015, pp.\u00a0123\u2013145.","DOI":"10.1007\/978-3-319-24177-7_7"},{"key":"ref018","unstructured":"Facebook, RocksDB: A persistent key-value store for fast storage environment, https:\/\/rocksdb.org\/ (Accessed: 2018-05-14)."},{"key":"ref019","doi-asserted-by":"crossref","unstructured":"S.\u00a0Garg, P.\u00a0Mohassel and C.\u00a0Papamanthou, TWORAM: efficient oblivious RAM in two rounds with applications to searchable encryption, in: CRYPTO, LNCS, Vol.\u00a09816, Springer, 2016, pp.\u00a0563\u2013592.","DOI":"10.1007\/978-3-662-53015-3_20"},{"key":"ref020","unstructured":"C.\u00a0Gentry, A fully homomorphic encryption scheme, PhD thesis, Stanford, CA, USA, 2009. ISBN 978-1-109-44450-6."},{"key":"ref021","doi-asserted-by":"crossref","unstructured":"J.\u00a0Ghareh Chamani, D.\u00a0Papadopoulos, C.\u00a0Papamanthou and R.\u00a0Jalili, New constructions for forward and backward private symmetric searchable encryption, in: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS \u201918, ACM, 2018, pp.\u00a01038\u20131055.","DOI":"10.1145\/3243734.3243833"},{"key":"ref022","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, S.\u00a0Goldwasser and S.\u00a0Micali, How to construct random functions (extended abstract), in: FOCS, IEEE Computer Society Press, 1984, pp.\u00a0464\u2013479.","DOI":"10.1109\/SFCS.1984.715949"},{"key":"ref023","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"ref024","doi-asserted-by":"crossref","unstructured":"S.\u00a0Goldwasser, S.\u00a0Micali and R.L.\u00a0Rivest, A \u201cparadoxical\u201d solution to the signature problem (extended abstract), in: FOCS, IEEE Computer Society, 1984, pp.\u00a0441\u2013448.","DOI":"10.1109\/SFCS.1984.715946"},{"key":"ref025","doi-asserted-by":"publisher","DOI":"10.1137\/0217017"},{"key":"ref026","doi-asserted-by":"crossref","unstructured":"M.D.\u00a0Green and I.\u00a0Miers, Forward secure asynchronous messaging from puncturable encryption, in: IEEE Symposium on Security and Privacy, IEEE Computer Society Press, 2015, pp.\u00a0305\u2013320.","DOI":"10.1109\/SP.2015.26"},{"key":"ref027","doi-asserted-by":"crossref","unstructured":"S.\u00a0Kamara and T.\u00a0Moataz, Boolean searchable symmetric encryption with worst-case sub-linear complexity, in: EUROCRYPT, LNCS, Vol.\u00a010212, Springer, 2017, pp.\u00a094\u2013124.","DOI":"10.1007\/978-3-319-56617-7_4"},{"key":"ref028","doi-asserted-by":"crossref","unstructured":"S.\u00a0Kamara, C.\u00a0Papamanthou and T.\u00a0Roeder, Dynamic searchable symmetric encryption, in: ACM CCS, ACM Press, 2012, pp.\u00a0965\u2013976.","DOI":"10.1145\/2382196.2382298"},{"key":"ref029","doi-asserted-by":"crossref","unstructured":"A.\u00a0Kiayias, S.\u00a0Papadopoulos, N.\u00a0Triandopoulos and T.\u00a0Zacharias, Delegatable pseudorandom functions and applications, in: ACM CCS, ACM Press, 2013, pp.\u00a0669\u2013684.","DOI":"10.1145\/2508859.2516668"},{"key":"ref030","doi-asserted-by":"crossref","unstructured":"K.S.\u00a0Kim, M.\u00a0Kim, D.\u00a0Lee, J.H.\u00a0Park and W.\u00a0Kim, Forward secure dynamic searchable symmetric encryption with efficient updates, in: ACM CCS, ACM Press, 2017, pp.\u00a01449\u20131463.","DOI":"10.1145\/3133956.3133970"},{"key":"ref031","doi-asserted-by":"publisher","DOI":"10.3934\/amc.2013.7.1"},{"key":"ref032","doi-asserted-by":"publisher","DOI":"10.1023\/B:DESI.0000036250.18062.3f"},{"key":"ref033","unstructured":"M.\u00a0Naveed, The fallacy of composition of oblivious RAM and searchable encryption, IACR Cryptology ePrint Archive 2015 (2015), 668."},{"key":"ref034","doi-asserted-by":"crossref","unstructured":"M.\u00a0Naveed, M.\u00a0Prabhakaran and C.A.\u00a0Gunter, Dynamic searchable encryption via blind storage, in: IEEE Symposium on Security and Privacy, IEEE Computer Society Press, 2014, pp.\u00a0639\u2013654.","DOI":"10.1109\/SP.2014.47"},{"key":"ref035","doi-asserted-by":"crossref","unstructured":"T.\u00a0Pornin and J.P.\u00a0Stern, Digital signatures do not guarantee exclusive ownership, in: ACNS, LNCS, Vol.\u00a03531, 2005, pp.\u00a0138\u2013150.","DOI":"10.1007\/11496137_10"},{"key":"ref036","unstructured":"NLTK Project, Natural Language Toolkit, https:\/\/www.nltk.org\/ (Accessed: 2018-05-14)."},{"key":"ref037","unstructured":"D.X.\u00a0Song, D.\u00a0Wagner and A.\u00a0Perrig, Practical techniques for searches on encrypted data, in: IEEE Symposium on Security and Privacy, IEEE Computer Society Press, 2000, pp.\u00a044\u201355."},{"key":"ref038","unstructured":"X.\u00a0Song, C.\u00a0Dong, D.\u00a0Yuan, Q.\u00a0Xu and M.\u00a0Zhao, Forward private searchable symmetric encryption with optimized I\/O efficiency, in: IEEE Transactions on Dependable and Secure Computing, 2018."},{"key":"ref039","doi-asserted-by":"crossref","unstructured":"E.\u00a0Stefanov, C.\u00a0Papamanthou and E.\u00a0Shi, Practical dynamic searchable encryption with small leakage, in: NDSS, The Internet Society, 2014.","DOI":"10.14722\/ndss.2014.23298"},{"key":"ref040","doi-asserted-by":"crossref","unstructured":"E.\u00a0Stefanov, M.\u00a0van Dijk, E.\u00a0Shi, C.W.\u00a0Fletcher, L.\u00a0Ren, X.\u00a0Yu and S.\u00a0Devadas, Path ORAM: An extremely simple oblivious RAM protocol, in: ACM CCS, ACM Press, 2013, pp.\u00a0299\u2013310.","DOI":"10.1145\/2508859.2516660"},{"key":"ref041","doi-asserted-by":"crossref","unstructured":"S.F.\u00a0Sun, X.\u00a0Yuan, J.K.\u00a0Liu, R.\u00a0Steinfeld, A.\u00a0Sakzad, V.\u00a0Vo and S.\u00a0Nepal, Practical backward-secure searchable encryption from symmetric puncturable encryption, in: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS \u201918, ACM, 2018, pp.\u00a0763\u2013780.","DOI":"10.1145\/3243734.3243782"},{"key":"ref042","unstructured":"The OpenSSL Project, OpenSSL Cryptography and SSL\/TLS Toolkit, https:\/\/www.openssl.org\/ (Accessed: 2018-05-14)."},{"key":"ref043","doi-asserted-by":"crossref","unstructured":"S.\u00a0Vaudenay, Digital signature schemes with domain parameters: Yet another parameter issue in ECDSA, in: ACISP, LNCS, Vol.\u00a03108, Springer, 2004, pp.\u00a0188\u2013199.","DOI":"10.1007\/978-3-540-27800-9_17"},{"key":"ref044","unstructured":"Y.\u00a0Zhang, J.\u00a0Katz and C.\u00a0Papamanthou, All your queries are belong to us: The power of file-injection attacks on searchable encryption, in: USENIX Security Symposium, USENIX Association, 2016, pp.\u00a0707\u2013720."}],"container-title":["Journal of Computer Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-191322","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/JCS-191322","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-191322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T20:45:22Z","timestamp":1777495522000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/JCS-191322"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,21]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,3,17]]}},"alternative-id":["10.3233\/JCS-191322"],"URL":"https:\/\/doi.org\/10.3233\/jcs-191322","relation":{},"ISSN":["0926-227X","1875-8924"],"issn-type":[{"value":"0926-227X","type":"print"},{"value":"1875-8924","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,21]]}}}