# Introduction to Attribute Based Searchable Encryption

Dalia Khader

► To cite this version:

Dalia Khader. Introduction to Attribute Based Searchable Encryption. 15th IFIP International Conference on Communications and Multimedia Security (CMS), Sep 2014, Aveiro, Portugal. pp.131-135, 10.1007/978-3-662-44885-4_11. hal-01404203

HAL Id: hal-01404203

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

Submitted on 28 Nov 2016

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Introduction to Attribute Based Searchable Encryption

Dalia Khader

daliakhader@googlemail.com

**Abstract.** An Attribute Based Searchable Encryption Scheme (ABSE) is a public key encryption with keyword search (PEKS) where each user owns a set of attributes, and the senders decide on a policy. The policy is a function of these attributes expressed as a predicate and determines, among the users of the system, who is eligible to decrypt and search the ciphertext. Only members who own sufficient attributes to satisfy that policy can send the server a valid search query. In our work we introduce the concept of a secure ABSE by defining the functionalities and the relevant security notions.

**Keywords:** PEKS, Attribute Based Encryption, Public Key Cryptography

## 1 Introduction

Searchable encryption (SE) is an encryption scheme that supports keyword based retrieval of documents. The main challenge of SE is to allow third parties to search the ciphertexts without giving them decrypting capabilities. This has been an active research area for more than a decade. Song et al. [5] proposed the first scheme that enables searchability in symmetric encryption while Boneh et al. [2] introduced a scheme for public key encryption with keyword search (PEKS).

Searchable encryption schemes assume that the user sending the search query owns the decryption key and that the sender has to know the identity of the user querying the data in order to encrypt using the corresponding encryption key. This raises the question, what if the encrypted data is shared between several receivers and is kept in a remote shared storage that is not trusted for confidentiality?

Attribute-Based Encryption (ABE) [4] addresses this problem. An ABE is a scheme in which each user is identified by a set of attributes, and some function of those attributes, the policy, is used to decide on decryption capabilities. The two types of ABE schemes are: key-policy and ciphertext-policy [3, 1].

This paper defines a new primitive attribute based searchable encryption (ABSE). In ABSE senders decide on a policy that determines user's eligibility not only for decrypting but also for searching the data. Unlike existing proposals in the literature [6], ours is based on a hybrid system of key and cipher policy which gives more flexibility, a strong security, and allows for multi-authorities.

## 2 Formal Definition of ABSE

To define an ABSE we introduce the five entities involved: a central authority *TTP* who sets up the system, a server *S* where all encrypted data is uploaded to. An encryptor *E* who uploads the data and sets the policy. The querier *Q* who wants to search the server and download documents. Many attribute authorities *AT* each responsible of a set of attributes and that give out private keys to users owning these attributes.
**Definition 1.** An Attribute Based Searchable Encryption Scheme consists of the following probabilistic polynomial time algorithms: **ABSE** := ($TSetup, AddUser, ASetup, AttG, PrdG, PrdVK, PrdQT, ABSE, TrpG, TEST$)

$TSetup(k) \to (PP, UMK)$ : Run by $\mathcal{TP}$ to set up the system. Takes a security parameter $k$ and outputs public parameters $PP$ and a user master key $UMK$ which is kept secret.

$AddUser(PP, UMK) \to (RK_i, SK_i)$ : Run by $\mathcal{TP}$ every time a user registers with the system. It outputs a registration key $RK_i$ that will be used to register with attribute authorities and servers. It outputs $SK_i$ that is secret to the user and will be used in creating trapdoors.

$ASetup(PP) \to (AMK_j, APK_j)$ : Run by $\mathcal{AT}$ to set up the attribute authority. It outputs an attribute master key $AMK_j$ which is secret to $\mathcal{AT}$ and is used to create attribute private keys when users register. It also outputs an attribute public key $APK_j$ which is used in building the policies and is public to all.

$AttG(RK_i, AMK_j) \to ASK_{i,j}$ : Run by $\mathcal{AT}$ to register a user $i$, and outputs an attribute private key $ASK_{i,j}$ that will be used in proving possession of attribute $j$.

$PrdG(\Psi, AP) \to (ST_\Psi, IT_\Psi)$ : Given a predicate $\Psi$ and a list of attribute public keys $AP = \{APK_j\}_{j=1}^m$, the algorithm generates a searching token $ST_\Psi$ that will be used in creating trapdoors and an indexing token $IT_\Psi$ used for creating searchable ciphertext.

