Order-revealing encryption (ORE) is a cryptographic primitive that enables ciphertext comparison while leaking nothing about the underlying plaintext beyond their lexicographic ordering. However, how to achieve efficient and secure ciphertext comparison for multi-user settings is still a challenging problem. In this work, we propose an efficient multi-client order-revealing encryption scheme (namedm-ORE) by introducing a new token-based comparison method. Specifically, data owner is enabled to delegate token generation ability to some authorized users without revealing his secret key, and then each authorized user can perform comparison on ciphertexts from multiple data owners by generating the associated comparison tokens. Benefiting from our new method,m-ORE can not only reduce ciphertext size but also improve comparison efficiency, compared with the state-of-the-art (Cash et al. Asiacrypt 2018). Further, we present a non-interactive multi-client range query scheme by extendingm-ORE. Finally, we show a formal security analysis and implement our scheme. The evaluation result demonstrates thatm-ORE outperforms the scheme by Cash et al. in terms of both query and storage cost while achieving the same level of security.

1. 1.

   https://github.com/kevinlewi/fastore.

2. 2.

   https://github.com/collisionl/m-ORE.

This work was supported by the National Natural Science Foundation of China (Nos. 62072357 and 61960206014), the Preferential Funding for Scientific and Technological Activities of Overseas Students in Shaanxi Province (No. 2019-25), the Fundamental Research Funds for the Central Universities (No. JB211503), and Innovation Fund of Xidian University (No. YJS2114).

Authors and Affiliations

1. State Key Laboratory of Integrated Service Networks (ISN), Xidian University, Xi’an, 710071, China

   Chunyang Lv, Jianfeng Wang & Xiaofeng Chen

2. State Key Laboratory of Cryptology, P. O. Box 5159, Beijing, 100878, China

   Chunyang Lv, Jianfeng Wang & Xiaofeng Chen

3. Shanghai Jiao Tong University, Shanghai, 200240, China

   Shi-Feng Sun

4. School of Cyberspace Security, Xi’an University of Posts and Telecommunications, Xi’an, 710121, China

   Yunling Wang

5. School of Computer Science and Technology, Xi’an Jiaotong University, Xi’an, 710049, China

   Saiyu Qi

Corresponding authors

Correspondence toJianfeng Wang orXiaofeng Chen.

Editors and Affiliations

1. Purdue University, West Lafayette, IN, USA

   Elisa Bertino

2. National Research Center for Applied Cybersecurity ATHENE, Fraunhofer Institute for Secure Information Technology SIT, Darmstadt, Germany

   Haya Shulman

3. National Research Center for Applied Cybersecurity ATHENE, Technische Universität Darmstadt, Fraunhofer Institute for Secure Information Technology SIT, Darmstadt, Germany

   Michael Waidner

Appendix

A Security Analysis of Range Query Scheme

To define the security of multi-client range query scheme in Sect. 5.1, we first introduce a slight modification to the security notions that by ourm-ORE scheme from Sect. 4. Recall that anm-ORE scheme is secure with respect to a leakage profile\(\mathcal {L}_f(\cdot )\) if for any adversarially-chosen sequence of messages\((m_1,\cdots ,m_q)\), there is an efficient simulator\(\mathcal {S}\) that can simulate the realm-ORE ciphertext and token given the leakage\(\mathcal {L}_f(m_1,\cdots ,m_q)\).

Similar to [16], we define a leakage function\(\mathcal {L}_f(\cdot ,\cdot )\) that if there exists an efficient simulator such that for any two adversarially-chosen collections of plaintexts\((m_1,\cdots ,m_q)\) and\((m_1,\cdots ,m_k)\), the simulator can simulate the outputs of\(\textsf {m-ORE.Enc}(\cdot ,m_i)\) and\(\textsf {m-ORE.TGen}(\cdot ,m_j)\) for all\(i\in [q], j\in [k]\) given only the leakage\(\mathcal {L}_f((m_1,\cdots ,m_q),\)\((m_1,\cdots ,m_k))\). That is:

in which\(q=k\). We argue that this leakage profile is essentially the same as\(\mathcal {L}_f(m_1,\cdots ,m_q)\).

We then define the security of our range query scheme\(\varSigma \) in two different aspects, online and offline security. Online security models the information revealed to a malicious server duringUpdate andSearch, while offline security considers the situation of an adversary obtains a one-time snapshot of the encrypted database from the server which was studied by Naveed et al. [19] and Grubbs et al. [13]. First, we formalize the online security as follows:

Theorem 3

For a database\(\mathbf{DB} _i\) containing useri’s data which is essentially a set ofm-ORE ciphertext\((c_1,\cdots ,c_q)\) on the server and a sequence of queries\(\mathbf{q} _i\) from useri which is a set ofm-ORE token\((t_1,\cdots ,t_k)\). Let\(\mathcal {L}_{RQ}\) be the leakage function.

We say that the range query scheme\(\varSigma \) achieves online security with respect to the leakage function\(\mathcal {L}_{RQ}\).

Proof

The proof follows the proof of Theorem 2 except the leakage profile were substituted by\(\mathcal {L}_f((m_1,\cdots ,m_q),(m_1,\cdots ,m_k))\) which is very similar. And the simulator\(\mathcal {S}\) only needs to output the ciphertexts for\(m_i\) where\(\forall i\in [q]\) and token for\(m_j\) where\(\forall j\in [k]\).

Note that we define the leakage function\(\mathcal {L}_{RQ}\) under a condition that\(\mathbf{DB} \) and\(\mathbf{q} \) are from the same user. It is clear that the leakage will be none if these are from different users. The reason is thatm-ORE.Cmp will not work in this case and\(\textsf {msdb}(m_j,m_i)=\textsf {msdb}(m_j,m_l)\) will always hold for alli andj.

The offline security of our range query scheme follows directly from the fact that the encrypted database stored on the server only contains a collection group elements from\(\mathbb {G}_1\) and were generated with random factor, which is simulatable given just the size of the collection.

Theorem 4

The range query scheme\(\varSigma \) is offline secure.

Proof

The proof follows the proof of Theorem 2 except the simulator\(\mathcal {S}\) only needs to simulate the ciphertext for all the messages.

Reprints and permissions

© 2021 Springer Nature Switzerland AG

Policies and ethics