Structured encryption explained
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
and a query
, one can generate a query token
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] [3] dictionaries and graphs.[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.
Notes and References
- Book: Chase. Melissa. Kamara. Seny. Advances in Cryptology - ASIACRYPT 2010 . Structured Encryption and Controlled Disclosure . 2010. Abe. Masayuki. Lecture Notes in Computer Science. 6477 . en. Berlin, Heidelberg. Springer. 577–594. 10.1007/978-3-642-17373-8_33. 978-3-642-17373-8. free.
- Curtmola. Reza. Garay. Juan. Kamara. Seny. Ostrovsky. Rafail. 2011-01-01. Searchable symmetric encryption: Improved definitions and efficient constructions. Journal of Computer Security. en. 19. 5. 895–934. 10.3233/JCS-2011-0426. 0926-227X.
- Web site: Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation – NDSS Symposium. 2022-02-23. en-US.
- Book: Meng. Xianrui. Kamara. Seny. Nissim. Kobbi. Kollios. George. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security . GRECS . 2015-10-12. https://doi.org/10.1145/2810103.2813672. CCS '15. New York, NY, USA. Association for Computing Machinery. 504–517. 10.1145/2810103.2813672. 978-1-4503-3832-5. 6166972 .