$PrdVK(\Psi) \to VT_\Psi$ : Run by $S$. For each predicate in the system the server creates a verification token $VT_\Psi$ that is kept secret to the server.

$PrdQT(\Psi, VT_\Psi, RK_i, AP) \to QT_{i,\Psi}$ : Run by the $S$. Given a predicate verification token $VT_\Psi$ and a registration key $RK_i$, the server outputs a query token $QT_{i,\Psi}$ that allows the user $i$ to search for keywords encrypted under the predicate $\Psi$.

$ABSE(W, \Psi, IT_\Psi) \to E_{\Psi,W}$ : Run by $\mathcal{E}$. For a keyword $W$ and under token $IT_\Psi$ create a searchable ciphertext $E_{\Psi,W}$.

$TrpG(W, \Psi, QT_{i,\Psi}, ST_\Psi, SK_i, AS_i) \to T_{\Psi,W}$ : Run by $\mathcal{Q}$. Given a keyword, a query token, a searching token, a user secret key and a set of user private attribute keys $AS_i = \{ASK_{i,j}\}_{j=1}^m$, output a trapdoor $T_{\Psi,W}$.

$TEST(E_{\Psi,W}, T_{\Psi,W}, VT_\Psi, RK_i) \to \{0, 1\}$ : Run by the $S$. Given a searchable ciphertext, a trapdoor, a verification token and a registration key output 1 if the user satisfies the predicate and if the keyword is found, otherwise output 0.

**On The Security of ABSE** The security notions of an ABSE are: correctness, security against Attribute Based Chosen Keyword Attack (ACKA) and security against Attributes Forgeability Attacks (AFA). We need three game models to define these notions (See Figures 1(a), 1(b), 1(c)) where the adversary is given access to certain oracles and a trace of the responses is recorded. Both are explained below.

<table><tr><td>CUL</td><td>Corrupted Users</td><td>HUL</td><td>Honest Users</td><td>CRK</td><td>Corrupted RK<sub>i</sub></td></tr><tr><td>CRK</td><td>Corrupted RK<sub>i</sub></td><td>HA</td><td>Honest AT</td><td>CA</td><td>Corrupted AT</td></tr><tr><td>CASK</td><td>Revealed ASK<sub>i,j</sub></td><td>TrapL</td><td>Queried trapdoors</td><td>HASK</td><td>Non-revealed ASK<sub>i,j</sub></td></tr><tr><td>PredL</td><td>List of (ST<sub>Ψ</sub>, IT<sub>Ψ</sub>)</td><td>RQTL</td><td>Revealed QT<sub>i,Ψ</sub></td><td>QTL</td><td>Non-revealed QT<sub>i,Ψ</sub></td></tr><tr><td>VTL</td><td>Non-revealed VT<sub>Ψ</sub></td><td>RVTL</td><td>Revealed VT<sub>Ψ</sub></td><td></td><td></td></tr></table>

**AddUsr** : Adds user $i$ to the system by running AddUser, and adding $(RK_i, SK_i)$ to HUL.

**UsrCpt** : Corrupts user $i$ by revealing $(RK_i, SK_i)$ and adding them to CUL and CRK.

**RKCpt** : Partially corrupts user $i$ by revealing registration key $RK_i$ and adding it to CRK.

**AddAtt** : Adds an honest attribute authority $j$ to the system by running ASetup, computing $(APK_j, AMK_j)$ and publishing $APK_j$.

**AMKCpt** : Corrupts attribute authority $j$ by revealing $AMK_j$ and adding to CA.

**AddASK** : Runs AttG to compute $ASK_{i,j}$, and adds it to HASK.

**ASKCpt** : Corrupts an attribute private key by revealing $ASK_{i,j}$ and adding it to CASK.
**TrapO**: The challenger generates a trapdoor for certain keyword $W$ using a querying token $QT_{i,\Psi}$ and searchable token $ST_{\Psi}$ on behalf of user $i$ with set of attributes $AS_i$. The list *TrapL* is updated with all the information used as input and as output to the algorithm *TrpG*.

**AddPred**: Generates a searchable token and an indexing token $(ST_{\Psi}, IT_{\Psi})$ for predicate $\Psi$ by running *PrdG* and then updates the list *PredL*.

