Content deleted Content added
date value and line feed ref error msgs |
→History of Searchable Symmetric Encryption: Fixed typo Tags: Mobile edit Mobile web edit |
||
| (30 intermediate revisions by 15 users not shown) | |||
Line 1:
{{Short description|System allowing searching of encrypted documents}}
'''Searchable symmetric encryption''' ('''SSE''') is a 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 journal|last1=Dawn Xiaoding Song|last2=Wagner|first2=D.|last3=Perrig|first3=A.|title=Practical techniques for searches on encrypted data|url=http://dx.doi.org/10.1109/secpri.2000.848445|journal=Proceeding 2000 IEEE Symposium on Security and Privacy. S&P 2000|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 journal|last1=Curtmola|first1=Reza|last2=Garay|first2=Juan|last3=Kamara|first3=Seny|last4=Ostrovsky|first4=Rafail|date=2006-10-30|title=Searchable symmetric encryption: improved definitions and efficient constructions|url=https://doi.org/10.1145/1180405.1180417|journal=Proceedings of the 13th ACM Conference on Computer and Communications Security|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> 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. ▼
[[File:Searchable Symmetric Encryption (SSE) scheme.png|thumb|400x400px|Keyword search using an SSE scheme]]
▲'''Searchable symmetric encryption''' ('''SSE''')
== Description ==
Line 7 ⟶ 9:
A static SSE scheme consists of three algorithms <math>\mathsf{SSE = (Setup, Token, Search)}</math> that work as follows:
* <math>\mathsf{Setup}</math> takes as input a security parameter <math>k</math> and a document collection <math>\mathbf{D}</math> and outputs a symmetric key <math>K</math>, an encrypted index <math>\mathbf{I}</math>, and an encrypted document collection <math>\mathbf{ED}</math>
* <math>\mathsf{Token}</math> takes as input the secret key <math>K</math> and a keyword <math>w</math> and outputs a search token <math>tk</math>
* <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{
=== 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,
* <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.
An SSE scheme that does not support <math>\mathsf{DeleteToken}</math> and <math>\mathsf{Delete}</math> is called semi-dynamic.
== 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]]
Goh
All the previously mentioned constructions support single keyword search. Cash, Jarecki, Jutla, [[Hugo Krawczyk|Krawczyk]],
== Security ==
SSE schemes are designed to guarantee that the untrusted server cannot learn any partial information about the documents or the search queries beyond some well-defined and reasonable leakage. The leakage of a scheme is formally described using a leakage profile which itself can consists of several leakage patterns. SSE constructions attempt to minimize leakage while achieving the best possible search efficiency.
SSE security can be analyzed in several adversarial models but the most common are:
* the persistent model
* the snapshot model
=== Security in the Persistent Model ===
In the persistent model, there are SSE schemes that achieve a wide variety of leakage profiles. The most common leakage profile for static schemes that achieve single keyword search in optimal time is <math>\Lambda_{\mathrm{opt}}</math> which reveals the number of documents in the collection, the size of each document in the collection, if and when a query was repeated and which encrypted documents match the search query.
When considering dynamic SSE schemes, the state-of-the-art constructions with optimal time search have leakage profiles that guarantee forward privacy
=== Security in the Snapshot Model ===
In the snapshot model, efficient dynamic SSE schemes with no leakage beyond the number of documents and the size of the collection can be constructed.
=== Cryptanalysis ===
A leakage profile only describes the leakage of an SSE scheme but it says nothing about whether that leakage can be exploited or not. [[Cryptanalysis]] is therefore used to better understand the real-world security of a leakage profile. There is a wide variety of attacks working in different adversarial models, based on a variety of assumptions and attacking different leakage profiles.
== See also ==
Line 60 ⟶ 61:
{{reflist}}
[[Category:Cryptographic primitives]]
| |||