Searchable symmetric encryption

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.^[1][2] 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

A searchable symmetric encryption scheme is a symmetric-key encryption scheme that encrypts a collection of documents ${\displaystyle \mathbf {D} =(\mathrm {D_{1}} ,\dots ,\mathrm {D_{n}} )}$ , where each document ${\displaystyle \mathrm {D_{i}} \subseteq \mathbb {W} }$  is viewed as a set of keywords from a keyword space ${\displaystyle \mathbb {W} }$ . Given the encryption key ${\displaystyle K}$  and a keyword ${\displaystyle w\in \mathbb {W} }$ , one can generate a search token ${\displaystyle tk}$  with which the encrypted data collection can be searched for ${\displaystyle w}$ . The result of the search is the subset of encrypted documents that contain the keyword ${\displaystyle w}$ .

Static SSE

A static SSE scheme consists of three algorithms ${\displaystyle {\mathsf {SSE=(Setup,Token,Search)}}}$  that work as follows:

• ${\displaystyle {\mathsf {Setup}}}$  takes as input a security parameter ${\displaystyle k}$  and a document collection ${\displaystyle \mathbf {D} }$  and outputs a symmetric key ${\displaystyle K}$  and an encrypted document collection ${\displaystyle \mathbf {ED} }$ 
• ${\displaystyle {\mathsf {Token}}}$  takes as input the secret key ${\displaystyle K}$  and a keyword ${\displaystyle w}$  and outputs a search token ${\displaystyle tk}$ 
• ${\displaystyle {\mathsf {Search}}}$  takes as input the encrypted document collection ${\displaystyle \mathbf {ED} }$  and a search token ${\displaystyle tk}$  and outputs a set of encrypted documents ${\displaystyle \mathbf {R} \subseteq \mathbf {ED} }$ 

A static SSE scheme is used by a client and an untrusted server as follows. The client encrypts its data collection using the ${\displaystyle {\mathsf {Setup}}}$  algorithm which returns a secret key ${\displaystyle K}$  and an encrypted document collection ${\displaystyle \mathbf {ED} }$ . The client keeps ${\displaystyle K}$  secret and sends ${\displaystyle \mathbf {ED} }$  to the untrusted server. To search for a keyword ${\displaystyle w}$ , the client runs the ${\displaystyle {\mathsf {SearchToken}}}$  algorithm on ${\displaystyle K}$  and w to generate a search token ${\displaystyle tk}$  which it sends to the server. The server runs Search with ${\displaystyle \mathbf {ED} }$  and ${\displaystyle tk}$  and returns the resulting encrypted documents back to the server.

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 ${\displaystyle {\mathsf {SSE=(Setup,Token,Search,InertToken,Insert,DeleteToken,Delete)}}}$  where ${\displaystyle {\mathsf {Setup}}}$ , ${\displaystyle {\mathsf {Token}}}$  and ${\displaystyle {\mathsf {Search}}}$  are as in the static case and the remaining algorithms work as follows:

• ${\displaystyle {\mathsf {InsertToken}}}$  takes as input the secret key ${\displaystyle K}$  and a new document ${\displaystyle \mathrm {D_{n+1}} }$  and outputs an insert token ${\displaystyle itk}$ 
• ${\displaystyle {\mathsf {Insert}}}$  takes as input the encrypted document collection EDC and an insert token ${\displaystyle itk}$  and outputs an updated encrypted document collection ${\displaystyle \mathbf {ED'} }$ 
• ${\displaystyle {\mathsf {DeleteToken}}}$  takes as input the secret key ${\displaystyle K}$  and a document identifier ${\displaystyle id}$  and outputs a delete token ${\displaystyle dtk}$ 
• ${\displaystyle {\mathsf {Delete}}}$  takes as input the encrypted data collection ${\displaystyle \mathrm {EDC} }$  and a delete token ${\displaystyle dtk}$  and outputs an updated encrypted data collection ${\displaystyle \mathbf {ED'} }$ 

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

An SSE scheme that does not support ${\displaystyle {\mathsf {DeleteToken}}}$  and ${\displaystyle {\mathsf {Delete}}}$  is called semi-dynamic.

History of Searchable Symmetric Encryption

The problem of searching on encrypted data was considered by Song, Wagner and Perrig ^[1] though previous work on Oblivious RAM by Goldreich and Ostrovsky ^[3] could be used in theory to address the problem. This work ^[1] proposed an SSE scheme with a search algorithm that runs in time ${\displaystyle O(s)}$ , where ${\displaystyle s=|\mathbf {D} |}$ . Goh ^[4] and Chang and Mitzenmacher ^[5] gave new SSE constructions with search algorithms that run in time ${\displaystyle O(n)}$ , where ${\displaystyle n}$  is the number of documents. Curtmola, Garay, Kamara and Ostrovsky ^[2] later proposed two static constructions with ${\displaystyle O(\mathrm {opt} )}$  search time, where ${\displaystyle \mathrm {opt} }$  is the number of documents that contain ${\displaystyle w}$ , which is optimal. This work also proposed a semi-dynamic construction with ${\displaystyle O(\mathrm {opt} \cdot \log(u))}$  search time, where ${\displaystyle u}$  is the number of updates. An optimal dynamic SSE construction was later proposed by Kamara, Papamanthou and Roeder. ^[6]

Goh ^[4] and Chang and Mitzenmacher ^[5] proposed security definitions for SSE but the definitions had limitations. Curtmola, Garay, Kamara and Ostrovsky ^[2] proposed the notion of adaptive security for SSE which is now standard. This work also was the first to observe leakage in SSE and to formally capture it as part of the security definition.

All the previously mentioned constructions support single keyword search. Cash, Jarecki, Jutla, Krawczyk, Rosu and Steiner ^[7] proposed an SSE scheme that supports conjunctive search in sub-linear time in ${\displaystyle n}$ . 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, Malkin, Choi, George, Keromytis and Bellovin ^[8] described a construction that supports conjunctive and all disjunctive and Boolean searches in sub-linear time.

See also

• Homomorphic encryption
• Oblivious RAM
• Structured encryption
• Deterministic encryption

References

1. Dawn Xiaoding Song; Wagner, D.; Perrig, A. (2000). "Practical techniques for searches on encrypted data". Proceeding 2000 IEEE Symposium on Security and Privacy. S&P 2000. IEEE Comput. Soc: 44–55. doi:10.1109/secpri.2000.848445. ISBN 0-7695-0665-8. S2CID 2829840.
2. Curtmola, Reza; Garay, Juan; Kamara, Seny; Ostrovsky, Rafail (2006-10-30). "Searchable symmetric encryption: improved definitions and efficient constructions". Proceedings of the 13th ACM Conference on Computer and Communications Security. CCS '06. Alexandria, Virginia, USA: Association for Computing Machinery: 79–88. doi:10.1145/1180405.1180417. ISBN 978-1-59593-518-2. S2CID 961719.
3. Goldreich, Oded; Ostrovsky, Rafail (1996-05). "Software protection and simulation on oblivious RAMs". Journal of the ACM. 43 (3): 431–473. doi:10.1145/233551.233553. ISSN 0004-5411. {{cite journal}}: Check date values in: |date= (help)
4. Goh, Eu-Jin. "Secure Indexes".
5. Chang, Yan-Cheng; Mitzenmacher, Michael (2005). Ioannidis, John; Keromytis, Angelos; Yung, Moti (eds.). "Privacy Preserving Keyword Searches on Remote Encrypted Data". Applied Cryptography and Network Security. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 442–455. doi:10.1007/11496137_30. ISBN 978-3-540-31542-1.
6. Kamara, Seny; Papamanthou, Charalampos; Roeder, Tom (2012-10-16). "Dynamic searchable symmetric encryption". Proceedings of the 2012 ACM conference on Computer and communications security. CCS '12. New York, NY, USA: Association for Computing Machinery: 965–976. doi:10.1145/2382196.2382298. ISBN 978-1-4503-1651-4.
7. Cash, David; Jarecki, Stanislaw; Jutla, Charanjit; Krawczyk, Hugo; Roşu, Marcel-Cătălin; Steiner, Michael (2013). Canetti, Ran; Garay, Juan A. (eds.). "Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries". Advances in Cryptology – CRYPTO 2013. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 353–373. doi:10.1007/978-3-642-40041-4_20. ISBN 978-3-642-40041-4.
8. Pappas, Vasilis; Krell, Fernando; Vo, Binh; Kolesnikov, Vladimir; Malkin, Tal; Choi, Seung Geol; George, Wesley; Keromytis, Angelos; Bellovin, Steve (2014-05). "Blind Seer: A Scalable Private DBMS". 2014 IEEE Symposium on Security and Privacy. IEEE. doi:10.1109/sp.2014.30. {{cite journal}}: Check date values in: |date= (help)