<figure><img src="image_1.png" /></figure>

HAL
open science

# A New Approach for Private Searches on Public-Key Encrypted Data

Amar Siad

► To cite this version:

Amar Siad. A New Approach for Private Searches on Public-Key Encrypted Data. 13th International Conference on Communications and Multimedia Security (CMS), Sep 2012, Canterbury, United Kingdom. pp.160-173, 10.1007/978-3-642-32805-3_13 . hal-01540893

HAL Id: hal-01540893

https://inria.hal.science/hal-01540893

Submitted on 16 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A new Approach for Private Searches on Public-Key Encrypted Data

Amar SIAD

LAGA, UMR 7539, CNRS, Department of Mathematics, University of Paris XIII and University Paris of VIII, 2 rue de la Liberté 93526 SAINT-DENIS, FRANCE

siad@math.univ-paris13.fr

**Abstract.** Public-key Encryption with Keyword Search (PEKS) allows authorized users to search by keywords on encrypted data by generating trapdoors for the desired keywords. Basically there are two requirements for the process of trapdoors generation. On one hand, it is important to allow users to privately search on encrypted data without revealing keywords to the Trapdoor Generation Entity $TGE$, and solutions proposed are based on the use of blinding protocols between user and $TGE$. On the other hand, in some applications it is necessary to prevent $TGE$ from generating trapdoors on behalf of a legitimate user, this is done by splitting the $TGE$ and generating trapdoors in distributed manner. Until now, these two requirements in PEKS were considered separately and many solutions were proposed dealing with each one. However, no solution is known to satisfy the two requirements at the same time. In this paper we present a new approach to deal with this issue. First, we extend the notion of anonymous Identity-Based Encryption with distributed Private Key Generator to handle the blind key-extraction protocols as in Blind IBE. We call such new schemes blind anonymous $(n, t)$-IBE, and we give concrete construction of such schemes. Second, we generically transform the blind anonymous $(n, t)$-IBE into a threshold PEKS with oblivious keyword search satisfying the requirements specified above.

**Keywords:** Threshold Searchable Encryption, Public key Encryption with Keyword Search, Blind Identity-Based Encryption.

## 1 Introduction

**Public-key encryption with keyword search.** The first formalization of the concept of public-key encryption with keyword search (PEKS) was proposed by Boneh, et al. [2], the authors presented an application that allows user Alice to have the email server extract encrypted emails that contain a particular keyword by providing a trapdoor corresponding to that keyword, while the email server and other parties do not learn anything else about the email. PEKS is very useful, it provides mechanism for searching on encrypted data for public key cryptosystems. Furthermore, it has a very close connection to anonymous
identity-based encryption as defined in [2]. This connection has been studied
more thoroughly by Abdalla et al. [1]. For this reason, most work (including
ours) on asymmetric searchable encryption has a direct use for identity-based
encryption, and vice versa.

After [2] a flurry of PEKS schemes were proposed [0, 5, 11, 19], each one deals
with a special scenario application. We focus our interest on special schemes
[12,10,16] proposing mechanisms for generating trapdoors. Camenisch et al. [10]
introduced the concept of public key encryption with oblivious keyword search
(PEOKS) which uses Blind key extraction protocols to hide keyword from the
TE. They extended the definition of PEKS to incorporate the encryption of
a secret message when computing a searchable encryption. This secret message
can contain a symmetric key, which allows PEKS to be used directly in settings
such as [9]. Hiding keywords from TGE allows generation of trapdoors in blind
manner. However, TGE can always try to derive all possible trapdoors according
to a certain "dictionary". It seems that there is not much can be done to protect
the scheme against a strong adversary like the TGE in this situation. Further-
more, as noticed by the authors, using PEOKS in practice needs an additional
trusted authority which is responsible of certifying keywords.

Wang et al. [12] constructed a threshold keywords search scheme, using
Shamir verifiable secret sharing, in which users encrypt their data and upload
it to the server with secure indexes, then a subset of users should collaborate to
generate a trapdoor for the target keywords. Decryption also is done in threshold
manner, and secret keys used for decryption and trapdoor generation are chosen
and distributed by a centralized dealer. The scheme presented is based on the
random oracle IBE of Boneh and Franklin [17] and no formal relation between
the PEKS scheme and the underlying IBE scheme is given. Furthermore, the
given scheme does not support the feature of hiding keywords from TGE. In the
same category, Siad [16] showed how to generically construct threshold PEKS
from anonymous IBE with distributed Private Key Generator and presented a
practical architecture for deployment of TPEKS. However, as in [12] the pro-
posed solution does not hide keywords from the TGE. Furthermore, no concrete
construction is given.

**Identity-based encryption with distributed PKG.** A well known approach to design distributed protocols is to use multi-party computation. Although results obtained in general multi-party computation guarantee feasibility, they cannot be directly applied without affecting computation complexity. In contrast, threshold protocols for specific tasks should be developed at hand and are therefore much more efficient and practical.

In the identity-based encryption settings, there have been many proposals.
Boneh and Franklin [17] were the first to suggest the distribution of the master se-
cret key, their scheme have the advantage of being straightforward to distribute.
Geisler and Smart [4] proposed a distributed version of sakai-kasahara based
systems which requires for each ID-based key a secure multi-party computation
to be performed amongst the servers and presented an implementation in the
semi-honest model. The drawback oft he proposed solution is that it lacks a for-
mal security analysis. Recently, Kate and Goldberg [6] considered IBE schemes
with more complex user's private key structure (distribution of such schemes
requires inversion in the exponent, addition, and multiplication of shares). The
authors developed a distributed private-key generators for three IBE schemes
along with the security proofs in the random oracle model. Another interesting
work [3,5] with an application in the IBE settings, proposes a different approach
in which the *PKG* is replaced by a distributed set of users, each one of them
holding a small piece of the master secret in the form of a short password. The
authors defined ideal functionalities for distributed public-key generation and
virtual private-key computation in the UC framework and constructed efficient
protocols that securely realize them.

