Searchable symmetric encryption: Difference between revisions

Revision as of 20:17, 27 January 2023

Revision as of 22:24, 28 January 2023

Line 25:

== History of Searchable Symmetric Encryption ==

The problem of searching on encrypted data was considered by [[Dawn Song|Song]], [[David A. Wagner|Wagner]] and [[Adrian Perrig|Perrig]]<ref name=":0" /> though previous work on [[Oblivious RAM]] by [[Oded Goldreich|Goldreich]] and [[Rafail Ostrovsky|Ostrovsky]]<ref>{{Cite journal|last1=Goldreich|first1=Oded|last2=Ostrovsky|first2=Rafail|date=May 1996|title=Software protection and simulation on oblivious RAMs|url=http://dx.doi.org/10.1145/233551.233553|journal=Journal of the ACM|volume=43|issue=3|pages=431–473|doi=10.1145/233551.233553|hdl=1721.1/103684 |s2cid=7502114 |issn=0004-5411|hdl-access=free}}</ref> could be used in theory to address the problem. This work<ref name=":0" /> proposed an SSE scheme with a search algorithm that runs in time <math>O(s)</math>, where <math>s = |\mathbf{D}|</math>. Goh<ref name=":2">{{Cite web|last=Goh|first=Eu-Jin|title=Secure Indexes|url=https://eprint.iacr.org/2003/216}}</ref> and Chang and [[Michael Mitzenmacher|Mitzenmacher]]<ref name=":3">{{Cite journal|last1=Chang|first1=Yan-Cheng|last2=Mitzenmacher|first2=Michael|date=2005|editor-last=Ioannidis|editor-first=John|editor2-last=Keromytis|editor2-first=Angelos|editor3-last=Yung|editor3-first=Moti|title=Privacy Preserving Keyword Searches on Remote Encrypted Data|url=https://link.springer.com/chapter/10.1007/11496137_30|journal=Applied Cryptography and Network Security|series=Lecture Notes in Computer Science|volume=3531 |language=en|___location=Berlin, Heidelberg|publisher=Springer|pages=442–455|doi=10.1007/11496137_30|isbn=978-3-540-31542-1|doi-access=free}}</ref> gave new SSE constructions with search algorithms that run in time <math>O(n)</math>, where <math>n</math> is the number of documents. Curtmola, Garay, [[Seny Kamara|Kamara]] and [[Rafail Ostrovsky|Ostrovsky]]<ref name=":1" /> later proposed two static constructions with <math>O(\mathrm{opt} )</math> search time, where <math>\mathrm{opt}</math> is the number of documents that contain <math>w</math>, which is optimal. This work also proposed a semi-dynamic construction with <math>O(\mathrm{opt}\cdot \log(u))</math> search time, where <math>u</math> is the number of updates. An optimal dynamic SSE construction was later proposed by [[Seny Kamara|Kamara]], Papamanthou and Roeder.<ref>{{Cite journal|last1=Kamara|first1=Seny|last2=Papamanthou|first2=Charalampos|last3=Roeder|first3=Tom|date=2012-10-16|title=Dynamic searchable symmetric encryption|url=https://doi.org/10.1145/2382196.2382298|journal=Proceedings of the 2012 ACM Conference on Computer and Communications Security|series=CCS '12|___location=New York, NY, USA|publisher=Association for Computing Machinery|pages=965–976|doi=10.1145/2382196.2382298|isbn=978-1-4503-1651-4|s2cid=243046 }}</ref>

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 journal|last1=Chase|first1=Melissa|last2=Kamara|first2=Seny|date=2010|editor-last=Abe|editor-first=Masayuki|title=Structured Encryption and Controlled Disclosure|url=https://link.springer.com/chapter/10.1007/978-3-642-17373-8_33|journal=Advances in Cryptology - ASIACRYPT 2010|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]], Rosu and Steiner<ref>{{Cite journal|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|date=2013|editor-last=Canetti|editor-first=Ran|editor2-last=Garay|editor2-first=Juan A.|title=Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries|url=https://link.springer.com/chapter/10.1007/978-3-642-40041-4_20|journal=Advances in Cryptology – CRYPTO 2013|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 journal|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|date=May 2014|title=Blind Seer: A Scalable Private DBMS|url=http://dx.doi.org/10.1109/sp.2014.30|journal=2014 IEEE Symposium on Security and Privacy|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 ==