Searchable Encryption: SSE and PEKS

The Problem of Searching Encrypted Data

Searchable encryption (Searchable Encryption, or SE) — a class of cryptographic encryption algorithms that make it possible to search encrypted data (files, database records, etc.). Its area of application is providing privacy for data stored on an untrusted remote resource .

In general, such encryption can be based on either symmetric or asymmetric ciphers. However, since practical tasks involve encrypting large volumes of data, symmetric searchable encryption is more common (accordingly, Searchable Symmetric Encryption, abbreviated SSE). Most asymmetric approaches are based on public-key encryption with keyword search (Public Key Encryption with Keyword Search, abbreviated PEKS)

Encryption — the reversible transformation of information in order to conceal it from unauthorized persons, while at the same time granting authorized users access to it. Primarily, encryption serves the purpose of preserving the confidentiality of transmitted information. An important feature of any encryption algorithm is the use of a key, which fixes the choice of a specific transformation from among those possible for the given algorithm. Within this article we will consider data obtained as a result of encryption.

Homomorphic encryption — a form of encryption that makes it possible to perform certain mathematical operations on ciphertext and obtain an encrypted result that corresponds to the result of the operations performed on the plaintext.

Partially homomorphic cryptosystems — cryptosystems that are homomorphic with respect to only one operation (either addition or multiplication). Fully homomorphic cryptosystems are homomorphic with respect to several operations.

Data search — a branch of computer science studying algorithms for finding and processing information in both structured (see e.g. databases) and unstructured (e.g. a text document) data. In general, search means investigating something with the aim of finding a non-obvious, lost, or hidden part. Data search is usually associated with processing some data store that cannot be read or comprehended sequentially, with the aim of finding the subset of that data of interest to whoever set the task (or establishing its absence). Efficient search algorithms existed long before the advent of computers and were used, for example, to find books in libraries. There is also uninformed data search, where algorithms can process any data regardless of its nature, such as bitwise search.

The relevance of the problem of searching for occurrences in encrypted data is driven by the rapid growth of the cloud storage market, whereas at present no protocols exist for the secure processing of data on the cloud server side, since processing data in encrypted form requires either handing the server the secret key or downloading the entire database every time. Solving the problem of searching for occurrences over encrypted data will make it possible to safely store data outside the trusted zone.

History

The idea of searching over ciphertext became relevant against the backdrop of the emergence of cloud data storage. Users' data is stored on remote resources that may be untrusted (or “semi-trusted” ). To ensure privacy in this case, encryption is applied to the data . However, with ordinary encryption, in order to search this data the user would either have to download the entire dataset and decrypt it, or else give the server the means to decrypt it, which contradicts the original purpose of encryption .

The first attempts to ensure user privacy when working with a server can be considered the 1990s work on oRAM, in which the memory access pattern was hidden from the server while processing a user's request .

The first work in the direction of searching encrypted data was published in 2000 by Dawn Xiaodong Song, David Wagner, and Adrian Perrig. Their algorithm performed exact-match search over ciphertext .

Whereas the SWP00 algorithm built an encryption method in which the search is performed over the ciphertext itself, most later implementations involve building an encrypted index , over which search takes less time , allows data on the server to be updated (dynamic SSE) , or allows extended search to be used ^[10]. The cost of this is an increase in the size of the encrypted data and a higher risk of leaks.

In a 2003 paper by Eu-Jin Goh , search over an encrypted index was proposed for the first time, based on exact-match search. And in 2009, a paper by Emily Shen, Elaine Shi, and Brent Waters — private predicate search^[10].

In the PEKS direction, the first result was presented in a 2004 paper authored by Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano .

Initially, when checking new algorithms for security, only the general requirements for cryptographic systems were verified. Definitions of cryptographic strength for SE that account for the specific features of possible new kinds of leaks were given in a 2006 paper by Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky .

The ability to search implies the possible presence of information leakage with every search query^[11]. These leaks can stem from the deterministic nature of encryption steps, restrictions on the input data, and so on. Using oRAM to hide the server's operation and reduce leakage was considered as a possible solution^[11], but this method has also been criticized^[12].

Description of the Principle

To meet the need for search, the first algorithm proposed was the Song-Wagner-Perrig algorithm, in which the user makes search queries to a file server holding encrypted data, without revealing to it either the contents of the files or the search query itself. The encryption consists of performing a reversible operation (e.g., XOR) with a pseudorandom sequence, and the key is, correspondingly, the seed of the PRNG. Such a scheme performs search in time linear in the size of the ciphertext, and its reliability depends on the quality of the pseudorandom sequence and of the pre-encryption .