**Our contribution.** First, we formalize the concept of blind anonymous $(n, t)$-IBE$^1$ as an extension of anonymous IBE schemes with distributed PKG for which we add a blinding phase. In this context, anonymous means that the ciphertext does not leak the identity under which it was encrypted [1] and blind means that a user can request the decryption key for a given identity without the PKGs learning the identity [23]. Second, we give a concrete construction of a blind anonymous $(n, t)$-IBE along with the security proofs. Our construction focuses only on the blinding protocol under the standard definitions of security following the ideal/real world paradigm in the standalone setting [13] and we discuss its extension to the universal composability framework [14]. Finally, we give an application of the blind anonymous $(n, t)$-IBE in the setting of PEKS. We show how to generically transform a blind anonymous $(n, t)$-IBE into a threshold PEKS with oblivious keyword search and we described a system architecture for real world deployment of TPEOKS to build a public key encrypted database with distributed and blinded generation of trapdoors.

2 Preliminaries

**2.1 Identity-Based Encryption**

An identity-based encryption (IBE) scheme supports two types of players: a sin-
gle Private Key Generator $\mathcal{PKG}$ and multiple users. An IBE scheme consists of
algorithms (IBESetup, IBEKeyGen, IBEExtract, IBEEnc, IBEDec).

**Anonymous (n, t)-IBE.** Abdella et al. [1] defined anonymity against user attacks for IBE similarly to semantic security. The attacker's goal is to distinguish the intended recipient of a ciphertext between two chosen identities. An anonymous IBE scheme with distributed *PKG* ($(n, t)$-IBE) extends a regular anonymous IBE scheme by distributing the master secret key of the *PKG* among $n$

<footnote n="1">¹ A related concept of our blind anonymous (n, t)-IBE was proposed by Siad and Amara [20]. However, their security model is based on the use of properties of p-signatures [7] and their protocol is less efficient than ours since it relies on a general two-party protocol and no formal analysis was given. Furthermore, the authors does not relate their scheme to the concept of searchable encryption.</footnote>
PKGs. In addition to IBEEnc and IBEDecr algorithms which remain unchangeable, an (n, t)-IBE scheme consists of the following algorithms:

- **IBE Global Setup**: Off-line bootstrapping procedure run by any untrusted entity to generate global parameters $\mathcal{GP}$. This includes the threshold parameters, description of the groups and their generators, and the bilinear pairing.

- **(n, t)-IBE KeyGen**: Distributed protocol run between $n$ players takes global parameters $\mathcal{GP}$ as input and outputs for each player a share $\mathit{sk}_i$ of a master secret key $\mathit{msk}$ and the master public key $\mathit{mpk}$.

- **(n, t)-IBE Extract**: Distributed protocol that takes as input, for each player, the user identity $id$, the public key $mpk$ and the master-secret share $\mathit{sk}_i$ and outputs a verifiable private-key share $d_{id}^{(i)}$. The user computes her private key $d_{id}$ after verifying the received shares $d_{id}^{(i)}$ from at least $t+1$ PKG.

CPA-security and user-anonymity for (n, t)-IBE ((n, t)-IBE-IND-CPA, (n, t)-IBE-ANON-CPA) are defined [16]. In addition to the key extraction oracle $O_{Extract}(.)$ a new oracle $O_{Corrupt}(t,..)$ is defined to allow the adversary to choose $t$ players to corrupt. Furthermore, (n, t)-IBE-IND-CPA and (n, t)-IBE-ANON-CPA can be combined in one game called (n, t)-IBE-IND-ANON-CPA security.

## 2.2 Public-key Encryption with Keyword Search

**Definition 1. (PEKS) [10]** A non-interactive public key encryption with keyword search scheme consists of the following polynomial time randomized algorithms:

- **KeyGen**($1^k$): generates public/private key pair $pk, sk$.

- **PEKS**($pk, W, M$): produces a searchable encryption $S_{W,M}$ for keyword $W$ and message $M$.

- **Trapdoor**($sk, W$) : produces a trapdoor $T_W$ for keyword $W$.

- **Test**($S_W, T_{\hat{W}}$): outputs $M$ if $\hat{W} = W$ and $\perp$ otherwise.

In PEKS, the party holding the secret key $sk$ (called Trapdoor Generation Entity $\mathcal{TGE}$) runs the Trapdoor algorithm to obtain the trapdoor $T_w$ for a keyword $W$. Threshold Public key encryption with keyword search (TPEKS) is an extension of PEKS in which a user $U$ performing a search can generate trapdoor shares $T_{i,w}$ from the trapdoor generation entities $\mathcal{TGE}$s in a distributed manner and combine them to compute the final trapdoor.

**Definition 2. (TPEKS)** A threshold public key encryption with keyword search scheme consists of the following polynomial time randomized algorithms: (1) **Setup**($1^k$): generates $\mathcal{GP}$, the parameters of the scheme; (2) (n, t)-**KeyGen**($\mathcal{GP}$): generate the master key pair $msk/mpk$, each player $P_i$ gets its own share $\mathit{sk}_i$ of $msk$; (3) **TPEKS**($\mathcal{GP}, W, M$): produces a searchable encryption $S_{W,M}$ for keyword $W$ and message $M$; (4) (n, t)-**Trapdoor**($W$): produces shares $T_{i,W}$ of the trapdoor $T_W$ for $W$; (5) **Test**($S_{W,M}, T_{\hat{W}}$): outputs $M$ if $\hat{W} = W$ and $\perp$ otherwise.
**Proof of Knowledge.** We use the following notation for proofs of knowledge of discrete logarithms and proofs of the validity of statements about discrete logarithms. PoK{$\{(a, b) : C = g^a h^b\}$}. This proof denotes a "zero-knowledge Proof of Knowledge of integers $a, b$ such that the equality $C = g^a h^b$ holds". The convention used here is that values in the parenthesis denote values known only to the prover, while all other values are known to the verifier.

## 3 Formal Definition and Security Model

**Blind anonymous (n, t)-IBE.** A blind anonymous (n, t)-IBE scheme consists of the same players as the anonymous (n, t)-IBE, together with the same algorithms IBESetup, (n, t)-IBEKeyGen, (n, t)-IBEExtract, IBEEnc, IBEDec, a secure commitment scheme $COM=(\text{Setup}, \text{Commit})$, and the protocol (n, t)-IBEBlindExtract defined as follows:

- $\pi_{\text{Blind}}$: The blinding protocol $\pi_{\text{Blind}}$ is composed of a sequence of two-party protocols

$\pi_i : ((\mathcal{P}\mathcal{K}\mathcal{G}_i(\mathcal{G}\mathcal{P}, \mathit{ski}, \mathcal{C}), \mathcal{U}(\mathcal{G}\mathcal{P}, \mathit{id}, \mathit{open}_{\mathit{id}})) \rightarrow (\overline{\mathit{id}}_i, \mathit{nothing}))$ run between the user with identity $\mathit{id}$, opening information $\mathit{open}_{\mathit{id}}$ as private inputs and $\mathcal{P}\mathcal{K}\mathcal{G}_i$ with secret key $\mathit{ski}$ as private input. If $\mathcal{C} = \text{commit}(\mathit{id}, \mathit{open}_{\mathit{id}})$ then the $\mathcal{P}\mathcal{K}\mathcal{G}_i$ gets the blinded identity $\overline{\mathit{id}}_i$ and the users gets nothing. Otherwise both parties output $\perp$.

- (n, t)-IBEExtract the same as in (n, t)-IBE. Yet, the players takes as input the resulting blinded identity from the protocol $\pi_{\text{Blind}}$.

An alternative and more natural definition is to require the Blind anonymous (n, t)-IBE be an extension of a regular IBE scheme and to require that (n, t)-IBEBlindExtract to be a secure multi-party computation protocol in which the user enters his identity and a commitment to it, and in which the parties representing the distributed key generation authority enter their key shares. This definition covers blindness and does not leak any information to PKGs about the user's identity. However, as we prefer modular composition of protocols and we assume existence of (n, t)-IBE schemes we prefer the first definition and we require that protocols $\pi_1, ..., \pi_n$ satisfy security properties of two-party computation in both semi-honest and malicious adversary models. Furthermore, using generic tools may be inefficient, since we seek to optimize this specific computation, we present an efficient implementation of these protocols.

### 3.1 Security model

In two-party computation, two parties want to jointly compute a function of their own secret inputs. The standard way of defining security in this setting is through the ideal/real simulation paradigm which provides strong security guarantees like privacy, correctness, etc. and has an important property which is the composition theorem that guarantees certain behaviour when the secure protocol is used as a sub-protocol in another larger protocol. However, in many
other settings including our case, it may be sufficient to guarantee privacy only. Indeed, one can use privacy only definition of security in the malicious model in similar way as it is defined for oblivious transfer in [18]. Yet, as noticed by the authors, no general composition theorem is known for the definition that follows privacy-only approach. As our blinding protocols should operate as sub-protocols in the extraction protocol we preferred the first approach to use the advantage of the composition theorem. Indeed, we define security of protocol $\pi_i$ according to the real/ideal paradigm. First, we define an ideal model where a trusted party is used to compute the function (the blinded identity in our case) for the two parties in "perfect security". Then, we construct a real protocol which is said secure if no adversary can do more harm in the real world execution than in the ideal world execution.

**Real world execution.** in the real world, the blinding protocol $\pi_i$ run between the user $U$ and the $\mathcal{PKG}_i$ as follows: If $\mathcal{PKG}_i$ is corrupted then $\pi_i$ is run between $U$ and adversary $A$ corrupting $\mathcal{PKG}_i: \pi_i (A(\mathcal{GP}, \mathcal{C}, \text{state}), U(\mathcal{GP}, id, \text{open}_{id}))$. In case $U$ is corrupted then $\pi_i$ is run between $\mathcal{PKG}_i$ and adversary $A$ corrupting $U$ as follows: $\pi_i (\mathcal{PKG}_i(\mathcal{GP}, sk_i, \mathcal{C}), A(\mathcal{GP}, \text{sate}))$ with $\mathcal{PKG}_i$.

**Ideal world execution.** Ideal world execution is defined by means of a functionality $\mathcal{F}_{\text{Blind}}$ that allows one corruption of either user or $\mathcal{PKG}$ and not both of them at the same time. $\mathcal{F}_{\text{Blind}}$ is intended to capture blinding protocols for an arbitrary IBE scheme (and not a specific scheme). Thus, we will use the following function as black-box parameter in our definition of the functionality:

**BlindedId**: $(sk_i, id) \mapsto \overline{id}_i$: Given an identity $id$ and secret key $sk_i$, this function computes the blinded identity $\overline{id}_i$.

$\mathcal{F}_{\text{Blind}}$: This functionality is given a security parameter $k$, public commitment $\mathcal{C}$ to the identity, and runs with two parties $\mathcal{PKG}_i$, $U$, and an adversary $S$. $\mathcal{F}_{\text{Blind}}$ is also given a function **BlindedId**: $(sk_i, id) \mapsto \overline{id}_i$, where $\overline{id}_i$ is the blinded identity.

- **Inputs.** $\mathcal{PKG}_i$'s private input is $sk_i$ and $U$'s private input is $(id, \text{open}_{id})$. $S$ sees inputs and outputs of corrupted party which he may change.

- **Computation.** $\mathcal{F}_{\text{Blind}}$ receives inputs of honest parties and compute $\overline{id}_i = \text{BlindedId}(sk_i, id)$ if $\mathcal{C} = \text{commit}(id, \text{open}_{id})$.

* If $\mathcal{PKG}_i$ is corrupted send $\overline{id}_i$ to $\mathcal{S}$, send $\perp$ to $U$,

* If $U$ is corrupted send $\perp$ to $\mathcal{S}$, send $\overline{id}_i$ to $\mathcal{PKG}_i$.

- **Output.** Honest $\mathcal{PKG}_i$ sets his output to $\overline{id}_i$. $U$ sets his output to $\perp$.

Having defined the real and ideal models, we should now define security which asserts that a real-world protocol emulates the ideal-world (which run with a trusted party). More formally, adversaries in ideal model are able to simulate adversaries in real model. We define $\mathcal{PKG}$ security and user security as follows:

