SCIENCE CHINA Information Sciences, Volume 60, Issue 12: 122105(2017) https://doi.org/10.1007/s11432-016-0540-x

VKSE-MO: verifiable keyword search over encrypted data in multi-owner settings

More info
  • ReceivedSep 30, 2016
  • AcceptedNov 24, 2016
  • PublishedApr 24, 2017


Searchable encryption (SE) techniques allow cloud clients to easily store data and search encrypted data in a privacy-preserving manner, where most of SE schemes treat the cloud server as honest-but-curious. However, in practice, the cloud server is a semi-honest-but-curious third-party, which only executes a fraction of search operations and returns a fraction of false search results to save its computational and bandwidth resources. Thus, it is important to provide a results verification method to guarantee the correctness of the search results. Existing SE schemes allow multiple data owners to upload different records to the cloud server, but these schemes have very high computational and storage overheads when applied in a different but more practical setting where each record is co-owned by multiple data owners. To address this problem, we develop a verifiable keyword search over encrypted data in multi-owner settings (VKSE-MO) scheme by exploiting the multisignatures technique. Thus, our scheme only requires a single index for each record and data users are assured of the correctness of the search results in challenging settings. Our formal security analysis proved that the VKSE-MO scheme is secure against a chosen-keyword attack under a random oracle model. In addition, our empirical study using a real-world dataset demonstrated the efficiency and feasibility of the proposed scheme in practice.


This work was supported by National High Technology Research and Development Program (863 Program) (Grant No. 2015AA016007), National Nature Science Foundation of China (Grant Nos. 61303221, 61472310, 61370078, 61309016), Science Foundation of Two sides of Strait (Grant Nos. U1405255, U1135002), and Shaanxi Science & Technology Coordination & Innovation Project (Grant No. 2016TZC-G-6-3).

  • Figure 1

    Settings considered by various schemes. (a) Settings in our scheme; (b) settings in previous SE schemes.

  • Figure 2

    (Color online) System model of our scheme.

  • Figure 3

    Example of an index structure.

  • Figure 5

    (Color online) Computational costs. (a) Trapalgorithm; (b) Searchalgorithm.

  • Figure 6



    Algorithm 1 Ciphertext generation algorithm

    Require:File set $F=\{f_{i}\}_{1\leq i\leq n}$, identity set ${\rm ID}=\{{\rm id}_{i}\}_{1\leq i\leq n}$, keyword set $W=\{w_{j}\}_{1\leq j\leq m}$;

    Output:Ciphertext set $C$, signature set Sig, index set $I$.

    Given ${\rm sk}_{\mathcal{O}_{t} },{\rm pk}_{S},{\rm pk}_{u},{\rm PK}$;

    for $1\leq i\leq n$

    Encrypt $f_{i}$ as $c_{i}$ using PK; /$\ast$ use the public key PK $\ast$/

    Generate signature ${\rm sig}_{i}$ for $f_{i}$; /$\ast$ use the secret keys $\{{\rm sk}_{\mathcal{O}_{t} }\}$ of multiple DOs $\ast$/

    end for

    Return Ciphertext set $C=\{c_{i},\ldots,c_{n}\}$, signature set ${\rm Sig}=\{{\rm sig}_{1},\ldots,{\rm sig}_{n}\}$;

    for $1\leq j\leq m$

    Build index $I_{w_{j} }=\{I_{1},I_{2},I_{3},I_{4}\}$; /$\ast$ use the public keys $({\rm pk}_{S},{\rm pk}_{u})$ of cloud server and DU $\ast$/

    end for

    Return index set $I=\{I_{w_{1} },\ldots,I_{w_{m} }\}$;

    Send $(C,I,{\rm Sig})$ to CSP.


    Algorithm 2 Ciphertext search algorithm

    Require:Search token $T_{w'}=\{T_{w',1},T_{w',2}\}$, index set $I=\{I_{w}|w\in W\}$, public/secret key pair $({\rm pk}_{S},{\rm sk}_{S})$, ciphertext set $C=\{c_{i}\}_{1\leq i\leq n}$;

    Output:Search results $C'_{w'}$ and corresponding identity set ${\rm ID}'_{w'}$.

    Index $I_{w_{j} }=\{I_{1},I_{2},I_{3},I_{4}\}$ for each keyword $w_{j}\in W$;

    for $1\leq j\leq m$

    Compute $\gamma'=H_{2}(e(I_{1},b)^{z})$;

    Check $e(I_{2}^{\gamma'},T_{w',2})I_{3}^{T_{w',1} }\stackrel{?}{=}I_{4}$ (1);

    if Eq. (1) holds then

    Output $C_{w_{j} }=C'_{w'}$, ${\rm ID}_{w_{j} }={\rm ID}'_{w'}$; /$\ast$ Eq. (1) holds, then $w_{j}=w'$ $\ast$/


    Output $\bot$;

    end if

    end for

    Return $C'_{w'}=\{c'_{j}\}_{1\leq j\leq \#C'_{w'} }$, ${\rm ID}'_{w'}=\{{\rm id}'_{j}\}_{1\leq j\leq \#C'_{w'} }$; /$\ast$ Return the ciphertext that contains $w'$ $\ast$/

    Send $C'_{w'}$, ${\rm ID}'_{w'}$ to PAS.


    Algorithm 3 Results verification algorithm

    Require:Signature set ${\rm Sig}=\{{\rm sig}_{1},\ldots,{\rm sig}_{n}\}$, search results $C'_{w'}=\{c'_{j}\}_{1\leq j\leq \#C'_{w'} }$, identity set ${\rm ID}'_{w'}=\{{\rm id}'_{j}\}_{1\leq j\leq \#C'_{w'} }$;

    Output:“Accept" or “Reject".

    Send challenge information $\{\tau_{j}\}_{1\leq j\leq \#C'_{w'} }$ to CSP;

    for $1\leq j\leq \#C'_{w'}$

    Compute $\mu=\sum_{j=1}^{\#C'_{w'} }\tau_{j}H_{2}(c'_{j})$;

    Compute $\nu=\prod_{j=1}^{\#C'_{w'} }({\rm sig}'_{j})^{\tau_{j} }$;

    Send $\{\mu,\nu\}$ to PAS; /$\ast$ Proof information returned by cloud server $\ast$/

    Compute $\prod_{j=1}^{\#C'_{w'} }H_{1}({\rm id}'_{j})^{\tau_{j} }$;

    end for

    for $1\leq t\leq s$

    Compute $\prod_{t=1}^{s}g^{x_{t} }$;

    end for

    Check $e(\nu,g)\stackrel{?}{=}e(\prod_{j=1}^{\#C'_{w'} }H_{1}({\rm id}'_{j})^{\tau_{j} }\cdot g^{\mu},\prod_{t=1}^{s}g^{x_{t} })$ (2);

    if Eq. (2) holds then

    Output “Accept"; /$\ast$ Cloud server returns the correct search results $\ast$/


    Output “Reject"; /$\ast$ Cloud server returns the false search results $\ast$/

    end if

    Send the correct search results to DU.

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有