Post-quantum Multi-client Conjunctive Searchable Symmetric Encryption from Isogenies

Sikhar Patranabis ORCID: orcid.org/0000-0002-2309-7939¹⁰

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 15351))

Included in the following conference series:

International Conference on Security, Privacy, and Applied Cryptography Engineering

53 Accesses

Abstract

Multi-client searchable symmetric encryption (SSE) allows multiple third-party clients to execute fast encrypted search queries over a symmetrically encrypted database created by a data owner and held by an (untrusted) data server. Although SSE is ostensibly a symmetric-key cryptoprimitive, existing multi-client SSE schemes that support conjunctive and general Boolean queries rely crucially on the classical hardness of the discrete log problem over cyclic groups, and are completely broken by quantum attacks. This leaves open the question of designing multi-client conjunctive (and more expressive) SSE schemes from plausibly quantum-safe assumptions.

In this paper, we present the first plausibly quantum-safe multi-client SSE scheme supporting conjunctive keyword queries while relying on the hardness of certain isogeny-based assumptions (such as CSIDH and CSI-FiSh) that can be modeled using cryptographic group actions. As a core technical contribution, we present a novel adaptation of the widely studied but quantum-broken Oblivious Cross-Tags ($\textsf{OXT}$) protocol (Cash et al., Crypto 2013) to the setting of cryptographic group actions. This scheme, which we call $\textsf{GXT}$, supports conjunctive keyword queries in the single-client setting. We then present $\mathsf {MC\text {-}GXT}$ – an extension of $\textsf{GXT}$ to the multi-client setting. Our constructions match the asymptotic efficiency guarantees of the original $\textsf{OXT}$ scheme in terms of storage requirements and conjunctive query complexity, while additionally providing data and query privacy guarantees based on well-studied and plausibly quantum-safe isogeny-based hardness assumptions.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic

£29.99 /Month

Get 10 units per month
Download Article/Chapter or eBook
1 Unit = 1 Article or 1 Chapter
Cancel anytime

Buy Now

Chapter: GBP 19.95; Price includes VAT (United Kingdom)

eBook: GBP 49.99; Price includes VAT (United Kingdom)

Softcover Book: GBP 59.99; Price includes VAT (United Kingdom)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

1.
Note that a function $f:{\mathbb N}\rightarrow {\mathbb R}$ is said to be negligible in $\lambda $ if for every positive polynomial p, $f(\lambda )<1/p(\lambda )$ when $\lambda $ is sufficiently large.
2.
In this paper, we consider conjunctive keyword queries where $\bar{w} = (w_1,\ldots ,w_\mu )$ is a conjunction over a collection of keywords.
3.
Note that if a query has $n' < n$ x-terms, it is padded by setting the last $(n-n')$ x-terms to the dummy symbol.
4.
Here, the eavesdropper $\textsf{E}$ could, for example, be the data server $\textsf{dS}$.

References

Alamati, N., De Feo, L., Montgomery, H., Patranabis, S.: Cryptographic group actions and applications. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part II. LNCS, vol. 12492, pp. 411–439. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-64834-3_14 December
Chapter Google Scholar
Beullens, W., Kleinjung, T., Vercauteren, F.: CSI-FiSh: efficient isogeny based signatures through class group computations. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part I. LNCS, vol. 11921, pp. 227–247. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-34578-5_9 December
Chapter Google Scholar
Boneh, D., Kogan, D., Woo, K.: Oblivious pseudorandom functions from isogenies. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part II. LNCS, vol. 12492, pp. 520–550. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-64834-3_18 December
Chapter Google Scholar
Brassard, G., Yung, M.: One-way group actions. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 94–107. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-38424-3_7
Chapter Google Scholar
Cash, D., et al.: Dynamic searchable encryption in very-large databases: Data structures and implementation. In: 21st Annual Network and Distributed System Security Symposium, NDSS 2014, San Diego, California, USA, 23–26 February 2014. The Internet Society (2014)
Google Scholar
Cash, D., Jarecki, S., Jutla, C.S., Krawczyk, H., Rosu, M.-C., Steiner, M.: Highly-scalable searchable symmetric encryption with support for Boolean queries. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 353–373. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_20 August
Chapter Google Scholar
Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: CSIDH: an efficient post-quantum commutative group action. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part III. LNCS, vol. 11274, pp. 395–427. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-030-03332-3_15 December
Chapter Google Scholar
Chang, Y.-C., Mitzenmacher, M.: Privacy preserving keyword searches on remote encrypted data. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 442–455. Springer, Heidelberg (2005). https://doi.org/10.1007/11496137_30 June
Chapter Google Scholar
Chase, M., Kamara, S.: Structured encryption and controlled disclosure. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 577–594. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_33 December
Chapter Google Scholar
Couveignes, J.-M.: Hard homogeneous spaces. Cryptology ePrint Archive, Report 2006/291 (2006). https://eprint.iacr.org/2006/291
Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. In: Juels, A., Wright, R.N., De Capitani di Vimercati, S. (eds.) ACM CCS 2006, pp. 79–88. ACM Press, October / November 2006
Google Scholar
De Feo, L., et al.: SCALLOP: scaling the CSI-FiSh. In: Boldyreva, A., Kolesnikov, V. (eds.) PKC 2023, Part I. LNCS, vol. 13940, pp. 345–375. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-31368-4_13
Chapter Google Scholar
Jarecki, S., Jutla, C.S., Krawczyk, H., Rosu, M.-C., Steiner M.: Outsourced symmetric private information retrieval. In: Sadeghi, A.-R., Gligor, V.D., Yung, M. (eds.) ACM CCS 2013, pp. 875–888. ACM Press, November 2013
Google Scholar
Jarecki, S., Kiayias, A., Krawczyk, H., Xu, J.: Highly-efficient and composable password-protected secret sharing (or: How to protect your bitcoin wallet online). In: IEEE European Symposium on Security and Privacy, EuroS &P 2016, Saarbrücken, Germany, 21–24 March 2016, pp. 276–291. IEEE (2016)
Google Scholar
Jarecki, S., Kiayias, A., Krawczyk, H., Xu, J.: TOPPSS: cost-minimal password-protected secret sharing based on threshold OPRF. In: Gollmann, D., Miyaji, A., Kikuchi, H. (eds.) ACNS 2017. LNCS, vol. 10355, pp. 39–58. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-61204-1_3
Chapter Google Scholar
Kamara, S., Moataz, T.: Boolean searchable symmetric encryption with worst-case sub-linear complexity. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, Part III, vol. 10212, pp. 94–124. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_4
Chapter Google Scholar
Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: Yu, T., Danezis, G., Gligor, V.D. (eds.) ACM CCS 2012, pp. 965–976. ACM Press, October 2012
Google Scholar
Lai, Y.-F., Galbraith, S.D., Delpech de Saint Guilhem, C.: Compact, efficient and UC-secure isogeny-based oblivious transfer. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021, Part I. LNCS, vol. 12696, pp. 213–241. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_8
Chapter Google Scholar
Moriya, T., Onuki, H., Takagi, T.: SiGamal: a supersingular isogeny-based PKE and its application to a PRF. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part II. LNCS, vol. 12492, pp. 551–580. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_19
Chapter Google Scholar
Naor, M., Pinkas, B., Reingold, O.: Distributed pseudo-random functions and KDCs. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 327–346. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_23
Chapter Google Scholar
Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. In: 38th FOCS, pp. 458–467. IEEE Computer Society Press, October 1997
Google Scholar
Page, A., Robert, D.: Introducing Clapoti(s): evaluating the isogeny class group action in polynomial time. IACR Cryptol. ePrint Arch., page 1766 (2023)
Google Scholar
Song, D.X., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: 2000 IEEE Symposium on Security and Privacy, pp. 44–55. IEEE Computer Society Press, May 2000
Google Scholar
Sun, S.-F., Liu, J.K., Sakzad, A., Steinfeld, R., Yuen, T.H.: An efficient non-interactive multi-client searchable encryption with support for Boolean queries. In: Askoxylakis, I., Ioannidis, S., Katsikas, S., Meadows, C. (eds.) ESORICS 2016, Part I. LNCS, vol. 9878, pp. 154–172. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45744-4_8
Chapter Google Scholar
Talapatra, D., Patranabis, S., Mukhopadhyay, D.: Conjunctive searchable symmetric encryption from hard lattices. In: IEEE EuroS &P 2023, pp. 958–978. IEEE (2023)
Google Scholar

