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).


[1] Xia Z, Wang X, Zhang L. A Privacy-Preserving and Copy-Deterrence Content-Based Image Retrieval Scheme in Cloud Computing. IEEE TransInformForensic Secur, 2016, 11: 2594-2608 CrossRef Google Scholar

[2] Li Q, Ma J, Li R. Secure, efficient and revocable multi-authority access control system in cloud storage. Comp Security, 2016, 59: 45-59 CrossRef Google Scholar

[3] Li H W, Liu D X, Dai Y S, et al. Engineering searchable encryption of mobile cloud networks: when QoE meets QoP. IEEE Wirel Commun, 2015, 22: 74--80. Google Scholar

[4] Fu Z J, Sun X M, Ji S, et al. Towards efficient content-aware search over encrypted outsourced data in cloud. In: Proceedings of Annual IEEE International Conference on Computer Communications, San Francisco, 2016. 1--9. Google Scholar

[5] li , Liu D, Dai Y. Personalized Search over Encrypted Data with Efficient and Secure Updates in Mobile Clouds. IEEE Trans Emerg Top Comput, 2015, : 1-1 CrossRef Google Scholar

[6] Song D X, Wagner D, Perrig A. Practical techniques for searches on encrypted data. In: Proceedings of IEEE Symposium on Security and Privacy, California, 2000. 44--55. Google Scholar

[7] Boneh D, Crescenzo G D, Ostrovsky R, et al. Public key encryption with keyword search. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, 2004. 506--522. Google Scholar

[8] Miao Y, Ma J, Liu Z. Revocable and anonymous searchable encryption in multi-user setting. Concurrency Computat-Pract Exper, 2016, 28: 1204-1218 CrossRef Google Scholar

[9] Chai Q, Gong G. Verifiable symmetric searchable encryption for semi-honest-but-curious cloud servers. In: Proceedings of IEEE International Conference on Communications, Ottawa, 2012. 917--922. Google Scholar

[10] Zheng Q J, Xu S H, Ateniese G. VABKS: verifiable attribute-based keyword search over outsourced encrypted data. In: Proceedings of IEEE Conference on Computer Communications, Toronto, 2014. 522--530. Google Scholar

[11] Sun W H, Liu X F, Lou W J, et al. Catch you if you lie to me: Efficient verifiable conjunctive keyword search over large dynamic encrypted cloud data. In: Proceedings of IEEE Conference on Computer Communications, Kowloon, 2015. 2110--2118. Google Scholar

[12] Fu Z, Shu J, Sun X. Smart cloud search services: verifiable keyword-based semantic search over encrypted cloud data. IEEE Trans Consumer Electron, 2014, 60: 762-770 CrossRef Google Scholar

[13] Cheng R, Yan J B, Guan C W, et al. Verifiable searchable symmetric encryption from indistinguishability obfuscation. In: Proceedings of ACM Symposium on Information, Computer and Communications Security, Singapore, 2015. 621--626. Google Scholar

[14] Li T, Liu Z L, Li P, et al. Verifiable searchable encryption with aggregate keys for data sharing in outsourcing storage. In: Proceedings of Australasian Conference on Information Security and Privacy, Melbourne, 2016. 153--169. Google Scholar

[15] Sun W, Yu S, Lou W. Protecting Your Right: Verifiable Attribute-Based Keyword Search with Fine-Grained Owner-Enforced Search Authorization in the Cloud. IEEE Trans Parallel Distrib Syst, 2016, 27: 1187-1198 CrossRef Google Scholar

[16] Li J G, Lin Y P, Wen M, et al. Secure and verifiable multi-owner ranked-keyword search in cloud computing. In: Proceedings of International Conference on Wireless Algorithms, Systems, and Applications, Qufu, 2015. 325--334. Google Scholar

[17] Zhang W, Lin Y, Xiao S. Privacy Preserving Ranked Multi-Keyword Search for Multiple Data Owners in Cloud Computing. IEEE Trans Comput, 2016, 65: 1566-1577 CrossRef Google Scholar

[18] Lu S, Ostrovsky R, Sahai A. Sequential Aggregate Signatures, Multisignatures, and Verifiably Encrypted Signatures Without Random Oracles. J Cryptol, 2013, 26: 340-373 CrossRef Google Scholar

[19] Ren Y J, Shen J, Wang J, et al. Mutual verifiable provable data auditing in public cloud storage. J Int Tech, 2015, 16: 317--323. Google Scholar

[20] Wang B, Li H, Liu X. Efficient public verification on the integrity of multi-owner data in the cloud. J Commun Netw, 2014, 16: 592-599 CrossRef Google Scholar

[21] Chen R M, Mu Y, Yang G M, et al. Dual-server public-key encryption with keyword search for secure cloud storage. IEEE Trans Inf Foren Secur, 2016, 11: 789--798. Google Scholar

[22] Wang W, Xu P, Li H. Secure hybrid-indexed search for high efficiency over keyword searchable ciphertexts. Future Generation Comp Syst, 2016, 55: 353-361 CrossRef Google Scholar

[23] Yang Y, Ma M D. Conjunctive keyword search with designated tester and timing enabled proxy re-encryption function for E-health clouds. IEEE Trans Inf Foren Secur, 2016, 11: 746--759. Google Scholar

[24] Xia Z, Wang X, Sun X. A Secure and Dynamic Multi-Keyword Ranked Search Scheme over Encrypted Cloud Data. IEEE Trans Parallel Distrib Syst, 2016, 27: 340-352 CrossRef Google Scholar

[25] Fu Z J, Sun X M, Liu Q, et al. Achieving efficient cloud search services: multi-keyword ranked search over encrypted cloud data supporting parallel computing. IEICE Trans, 2015, 98: 190--200. Google Scholar

[26] Fu Z, Ren K, Shu J. Enabling Personalized Search over Encrypted Outsourced Data with Efficiency Improvement. IEEE Trans Parallel Distrib Syst, 2016, 27: 2546-2559 CrossRef Google Scholar

[27] Fu Z, Wu X, Guan C. Toward Efficient Multi-Keyword Fuzzy Search Over Encrypted Outsourced Data With Accuracy Improvement. IEEE TransInformForensic Secur, 2016, 11: 2706-2716 CrossRef Google Scholar

[28] Li H, Yang Y, Luan T H. Enabling Fine-Grained Multi-Keyword Search Supporting Classified Sub-Dictionaries over Encrypted Cloud Data. IEEE Trans Dependable Secure Comput, 2016, 13: 312-325 CrossRef Google Scholar

[29] Li H, Liu D, Dai Y. Enabling Efficient Multi-Keyword Ranked Search Over Encrypted Mobile Cloud Data Through Blind Storage. IEEE Trans Emerg Top Comput, 2015, 3: 127-138 CrossRef Google Scholar

[30] Layouni M, Yoshida M, Okamura S. Efficient multi-authorizer accredited symmetrically private information retrieval. In: Proceedings of International Conference on Information and Communications Security, Birmingham, 2008. 387--402. Google Scholar

[31] Attrapadung N, Libert B, Panafieu E D. Expressive key-policy attribute-based encryption with constant-size ciphertexts. In: Proceedings of International Conference on Practice and Theory in Public Key Cryptography, Taormina, 2011. 90--108. Google Scholar

  • 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 6

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

  • Figure 7



    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.

  • Table 1   Comparison of the functionalities of various schemes
    Scheme Keyword search Result verification Multi-owner setting
    VABKS [10] Yes Yes No
    VCKS [11] Yes Yes No
    Re-dtPECK [23] Yes No No
    ABKS-UR [15] Yes Yes No
    VKSE-MO Yes Yes Yes

    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.

  • Table 2   Notation definitions
    Symbol Description Symbol Description
    $F=\{f_{i}\}_{1\leq~i\leq~n}$ Data file set $T_{w}$ Trapdoor for $w\in~W$
    ${\rm~ID}=\{{\rm~id}_{i}\}_{1\leq~i\leq~n}$ Identity set for $F$ $C_{w}=\{c_{j}\}_{1\leq~j\leq~\#C_{w}}$ Results containing $w\in~W$
    $C=\{c_{i}\}_{1\leq~i\leq~n}$ Ciphertext set for $F$ $\#C_{w}$ Number of ciphertext in $C_{w}$
    $W=\{w_{j}\}_{1\leq~j\leq~m}$ Keyword set ${\rm~ID}_{w}=\{{\rm~id}_{j}\}_{1\leq~j\leq~\#C_{w}}$ Identity set of $C_{w}$
    $I_{w}$ Index for $w\in~W$ ${\rm~Sig}=\{{\rm~sig}_{i}\}_{1\leq~i\leq~n}$ Signature set for $F$
    $I$ Index set for $W$ ${\rm~sig}_{i}=\{{\rm~sig}_{t,i}\}_{1\leq~t\leq~s}$ DOs signature set for $f_{i}$

    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.

  • Table 3   Computational complexity of different algorithms in the two schemes
    Different algorithm VKSE-MO scheme ABKS-UR [15] scheme
    KeyGen $(2s+1+|\mathcal{U}|)E$ $(2|\mathcal{U}|+2|\mathcal{N}|+1)E$
    Enc $(2m+2n+4)E+n\mathcal{O}_{H_{1}}+3P$ $n(|\mathcal{N}|+2)E$
    Trap $(R+1)E$ $(2|\mathcal{N}|+1)E$
    Search $(2+R)E+(1+R)P$ $(|\mathcal{N}|+1)P+E$
    Verify $(1+\#C_{w})E+2P+\#C_{w}\mathcal{O}_{H_{1}}$ Not considerated

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

京ICP备18024590号-1       京公网安备11010102003388号