Besides methods based on symmetric encryption, algorithms using a public key also have their place. For example, emails can be encrypted for the recipient with their public key. The recipient may wish to store them on a remote mail server while retaining the ability to search. Alternatively, a scheme may be designed so that from the encrypted message the mail server can tell that it contains, for example, the keyword (“urgent”) and route the message or set its forwarding priority accordingly, without learning anything beyond that word ^[13].

Classification

SE is based on the presence of a client-server architecture. As a result, different approaches to building algorithms can differ in the number of clients that have access to the data. There may be one or several clients with the right to place data on the server (writers), and one or several clients with the right to perform search (readers). Thus, four classes of algorithms can be distinguished :

• one writer/one reader (S/S)
• one writer/many readers (S/M)
• many writers/one reader (M/S)
• many writers/many readers (M/M)

Class S/S mostly covers symmetric encryption algorithms, since the owner of the information will keep a single key. Algorithms of class M/S assume the presence of multiple clients encrypting data for a single recipient. This is how, for instance, encrypted email systems are arranged. It is worth noting that algorithms of this class can be trivially turned into S/S algorithms if the reading client does not distribute the public key .

A 2016 survey paper provides statistics on the amount of research in the various SE classes:

Example (the SWP00 Algorithm)

The Song-Wagner-Perrig algorithm was proposed in a 2000 paper and is a form of symmetric searchable encryption . It runs in time linear in the size of the data being encrypted and uses fundamental cryptographic primitives, which makes it convenient to examine .

Basic Idea

The basic idea can be illustrated with the following example, in which only the ability to search is provided, at the cost of some privacy.

Suppose the user Alice wants to encrypt a document made up of the words . Her goal — to perform a reversible XOR operation on each of the words with some secret value .

For this she will need :

• a pseudorandom generator G with seed k, used to create the sequence S, where k is part of her secret key

• a pseudorandom function F with keys , needed to expand the elements of the sequence S to the length of the words (it returns m-bit values)

• a pseudorandom function f with key , for generating the keys

• a pseudorandom permutation E with key , for pre-encryption

The encryption algorithm :

1. First Alice generates the sequence .
2. To encrypt the next word of length n bits located at position i, an of length n-m bits is generated.
3. is computed as the concatenation of and
   .
4. The result of encryption is .

Here the sequence of keys can be chosen in different ways (for example, using the same key or some fixed set of keys) .

A scheme built this way allows a search over the ciphertext to be carried out as follows :

Suppose Alice's encrypted document is stored with Bob. Alice wants to find the word W, so she sends it together with the set of keys for the positions i at which W might occur. Bob then checks whether the sum modulo of the next encrypted word can be represented together with the sample in the form :

If this condition is satisfied, Alice is returned confirmation of the match and the position i. If, however, a key was not sent for some position, Bob learns nothing about that word .

Such a search algorithm has linear complexity. The drawbacks of the basic scheme are that Bob knows the contents of the query, and upon a successful search he learns the contents of both the document itself and the keys used for encryption .

Hiding the Keys

To increase the flexibility of search and the privacy of the encrypted data, an additional generator can be used for the keys, with its own separate key. Then for each word, and instead of disclosing the whole group of keys, Alice will attach to the search query only the one needed .

Hiding the Plaintext

So that Bob does not gain access to the plaintext data, it should be pre-encrypted. That is, one should first obtain a pre-encrypted document from , where . It is worth noting that the encryption E must not depend on the position of the word (identical words in different parts of the document would otherwise produce identical ciphertext) .

To search, Alice sends Bob the encrypted word and the key to it, . Bob can then perform the search without having access to the plaintext .

However, this scheme reveals a new drawback. From the ciphertext alone, Alice will not be able to recover the original text if she does not know what it was. That is, she needs to know (or at least the last m bits) so that, from , she can restore .

Final Version

The final form of the Song-Wagner-Perrig algorithm looks as follows :

1. The word undergoes pre-encryption: .
2. is split into two parts — of length n-m bits and of length m bits.
3. From the key is generated.
4. With generator G and key k, an (n-m)-bit term of the sequence is generated.
5. is expanded to the n-bit .
6. Finally the ciphertext is computed as .

The search on Bob's side proceeds as described earlier, using .

In this scheme, Alice (or anyone else) can decrypt the data given the keys and and knowing the position of the word, i. To do this :

1. Using the seed k, Alice obtains the element .
2. is taken as addition modulo 2 of the high-order n-m bits of with .
3. is reconstructed.
4. The original text is found as .