*PKG Security (Corrupt user).* for every probabilistic polynomial-time adversary.
sary $\mathcal{A}$ for the real model, there exists a probabilistic polynomial-time adversary $\mathcal{S}$ for the ideal model such that for every auxiliary input $z \in \{0, 1\}^*$:

$$ \mathrm{REAL}_{\mathcal{A}(z), \mathcal{PKG}}(id, open_{id}, sk_i) \stackrel{c}{\approx} \mathrm{IDEAL}_{\mathcal{S}(z), \mathcal{PKG}}(id, open_{id}, sk_i) $$

**User Security (Corrupt PKG):** for every probabilistic polynomial-time adversary $\mathcal{A}$ for the real model, there exists a probabilistic polynomial-time adversary $\mathcal{S}$ for the ideal model such that for every auxiliary input $z \in \{0, 1\}^*$:

$$ \mathrm{REAL}_{\mathcal{A}(z), \mathcal{U}}(id, open_{id}, sk_i) \stackrel{c}{\approx} \mathrm{IDEAL}_{\mathcal{S}(z), \mathcal{U}}(id, open_{id}, sk_i). $$

**Definition 3.** The blinding protocol $\pi_{\text{Blind}}$ is secure if each one of its sub-protocols $\pi_i$ for $i = 1, ..., n$ satisfies PKG Security and User Security properties.

**Definition 4. (Security for blind anonymous (n,t)-IBE)**

Let $\Pi$ an anonymous $(n,t)$-IBE scheme. A blind anonymous $(n,t)$-IBE scheme $= (\Pi, (n,t)-\text{IBEBlindExtract}(\pi_{\text{Blind}},(n,t)-\text{IBEExtract}), \mathcal{COM})$ is $(n,t)$-IBE-IND-CPA (resp. $(n,t)$-IBE-ANON-CPA) secure in the static malicious model if and only if: (1) The underlying $\Pi$ is $(n,t)$-IBE-IND-CPA (resp. $(n,t)$-IBE-ANON-CPA) secure, (2) $\mathcal{COM}$ is a secure commitment scheme, and (3) $\pi_{\text{Blind}}$ is secure (in the sense of definition 3).

# 4 Construction

We present in this section an efficient implementation of a blinding protocol for Gentry [19] scheme using ideas from protocols developed in [8]. The choice of Gentry scheme is motivated by many factors. Firstly, we require an anonymous scheme which is secure in the standard model and sufficiently efficient, this requirement excludes many distributed schemes like Sakai-Kasahara in [20,4,6], Boneh-Franklin in [6]. Secondly, we require a scheme for which there exists a distributed version that is relatively efficient and practical, since Gentry's scheme shares similarities with Sakai-Kasahara, it can be distributed the same way as in [4,6], this requirement excludes also the scheme of Boyen-Waters [15] modified in [10] due to its complex structure of user's private-keys which makes the distribution of these schemes much more difficult.

Let $\mathcal{COM} = (\text{Setup}, \text{Commit})$ be a secure commitment scheme and let $\Pi(\text{KeyGen}, \text{Enc}, \text{Dec})$ be an additively homomorphic and semantically secure encryption scheme, such that $\text{Enc}(e) \otimes r = \text{Enc}(er)$, and $\text{Enc}(a) \oplus \text{Enc}(b) = \text{Enc}(a + b)$. We require also $\Pi$ to be verifiable, that is there exist an efficient proofs of knowledge on encrypted messages (e.g. the content of a ciphertext belongs to a given interval). We construct the blinding protocol as follows:

1. $\mathcal{PKG}_i$ generates a key pair $(pk_{hom}, sk_{hom})$ for the homomorphic scheme $\Pi$ by running algorithm $(pk_{hom}, sk_{hom}) \leftarrow \text{KeyGen}(1^k)$. Then computes $c_1 = \text{Enc}(pk_{hom}, \alpha_i)$ and sends $c_1, pk_{hom}$ to the user $\mathcal{U}$ and engages with her in an interactive zero-knowledge proof $\text{PoK}_1 = \text{PoK}(\{\alpha_i) : c_1 = \text{Enc}(\alpha_i)\})$ that $c_1$ encrypts to a message in $[0, p]$. If the proof fails abort.
2. The user $\mathcal{U}$ randomly chooses $\rho_1 \stackrel{R}{\leftarrow} \mathbb{Z}_p$, $\rho_2 \stackrel{R}{\leftarrow} [0, 2^{kp}]$, and computes $c_2 = ((c_1 \oplus \text{Enc}(pk_{\text{hom}}, -id)) \otimes \rho_1) \oplus \text{Enc}(pk_{\text{hom}}, r\rho_2)$. Then sends $c_2$ and $C = \text{commit}(id, \text{open}_{id})$ to $\mathcal{PKG}_i$. (see section 5 for how $C$ is used to handle stateful randomness).

3. $\mathcal{U}$ and $\mathcal{PKG}_i$ perform an interactive zero-knowledge proof $\text{PoK}_2 = \text{PoK}\{ (id, \text{open}_{id}, \rho_1, v, \mu) : c_2 = ((c_1 \oplus v) \otimes \rho_1) \oplus \mu \wedge C = \text{commit}(id, \text{open}_{id}) \}$ in which $\mathcal{U}$ shows that $c_2$ has been computed correctly using the identity $id$ committed to in $C$ and $\rho_1, \rho_2$ are in the appropriate range. If the proof fails abort.

4. $\mathcal{PKG}_i$ decrypts $c_2$ and does a single modulo $p$ reduction to obtain $\overline{id}_i = \text{Dec}(sk_{\text{hom}}, c_2) \bmod p = (\alpha_i - id)\rho_1$.

**Theorem 1.** *Assume that The $\Pi(\text{KeyGen}, \text{Enc}, \text{Dec})$ is a homomorphic semantically secure encryption scheme relative to addition, and that $\text{COM} = (\text{Setup}, \text{Commit})$ is a secure commitment scheme. Then, the above protocol is a secure blinding protocol for Gentry scheme that satisfies User security and $\mathcal{PKG}$ security properties.*