**AddVT**: Runs *PrdVK* to obtain a verification token $VT_{\Psi}$ and updates *VTL*.

**RevealVT**: Corrupting the verification token $VT_{\Psi}$ by revealing it and $RVTL$ is updated.

**AddQT**: Generates a querying token $QT_{i,\Psi}$ by running *PrdQT*, then *QTL* is updated.

**RevealQT**: The querying token $QT_{i,\Psi}$ of user $i$ and predicate $\Psi$ is revealed to the adversary and the list *RQTL* is updated.

**Chb**: Challenges the adversary to guess whether a trapdoor $T_b$ ($b \in \{0, 1\}$) was generated for keyword $W_0$ or $W_1$. The adversary chooses the predicate, the set of attributes and the user he would like to be challenged upon.

**Correctness of ABSE.** This property demands that if a searchable encryption $E_{\Psi,W}$ was produced correctly, i.e. using valid $IT_{\Psi}$ and if a trapdoor $T_{\Psi,W}$ was introduced correctly using valid $QT_{i,\Psi}$, $ST_{\Psi}$, $SK_i$, $AS_i$, then the *TEST* algorithm should return 1 if the predicate is satisfied $\Psi(AS_i) = 1$ and the keywords match $W = W'$, otherwise the *TEST* algorithm should return 0. Figure 1(a) explains the details. Formally, the ABSE is said to be correct if for a security parameter $k$ and all polynomial time adversaries $\mathcal{A}$ the following advantage is negligible: $\text{Adv}_{\mathcal{A}}^{\text{corr}}(k) = |\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{corr}}(k) = 1]|$

**Attribute based Chosen Keyword Attacks.** We define security for an ABSE in the sense of semantic-security. The aim is to ensure that an encryption *ABSE* does not reveal any information about keyword *W* except to a *Q* who satisfies the policy and can create trapdoors. We define the security against an active attackers *A* whose given access to a set of oracles shown in Figure 1(b). Let the advantage of winning the game be defined as follows: $\text{Adv}_{\mathcal{A}}^{\text{ACKA}}(k) = |\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{ACKA}_0}(k) = 1] - \text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{ACKA}_1}(k) = 1]|$
An ABSE scheme is said to be secure against an ACKA if for a given security parameter $k$ and all polynomial time adversary $\mathcal{A}$ the advantage $\text{Adv}_{\mathcal{A}}^{\text{ACKA}}(k)$ is negligible.

**Attribute Forgeability Attack.** This security notion captures forgeability of trapdoors where the adversary can produce a trapdoor without having the sufficient attribute set that satisfies the predicate $\Psi$. The adversary is given access to the oracles described in Figure 1(c). The challenge is to produce a pair of searchable encryption $E_{\Psi'}^*$ and trapdoor $T_{\Psi'}^*$, under predicate $\Psi'$ such that the *TEST*($E_{\Psi'}^*$, $T_{\Psi'}^*$, $VT_{\Psi'}$, $RK_i'$) outputs 1 for a given $RK_i'$. The definition includes coalition of attributes. Formally, an ABSE scheme is said to be secure against an AFA if for a security parameter $k$ and all polynomial time adversaries $\mathcal{A}$ the following advantage is negligible: $\text{Adv}_{\mathcal{A}}^{\text{AFA}}(k) = |\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{AFA}}(k) = 1]|$

## 3 Conclusion

We define a new ABSE scheme and the security notions required. A working construction and security proofs are provided in a full version of this paper.
Experiment Exp<sub>A</sub><sup>con</sup>(k):

* (PP,UMK) ← TSetup(k)

* HUL, HA, PredL, HASK, QTL, VTL = φ

* (SKᵢ, RKᵢ, ASᵢ, QTᵢ,Ψ, STΨ, ITΨ) ← A(PP : AddUser(.), AddAtt(.), AddASK(.,.), AddPred(.,.), AddQT(.,.), AddVT(.))

* If [(SKᵢ, RKᵢ) ∉ HUL] ∨ [∃j ∈ Ψ s.t. (AMKⱼ, APKⱼ) ∉ HA] ∨ [∃j ∈ ASᵢ s.t. (ASKᵢⱼ) ∉ HASK] ∨ [VTΨ ∉ VTL]: Return 0

