Searchable symmetric encryption: Difference between revisions

Revision as of 14:48, 19 June 2025

Latest revision as of 02:57, 26 August 2025

(One intermediate revision by one other user not shown)

Line 18:

A dynamic SSE scheme supports, in addition to search, the insertion and deletion of documents. A dynamic SSE scheme consists of seven algorithms <math>\mathsf{SSE = (Setup, Token, Search, InsertToken, Insert, DeleteToken, Delete)}</math> where <math>\mathsf{Setup}</math>, <math>\mathsf{Token}</math> and <math>\mathsf{Search}</math> are as in the static case and the remaining algorithms work as follows:

* <math>\mathsf{InsertToken}</math> takes as input the secret key <math>K</math> and a new document <math>\mathrm{D_{n+1}}</math> and outputs an insert token <math>itk</math>

* <math>\mathsf{Insert}</math> takes as input the encrypted document collection EDC<math>\mathbf{ED}</math> and an insert token <math>itk</math> and outputs an updated encrypted document collection <math>\mathbf{ED'}</math>

* <math>\mathsf{DeleteToken}</math> takes as input the secret key <math>K</math> and a document identifier <math>id</math> and outputs a delete token <math>dtk</math>

* <math>\mathsf{Delete}</math> takes as input the encrypted data collection <math>\mathrmmathbf{EDCED}</math> and a delete token <math>dtk</math> and outputs an updated encrypted data collection <math>\mathbf{ED'}</math>

To add a new document <math>\mathrm{D_{n+1}}</math> the client runs <math>\mathsf{InsertToken}</math> on <math>K</math> and <math>\mathrm{D_{n+1}}</math>to generate an insert token <math>itk</math> which it sends to the server. The server runs <math>\mathsf{Insert}</math> with <math>\mathbf{ED}</math> and <math>itk</math> and stores the updated encrypted document collection. To delete a document with identifier <math>id</math>, the client runs the <math>\mathsf{DeleteToken}</math> algorithm with <math>K</math> and <math>id</math> to generate a delete token <math>dtk</math> which it sends to the server. The server runs <math>\mathsf{Delete}</math> with <math>\mathbf{ED}</math> and <math>dtk</math> and stores the updated encrypted document collection.

Line 31:

Goh<ref name=":2" /> and Chang and [[Michael Mitzenmacher|Mitzenmacher]]<ref name=":3" /> proposed security definitions for SSE. These were strengthened and extended by Curtmola, Garay, Kamara and Ostrovsky<ref name=":1" /> who proposed the notion of adaptive security for SSE. This work also was the first to observe leakage in SSE and to formally capture it as part of the security definition. Leakage was further formalized and generalized by Chase and [[Seny Kamara|Kamara]].<ref>{{Cite book|last1=Chase|first1=Melissa|last2=Kamara|first2=Seny|title=Advances in Cryptology - ASIACRYPT 2010 |chapter=Structured Encryption and Controlled Disclosure |date=2010|editor-last=Abe|editor-first=Masayuki|series=Lecture Notes in Computer Science|volume=6477 |language=en|___location=Berlin, Heidelberg|publisher=Springer|pages=577–594|doi=10.1007/978-3-642-17373-8_33|isbn=978-3-642-17373-8|doi-access=free}}</ref> Islam, Kuzu and Kantarcioglu described the first leakage attack.<ref>{{Cite journal|last1=Islam|first1=Mohammad|last2=Kuzu|first2=Mehmet|last3=Kantarcioglu|first3=Murat|title=Access Pattern disclosure on Searchable Encryption:Ramification, Attack and Mitigation|url=https://www.ndss-symposium.org/wp-content/uploads/2017/09/06_1.pdf|journal=Network and Distributed System Security (NDSS) Symposium}}</ref>

All the previously mentioned constructions support single keyword search. Cash, Jarecki, Jutla, [[Hugo Krawczyk|Krawczyk]], RosuRoşu and Steiner<ref>{{Cite book|last1=Cash|first1=David|last2=Jarecki|first2=Stanislaw|last3=Jutla|first3=Charanjit|last4=Krawczyk|first4=Hugo|last5=Roşu|first5=Marcel-Cătălin|last6=Steiner|first6=Michael|title=Advances in Cryptology – CRYPTO 2013 |chapter=Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries |date=2013|editor-last=Canetti|editor-first=Ran|editor2-last=Garay|editor2-first=Juan A.|series=Lecture Notes in Computer Science|volume=8042 |language=en|___location=Berlin, Heidelberg|publisher=Springer|pages=353–373|doi=10.1007/978-3-642-40041-4_20|isbn=978-3-642-40041-4|doi-access=free}}</ref> proposed an SSE scheme that supports conjunctive search in sub-linear time in <math>n</math>. The construction can also be extended to support disjunctive and Boolean searches that can be expressed in searchable normal form (SNF) in sub-linear time. At the same time, Pappas, Krell, Vo, Kolesnikov, [[Tal Malkin|Malkin]], Choi, George, Keromytis and [[Steven M. Bellovin|Bellovin]]<ref>{{Cite book|last1=Pappas|first1=Vasilis|last2=Krell|first2=Fernando|last3=Vo|first3=Binh|last4=Kolesnikov|first4=Vladimir|last5=Malkin|first5=Tal|last6=Choi|first6=Seung Geol|last7=George|first7=Wesley|last8=Keromytis|first8=Angelos|last9=Bellovin|first9=Steve|title=2014 IEEE Symposium on Security and Privacy |chapter=Blind Seer: A Scalable Private DBMS |date=May 2014|pages=359–374 |publisher=IEEE|doi=10.1109/sp.2014.30|isbn=978-1-4799-4686-0 |s2cid=9165575 |doi-access=free}}</ref> described a construction that supports conjunctive and all disjunctive and Boolean searches in sub-linear time.

== Security ==