**Proof.** The proof is divided into two parts, one to show that the protocol meets the $\mathcal{PKG}$ security property, and a second to show User security.

**$\mathcal{PKG}$ security.** For any real-world adversary $\mathcal{A}$ (corrupting the user) we construct a simulator $\mathcal{S}$ such that the "real" and "ideal" executions are computationally indistinguishable. More formally, for any distinguisher $\mathcal{D}$ there exists a negligible function $\nu(\cdot)$ such that:

$\Pr[\mathcal{D}(\text{REAL}_{\mathcal{A}(z), \mathcal{PKG}}(id, sk_i))] - \Pr[\mathcal{D}(\text{IDEAL}_{\mathcal{S}(z), \mathcal{PKG}}(id, sk_i))] \le v(k)$.

Note that the simulator $\mathcal{S}$ can rewind an instance of the adversary $\mathcal{A}$ that it runs internally. He simulates the communication between $\mathcal{D}$ and $\mathcal{A}$ by passing $\mathcal{D}$'s input to $\mathcal{A}$ and $\mathcal{A}$'s output to $\mathcal{D}$. To construct a simulator $\mathcal{S}$, we consider the following sequence of games. We start from the first game representing the real world experiment and modify elements via a series of games until we arrive to the last game which represents the ideal world execution. Let $\text{Adv}[\text{Game i}]$ be $\mathcal{D}$'s advantage in distinguishing the output of Game i from the Real distribution, we define also a set of negligible functions $\nu_1(\cdot), \dots, \nu_n(\cdot)$ where $\nu_i(\cdot)$ is the $i^{th}$ function for the $i^{th}$ game.

**Game 0:** In this game the honest real-world $\mathcal{PKG}$ interacts with the adversary $\mathcal{A}$ as in the real world protocol. It is clear that $\text{Adv}[\text{Game 0}] = 0$.

**Game 1:** $\mathcal{A}$ interacts with $\mathcal{S}'$ which behaves as the real protocol for steps 1 and 2, but then uses the knowledge extractor for $\text{PoK}_2$ to extract from $\mathcal{A}$ the values $\rho_1, id, \text{open}_{id}$ and outputs $\perp$ if the knowledge extractor fails or $C \neq \text{commit}(id, \text{open}_{id})$. Since this extractor fails with probability negligible in $k$, then $\text{Adv}[\text{Game 1}] - \text{Adv}[\text{Game 0}] \le \nu_1(k)$.

**Game 2:** $\mathcal{A}$ interacts with $\mathcal{S}$. In this game, we replace $c_1$ by the value $c_1^* = \text{Enc}(0)$. The difference from Game 1 is equal to $\mathcal{D}$'s advantage in distinguishing the encryption of the value 0 from an encryption of a random value. $\text{Adv}[\text{Game}$
2] - Adv [Game 1] $\le$ Adv[Enc]. By the security of the encryption scheme we have $\text{Adv}[\text{Enc}] \le \nu_2(k)$. Thus Adv[Game 2] - Adv [Game 1] $\le \nu_2(k)$. The ideal-world simulator $\mathcal{S}$ is an algorithm that performs all of the changes between the games above, and runs internally $\mathcal{A}$, it is described as follows:

1. First, $\mathcal{S}$ honestly generates a key pair $(pk_{hom}, sk_{hom}) \leftarrow \text{KeyGen}(1^k)$, computes $c_1^* = \text{Enc}(pk_{hom}, 0)$, and sends $c_1, pk_{hom}$ to $\mathcal{A}$. $\mathcal{S}$ uses the zero-knowledge simulator to simulate the ZK proof $\text{PoK}_1$ with $\mathcal{A}$.

2. $\mathcal{S}$ receives from $\mathcal{A}$ random values $c_2$ and $\mathcal{C}$.

3. $\mathcal{S}$ acts as the verifier for the proof that $c_2$ was computed correctly. If the proof fails to verify, $\mathcal{S}$ aborts. Otherwise, $\mathcal{S}$ runs the proof of knowledge extraction algorithm to extract $(id, \text{open}_{id}, \rho_1)$ and checks that $\mathcal{C} = \text{commit}(id, \text{open}_{id})$ if it isn't it aborts.

4. Next, $\mathcal{S}$ submits $id, \rho_1$ to the trusted party, who returns the valid blinded identity $\overline{id} = (\alpha_i + id)\rho_1$. Finally, $\mathcal{S}$ returns $\perp$ to $\mathcal{A}$.

Summing the differences between the above games, it is clear that Adv [Game 2] is negligible, and therefore no p.p.t. algorithm can distinguish the distribution of Game 2 from Game 0. Thus,
$$ \Pr[\mathcal{D}(\text{REAL}_{\mathcal{A}(z), \mathcal{PKG}}(id, sk_i))] - \Pr[\mathcal{D}(\text{IDEAL}_{\mathcal{S}(z), \mathcal{PKG}}(id, sk_i))] \le \nu(k). \quad \square $$

**User security.** For any real-world adversary $\mathcal{A}$ (corrupting the PKG) we construct a simulator $\mathcal{S}$ such that, for any distinguisher $\mathcal{D}$:
$$ \Pr[\mathcal{D}(\text{REAL}_{\mathcal{A}(z), \mathcal{U}}(id, sk_i))] - \Pr[\mathcal{D}(\text{IDEAL}_{\mathcal{S}(z), \mathcal{U}}(id, sk_i))] \le \nu(k). $$

We consider series of games starting from the real experiment until we arrive at the ideal execution. Let Adv [Game i] be $\mathcal{D}$'s advantage in distinguishing the output of Game i from the Real distribution.

**Game 0:** In the first game the honest real-world user interacts with the adversary $\mathcal{A}$ as in the real world protocol. Clearly Adv [Game 0] = 0.

**Game 1:** in this game, $\mathcal{A}$ interacts with an alternative simulator $\mathcal{S}'$ which runs as in the real protocol, but the zero-knowledge proof-of-knowledge $\text{PoK}_2$ is replaced by a simulated proof. We have $\text{Adv}[\text{Game 1}] - \text{Adv}[\text{Game 0}] \le \text{Adv}[\text{ZK}]$, where $\text{Adv}[\text{ZK}]$ is the advantage of an adversary in breaking the security of the zero-knowledge proof system which is negligible. Thus, $\text{Adv}[\text{Game 1}] - \text{Adv}[\text{Game 0}] \le \nu_1(k)$.

**Game 2:** In this game, $\mathcal{A}$ interacts with $\mathcal{S}''$. The difference from Game 1 is that the computing of $c_2$ is replaced by $c_2' = x \oplus c_1$ and the commitment $\mathcal{C}$ to $id$ is replaced by a commitment $\mathcal{C}^*$ to $x$, where $x$ is a value chosen at random. The difference between Game 2 and Game 1 is equal to $\mathcal{D}$'s advantage in distinguishing distribution of $c_2'$ from the one of $c_2$ and $\mathcal{C}^*$ from $\mathcal{C}$. We observe that $c_2'$ is distributed statistically close to the uniform distribution, since $x$ is random and $c_1$ is an encryption of a value chosen at random in $\mathcal{Z}_p$. In the same way the value $c_2$ computed in the real protocol is distributed statistically close to the uniform distribution. Finally, the security of the commitment scheme guarantees that no adversary can distinguish $\mathcal{C}^*$ from the valid commitment $\mathcal{C}$. Thus Adv[Game 2]-Adv[Game 1] $\le \nu_2(k)$.
**Game 3:** In the final game, we employ the knowledge extractor to extract from $\mathcal{A}$ the value $\alpha_i$. If the knowledge extractor fails, set $S$ output to $\perp$. Let $\text{Pr}[\text{error}]$ be the probability that the knowledge extractor fails, then Adv[Game 3] - Adv[Game 2] $\le \text{Pr}[\text{error}]$. We know that $\text{Pr}[\text{error}]\le \nu_3(k)$, Thus Adv[Game 3]-Adv[Game 2]$\le \nu_3(k)$

The ideal-world simulator $\mathcal{S}$ is an algorithm that performs all of the changes between the games above, and runs internally $\mathcal{A}$, it is described as follows:

1. $\mathcal{S}$ receives $c_1, pk_{hom}$ from $\mathcal{A}$ and acts as verifier for ZK proof that $c_1$ is correctly computed. If the proof fails $\mathcal{S}$ aborts. Otherwise $\mathcal{S}$ runs proof of knowledge extractor to extract $\alpha_i$ from the proof. $\mathcal{S}$ submits $\alpha_i$ to the trusted party and gets $\perp$.

2. $\mathcal{S}$ chooses random values $x, open_x$, and computes $c'_2 = c_1 \oplus \text{Enc}(x), C^* = \text{commit}(x, open_x)$ and sends $c'_2, C^*$ to $\mathcal{A}$. Then, $\mathcal{S}$ uses the simulator for the zero knowledge proof to interact with the adversary for a proof of knowledge of $x$.

Summing the differences between the above games, we get Adv[Game 3] - Adv[Game 0] is negligible, and therefore no p.p.t. algorithm can distinguish the distribution of Game 3 from Game 0. Thus, $\text{Pr}[\mathcal{D}(\text{REAL}_{\mathcal{A}(z),\mathcal{U}}(id, sk_i))] - \text{Pr}[\mathcal{D}(\text{IDEAL}_{\mathcal{S}(z),\mathcal{U}}(id, sk_i))] \le \nu(k)$ $\square$

## 4.1 Extension to the universal composition model

Universal composition framework [14] guarantees security under concurrent execution. A protocol that is universally composable (UC secure) maintains its security even when it is run in an arbitrary environment and with other protocols. Compared to the security model of [13] used in our work, the UC framework introduces an additional entity called the environment $\mathcal{Z}$ which interacts with the adversary $\mathcal{A}$ in an arbitrary way. An immediate consequence of this free interaction between $\mathcal{Z}$ and $\mathcal{A}$ is that it imposes a restriction in the security proofs when constructing the simulator $\mathcal{S}$. The latter cannot use rewinding technique anymore. The protocol presented above is secure in the non-concurrent model, it is possible to extend it to the concurrent model, since the UC framework preserves the overall structure of the approach taken in [13]. Thus, to construct a UC-secure version of our protocol we should consider the following differences:

1. **Commitment schemes.** We should replace the commitment scheme with a universally composable scheme that UC realizes functionality $\mathcal{F}_{COM}$. Our protocol can use any UC-secure commitment scheme, in particular the efficient scheme proposed by Damgard and Neilson [25] can be used. We notice that UC-secure commitment protocol requires an additional trusted setup assumption such as a common reference string.

2. **Rewinding techniques.** The only places in the security proof of the blind- ing protocol in which the simulator uses rewinding are within the zero- knowledge proofs. This fact can be used to modify the protocol in such a way it will be possible to construct a straight-line simulator which is enough
to move to universal composability model. Thus, we should replace the zero-knowledge proofs in our protocol with new zero-knowledge proofs that have non-rewinding simulators.

3. **Reactive tasks.** Another difference between the two models, is that the UC framework allows capturing not only secure function evaluation but also reactive tasks, which is obtained by replacing the trusted party by an ideal functionality. However, Goldreich [24] showed that the definition of security in [13] can be extended to the case of reactive tasks in a straightforward way by allowing the trusted party to obtain inputs and send outputs in phases (for more details see discussion in [24] section 7).

4. **Homomorphic encryption.** Another element to consider is the encryption scheme, although we used a generic scheme which can be efficiently instan- tiated by Paillier scheme [22], it remains to investigate schemes of practical use which are secure in the UC framework. We can use as a starting point the work of Prabhakaran and Rosulek [21] that showed that indistinguishability- based security definitions of homomorphic encryption imply a natural defi- nition of security in the Universal Composition framework.

# 5 Threshold PEKS with oblivious keyword search

