a glossary of terms | EncryptedSystems.org

This post is a glossary of terms that are commonly used in research papers in encrypted search and encrypted systems. This should be used as a resource that readers can come back to when when reading future posts. The glossary will be updated as needed.

Auxiliary information: information about the client’s queries and/or data that the adversary learns from out-of-band sources.
Deterministic encryption (DTE): an encryption scheme that always encrypts a message to the same ciphertext. A DTE is property-preserving in the sense that it reveals the equality property: given two or more cipertexts one can learn if they encrypt the same message by checking if they are equal.
Dictionary: a data structure that holds a set of key/value pairs while supporting (at least) get and put operations. In some encrypted search research paper (and on this site) we will refer to the “keys” in a key/value pairs as a label so that there is no confusion with cryptographic keys. With this in mind, a get operation takes as input a label and returns the value associated with it and a put operation takes as input a label/value pair and inserts it in the dictionary.
Encrypted algorithm: an algorithm that can be executed over encrypted data. Typically, this refers to solutions that are tailor-made to support a given algorithm and are optimal or close to optimal in performance. This is in contrast to solutions based on, say homomorphic encryption, which need one to transform the algorithm into an arithmetic circuit before being able to execute it.
Encrypted data structure: a data structure whose stored data items are encrypted and that supports the relevant data structure operations over the encrypted items without needing the key.
Encrypted dictionary (EDX): a dictionary structure whose label/value pairs are encrypted and that supports get and put operations over the encrypted pairs.
Encrypted multi-map (EMM): a multi-map structure whose label/tuple pairs are encrypted and that supports get and put operations over the encrypted pairs.
Encrypted Search: the field that focuses on designing and analyzing encrypted search algorithms. The techniques and protocols developed in this field are what underlie most encrypted systems and, in particular, encrypted databases.
Encrypted search algorithms (ESA): special-purpose encrypted algorithms for search/query tasks like keyword search over a collection of unstructured documents, or querying document or relational databases.
Typically, this refers to solutions that are optimal or close to optimal.
Homomorphic encryption: an encryption scheme that encrypts elements from an algebraic structure and supports its operation(s) on encrypted data. For example, an additively-homomorphic encryption scheme encrypts elements from an additive group and supports addition over the encrypted elements. A multiplicatively homomorphic encryption scheme encrypts elements from a multiplicative group and supports multiplication over the encrypted elements. A fully-homomorphic encryption scheme encrypts elements of a ring and supports addition and multiplication over the encrypted elements.
Injection attack: a leakage attack with the following structure: (1) the adversary tricks the client into inserting data of its choice into its encrypted structure; (2) the adversary observes the leakage that is created when the client queries the encrypted structure; (3) the adversary uses this information to learn as much as possible about the client queries.
Inference attack: a leakage attack with the following structure: (1) the adversary starts with some auxiliary information about the client’s queries and/or data; (2) the adversary observes the leakage produced by the client’s queries; (3) the adversary uses this information to recover information about the client’s queries and/or data.
Known-data attack: a leakage attack with the following structure: (1) the adversary knows some fraction of the client’s data; (2) the adversary observes the leakage produced by the client’s queries; (3) the adversary uses this information to recover information about the client’s queries and/or data.
Leakage: information revealed about private inputs by a cryptographic scheme. In the case of ESAs, this information is about client queries and/or data.
Leakage graph: a graph-based representation of leakage.
Leakage profile: the leakage of an ESA. With respect to an encrypted structure this refers to leakage from the encrypted structure itself and of all its operations.
Leakage pattern: many leakage profiles can be decomposed into smaller units called leakage patterns.
Leakage suppression: techniques to partially or completely remove the leakage of an ESA.
Multi-map: a data structure that holds a set of key/tuple pairs while supporting (at least) get and put operations. In some encrypted search papers (and on this site) we will refer to the “keys” in a key/tuple pair as a label so that there is no confusion with cryptographic keys. With this in mind, a get operation takes as input a label and returns the tuple
associated with it and a put operation takes as input a label/tuple pair and inserts it in the multi-map.
Order-preserving encryption: an encryption scheme that encrypts messages in such a way that their ciphertexts preserve their order. For example, given three values \(a, b, c\) such that \(a \lt b \lt c\), then their ciphertests \(\mathsf{ct}_a, \mathsf{ct}_b, \mathsf{ct}_c\) will be such that \(\mathsf{ct}_a \lt \mathsf{ct}_b \lt \mathsf{ct}_c\).
Oblivious RAM (ORAM): encryption scheme that encrypts an array and supports read and write operations to an array index without revealing which index was accessed.
Persistent adversary: an adversary that tries to recover information about the client’s queries and/or data from: (1) the encrypted data structure; and (2) the messages sent back and forth between the client and the server during the execution of operations. The latter is usually referred to as the transcript of the operation.
Property-preserving encryption (PPE): an encryption scheme that encrypts data in such a way that the ciphertext reveals a certain property of the data. Deterministic and order-preserving encryption schemes are PPE schemes.
Query equality (qeq): a leakage pattern that reveals if and when two operations were for the same query. In the case of an EMM or an EDX, it reveals if and when two get operations were for the same label.
Searchable symmetric encryption (SSE): an encryption scheme that encrypts a collection of unstructured documents \((D_1, \dots, D_n)\), where \(D_i\) is a subset of keywords from a keyword space \(\mathbb{W}\), and supports keyword search. In other words, given a keyword \(w\) from the keyword space, return all the documents that contain \(w\).
Snapshot adversaries: a single-snapshot adversary is an adversary that tries to recover information about the client’s queries and/or data from the encrypted data structure. Notice that a snapshot adversary does not have access to the transcripts of operations, which makes it weaker than a persistent adversary. A multi-snapshot adversary is a adversary that has access to the encrypted structure after every operation. A multi-snapshot adversary is stronger than a single-snapshot adversary.
Structured Encryption (STE): an encryption scheme that encrypts a data structure in such a way that it can be queried and updated efficiently. STE schemes produce encrypted structures. Examples of STE schemes include dictionary encryption schemes which encrypt dictionaries, multi-map encryption schemes which encrypt multi-maps and graph encryption schemes which encrypt graphs.
Token: some encrypted structures have query and update operations that require a single round of communication and some have operations that require multiple rounds. If an encrypted structure has a single-round operation, we usually refer to the message sent by the client to the server as a token. Intuitively speaking, a token can be thought of as an encrypted form of the operation.
Volume: a leakage pattern that reveals the size of a query’s response. The exact definition of size varies depending on the structure being studied. For example, for an EMM it might be the number of elements in the returned tuple.

Related Posts