Content deleted Content added
m link cryptanalysis |
→History of Searchable Symmetric Encryption: Fixed typo Tags: Mobile edit Mobile web edit |
||
| (3 intermediate revisions by 2 users not shown) | |||
Line 1:
{{Short description|System allowing searching of encrypted documents}}
[[File:Searchable Symmetric Encryption (SSE) scheme.png|thumb|400x400px|Keyword search using an SSE scheme]]
'''Searchable symmetric encryption''' ('''SSE''') is a form of [[encryption]] that allows one to efficiently search over a collection of encrypted documents or files without the ability to decrypt them.<ref name=":0">{{Cite book|last1=Dawn Xiaoding Song|last2=Wagner|first2=D.|last3=Perrig|first3=A.|title=Proceeding 2000 IEEE Symposium on Security and Privacy. S&P 2000 |chapter=Practical techniques for searches on encrypted data |chapter-url=http://dx.doi.org/10.1109/secpri.2000.848445|year=2000|pages=44–55|publisher=IEEE Comput. Soc|doi=10.1109/secpri.2000.848445|isbn=0-7695-0665-8|s2cid=2829840}}</ref><ref name=":1">{{Cite book|last1=Curtmola|first1=Reza|last2=Garay|first2=Juan|last3=Kamara|first3=Seny|last4=Ostrovsky|first4=Rafail|title=Proceedings of the 13th ACM conference on Computer and communications security |chapter=Searchable symmetric encryption |date=2006-10-30|chapter-url=https://doi.org/10.1145/1180405.1180417|series=CCS '06|___location=Alexandria, Virginia, USA|publisher=Association for Computing Machinery|pages=79–88|doi=10.1145/1180405.1180417|isbn=978-1-59593-518-2|s2cid=961719}}</ref><ref>{{Cite journal |last1=Amorim |first1=Ivone |last2=Costa |first2=Ivan |date=2023-07-01 |title=Leveraging Searchable Encryption through Homomorphic Encryption: A Comprehensive Analysis |journal=Mathematics |language=en |volume=11 |issue=13 |pages=2948 |doi=10.3390/math11132948 |doi-access=free |issn=2227-7390|arxiv=2306.14407 }}</ref> SSE can be used to outsource files to an untrusted cloud storage server without ever revealing the files in the clear but while preserving the server's ability to search over them.
== Description ==
Line 13:
* <math>\mathsf{Search}</math> takes as input the encrypted index <math>\mathbf{I}</math>, the encrypted document collection <math>\mathbf{ED}</math> and a search token <math>tk</math> and outputs a set of encrypted documents <math>\mathbf{R} \subseteq \mathbf{ED}</math>
A static SSE scheme is used by a client and an untrusted server as follows. The client encrypts its data collection using the <math>\mathsf{Setup}</math> algorithm which returns a secret key <math>K</math>, an encrypted index <math>\mathbf{I}</math> and an encrypted document collection <math>\mathbf{ED}</math>. The client keeps <math>K</math> secret and sends <math>\mathbf{ED}</math> and <math>\mathbf{I}</math> to the untrusted server. To search for a keyword <math>w</math>, the client runs the <math>\mathsf{Token}</math> algorithm on <math>K</math> and <math>w</math> to generate a search token <math>tk</math> which it sends to the server. The server runs Search with <math>\mathbf{ED}</math>, <math>\mathbf{I}</math>, and <math>tk</math> and returns the resulting encrypted documents back to the client.
=== Dynamic SSE ===
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
* <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>\
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]],
== Security ==
| |||