Download references

Author information

Authors and Affiliations

IBM Research, Bangalore, India
Sikhar Patranabis

Authors

Sikhar Patranabis
View author publications
You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sikhar Patranabis .

Editor information

Editors and Affiliations

New York University Abu Dhabi, Abu Dhabi, Abu Dhabi, United Arab Emirates
Johann Knechtel
Indian Institute of Technology Kanpur, Kanpur, Uttar Pradesh, India
Urbi Chatterjee
University of Florida, Gainesville, FL, USA
Domenic Forte

Appendices

Appendix

A Additional Preliminaries

In this section, we recall the definitions of some basic cryptographic primitives that we use in our constructions.

Definition 5

(Pseudorandom Function). A pseudorandom function (PRF) is a family of polynomial-time computable functions $F:\mathcal {K}\times \mathcal {X}\rightarrow \mathcal {Y}$ (where the sets $(\mathcal {K},\mathcal {X},\mathcal {Y})$ are all parameterized by the security parameter $\lambda \in \mathbb {N}$, and where each function $F(\textsf{sk},\cdot )$ is indexed by some key $\textsf{sk}\in \mathcal {K}$), such that for any PPT adversary $\mathcal {A}$, any random key $\textsf{sk}\leftarrow \mathcal {K}$ and any function $f \leftarrow \textsf{Funcs}(\mathcal {X}, \mathcal {Y})$ sampled randomly from the set of all functions with domain $\mathcal {X}$ and range $\mathcal {Y}$, we have

$$\begin{aligned} \left| \Pr \left[ \mathcal {A}^{F(\textsf{sk}, \cdot )}(1^{\lambda }) = 1\right] - \Pr \left[ \mathcal {A}^{f(\cdot )}(1^{\lambda }) = 1\right] \right| \le \textsf{negl}(\lambda ). \end{aligned}$$

Definition 6

(Symmetric-Key Encryption). A symmetric-key encryption scheme $\textsf{SKE}$ is a tuple of polynomial-time algorithms $(\textsf{KeyGen}, \textsf{Enc}, \textsf{Dec})$ described as follows:

$\bullet $:: $\textsf{sk}\leftarrow \textsf{KeyGen}(1^{\lambda })$: a randomized algorithm that takes as input the security parameter $\lambda $ and outputs a secret key $\textsf{sk}$.
$\bullet $:: $c \leftarrow \textsf{Enc}(\textsf{sk}, m)$: a randomized algorithm that takes as input $\textsf{sk}$ and a message $m\in \{0,1\}^*$, and generates a ciphertext c.
$\bullet $:: $m = \textsf{Dec}(\textsf{sk}, c)$: a deterministic algorithm that, on input the secret key K and a ciphertext c, outputs a message m.

We require a symmetric-key encryption scheme $\textsf{SKE}$ to satisfy correctness and IND-CPA security as described below.

Correctness. We say that a symmetric-key encryption scheme $\textsf{SKE}= (\textsf{KeyGen}, \textsf{Enc}, \textsf{Dec})$ is correct if for any security parameter $\lambda \in {\mathbb N}$, any $\textsf{sk}\leftarrow \textsf{KeyGen}(1^{\lambda })$, and any $m \in \{0,1\}^*$, we have $\textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{sk}, m)) = m$.

IND-CPA Security. We first define the IND-CPA security game below.

$\underline{\textsf{Game}^{\textsf{SKE}, \mathsf {IND-CPA}}_{\mathcal {A}= (\mathcal {A}_1,\mathcal {A}_2)}}$

1.
$\textsf{sk}\leftarrow \textsf{KeyGen}(1^{\lambda })$.
2.
$(\textsf{st}, m_0, m_1) \leftarrow \mathcal {A}_1^{\textsf{Enc}(K,\cdot )}(1^{\lambda })$.
3.
Sample $b \leftarrow \{0,1\}$.
4.
$c_b \leftarrow \textsf{Enc}(K, m_b)$.
5.
$b' \leftarrow \mathcal {A}_2^{\textsf{Enc}(K,\cdot )}(\textsf{st}, c_b)$.
6.
If $b'=b$, output 1, else output 0.

We say that a symmetric-key encryption scheme $\textsf{SKE}= (\textsf{KeyGen}, \textsf{Enc}, \textsf{Dec})$ is IND-CPA secure if for any security parameter $\lambda $ and any probabilistic polynomial-time (PPT) adversary $\mathcal {A}= (\mathcal {A}_1, \mathcal {A}_2)$, we have

$$\begin{aligned} \left| \Pr \left[ \textsf{Game}^{\textsf{SKE},\mathsf {IND-CPA}}_{\mathcal {A}} = 0\right] -\Pr \left[ \textsf{Game}^{\textsf{SKE},\mathsf {IND-CPA}}_{\mathcal {A}} = 1\right] \right| \le {\textsf{negl}}(\lambda ). \end{aligned}$$

B Detailed Security Definition of Oblivious PRF

