Structured encryption

Structured encryption (STE) is a form of encryption that encrypts a data structure so that it can be privately queried. Structured encryption can be used as a building block to design end-to-end encrypted databases, efficient searchable symmetric encryption (SSE) and other algorithms that can be efficiently executed on encrypted data.

Description

A structured encryption scheme^[1] is a symmetric-key encryption scheme that encrypts a data structure in such a way that, given the key $K$ and a query $q$ , one can generate a query token $qtk$ with which the encrypted data structure can be queried. If the STE scheme is dynamic then it also supports update operations like inserts and deletes. There are several forms of STE including response-revealing STE where the response to the query is output in plaintext and response-hiding where the response to the query is output in encrypted form. STE schemes guarantee that no information about the data or queries can be recovered from the encrypted data structure and tokens beyond a well-specified and "reasonable" leakage profile.

STE schemes with a variety of leakage profiles have been designed for a wide array of abstract data types and data structures including arrays, multi-maps,^[2]^[1]^[3] dictionaries and graphs.^[1]^[4]

STE is closely related to but different than searchable symmetric encryption. The purpose of SSE is to encrypt document collections in such a way that keyword search can still be executed on the encrypted documents whereas the purpose of STE is to encrypt data structures in such a way that queries can still be executed over the encrypted structure. Certain types of STE schemes like multi-map encryption schemes can be used to design sub-linear and optimal SSE schemes.^[2]

References

^ ^a ^b ^c Chase, Melissa; Kamara, Seny (2010). "Structured Encryption and Controlled Disclosure". In Abe, Masayuki (ed.). Advances in Cryptology - ASIACRYPT 2010. Lecture Notes in Computer Science. Vol. 6477. Berlin, Heidelberg: Springer. pp. 577–594. doi:10.1007/978-3-642-17373-8_33. ISBN 978-3-642-17373-8.
^ ^a ^b Curtmola, Reza; Garay, Juan; Kamara, Seny; Ostrovsky, Rafail (2011-01-01). "Searchable symmetric encryption: Improved definitions and efficient constructions". Journal of Computer Security. 19 (5): 895–934. doi:10.3233/JCS-2011-0426. ISSN 0926-227X.
^ "Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation – NDSS Symposium". Retrieved 2022-02-23.
^ Meng, Xianrui; Kamara, Seny; Nissim, Kobbi; Kollios, George (2015-10-12). "GRECS". Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. CCS '15. New York, NY, USA: Association for Computing Machinery. pp. 504–517. doi:10.1145/2810103.2813672. ISBN 978-1-4503-3832-5. S2CID 6166972.

[:0-1] Chase, Melissa; Kamara, Seny (2010). "Structured Encryption and Controlled Disclosure". In Abe, Masayuki (ed.). Advances in Cryptology - ASIACRYPT 2010. Lecture Notes in Computer Science. Vol. 6477. Berlin, Heidelberg: Springer. pp. 577–594. doi:10.1007/978-3-642-17373-8_33. ISBN 978-3-642-17373-8.

[:1-2] Curtmola, Reza; Garay, Juan; Kamara, Seny; Ostrovsky, Rafail (2011-01-01). "Searchable symmetric encryption: Improved definitions and efficient constructions". Journal of Computer Security. 19 (5): 895–934. doi:10.3233/JCS-2011-0426. ISSN 0926-227X.

[3] "Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation – NDSS Symposium". Retrieved 2022-02-23.

[4] Meng, Xianrui; Kamara, Seny; Nissim, Kobbi; Kollios, George (2015-10-12). "GRECS". Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. CCS '15. New York, NY, USA: Association for Computing Machinery. pp. 504–517. doi:10.1145/2810103.2813672. ISBN 978-1-4503-3832-5. S2CID 6166972.

[1]

[2]

[3]

[4]