谓词加密是在基于身份加密的基础上发展起来的一种表达力更广泛的公钥加密，可在保护数据隐私的同时对数据进行细粒度访问控制。但目前已存的谓词加密方案效率较低，且针对具体问题的丰富性研究不足，难以满足现实需求。因此，本文面向以下两个特定隐私保护场景的需求，对谓词加密的丰富性扩展、效率提高等方面进行了详细研究：

（1）在保护隐私的数据整合场景中，若数据库B满足条件：数据库A的属性集合与自己的属性集合互补，则可访问数据库A的加密数据并获得其具体内容，从而合并两个数据库，得到一个完整的数据库。然而之前的谓词加密方案谓词表达力不够丰富，不可处理该场景。为解决该问题，本文利用拉格朗日插值与压缩技术设计了一个集合互补谓词加密（Complementary set predicate encryption，CSPE）方案，并将之应用于保护隐私的数据整合。该方案是第一个可解决集合互补问题的谓词加密，弥补了已存谓词加密表达丰富性的不足，且达到了常数大小的密文和私钥，效率较高。

（2）在疫情爆发后的保护隐私的接触者追踪场景中，若防疫中心满足条件：用户的二维时空（时间和位置）数据形成的轨迹集合与确诊者的二维时空轨迹集合的交集非空，则可访问用户的加密数据并获得其私人信息，从而及时通知该用户。另外，该场景中用户的时空数据大多贮存于资源有限的轻量级设备中，比如手机。然而先前能处理该问题的谓词加密方案需要至少线性大小的密文或私钥，即所需存储量较大，不适合贮存能力有限的轻量级设备。为解决该问题，本文利用确定性私钥和一个映射技术设计了一个非空交集谓词加密（Non-empty intersection predicate encryption，NEIPE）方案，并将之应用于保护隐私的接触者追踪。该方案实现了常数大小的密文和私钥，相比于已存方案，更适用于贮存能力有限的轻量级设备。

Predicate encryption is a more expressive public key encryption that evolved from identity-based encryption, which can perform fine-grained access control to data while protecting data privacy. However, the existing predicate encryption schemes are inefficient, and the expression of research on specific problems is insufficient, so it is difficult to meet the practical requirements. Therefore, this paper conducts detailed studies on the expression extension and efficiency improvement of predicate encryption for the requirements of the following two specific privacy-preserving scenarios:

 (1) In the privacy-preserving data consolidation scenario, if database B satisfies the condition: the attribute set of database A is complementary to its own, the encrypted data of database A can be accessed and the specific content can be obtained, thereby consolidating the two databases to obtain a complete database. However, the previous predicate encryption schemes are not expressive enough to handle this scenario. To solve this problem, this paper designs a complementary set predicate encryption (CSPE) scheme using Lagrangian interpolation and compression technology, and applies it to privacy-preserving data consolidation. This scheme is the first predicate encryption that can solve the set complementarity problem, which makes up for the lack of expression of the existing predicate encryption, and is efficient due to a constant size of ciphertext and private key.

(2) In the privacy-preserving contact tracing scenario after the outbreak, if the epidemic prevention center satisfies the condition: the intersection of the trajectory set formed by the user’s two-dimension spatiotemporal (time and location) data and the two-dimension spatiotemporal trajectory set of the diagnosed person is not empty, then prevention center can access to the user’s encrypted data and obtain their private information, allowing timely notification of the user. In addition, most of the spatiotemporal data of users in this scenario are stored in storage-limited lightweight devices, such as mobile phones. However, previous predicate encryption schemes that can handle this problem require at least a linear size of ciphertext or private key, namely, require a large amount of storage and are not suitable for storage-limited lightweight devices. To solve this problem, this paper designs a non-empty intersection predicate encryption (NEIPE) scheme using deterministic private keys and a mapping technique, and applies it to privacy-preserving contact tracing. This scheme realizes constant-sized ciphertext and private key, so it is more suitable for storage-limited lightweight devices than existing schemes.

[1] Diffie W, Hellman M. New directions in cryptography[J]. IEEE transactions on Information Theory, 1976, 22(6): 644-654.

[2] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120-126.

[3] ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE transactions on information theory, 1985, 31(4): 469-472.

[4] Koblitz N. Elliptic curve cryptosystems[J]. Mathematics of computation, 1987, 48(177): 203-209.

[5] Katz J, Sahai A, Waters B. Predicate encryption supporting disjunctions, polynomial equations, and inner products[C]//annual international conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 2008: 146-162.

[6] Boneh D, Sahai A, Waters B. Functional encryption: Definitions and challenges[C]//Theory of Cryptography Conference. Springer, Berlin, Heidelberg, 2011: 253-273.

[7] Shamir A. Identity-based cryptosystems and signature schemes[C]//Workshop on the theory and application of cryptographic techniques. Springer, Berlin, Heidelberg, 1984: 47-53.

[8] Boneh D, Franklin M. Identity-based encryption from the Weil pairing[C]//Annual international cryptology conference. Springer, Berlin, Heidelberg, 2001: 213-229.

[9] Canetti R, Halevi S, Katz J. A forward-secure public-key encryption scheme[C]//International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2003: 255-271.

[10] Boneh D, Boyen X. Efficient selective-ID secure identity-based encryption without random oracles[C]//International conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 2004: 223-238.

[11] Boneh D, Boyen X. Secure identity based encryption without random oracles[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2004: 443-459.

[12] Waters B. Efficient identity-based encryption without random oracles[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2005: 114-127.

[13] Boyen X, Waters B. Anonymous hierarchical identity-based encryption (without random oracles)[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2006: 290-307.

[14] Gentry C. Practical identity-based encryption without random oracles[C]//Annual international conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 2006: 445-464.

[15] Zhang Xinfang, Xu Qiuliang. Anonymous Identity-based Encryption[C]//中国通信学会第五届学术年会论文集. 电子工业出版社, 2008: 356-361.

[16] Park J H. Efficient hidden vector encryption for conjunctive queries on encrypted data[J]. IEEE Transactions on Knowledge and Data Engineering, 2010, 23(10): 1483-1497.

[17] 李顺东, 杨坤伟, 巩林明, 毛庆, 刘新. 标准模型下可公开验证的匿名IBE方案[J]. 电子学报, 2016, 44(03): 673-678.

[18] 杨启良, 周彦伟, 杨坤伟, 王涛. 标准模型下可公开验证的匿名IBE方案的安全性分析[J]. 电子学报, 2020, 48(02): 291-295.

[19] Zhao X, Cao Z, Dong X, et al. Anonymous IBE from quadratic residuosity with fast encryption[C]//International Conference on Information Security. Springer, Cham, 2020: 3-19.

[20] Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions[C]//Proceedings of the fortieth annual ACM symposium on Theory of computing. 2008: 197-206.

[21] Cash D, Hofheinz D, Kiltz E. How to delegate a lattice basis[J]. Cryptology ePrint Archive, 2009.

[22] Dutta P, Susilo W, Duong D H, et al. Puncturable Identity-Based Encryption from Lattices[C]//Australasian Conference on Information Security and Privacy. Springer, Cham, 2021: 571-589.

[23] Boneh D, Gentry C, Waters B. Collusion resistant broadcast encryption with short ciphertexts and private keys[C]//Annual international cryptology conference. Springer, Berlin, Heidelberg, 2005: 258-275.

[24] Delerablée C. Identity-based broadcast encryption with constant size ciphertexts and private keys[C]//International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2007: 200-215.

[25] Maiti S, Misra S. P2B: Privacy preserving identity-based broadcast proxy re-encryption[J]. IEEE Transactions on Vehicular Technology, 2020, 69(5): 5610-5617.

[26] Wu L, Yang X, Zhang M, et al. New identity based proxy re-encryption scheme from lattices[J]. China Communications, 2019, 16(10): 174-190.

[27] Dutta P, Susilo W, Duong D H, et al. Collusion-resistant identity-based proxy re-encryption: lattice-based constructions in standard model[J]. Theoretical Computer Science, 2021, 871: 16-29.

[28] Kumar M, Chand S, Katti C P. A secure end-to-end verifiable internet-voting system using identity-based blind signature[J]. IEEE Systems Journal, 2020, 14(2): 2032-2041.

[29] Zhu H, Wang Y, Wang C, et al. An efficient identity-based proxy signcryption using lattice[J]. Future Generation Computer Systems, 2021, 117: 321-327.

[30] Sahai A, Waters B. Fuzzy identity-based encryption[C]//Annual international conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 2005: 457-473.

[31] Goyal V, Pandey O, Sahai A, et al. Attribute-based encryption for fine-grained access control of encrypted data[C]//Proceedings of the 13th ACM conference on Computer and communications security. 2006: 89-98.

[32] Bethencourt J, Sahai A, Waters B. Ciphertext-policy attribute-based encryption[C]//2007 IEEE symposium on security and privacy (SP'07). IEEE, 2007: 321-334.

[33] Cheung L, Newport C. Provably secure ciphertext policy ABE[C]//Proceedings of the 14th ACM conference on Computer and communications security. 2007: 456-465.

[34] Goyal V, Jain A, Pandey O, et al. Bounded ciphertext policy attribute based encryption[C]//International Colloquium on Automata, Languages, and Programming. Springer, Berlin, Heidelberg, 2008: 579-591.

[35] Liang X, Cao Z, Lin H, et al. Provably secure and efficient bounded ciphertext policy attribute based encryption[C]//Proceedings of the 4th international symposium on information, computer, and communications security. 2009: 343-352.

[36] Waters B. Ciphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization[C]//International workshop on public key cryptography. Springer, Berlin, Heidelberg, 2011: 53-70.

[37] Lewko A, Waters B. New proof methods for attribute-based encryption: Achieving full security through selective techniques[C]//Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2012: 180-198.

[38] Zhou Z, Huang D. On efficient ciphertext-policy attribute based encryption and broadcast encryption[C]//Proceedings of the 17th ACM conference on Computer and communications security. 2010: 753-755.

[39] Zhang Y, Zheng D, Chen X, et al. Computationally efficient ciphertext-policy attribute-based encryption with constant-size ciphertexts[C]//International Conference on Provable Security. Springer, Cham, 2014: 259-273.

[40] Herranz J, Laguillaumie F, Ràfols C. Constant size ciphertexts in threshold attribute-based encryption[C]//International Workshop on Public Key Cryptography. Springer, Berlin, Heidelberg, 2010: 19-34.

[41] Susilo W, Yang G, Guo F, et al. Constant-size ciphertexts in threshold attribute-based encryption without dummy attributes[J]. Information Sciences, 2018, 429: 349-360.

[42] Guo F, Mu Y, Susilo W, et al. CP-ABE with constant-size keys for lightweight devices[J]. IEEE transactions on information forensics and security, 2014, 9(5): 763-771.

[43] Odelu V, Das A K, Rao Y S, et al. Pairing-based CP-ABE with constant-size ciphertexts and secret keys for cloud environment[J]. Computer Standards & Interfaces, 2017, 54: 3-9.

[44] Xu S, Yang G, Mu Y. Revocable attribute-based encryption with decryption key exposure resistance and ciphertext delegation[J]. Information Sciences, 2019, 479: 116-134.

[45] 汪倩倩, 欧毓毅. 可追踪且可撤销的基于OBDD访问结构的CP-ABE方案[J]. 计算机应用研究, 2021, 38(04): 1185-1189.

[46] Zhang Y, Zheng D, Deng R H. Security and privacy in smart health: Efficient policy-hiding attribute-based access control[J]. IEEE Internet of Things Journal, 2018, 5(3): 2130-2145.

[47] 王悦, 樊凯. 隐藏访问策略的高效CP-ABE方案[J]. 计算机研究与发展, 2019, 56(10): 2151-2159.

[48] Ohtake G, Safavi-Naini R, Zhang L F. Outsourcing scheme of ABE encryption secure against malicious adversary[J]. Computers & Security, 2019, 86: 437-452.

[49] 杨贺昆, 冯朝胜, 晋云霞, 王蔺, 罗王平, 邓红辉. 支持可验证加解密外包的CP-ABE方案[J]. 电子学报, 2020, 48(08): 1545-1551.

[50] Ostrovsky R, Sahai A, Waters B. Attribute-based encryption with non-monotonic access structures[C]//Proceedings of the 14th ACM conference on Computer and communications security. 2007: 195-203.

[51] Lewko A, Sahai A, Waters B. Revocation systems with very small private keys[C]//2010 IEEE Symposium on Security and Privacy. IEEE, 2010: 273-285.

[52] Attrapadung N, Libert B, Panafieu E. Expressive key-policy attribute-based encryption with constant-size ciphertexts[C]//International workshop on public key cryptography. Springer, Berlin, Heidelberg, 2011: 90-108.

[53] Yamada S, Attrapadung N, Hanaoka G, et al. A framework and compact constructions for non-monotonic attribute-based encryption[C]//International Workshop on Public Key Cryptography. Springer, Berlin, Heidelberg, 2014: 275-292.

[54] Zhang J, Gao H. A compact construction for non-monotonic key-policy attribute-based encryption[J]. International Journal of High Performance Computing and Networking, 2019, 13(3): 321-330.

[55] Wu Q, Wang W. New Identity-based Broadcast Encryption with Constant Ciphertexts in the Standard Model[J]. J. Softw., 2011, 6(10): 1929-1936.

[56] Boneh D, Waters B. Conjunctive, subset, and range queries on encrypted data[C]//Theory of cryptography conference. Springer, Berlin, Heidelberg, 2007: 535-554.

[57] Iovino V, Persiano G. Hidden-vector encryption with groups of prime order[C]//International Conference on Pairing-Based Cryptography. Springer, Berlin, Heidelberg, 2008: 75-88.

[58] Park J H, Lee K, Susilo W, et al. Fully secure hidden vector encryption under standard assumptions[J]. Information Sciences, 2013, 232: 188-207.

[59] Waters B. Dual system encryption: Realizing fully secure IBE and HIBE under simple assumptions[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2009: 619-636.

[60] Park J H. Inner-product encryption under standard assumptions[J]. Designs, Codes and Cryptography, 2011, 58(3): 235-257.

[61] Attrapadung N, Libert B. Functional encryption for inner product: Achieving constant-size ciphertexts with adaptive security or support for negation[C]//International Workshop on Public Key Cryptography. Springer, Berlin, Heidelberg, 2010: 384-402.

[62] Guo F, Susilo W, Mu Y. Distance-based encryption: How to embed fuzziness in biometric-based encryption[J]. IEEE Transactions on Information Forensics and Security, 2015, 11(2): 247-257.

[63] Lyu H, Chen W, Hua X, et al. An improved data-complementing method via fuzzy rough sets for fuzzy-relationship matrix modeling and applications[C]//The 27th Chinese Control and Decision Conference (2015 CCDC). IEEE, 2015: 2856-2859.

[64] Yang J J, Li J Q, Niu Y. A hybrid solution for privacy preserving medical data sharing in the cloud environment[J]. Future Generation computer systems, 2015, 43: 74-86.

[65] van den Braak S W, Choenni S, Meijer R, et al. Trusted third parties for secure and privacy-preserving data integration and sharing in the public sector[C]//Proceedings of the 13th Annual International Conference on Digital Government Research. 2012: 135-144.

[66] Lv Z, Hong C, Zhang M, et al. Expressive and secure searchable encryption in the public key setting[C]//International Conference on Information Security. Springer, Cham, 2014: 364-376.

[67] Wu Y, Hou J, Liu J, et al. Novel multi-keyword search on encrypted data in the cloud[J]. IEEE Access, 2019, 7: 31984-31996.

[68] Liang X, Cao Z, Lin H, et al. Provably secure and efficient bounded ciphertext policy attribute based encryption[C]//Proceedings of the 4th international symposium on information, computer, and communications security. 2009: 343-352.

[69] Tseng Y F, Liu Z Y, Tso R. Practical Inner Product Encryption with Constant Private Key[J]. Applied Sciences, 2020, 10(23): 8669.

[70] Malluhi Q M, Shikfa A, Trinh V C. A ciphertext-policy attribute-based encryption scheme with optimized ciphertext size and fast decryption[C]//Proceedings of the 2017 ACM on Asia conference on computer and communications security. 2017: 230-240.