Order-preserving encryption
An order-preserving encryption (OPE) scheme is a deterministic symmetric encryption scheme on an ordered plaintext space whose encryption function, under every key, is strictly increasing, so that the order of two plaintexts can be read off their ciphertexts. Security asks that encryption be indistinguishable from a uniformly random order-preserving function — BCLO09.
Syntax
For integers , write . An OPE scheme is a tuple of efficient algorithms with plaintext space and ciphertext space — BCLO09:
- , a randomized algorithm outputting a key .
- , a deterministic algorithm mapping to .
- , a deterministic algorithm outputting or .
Properties
Correctness and order preservation
An OPE scheme is correct if for every , every key output by and every , and order-preserving if for every such and all ,
Each is then an order-preserving injection . Write for the set of all such injections; each is determined by its image, so — standard.
IND-OCPA security
The adversary queries pairs of plaintexts to a left-right oracle that encrypts one side of each pair. An admissible adversary makes queries in the same relative order on both sides, for all ; without this restriction the order of two ciphertexts reveals — BCLO09.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{ind\text{-}ocpa}}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $K \gets \KeyGen(1^\secpar)$; $b \getsr \bits$
\State $\calO_0(m_0, m_1) := \Enc(K, m_0)$
\State $\calO_1(m_0, m_1) := \Enc(K, m_1)$
\Comment{All queries have the same relative order on both sides}
\State $b' \gets \calA^{\calO_b}(1^\secpar)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
An OPE scheme is IND-OCPA-secure if for all efficient admissible ,
is negligible. IND-OCPA leaks only equality and order among the queried plaintexts, which every order-preserving deterministic scheme reveals. No OPE scheme with a ciphertext space of practical size achieves it: IND-OCPA security forces to be exponential in — BCLO09.
POPF-CCA security
The adversary has encryption and decryption oracles, which in world run the scheme and in world evaluate a uniformly random order-preserving injection and its inverse, with for outside the image of — BCLO09.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{popf\text{-}cca}}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $K \gets \KeyGen(1^\secpar)$; $g \getsr \mathrm{OPF}_{M,N}$; $b \getsr \bits$
\State $\calO_0(m) := \Enc(K, m)$; $\calD_0(c) := \Dec(K, c)$
\State $\calO_1(m) := g(m)$; $\calD_1(c) := g^{-1}(c)$
\Comment{$g$ can be sampled lazily}
\State $b' \gets \calA^{\calO_b, \calD_b}(1^\secpar)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
An OPE scheme is POPF-CCA-secure if for all efficient ,
is negligible. As an object, OPE denotes, for all and computable in time with and , a correct, order-preserving and POPF-CCA-secure scheme with plaintext space and ciphertext space . A uniformly random is sampled lazily by binary search over : the number of plaintexts that maps into follows a hypergeometric distribution — BCLO09.
Variations
Order-revealing encryption
An order-revealing encryption (ORE) scheme drops the requirement that ciphertexts be ordered integers and compares them with a public algorithm instead — BLR+15. For every computable in time , an ORE scheme on is a tuple of efficient algorithms — CLWW16:
- , a randomized algorithm outputting a secret key.
- , a possibly randomized algorithm encrypting , read as an integer.
- , a deterministic algorithm that uses no key.
is correct if for all , except with negligible probability over and . An OPE scheme, with comparing ciphertexts as integers, is an ORE scheme — standard.
Security is relative to a leakage function of the sequence of queried plaintexts: in world a stateful simulator produces each ciphertext from the leakage of the queries so far — CLWW16.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{ore}}_{\Pi,\calA,\Sim,\calL}(\secpar)$}
\begin{algorithmic}
\State $\sk \gets \KeyGen(1^\secpar)$; $\stS \gets \Sim(1^\secpar)$; $b \getsr \bits$
\State $\calO_0(m) := \Enc(\sk, m)$
\State $\calO_1(m) := \Sim(\stS, \calL(m_1, \ldots, m_i))$
\Comment{$m_1, \ldots, m_i$ are the queries so far, $m_i = m$; $\Sim$ updates $\stS$}
\State $b' \gets \calA^{\calO_b}(1^\secpar)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
An ORE scheme is -secure if for all efficient there is an efficient such that
is negligible. As objects, best-possible ORE and ORE leaking the first differing bit denote, for every such , a correct ORE scheme on that is -secure, respectively -secure, for the leakage functions defined below.
Best-possible security
reveals the order of every pair of ciphertexts, so the least possible leakage is , and an -secure scheme has best-possible security. BLR+15 construct ORE that reveals only this order from multilinear maps, with security proved in a generic model of multilinear maps — BLR+15.
Leakage of the first differing bit
For , let be the least index with , counting from the most significant bit, and if . The leakage
adds the position of the first differing bit to the order — CLWW16. Since is a component of , best-possible security implies -security (Best-possible ORE ⇒ ORE leaking the first differing bit) — folklore. Any PRF yields an -secure ORE scheme (PRF ⇒ ORE) — CLWW16.
Mutable order-preserving encoding
In mutable OPE (mOPE), the client and server run an interactive protocol in which the server stores an order-preserving encoding of the encrypted values, and inserting a value may change the encodings of values inserted earlier; mOPE achieves IND-OCPA, which stateless OPE does not — PLZ13.
Modular OPE
Modular OPE prepends a secret shift modulo to an OPE scheme, so that the joint distribution of the ciphertexts is unchanged when all plaintexts are shifted by a common offset modulo ; in particular a single ciphertext reveals no information about the location of its plaintext in — BCO11.
Other results
- Given an efficient sampler for the hypergeometric distribution, any PRF yields a POPF-CCA-secure OPE (PRF ⇒ OPE) — BCLO09.
- For uniformly distributed plaintexts and suitable parameters, encryption under a uniformly random order-preserving function hides the exact value of each plaintext and the exact distance between two plaintexts, but reveals both to within a range of size roughly — BCO11.
- Against database columns encrypted under deterministic or order-preserving encryption, auxiliary data on the plaintext distribution recovers a large fraction of the plaintexts: frequency analysis and -optimization attack deterministic encryption, and the sorting and cumulative attacks attack OPE; the sorting attack recovers every plaintext of a dense column, in which every value of the domain occurs — NKW15.
Participates in
Builds on Order-preserving encryption
Produces Order-preserving encryption