In this section, we present a detailed simulation based security definition for $\textsf{OPRF}$. We adopt the standard real world-ideal world paradigm for our simulation based definition. We formally define the corresponding real and ideal world executions below.

The Real World Execution. We formally define a real world game $\textsf{Real}_{\mathcal {A},\mathcal {E}}^{\textsf{OPRF}}$ that is parameterized by a security parameter $\lambda $, and involves the following parties:

The honest party (either the client holding the input or the server holding the key).
An adversary $\mathcal {A}$ that controls the corrupt party (either a maliciously corrupt client or a maliciously corrupt server), and interacts with the honest parties and the environment $\mathcal {E}$.
The environment $\mathcal {E}$ that provides the honest party with its input, interacts with $\mathcal {A}$, receives the output of the honest party, and eventually outputs a bit $b\in \{0,1\}$.

Finally, the game $\textsf{Real}_{\mathcal {A},\mathcal {E}}^{\textsf{OPRF}}$ outputs the same bit as $\mathcal {E}$.

The Ideal World Execution. We next define an ideal world game $\textsf{Ideal}_{\textsf{Sim}, \mathcal {E}}^{\mathcal {F}_\textsf{OPRF}}$ that is again parameterized by $\lambda $, and involves the following parties interacting with the ideal functionality $\mathcal {F}_\textsf{OPRF}$ (described in Fig. 13, and also detailed subsequently).

The honest party (either the client holding the input or the server holding the key) that receives its input from the environment $\mathcal {E}$ and directly forward this input to $\mathcal {F}_\textsf{OPRF}$.
An ideal-world simulator $\textsf{Sim}$ that sends inputs to $\mathcal {F}_\textsf{OPRF}$ on behalf of the corrupt party (either a maliciously corrupt client or a passively corrupt server), and receives back the corresponding output from $\mathcal {F}_\textsf{OPRF}$. $\textsf{Sim}$ also interacts with the environment $\mathcal {E}$.
The environment $\mathcal {E}$ that provides the honest party with its input, and interacts with the simulator $\textsf{Sim}$. As in the real world, $\mathcal {E}$ also receives the outputs of the honest parties, and eventually outputs a bit $b\in \{0,1\}$.

Finally, the game $\textsf{Ideal}_{\textsf{Sim}, \mathcal {E}}^{\mathcal {F}_\textsf{OPRF}}$ outputs the same bit as $\mathcal {E}$.

The Ideal Functionality. The ideal functionality $\mathcal {F}_\textsf{OPRF}$ (described below) interacts with a set of clients $\{\textsf{C}\}$, a key-holding server $\textsf{S}$, and an ideal-world simulator $\textsf{Sim}$. We use $\textsf{sid}$ to denote a (unique) session id. For simplicity of exposition, we consider only one server $\textsf{S}$ per session id; however, multiple clients can submit evaluation requests in a given session. The ideal functionality keeps track of the following variables, all of which are initialized to $\bot $ or $\emptyset $ implicitly:

1.
$\textsf{TabInp}[\textsf{sid},x]$: contains a set of identities corresponding to clients that have issued the query $x\in \mathcal {X}$.
2.
$\textsf{TabEncInp}[\textsf{sid},x,\textsf{C}]$: contains a (randomized) encoding $x^*$ of the query x corresponding to the query issued by the client $\textsf{C}$.
3.
$\textsf{TabEval}[\textsf{sid},x]$: contains an output $y\in \mathcal {Y}$ corresponding to an input x. The uniqueness of y is defined naturally with respect to the tuple $(\textsf{sid},x)$ (this is essential for consistency).

Based on the above, we now formally define the security of a $\textsf{OPRF}$ scheme.

Definition 7

(Secure $\textsf{OPRF}$). We say that an $\textsf{OPRF}$ scheme securely realizes the ideal functionality $\textsf{Ideal}_{\textsf{Sim},\mathcal {E}}^{\mathcal {F}_\textsf{OPRF}}$ if for any security parameter $\lambda $ and any PPT adversary $\mathcal {A}$ in the real world, there exists a PPT simulator $\textsf{Sim}$ in the ideal world, such that for any environment $\mathcal {E}$, we have,

$$\begin{aligned} \begin{aligned} \bigg \vert \textsf{Pr}\bigg [\textsf{Real}_{\mathcal {A},\mathcal {E}}^\textsf{OPRF}(1^\lambda ) = 1\bigg ] -\textsf{Pr}\bigg [\textsf{Ideal}_{\textsf{Sim}, \mathcal {E}}^{\mathcal {F}_\textsf{OPRF}}(1^\lambda ) = 1\bigg ] \bigg \vert \le \textsf{negl}(\lambda ) \end{aligned} \end{aligned}$$

C Detailed Security Definition of Multi-client SSE

In this section, we present the detailed security definition of any multi-client SSE scheme $\mathsf {MC\text {-}SSE}$. The definition is divided into two parts: security of token generation and security of search.

1.1 C.1 Security of Token Generation

We first introduce a simulation-based security definition for token generation in $\mathsf {MC\text {-}SSE}$. We adopt the standard real world-ideal world paradigm, and formally define the corresponding real and ideal world executions for token generation below.

The Real World Execution. We first discuss the real-world execution $\textsf{Real}_{\mathcal {A},\mathcal {E}}^{\mathsf {MC\text {-}SSE},\textsf{Token}}$ of token generation in a $\mathsf {MC\text {-}SSE}$ scheme. Based on the syntax presented in Definition 3, we formally define a real world game $\textsf{Real}_{\mathcal {A},\mathcal {E}}^{\mathsf {MC\text {-}SSE},\textsf{Token}}$ that is parameterized by the security parameter $\lambda $, and involves the following parties: (i) a data owner (could be either honest or semi-honest), (ii) clients (could either be honest or maliciously corrupt), (iii) an adversary $\mathcal {A}$ that controls the corrupt parties, and (iv) the environment $\mathcal {E}$ that provides the honest parties with their inputs, interacts with $\mathcal {A}$, receives the outputs of the honest parties, and eventually outputs a bit $b\in \{0,1\}$. The game $\textsf{Real}_{\mathcal {A},\mathcal {E}}^{\mathsf {MC\text {-}SSE},\textsf{Token}}$ outputs the same bit.