* ABSE(W, ITΨ) → EΨ,W: TrpG(W', QTᵢ,Ψ, STΨ, SKᵢ, ASᵢ) → TΨ,W

* If [[Ψ(ASᵢ) ≠ 1] ∨ [W ≠ W')] ∧ [TEST(EΨ,W, TΨ,W, VTΨ, RKᵢ) = 0] : Return 1

* If [[Ψ(ASᵢ) = 1] ∧ [W = W]] ∧ [TEST(EΨ,W, TΨ,W, VTΨ, RKᵢ) = 1] : Return 1

* Else Return 0

(a) Correctness Game Model

Experiment Exp<sub>A</sub><sup>ACKA</sup>(k):

* (PP,UMK) ← TSetup(k)

* CUL, HUL, CRK, HA, CA, CASK, HASK, TrapL, PredL, QTL, RQTL, RVTL, VTL = φ

* $\tilde{b} \leftarrow A(\mathit{PP} : \mathit{User}(.), \mathit{RKCpt}(.), \mathit{AMKCpt}(.), \mathit{ASKCpt}(.,.), \mathit{RevealQT}(.,.), \mathit{AddVT}(.), \mathit{RevealVT}(.), \mathit{TrapO}(.,.,.,.), \mathit{AddUser}(.), \mathit{AddAtt}(.), \mathit{AddPred}(.,.), \mathit{AddQT}(.,.), \mathit{AddASK}(.,.), \mathit{Ch}(.,.,.,.,))$

* Return $\tilde{b}$

(b) Security against ACKA

Experiment Exp<sub>A</sub><sup>AFA</sup>(k):

* (PP,UMK) ← TSetup(k)

* CUL, HUL, CRK, HA, CA, CASK, HASK, TrapL, PredL, QTL, RQTL, RVTL, VTL = φ

* $(T_{\Psi'}^*, E_{\Psi'}^*, \Psi', RK'_i) \leftarrow A(\mathit{PP} : \mathit{UserCpt}(.), \mathit{RKCpt}(.), \mathit{AMKCpt}(.), \mathit{ASKCpt}(.,.), \mathit{RevealQT}(.,.), \mathit{AddVT}(.), \mathit{RevealVT}(.), \mathit{TrapO}(.,.,.,.), \mathit{AddUser}(.), \mathit{AddAtt}(.), \mathit{AddPred}(.,.), \mathit{AddQT}(.,.), \mathit{AddASK}(.,.))$

* If [TEST(E<sub>Ψ'</sub><sup>*</sup>, T<sub>Ψ'</sub><sup>*</sup>, VT<sub>Ψ'</sub><sup>*</sup>, RK<sub>i</sub><sup>*</sup>) = 0] ∨ [Ψ' ⊆ CA] ∨ [T<sub>Ψ'</sub><sup>*</sup> ∈ TrapL] ∨ [[VT<sub>Ψ'</sub><sup>*</sup> ∈ RVTL] ∧ [∀j ∈ Ψ', j ∈ CASK ∪ CA]] ∨ [[VT<sub>Ψ'</sub><sup>*</sup> ∉ RVTL] ∧ [∃i s.t. ∀j ∈ AS<sub>i</sub>, j ∈ CASK<sub>i</sub> ∪ CA and RK<sub>i</sub><sup>*</sup> = RK<sub>i</sub>]] : Return 0

* Else Return 1

(c) Security against AFA

References

1. J. Bethencourt, A. Sahai, and B. Waters. Ciphertext-policy attribute-based encryption. In *IEEE SSP'07*, pages 321–334.

2. D. Boneh, G. D. Crescenzo, R. Ostrovsky, and G. Persiano. Public key encryption with keyword search. In *EUROCRYPT'04*, pages 506–522.

3. V. Goyal, O. Pandey, A. Sahai, and B. Waters. Attribute-based encryption for fine-grained access control of encrypted data. In *ACM CCS'06*, pages 89–98.

4. A. Sahai and B. Waters. Fuzzy identity-based encryption. In *EUROCRYPT'05*. LNCS.

5. D. X. Song, D. Wagner, and A. Perrig. Practical techniques for searches on encrypted data. In *SSP'00*. IEEE.

6. Q. Zheng, S. Xu, and G. Ateniese. Vabks: Verifiable attribute-based keyword search over outsourced encrypted data. *IACR ePrint*.