Cryptographic Constructions

Song's Scheme

In 2000, Song published the paper “Practical Techniques for Searches on Encrypted Data” , in which the authors presented a set of algorithms for searching encrypted data. The search complexity of the algorithms presented was linear, O(n), for each encrypted document .

Fig. 1. The encryption algorithm in Song's scheme

Encryption Algorithm

• The input is a document, which is split into words according to a predefined criterion (usually the split is by the spacing between words), and all unique sequences are removed.
• From a single master key supplied by the user (MK), three subkeys are created, used in different parts of the algorithm and preventing the server from decrypting the data.
• Then each word is encrypted with a standard block algorithm , split into two unequal parts (depending on the user-defined parameter for the length of the left part of the encrypted message x , ), additionally processed as , where and the resulting values are combined together (an exclusive-or operation is performed), thereby forming the ciphertext , .

Search Algorithm

• For the search operation, the keyword must be encrypted according to the encryption algorithm and passed to the server side .
• After that, the server begins processing each stored encrypted record , obtaining as output a pair of values .
• And, since the length of the original stream cipher is known, namely x , from the resulting pair we can obtain the string Si.
• In the end we must compare the result of the function with the remaining bits .

The computational complexity of the deterministic keyword-search algorithm over encrypted data presented here grows exponentially as the input data grows, which explains its impracticality.

Comparison of the Main Schemes for Searching Encrypted Data

Features of existing systems for searching encrypted data

Capabilities for performing various kinds of search over encrypted data

A detailed description of the other developed search schemes shown in the comparison is not given, since none of them finds occurrences within encrypted data, but only performs keyword search on exact match .

The Scheme Presented by Fujitsu Laboratories

Specialists at Fujitsu's research division have developed a method for substring search over encrypted text that requires neither decrypting it nor pre-compiling a dictionary of keywords .

This method is based on the use of homomorphic encryption, thanks to which matching against a key string is carried out directly on the encrypted data, and there is no need to pre-include keywords in a dictionary. Earlier methods only allowed searching for the occurrence of a single string at a time. The method developed by Fujitsu Laboratories uses a batch search technique, which significantly increases the speed of data processing.

Fig. 2. Fujitsu Laboratories' batch search mode

Fig. 3. Search speed

Solutions to the Problem of Searching Encrypted Data

The CryptDB DBMS

In 2011, researchers from the Massachusetts Institute of Technology presented the CryptDB project, an attempt to solve the problem of securely storing data in databases hosted in cloud services and other systems outside the owner's control. The main problem with storing important information in an uncontrolled DBMS is the possibility of data leakage through a breach of the service or through unlawful actions by administrators. To address this problem, CryptDB provides encryption support such that data on the DBMS side never appears in the clear, and all queries sent to the DBMS contain only encrypted data, including within conditional clauses.

When using CryptDB, in the course of executing SQL queries all operations are performed only on encrypted data, i.e. a user can send an SQL query to the DBMS and obtain a result without the information being decrypted on the server side (the data is decrypted on the client's equipment). To preserve the confidentiality of the information, a multi-level encryption scheme is used, in which different data are placed on different nested cryptographic levels, each level having its own key and supporting a limited set of the simplest operations on encrypted data. To hide the data at each level, its own homomorphic encryption methods are used, in which the data is irreversibly transformed, but it remains possible to perform certain mathematical operations that give results analogous to the operations on the original data (encrypted data can be used for comparison, sorting, addition, etc. without prior decryption; for example, the condition decrypt(crypt(A) + crypt(B)) = A + B holds).

CrypDB Architecture

Microsoft Cipherbase

Cipherbase — a relational database that uses the latest specially configured hardware for storing and processing data in encrypted form. Cipherbase is an add-on for Microsoft SQL Server, developed specifically for organizations that provide database services and are concerned about data security, including from dishonest database administrators .

Cipherbase Architecture

The MRSE System

MRSE — a system for searching encrypted data that efficiently processes many queries at once without decrypting the data and while preserving its confidentiality. The system is based on partially homomorphic encryption .

The MRSE Model

Applications

Before it was shut down, Google Desktop was expected to become a prime example of the use of SSE .

However, at present, implementations of the algorithms (for example, the open-source implementation OpenSSE) are more research-oriented than practical in nature

See Also

• Cipher
• Encryption
• Homomorphic encryption
• Data search
• Database
• [[b6236]]
• Song's scheme
• Partially homomorphic encryption

See also

• Data analysis Data indexing and query processing.