The Ideal World Execution. We now define the ideal world game $\textsf{Ideal}_{\textsf{Sim},\mathcal {E}}^{\mathcal {F}_\textsf{Token}^\mathsf {MC\text {-}SSE}}$, that is again parameterized by $\lambda $, and consists of an ideal functionality $\mathcal {F}_\textsf{Token}^\mathsf {MC\text {-}SSE}$ (described in Fig. 4), as well as the following participants that interact with $\mathcal {F}_\textsf{Token}^\mathsf {MC\text {-}SSE}$: (i) the honest parties that receive their inputs from the environment $\mathcal {E}$ and directly forward these inputs to the ideal functionality $\mathcal {F}_\textsf{Token}^\mathsf {MC\text {-}SSE}$, (ii) an ideal-world simulator $\textsf{Sim}$ that sends inputs to $\mathcal {F}_\textsf{Token}^\mathsf {MC\text {-}SSE}$ on behalf of the corrupt parties and receives back the corresponding output from $\mathcal {F}_\textsf{Token}^\mathsf {MC\text {-}SSE}$, and (iii) the environment $\mathcal {E}$ that provides the honest parties with their inputs, and interacts with the simulator $\textsf{Sim}$. $\mathcal {E}$ receives the outputs of the honest parties, and eventually outputs a bit $b\in \{0,1\}$. The game $\textsf{Ideal}_{\textsf{Sim},\mathcal {E}}^{\mathcal {F}_\textsf{Token}^\mathsf {MC\text {-}SSE}}$ outputs the same bit.

The Ideal Functionality. We detail the ideal functionality $\mathcal {F}^\mathsf {MC\text {-}SSE}_\textsf{Token}$ in Fig. 4. The ideal functionality $\mathcal {F}_\textsf{Token}^\mathsf {MC\text {-}SSE}$ interacts with data owner $\textsf{D}$, clients $\textsf{C}$, data holding server $\textsf{dS}$, and a simulator $\textsf{Sim}$. The ideal functionality keeps track of the following variables, all of which are initialized to $\bot $ or $\emptyset $ implicitly (we use $\textsf{sid}$ to denote a (unique) session id):

1.
$\textsf{TabInp}[\textsf{sid},\bar{w}]$: contains a set of identities corresponding to clients that have issued the query $\bar{w}$.
2.
$\textsf{TabEncInp}[\textsf{sid},\bar{w},\textsf{C}]$: contains a (randomized) encoding y corresponding to the search query $\bar{w}$ corresponding to the query issued by the client $\textsf{C}$.
3.
$\textsf{TabToken}[\textsf{sid},\bar{w}]$: contains a search token $\textsf{stk}$ corresponding to an input search query $\bar{w}$. Uniqueness of $\textsf{stk}$ is defined naturally with respect to the tuple $(\textsf{sid},\bar{w})$.

Based on the above games and ideal functionality, we now formally define the security of token generation in $\mathsf {MC\text {-}SSE}$.

Definition 8

(Security of Token Generation in MC-SSE). We say that the real-world execution of token generation in a $\mathsf {MC\text {-}SSE}$ scheme securely emulates the ideal functionality $\mathcal {F}_\textsf{Token}^\mathsf {MC\text {-}SSE}$ if for any security parameter $\lambda $ and any malicious PPT adversary $\mathcal {A}$, there exists a PPT simulator $\textsf{Sim}$, such that for any environment $\mathcal {E}$, we have

$$\begin{aligned} \begin{aligned} \bigg \vert \textsf{Pr}\bigg [\textsf{Real}_{\mathcal {A},\mathcal {E}}^{\mathsf {MC\text {-}SSE},\textsf{Token}} (1^\lambda ) = 1\bigg ] -\textsf{Pr}\bigg [\textsf{Ideal}_{\textsf{Sim},\mathcal {E}}^{\mathcal {F}_\textsf{Token}^\mathsf {MC\text {-}SSE}}(1^\lambda ) = 1\bigg ] \bigg \vert \le \textsf{negl}(\lambda ). \end{aligned} \end{aligned}$$

1.2 C.2 Security of Search

We now present a notion of security of search in $\mathsf {MC\text {-}SSE}$ against a semi-honest data server in the standard real world/ideal world paradigm, where the real world and ideal world games are described formally described below. In the real world, the adversary’s view corresponds to real world executions of the various $\mathsf {MC\text {-}SSE}$ protocols, namely $(\textsf{Setup}, \textsf{Token}, \textsf{Search})$, corresponding to various queries issued (adaptively) by the adversary. In the ideal world, the view of the adversary is generated by a PPT simulator that does not have access to the actual queries issued by the adversary, but only has access to the leakage that the adversary was supposed to obtain when interacting with real-world executions of the $\mathsf {MC\text {-}SSE}$ protocols. For simulation-based security, we require the view of the adversary in the real and ideal worlds to be computationally indistinguishable. This is in-line with standard definitions of single-client SSE.

Leakage. We formally capture the leakage to the real-world adversary using a leakage function $\mathcal {L}=\left( \mathcal {L}_{\textsf{Setup}},\mathcal {L}_{\textsf{Search}}\right) $, with various sub-leakage components: (i) $\mathcal {L}_{\textsf{Setup}}$: a sub-functionality that captures any leakage about the plaintext database $\textsf{DB}$ that the data server obtains from the encrypted database $\textsf{EDB}$ generated by a real-world execution of the $\textsf{Setup}$ protocol of $\mathsf {MC\text {-}SSE}$, and (ii) $\mathcal {L}_{\textsf{Search}}$: a sub-functionality that captures any leakage about the plaintext database $\textsf{DB}$ and any leakage about an honest client’s keyword query, that is obtained by a (semi-honestly) corrupt data server during a real-world execution of the $\textsf{Search}$ protocol.

Now, we formally define the real world and ideal world games as follows.

Given the real world and ideal world games, and leakage functionality $\mathcal {L}$, we now formally describe the security of search in $\mathsf {MC\text {-}SSE}$.

Definition 9

(Security of Search in MC-SSE). We say that the real-world execution of the search protocol of any $\mathsf {MC\text {-}SSE}$ scheme $(\textsf{Setup}, \textsf{Token}, \textsf{Search})$ scheme satisfies $\mathcal {L}$-simulation security against a semi-honest data server if for any PPT adversary $\mathcal {A}$, there exists a PPT simulator $\textsf{Sim}$, such that,

$$\begin{aligned} \begin{aligned} \bigg \vert \textsf{Pr}\bigg [\textsf{Real}_{\mathcal {A}}^{\mathsf {MC\text {-}SSE},\textsf{Search}} (1^\lambda ) = 1\bigg ] -\textsf{Pr}\bigg [\textsf{Ideal}_{\mathcal {A}, \textsf{Sim}}^{\mathsf {MC\text {-}SSE},\textsf{Search}}(1^\lambda ,\mathcal {L}) = 1\bigg ] \bigg \vert \le \textsf{negl}(\lambda ) \end{aligned} \end{aligned}$$

D Proof of Theorem 2