We follow a generic transformation in [1,10,16] to transform our blind anony- mous $(n, t)$-IBE into TPEKS with oblivious keyword search. Notice that Gentry’s scheme uses stateful randomness in the secret key generation phase. However, as noted in [19], this requirement can be overcome easily and generically to get a stateless key-authority by using a pseudo-random function $f(id)$. In case of blinding protocols, this becomes more difficult since the $PKG$ does not have access to the identity list. Hence, we handle this requirement as follows: since the blinding protocols require an external entity for certifying identities by the generation of certificates on the committed identities as in [11] or anonymous credentials *cred* as in [10], a simple solution of stateful randomness in this case consists of adding a pseudo-random function $f \in \mathcal{F}$ and always use random coins derived from $f(com)$, where *com* is a commitment to the identity signed by the certificate (resp. credential). However, we should make the assumption that this new entity does not collude with $PKGs$ and generates always the same commitment for the same identity.

Given a blind anonymous $(n, t)$-IBE scheme (IBEGlobalSetup, $(n, t)$-IBEKeyGen, $(n, t)$-IBEBlindExtract, IBEEnc, IBEDec, $COM$) which is $(n, t)$-IBE-ANON-CPA secure, the TPEOKS scheme with oblivious keyword search is as follows:

1. **Setup(1**<sup>*k*</sup>): On input a security parameter $k$, run IBEGlobalSetup(1<sup>*k*</sup>) to generate global parameters $GP$.

2. $(n, t)$-**KeyGen**($GP$): On input global parameters $GP$ run the distributed key generation algorithm $(n, t)$-IBEKeyGen($GP$) to generate shares of the master secret key *msk* and the master public key *mpk*.

3. **TPEKS**(GP, W, M): On input a keyword W and a message M, this algorithm picks a random value $C_2 \in \{0, 1\}^k$ and computes the cyphertext
$C_1 = \text{IBEEnc}(\mathcal{GP}, W, C_2 \| M)$. As a result, the algorithm outputs the tuple $S_{W,M} = (C_1, C_2)$.

4. **(n, t)-BlindTrapdoor:** To generate a trapdoor $T_W$ associated with the keyword $W$, the user $U$ uses a commitment to her keyword $C = \text{commit}(W, \text{open}_W)$ and run $(n, t)$-IBEBlindExtract with $\mathcal{TGEs}$ where user takes as private inputs $W, \text{open}_W$ and $\mathcal{TGE}_i$'s private input is $\text{sk}_i$. Finally, the user gets a blinded trapdoor shares $T_{\bar{W}_i}$ which she can transform into $T_W$ by combining and unblinding at least $t+1$ shares.

5. **Test($S_{W,M}, T_{\bar{W}}$):** On input the searchable encryption $S_{W,M}$ and the trapdoor $T_{\bar{W}}$, it outputs $M$ if $C_2 \| M = \text{IBEDec}(T_{\bar{W}}, C_1)$ and $\perp$ otherwise.

**Definition 5.** Let $\mathcal{Y}$ be a TPEKS scheme. The TPEOKS scheme defined by $(\mathcal{Y}, (n,t)-\text{BlindTrapdoor}, \text{COM})$ is secure if and only if: (1) the underlying $\mathcal{Y}$ is secure TPEKS scheme, (2) COM is a secure commitment scheme, and (3) $(n,t)-\text{BlindTrapdoor}$ is instantiated using $\pi_{\text{Blind}}$ protocol which is secure (see definition 3).

## 5.1 System architecture for TPEOKS

We briefly describe an architecture that enables the use of threshold trapdoor generation in a blinded manner. We propose an architecture that extends the one presented in [10]. It is composed of four entities: Trapdoor Generation Entities $\mathcal{TGEs}$, data holders, keywords certifying authority $\mathcal{KCA}$, and the investigator. The overall architecture works as follows:

First, Trapdoor Generation Entities $\mathcal{TGEs}$ run jointly algorithm $(n, t)$-KeyGen to generate master public key $mpk$ and shares $\text{sk}_i$ of the master secret key. Second, data holders encrypt each data record using a random symmetric key $K$ and generate a searchable encryption $S_{W,K}$ for a keyword $W$ by running TPEKS($\mathcal{GP}, W, K$). The generated searchable encryption is stored with the data record in the database. The investigator requests authorisation from $\mathcal{KCA}$ to perform a search on a given database for a particular keyword $W$ and gets back a credential *cred* with attribute $W$. Next, the investigator presents the credential *cred* to $\mathcal{TGEs}$ and gets trapdoor shares by jointly running $(n, t)$-BlindTrapdoor with $\mathcal{TGEs}$, once combined and unblinded she obtains a trapdoor that matches a searchable encryption. Then she runs algorithm Test($S_{W,K}, T_{\bar{W}}$) and returns the symmetric key $K$ that allows her to decrypt the record associated with the searchable encryption $S_{W,K}$.

Notice that it is possible to separate the ability of searching for data records described by a keyword and the ability of decryption to allow better properties like delegation of search to a third party. To do this, we can proceed as follows: first, we omit the private-key $K$ from the algorithm TPEKS($\mathcal{GP}, W, K$) and add an encryption of $K$ encrypted under the public key belonging to the $\mathcal{TGEs}$. Test algorithm will return only true/false response whether or not a given data record is described by a keyword, and the investigator should submit the encrypted key $K$ to $\mathcal{TGEs}$ which act as threshold decryption servers. $\mathcal{TGEs}$ return decryption shares to the investigator, the latter combines the obtained shares to compute the symmetric key $K$ and proceeds to the decryption of the data record.
# 6 Conclusion

In this paper, we have presented a new searchable encryption scheme, namely threshold public-key encryption with oblivious keyword search TPEOKS. Unlike all previous schemes, our solution presents the advantage of allowing users to privately search by keywords on encrypted data and at the same time prevents the Trapdoor Generation Entity $TGE$ from generating trapdoors on behalf of a genuine user, which was an issue until now. In particular, we have used an approach that merges together TPEKS [16] and PEOKS [10] in one framework.

In order to implement TPEOKS, we have defined blind anonymous $(n, t)$-IBE schemes and provided a generic transformation from an anonymous $(n, t)$-IBE into a blind anonymous $(n, t)$-IBE. We have also developed a concrete construction of such schemes along with the security analysis in the standalone settings and we discussed the extension of the developed protocol to handle concurrent executions. Next, we have showed how to transform a blind anonymous $(n, t)$-IBE into TPEOKS generically. Finally, we described a system architecture for real world application of TPEOKS.

During this work, we carefully justified all our design choices along the way, in particular the security model that allows composition of protocols and the IBE scheme considered, other schemes maybe considered in a future work. Furthermore, we will focus on new constructions in the UC framework since we already discussed how to extend our proposed protocol to this framework.

# References

1. Abdalla, M., Bellare, M., Catalano, D., Kiltz, E., Kohno, T., Lange, T., Malone-Lee, J., Neven, G., Paillier, P., Shi, H.: Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 205-222. Springer, Heidelberg (2005)

2. Boneh, D., Di Crescenzo, G., Ostrovsky, R., Persiano, G.: Public key encryption with keyword search. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 506-522. Springer, Heidelberg (2004)

3. Abdalla, M., Boyen, X., Chevalier, C., Pointcheval, D.: Distributed public-key cryptography from weak secrets. In: S. Jarecki and G. Tsudik (Eds.): PKC '09. LNCS, vol. 5443, pp. 139-159, Springer-Verlag, (2009)

4. Geisler, M., Smart N.: Distributing the Key Distribution Centre in Sakai Kasahara Based Systems. In: M.G. Parker (Eds.): Cryptography and Coding 2009, LNCS 5921, pp. 252262, 2009. Springer-Verlag Berlin Heidelberg (2009)

5. Boyen, X., Chevalier, C., Fuchsbauer, G., Pointcheval, D.: Strong cryptography from weak secrets: Building efficient pke and ibe from distributed passwords. In: Bernstein, Daniel and Lange, Tanja (Ed.): Africacrypt '10, volume 6055 of LNCS, pages 297-315. Springer-Verlag Berlin Heidelberg, (2010)

6. Kate, A., Goldberg I.: Distributed Private-Key Generators for Identity-Based Cryptography. In: J.A. Garay and R. De Prisco (Eds.): SCN 2010, LNCS 6280, pp. 436453, 2010. Springer-Verlag Berlin Heidelberg (2010)

7. Belenkiy, M., Chase, M., Kohlweiss, M., Lysyanskaya, A.: P-signatures and noninteractive anonymous credentials. In R. Canetti, editor, TCC. LNCS, vol. 4948, pp. 356-374. Springer, (2008)
8. Belenkiy, M., Chase, M., Kohlweiss, M., Lysyanskaya, A., Shacham, H.: Randomizable Proofs and Delegatable Anonymous Credentials. In Crypto 09, volume 5677 of LNCS, pp. 108–125. Springer, (2009)

9. Waters, B., Balfanz, D., Durfee, G., Smetters, D.: Building an Encrypted and Searchable Audit Log. In: Proc. of Network and Distributed System Security Symposium (NDSS 2004) (2004)

10. Camenisch, J., Kohlweiss M., Rial A., Sheedy C.: Blind and Anonymous Identity-Based Encryption and Authorised Private Searches on Public Key Encrypted Data. In: S. Jarecki and G. Tsudik (Eds.): PKC 2009, LNCS 5443, pp. 196-214, (2009)

11. Chow, S. M. : Removing Escrow from Identity-Based Encryption New Security Notions and Key Management Techniques. In: Jarecki, Stanislaw and Tsudik, Gene (Eds.): PKC 2009, LNCS 5443, pp. 256-276, 2009. Springer-Verlag Berlin Heidelberg (2009)

12. Wang, P., Wang, H., Pieprzyk J.: Threshold Privacy Preserving Keyword Searches. In: V. Geffert et al. (Eds.): SOFSEM 2008, LNCS 4910, pp. 646-658, 2008. Springer-Verlag Berlin Heidelberg (2008)

13. Canetti, R. : Security and Composition of Multiparty Cryptographic Protocols. In
: the Journal of Cryptology, 13(1):143-202, (2000)

14. Canetti, R. : Universally composable security : a new paradigm for cryptographic protocols. In FOCS, pages 136–145, (2001)

15. Boyen, X., Waters, B.: Anonymous hierarchical identity-based encryption (without random oracles). In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 290307. Springer, Heidelberg (2006)

16. Siad, A.: Anonymous Identity-Based encryption with distributed Private-Key generator and searchable encryption. In NTMS’2012 - Security Track, (2012)

17. Boneh,D., Franklin,M.: Identity-Based Encryption from the Weil Pairing. In:Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213-229. Springer, Hei- delberg (2001)

18. Y. Lindell and B. Pinkas. Secure multiparty computation for privacy-preserving data mining. Journal of Privacy and Confidentiality, 1(1), p. 59–98, (2009)

19. Gentry, C.: Practical identity-based encryption without random oracles. In: Vaudey, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 445-464. Springer, Heidelberg (2006)

20. Siad, A., Amara, M.: Anonymous Key Issuing Protocol for Distributed Sakai-Kasahara Identity-based Scheme. In ICN 2011, pages 35–40, (2011)

21. Prabhakaran, M., Rosulek, M. : Homomorphic Encryption with Chosen-Ciphertext Security. In: Aceto, L., Damgrd, I., Goldberg, L., Halldrsson, M., Inglfsdttir, A., Walukiewicz, I. (eds.): AUTOMATA, LANGUAGES AND PROGRAMMING . LNCS, vol. 5126, pp. 667–678. Springer, Heidelberg (2008)

22. Paillier, P. : Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, LNCS, vol. 1592, pages 223–238, (1999)

23. Green, M., Hohenberger, S.: Blind identity-based encryption and simulatable obliv-
ious transfer. In: Kurosawa, K. (eds.): ASIACRYPT 2007. LNCS, vol. 4833, pp.
265-282. Springer, Heidelberg (2007)

24. Goldreich, O.: Foundations of Cryptography: Volume 2 Basic Applications. Cam-
bridge University Press (2004)

25. Damgard, I., Nielsen, J. B.: Perfect hiding and perfect binding universally com-
posable commitment schemes with constant expansion factor. In Yung, M. (eds.):
Advances in Cryptology CRYPTO 02, LNCS, vol. 2442, pp. 3–42, (2002)