We present a proof for the case of 2-conjunctive queries (i.e., where each query consists of one s-term and one x-term). The proof generalizes naturally to the more general case of $\mu $-conjunctions for any $\mu = \textsf{poly}(\lambda )$, and is not detailed separately.

1.1 D.1 Leakage of $\textsf{GXT}$ for 2-Conjunctive Queries

We recall the leakage function $\mathcal {L}^{\textsf{GXT}} =\left( \mathcal {L}^{\textsf{GXT}}_{\textsf{Setup}},\mathcal {L}^{\textsf{GXT}}_{\textsf{Search}}\right) $ for $\textsf{GXT}$ for the case of 2-conjunctive queries, where the various leakage sub-functions are as stated below:

$\mathcal {L}^{\textsf{GXT}}_\textsf{Setup}(\textsf{DB})$: The sub-leakage function $\mathcal {L}^{\textsf{GXT}}_\textsf{Setup}$, on input the plaintext database $\textsf{DB}= (\textsf{ind}_i,\textsf{W}_i)$, outputs the quantity $N = \sum _{w \in \textsf{W}} |\textsf{DB}(w)|$, where $\textsf{W}= \cup _i \textsf{W}_i$ is the set of all keywords in $\textsf{DB}$.
$\mathcal {L}^{\textsf{GXT}}_{\textsf{Search}}$: The sub-leakage function $\mathcal {L}^{\textsf{GXT}}_\textsf{Search}$ takes as input the plaintext database $\textsf{DB}$, and a list ${\textbf {Q }}$ of conjunctive search queries. Here, ${\textbf {Q }}$ is represented as ${\textbf {Q }}= (\textbf{s},\textbf{x})$, where $\textbf{s}$ denotes the list of s-terms for all queries, and $\textbf{x}_i$ denotes the list of x-terms for all queries. Q denotes the number of queries (i.e., $|\textbf{s}| = |\textbf{x}| = Q$). The sub-leakage function $\mathcal {L}^{\textsf{GXT}}_\textsf{Search}$ outputs the tuple $(\textsf{EP},\textsf{SP},\textsf{RP},\textsf{IP})$ (for 2-conjunctions, the leakage $\textsf{XP}$ is vacuous as each query has exactly one x-term), where in the case of 2-conjunctive queries, we have:
- $\textsf{EP}$ is the equality pattern indicating which pairs of queries have identical keywords as their s-terms. For ease of exposition, we use a slightly different interpretation of the equality pattern $\textsf{EP}$ as compared to the one stated in Theorem 2, but this interpretation is readily computable given the original interpretation from Theorem 2. Formally, we represent $\textsf{EP}\in [|\textsf{W}|]^Q$ as a table with entries in $[|\textsf{W}|]$, created by assigning each keyword an integer in $[|\textsf{W}|]$ determined by its order of appearance in $\textbf{s}$. For example, if $\textbf{s}= (w_1,w_1,w_2,w_3,w_1,w_3)$, then $\textsf{EP}= (1,1,2,3,1,3)$. To compute $\textsf{EP}[i]$, one finds the least $j\in [Q]$ such that $j\ge i$ and $\textbf{s}[j] = \textbf{s}[i]$ (observe that this is readily computable give the original interpretation of $\textsf{EP}$ from Theorem 2), and then lets $\textsf{EP}[i] = |\{\textbf{s}[1], \ldots , \textbf{s}[j]\}|$ to be the number of unique keywords appearing at indices less than or equal to j.
- $\textsf{SP}$ is the size pattern, i.e. the number of records matching the s-term in each query. Formally, we represent $\textsf{SP}$ as a Q-sized list, where for each $i\in [Q]$, we have $\textsf{SP}[i] = |\textsf{DB}(\textbf{s}[i])|$.
- $\textsf{RP}$ is the result pattern, i.e. the set of document identifiers matching each query. Formally, $\textsf{RP}$ is a Q-sized list, where for each $\ell \in [Q]$, we have $\textsf{RP}[\ell ] = \textsf{DB}(\textbf{s}[\ell ])\cap \left( \bigcap _{j\in [n]}\textsf{DB}(\textbf{x}_i[\ell ])\right) $.
- $\textsf{IP}$ is the conditional intersection pattern leakage, represented formally as a $Q\times Q$ table, where for $i,j\in [Q]$, the entry $\textsf{IP}[i,j]$ is set as follows:
  - $*$ If $i\ne j$ and $\textbf{x}[i] = \textbf{x}[j]$, then set $\textsf{IP}[i,j] = \textsf{DB}(\textbf{s}[i])\cap \textsf{DB}(\textbf{s}[j])$.
  - $*$ Else, set $\textsf{IP}[i,j] = \emptyset $.

1.2 D.2 The Simulator

We construct a simulator $\textsf{Sim}_{\textsf{GXT}}$. $\textsf{Sim}_{\textsf{GXT}}$ is given access to the leakage function $\mathcal {L}^{\textsf{GXT}} =\left( \mathcal {L}^{\textsf{GXT}}_{\textsf{Setup}},\mathcal {L}^{\textsf{GXT}}_{\textsf{Search}}\right) $ for $\textsf{GXT}$ for the case of 2-conjunctive queries as described above, and proceeds as follows.

Creating a Restricted Equality Pattern. The simulator $\textsf{Sim}_{\textsf{GXT}}$ first computes the restricted equality pattern of $\textbf{x}$, denoted $\widehat{\textbf{x}}$. Intuitively, $\widehat{\textbf{x}}$ captures which x-terms are “known” to the server as being equal. The restricted equality pattern $\widehat{\textbf{x}} \in |\textsf{W}|^Q$ is computed by $\textsf{Sim}_{\textsf{GXT}}$ as follows:

First, $\textsf{Sim}_{\textsf{GXT}}$ defines a relation $\equiv $ on $[Q]\times [Q]$ as: $i\equiv j$ for $(i,j)\in [Q]\times [Q]$ if $\textsf{IP}[i,j]\ne \phi $, and then turns this into an equivalence relation by taking its transitive closure.
Next, $\textsf{Sim}_{\textsf{GXT}}$ sorts the partitions of the equivalence relation by their least element, and assign $\widehat{\textbf{x}}[i]$ the index of the partition containing i.

The following lemma (imported from [6]) states that (informally speaking) $\widehat{\textbf{x}}$ serves as the “equality pattern” for $\textbf{x}$ when certain conditions hold.

Lemma 1

(Imported from [6]). Let $\textsf{DB}= (\textsf{ind}_i,\textsf{W}_i)_{i\in [d]}$ be a database, let $\textbf{s}, \textbf{x}\in \textsf{W}^Q$ be two vectors representing a set of Q 2-conjunctive queries as defined above, and let $|widehat{\textbf{x}}$ be the restricted equality pattern as defined above. Then for all $i, j \in [Q]$, we have

$$\begin{aligned} \widehat{\textbf{x}}[i] = \widehat{\textbf{x}}[j] \implies \textbf{x}[i] = \textbf{x}[j], \end{aligned}$$

and

$$\begin{aligned} (\textbf{x}[i] = \textbf{x}[j]) \wedge (\textsf{DB}(s[i]) \cap \textsf{DB}(s[j])\ne \phi ) \implies \widehat{\textbf{x}}[i] = \widehat{\textbf{x}}[j]. \end{aligned}$$

Proof. We refer the reader to [6] for the detailed proof.

Simulating the $\textsf{TSet}$. The simulator $\textsf{Sim}_{\textsf{GXT}}$ simulates the encrypted data structure $\textsf{TSet}$ as follows:

Initialize an empty list $L = \emptyset $.
For each $i \in |\textsf{W}|$, create a random $\textsf{stag}_i \leftarrow \{0,1\}^{\lambda }$.
For each $i\in |\textsf{W}|$, create a list ${\textbf {t}}_i$ subject to the following restrictions:
- $\sum _{i\in [|\textsf{W}|]} |{\textbf {t}}_i|= N$.
- If $i=\widehat{\textbf{x}}[j]$ for some $j\in [Q]$ set $|{\textbf {t}}_i| = \textsf{SP}[\widehat{\textbf{x}}[j]]$.
- Each entry in ${\textbf {t}}_i$ is of the form $(\textsf{e},y)$, where $\textsf{e}= \textsf{SKE}.\textsf{Enc}(K_e,0^\lambda )$ for some $K_e\leftarrow \{0,1\}^\lambda $, and where $y\leftarrow G$ is a uniformly random group element from the group G corresponding to the group action $(G,X,\star )$.
Set $L = (\textsf{stag}_i,{\textbf {t}}_i)_{i\in [|\textsf{W}|]}$. Store this list L locally for future use.
Finally, create the simulated dictionary $\textsf{TSet}$ as $\textsf{TSet}\leftarrow \textsf{Dict}.\textsf{Create}(L)$.

Simulating the $\textsf{XSet}$. The simulator $\textsf{Sim}_{\textsf{GXT}}$ now simulates the encrypted data structure $\textsf{XSet}$ as follows:

Initialize an empty set $\textsf{XSet}= \emptyset $.
Initialize an empty hash table $H = \emptyset $ and an empty permutation array $\textsf{WPerms} = \emptyset $.
For each $\ell \in \widehat{x}$ and each $\textsf{ind}\in \cup _{j\in [Q]}\textsf{RP}[j]$, set $H[\textsf{ind},\ell ] \leftarrow X$ as a uniformly random set element from the set X corresponding to the group action $(G,X,\star )$.
For each $i\in [Q]$, set $\textsf{WPerms}[\textsf{EP}[i]] \leftarrow \textsf{Perm}([\textsf{SP}[i]])$, where $\textsf{Perm}([\textsf{SP}[i]])$ generates a random permutation of the integers in the range [SP[i]].
Initialize a counter $i = 0$.
For each $\ell \in \widehat{x}$ and each $\textsf{ind}\in \cup _{j:\widehat{x}[j] = \ell }\textsf{RP}[j]$, do the following:
- Set $\textsf{XSet}= \textsf{XSet}\cup \{H[\textsf{ind},\ell ]\}$.
- Set $i = i+1$.
For each $j\in [i+1,N]$, set $\textsf{XSet}= \textsf{XSet}\cup \{u\}$ where $u \leftarrow X$ is a uniformly random set element from the set X corresponding to the group action $(G,X,\star )$.

At this point, the simulator $\textsf{Sim}_{\textsf{GXT}}$ is ready with the simulated encrypted database $\textsf{EDB}= (\textsf{TSet},\textsf{XSet})$.

Simulating the Query Transcript. The simulator $\textsf{Sim}_{\textsf{GXT}}$ now creates a transcript array $\textsf{stk}$, where for each $i\in [Q]$, $\textsf{stk}[i]$ denotes the transcript corresponding to the i-th query. For each $i\in [Q]$, the query transcript $\textsf{stk}[i]$ is created as follows:

Let $\ell = \widehat{\textbf{x}}[i]$.
Compute the set of “revealed” indices for the i-th query as $R = \textsf{RP}[i]\cup \sum _{j\in [Q]} \textsf{IP}[i,j]$.
Arrange set of indices in R in canonical order. Let the canonically ordered list be of the form $(\overline{\textsf{ind}}_1,\ldots ,\overline{\textsf{ind}}_{T'})$.
Since each index in R is also in $\textsf{DB}[\textbf{s}[i]]$, we must have $|R|\le \textsf{SP}[i]$. Pad the list R with additional dummy indices $(\overline{\textsf{ind}}_{T'+1},\ldots ,\overline{\textsf{ind}}_{\textsf{SP}[i]})$, where for each $j\in [T'+1,\textsf{SP}[i]]$, $\overline{\textsf{ind}}_{j} = \bot $.
Retrieve $(\textsf{stag}_{\ell },{\textbf {t}}_{\ell })$ from internal storage.
Let $\sigma = \textsf{WPerms}[\textsf{EP}[i]]$.
For each $c\in [\textsf{SP}[i]]$, do the following:
- Let $(\textsf{e}_c,y_c) = {\textbf {t}}_{\ell }[c]$, where $y_c\in G$ is a group element corresponding to the group action $(G,X,\star )$.
- If $\overline{\textsf{ind}}_{\sigma (c)}\ne \bot $, set $\textsf{xtoken}_i[c] = \left( (y_c)^{-1}\right) \star H[,\overline{\textsf{ind}}_{\sigma (c)},\ell ]$, where $\star $ denotes an action computation corresponding to the group action $(G,X,\star )$.
- Else, set $\textsf{xtoken}_i[c] \leftarrow X$ as a uniformly random set element.
Pick random $k > \textsf{SP}[i]$, and set $\textsf{xtoken}_i[c]\leftarrow X$ as a uniformly random set element for each $c\in [\textsf{SP}[i]+1,k]$.
Finally, set $\textsf{stk}[i] = (\textsf{stag}_\ell ,\textsf{xtoken}_i)$.

Finally, the simulator $\textsf{Sim}_{\textsf{GXT}}$ outputs $(\textsf{EDB}= (\textsf{TSet},\textsf{XSet}),\textsf{stk})$.

1.3 D.3 The Hybrid Argument

We now present a sequence of computationally indistinguishable hybrids that allow us to argue that the above simulation results in an ideal-world adversarial view that is computationally indistinguishable from the real-world adversarial view.

Hybrid-0. This is the real game.

Hybrid-1. In this hybrid, we replace the evaluations of the real PRF evaluations $F(K_S, \cdot ), F_G(K_X , \cdot ), F_G(K_I , \cdot ), F_G(K_X , \cdot )$, are replaced by evaluations of independent uniformly random functions with the appropriate domain and range (this is done via the usual lazy sampling strategy). This is indistinguishable from Hybrid-0 by the security of each PRF (Definition 5).

Hybrid-2. In this hybrid, we replace each $\textsf{e}$ entry in the $\textsf{TSet}$ by encryptions of $0^{\lambda }$ (under the same key $K_e$). The indistinguishability of this hybrid from Hybrid-1 follows by a standard hybrid argument over the $|\textsf{W}|$ encryption keys used in building $\textsf{TSet}$ f. We omit the tedious details. We stress that the reduction is possible because the game never invokes the decryption algorithm of the $\textsf{SKE}$ scheme, meaning that the reduction does not need to decrypt ciphertexts during the IND-CPA game.

Hybrid-3. In this hybrid, we set the y entries in the $\textsf{TSet}$ as $f_I(\overline{\textsf{ind}}_{\sigma (c)})/f_Z(s\Vert c)$, where $f_I$ and $f_Z$ are random functions and $\overline{\textsf{ind}}_{\sigma (c)}$ is set as in the simulation strategy defined above. We also maintain a table H with entries of the form $H[\textsf{ind},w] = (f_I(\textsf{ind})f_X(w))\star x_0$ (used to generate the $\textsf{XSet}$), and set the corresponding $\textsf{xtoken}[c]$ entry in $\textsf{stk}$ as $H[\overline{\textsf{ind}}_{\sigma (c)},x]^{1/y} = (f_X(x))f_Z(s\Vert c))\star x_0$. This is primarily a book-keeping hybrid, and the view of the adversary is identical in Hybrid-2 and Hybrid-3.

Hybrid-4. In this hybrid, we set the y entries in the $\textsf{TSet}$ as uniformly random elements in the group G. This is because the PRF $F_G(K_Z,\cdot )$ and its random counterpart $f_Z$ are never evaluated on the same input twice (each evaluation corresponds to a unique (w, c) pair), and hence the output distribution of $f_Z$ on $(w\Vert c)$ values is statistically indistinguishable from random. Hence, Hybrid-4 is statistically indistinguishable from Hybrid-3.

Hybrid-5. In this hybrid, we set the entries of the $\textsf{XSet}$ to be uniformly random. This hybrid is computationally indistinguishable from Hybrid-4 by the GA-DDH assumption (Definition 2) over the EGA $(G,X,\star )$.

Hybrid-6. In this hybrid, we set the $\textsf{TSet}$ exactly as in the simulation strategy described above. This hybrid is computationally indistinguishable from Hybrid-5 assuming that the dictionary scheme $\textsf{Dict}$ satisfies history independence.

Hybrid-7. In this hybrid, we change the manner in which the H array is accessed in order to enable the final simulator to work with its given leakage. Intuitively, now whenever the game access the H array at an index $(\textsf{ind}, x)$, it first tests to see if the game will ever access that index in H again. If it will come back to this position, it uses the value from H. It not, then the game replaces the H access with a random choice. Since that was to be the only usage of that position of H during the game, this doesn’t affect the distribution of the game. Hence, the view of the adversary is identical in Hybrid-6 and Hybrid-7.

Hybrid-8. In this hybrid, we switch entirely to the simulation strategy described earlier. Since we have entirely switched to generating and accessing $\textsf{TSet}$ and $\textsf{XSet}$ using the leakage by Hybrid-7, the view of the adversary is identical in Hybrid-7 and Hybrid-8.

The detailed proofs of indistinguishability for the hybrids above are similar to those used in the original security proof for $\textsf{OXT}$, and are not detailed further. This concludes the proof of Theorem 2.

E Proof of Theorem 4

We consider a session $\textsf{sid}$ with a single client $\textsf{C}$ with a conjunctive query $\bar{w}=(w_1,\dots ,w_\mu )$, a data owner $\textsf{D}$, and a passive eavesdropper $\textsf{E}$ who has no input^{Footnote 4} (we assume authenticated but no secure channels). We further assume that for each execution corresponding to a specific tuple $(\textsf{sid},\bar{w})$, a party plays exactly one role (this can change across different executions). Again we argue that considering this specific setting is without loss of generality. To see that fix a specific $(\textsf{vk},\bar{w})$. We consider three separate cases:

Case-1: Suppose that $\textsf{C}$ and $\textsf{D}$ are both honest, while the eavesdropper $\textsf{E}$ is passively corrupt. In this case, we want the following guarantee: $\textsf{E}$ should not be able to predict the output search token $\textsf{stk}$, without querying $\bar{w}$ explicitly.
Case-2: Suppose that $\textsf{C}$ is corrupt, while $\textsf{D}$ and $\textsf{E}$ are honest. In this case, we want the following guarantee: unless the $\textsf{C}$ derives the output search token $\textsf{stk}$ explicitly by interacting with $\textsf{D}$, it cannot efficiently predict $\textsf{stk}$.
Case-3: Suppose that $\textsf{C}$ is honest, while both $\textsf{D}$ and $\textsf{E}$ are corrupt. In this case, we want the following guarantees: (i) the query $\bar{w}$ remains private, and (ii) consistency, i.e., the search token $\textsf{stk}$ is, computed correctly.

This exhausts the objectives of all parties in the system. We describe a different ideal-world simulation strategy for each case:

Case-1: $\textsf{Sim}_\textsf{E}$ simulates the interactions between the honest client $\textsf{C}$ and the honest data owner $\textsf{D}$.
Case-2: $\textsf{Sim}_\textsf{C}$ interacts with the ideal functionality $\mathcal {F}_\textsf{Token}^\mathsf {MC\text {-}SSE}$ on behalf of the maliciously corrupt client $\textsf{C}$, while simulating the messages from the honest $\textsf{D}$.
Case-3: $\textsf{Sim}_\textsf{D}$ interacts with the ideal functionality $\mathcal {F}_\textsf{Token}^\mathsf {MC\text {-}SSE}$ on behalf of the maliciously corrupt data owner $\textsf{D}$, while simulating the messages from the honest $\textsf{C}$.

1.1 E.1 Simulation Strategy for Case-1

In this case, we need to ensure that no eavesdropper $\textsf{E}$ can predict the search token on a non-queried search query, even if it can access the entire communication transcript between an honest $\textsf{C}$ and an honest $\textsf{D}$. To this end, we construct a simulator $\textsf{Sim}_\textsf{E}$ that simulates the messages from the honest client $\textsf{C}$ and the honest data owner $\textsf{D}$ by directly using the simulators $\textsf{Sim}_F$ and $\textsf{Sim}_{X}$ for the underlying $\textsf{OPRF}$ schemes $\textsf{OPRF}_F$ and $\textsf{OPRF}_X$, respectively.

It is easy to see that any corrupt eavesdropper $\textsf{E}$ that manages to predict the search token on a non-queried search query can be turned into an adversary that manages to predict the output of either F or $F_X$ on a non-queried input, thus breaking the security of either $\textsf{OPRF}_F$ or $\textsf{OPRF}_X$. This completes the proof of security of token generation for case-1.

1.2 E.2 Simulation Strategy for Case-2

In this case, we want the following guarantee: unless the corrupt client $\textsf{C}$ derives the output search token $\textsf{stk}$ on a search query $\bar{w}$ by explicitly interacting with the honest data owner $\textsf{D}$, it cannot efficiently predict $\textsf{stk}$. In other words, if the corrupt $\textsf{C}$ issues $q = \textsf{poly}(\lambda )$ token generation queries to the honest $\textsf{D}$, it cannot more than q valid (query, token) tuples. To this end, we construct a simulator $\textsf{Sim}_\textsf{C}$ that interacts with the ideal functionality $\mathcal {F}_\textsf{Token}^\mathsf {MC\text {-}SSE}$ on behalf of the maliciously corrupt client $\textsf{C}$, while simulating the messages from the honest $\textsf{D}$. Let $\textsf{Sim}_F$ and $\textsf{Sim}_{X}$ be the simulators for the underlying $\textsf{OPRF}$ schemes $\textsf{OPRF}_F$ and $\textsf{OPRF}_X$, respectively. The simulation strategy used by $\textsf{Sim}_\textsf{C}$ is as follows:

1.
Since both $\textsf{OPRF}_F$ and $\textsf{OPRF}_X$ are maliciously secure, the corresponding simulators must have a mechanism to extract a malicious client’s $\textsf{OPRF}$ input from the client’s messages. $\textsf{Sim}_\textsf{C}$ uses the same strategy to extract the query $\bar{w}$ from the malicious client $\textsf{C}$ from its messages.
2.
$\textsf{Sim}_\textsf{C}$ simulates the messages from the honest data owner $\textsf{D}$ by directly using the simulators $\textsf{Sim}_F$ and $\textsf{Sim}_{X}$.
3.
Upon receiving $(\textsf{Token},\textsf{sid}, w^*)$ from the ideal functionality ($w^*$ being an encoded query), $\textsf{Sim}_\textsf{C}$ uses the extracted query $\bar{w}$ to issue a query of the form $(\textsf{Token},\textsf{sid},\bar{w})$ to the ideal functionality. If the ideal functionality outputs $\bot $, $\textsf{Sim}_\textsf{C}$ outputs $\bot $ to $\textsf{C}$. Otherwise, if the ideal functionality outputs $\textsf{stk}$, it outputs $\textsf{stk}$ to $\textsf{C}$.

Now, observe that any malicious client $\textsf{C}$ that manages to extract the output search token $\textsf{stk}$ on a search query $\bar{w}$ without interacting with the honest data owner $\textsf{D}$ must predict the output of either F or $F_X$ on a given input without actually querying it, thus breaking the security of either $\textsf{OPRF}_F$ or $\textsf{OPRF}_X$. This completes the proof of security of token generation for case-2.

1.3 E.3 Simulation Strategy for Case-3

In this case, we want the following guarantee: a malicious data owner $\textsf{D}$ cannot learn any information about the query issued by some honest client $\textsf{C}$. To this end, we construct a simulator $\textsf{Sim}_\textsf{D}$ that interacts with the ideal functionality $\mathcal {F}_\textsf{Token}^\mathsf {MC\text {-}SSE}$ on behalf of the maliciously corrupt data owner $\textsf{C}$, while simulating the messages from the honest client $\textsf{C}$. Let $\textsf{Sim}_F$ and $\textsf{Sim}_{X}$ be the simulators for the underlying $\textsf{OPRF}$ schemes $\textsf{OPRF}_F$ and $\textsf{OPRF}_X$, respectively. The detailed simulation strategy used by $\textsf{Sim}_\textsf{D}$ is as follows:

1.
Upon receiving $(\textsf{Input}, \textsf{sid}, w^*)$ from the ideal functionality, where $w^* = (w^*_1,\ldots ,w^*_{\mu })$, $\textsf{Sim}_\textsf{D}$ forwards it to the corrupt data owner $\textsf{D}$. If $\textsf{D}$ aborts, $\textsf{Sim}_\textsf{D}$ sends $\bot $ to the ideal functionality. Otherwise, $\textsf{Sim}_\textsf{D}$ responds to the ideal functionality with the same message $(\textsf{Input}, \textsf{sid}, w^*)$.
2.
$\textsf{Sim}_\textsf{D}$ simulates the messages from the honest client $\textsf{C}$ by directly using the simulators $\textsf{Sim}_F$ and $\textsf{Sim}_{X}$ on the encoded inputs $w^*_1$ and $(w^*_2,\ldots ,w^*_\mu )$. If the corrupt server aborts at any point, $\textsf{Sim}_\textsf{C}$ also aborts.
3.
If the corrupt server $\textsf{S}$ does not abort, $\textsf{Sim}_\textsf{D}$ submits a query of the form $(\textsf{Token},\textsf{sid},w^*)$ to the ideal functionality. If the ideal functionality aborts, $\textsf{Sim}_\textsf{D}$ also aborts. Otherwise, if the ideal functionality returns the same message, $\textsf{Sim}_\textsf{D}$ responds to the ideal functionality with the same message again.

Now observe that any malicious data owner $\textsf{D}$ that gains any information about the honest client’s input query must violate the input obliviousness guarantee of either $\textsf{OPRF}_F$ or $\textsf{OPRF}_X$. This completes the proof of security of token generation for case-3, and hence the proof of Theorem 4.

Rights and permissions

Reprints and permissions

Copyright information

About this paper

Cite this paper

Patranabis, S. (2025). Post-quantum Multi-client Conjunctive Searchable Symmetric Encryption from Isogenies. In: Knechtel, J., Chatterjee, U., Forte, D. (eds) Security, Privacy, and Applied Cryptography Engineering. SPACE 2024. Lecture Notes in Computer Science, vol 15351. Springer, Cham. https://doi.org/10.1007/978-3-031-80408-3_15

Download citation

DOI: https://doi.org/10.1007/978-3-031-80408-3_15
Published: 09 December 2024
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-80407-6
Online ISBN: 978-3-031-80408-3
eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics