集合成员关系判定的安全多方计算协议

doi:10.6040/j.issn.1671-9352.0.2019.716

摘要/Abstract

摘要： 基于全同态加密技术,构造了一个安全计算集合成员关系问题的多方协议。通过将判定集合成员关系问题转化为范德蒙行列式求值问题,该协议解决了已有研究成果中集合阶数的泄露问题,提高了安全性;并证明其在静态半诚实敌手模型下的安全性。该协议还具有判断集合是否有交集的功能。

关键词: 集合成员关系, 安全多方计算, 范德蒙行列式, 全同态加密

Abstract: Based on the fully homomorphic encryption, a protocol for secure multiparty computing set membership problem is proposed. By converting the problem of determining set membership into computing Vandermonde determinant, this protocol solves the problem of leakage of set orders in existing research results and improves security. The proof shows that the proposed protocol is safe in the presence of static semi-honest adversaries. Besides, this protocol has the function of judging whether two sets have an intersection.

Key words: set membership, secure multiparty computation, Vandermonde determinant, fully homomorphic encryption

中图分类号:

TP309

张茜,苏烨,秦静. 集合成员关系判定的安全多方计算协议[J]. 《山东大学学报(理学版)》, 2020, 55(4): 118-126.

ZHANG Xi, SU Ye, QIN Jing. Secure multiparty computation protocol of set memberships judge[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(4): 118-126.

参考文献

[1] YAO A C. Protocols for secure computations[C] //23rd Annual Symposium on Foundations of Computer Science(SFCS 1982), November 3-5, 1982. Chicago: IEEE, 1982: 160-164.
[2] GOLDREICH O, MICALI S, WIGDERSON A. How to play any mental game or a completeness theorem for protocols with honest majority[C] //STOC. [S.l.] :[s.n.] , 1987: 218-229.
[3] GOLDREICH O. Foundations of cryptography: volume 1[J]. Current Methods in Inorganic Chemistry, 2007, 39(509):359-364.
[4] CANETTI R. Security and composition of multiparty cryptographic protocols[J]. Journal of Cryptology, 2000, 13(1):143-202.
[5] RUJ S, STOJMENOVIC M, NAYAK A. Decentralized access control with anonymous authentication of data stored in clouds[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(2):384-394.
[6] DAN B, GIOVANNI D C, RAFAIL O, et al. Public key encryption with keyword search[C] // EUROCRYPT, 2004: 506-522
[7] FU S J, YU Y P, XU M. A secure algorithm for outsourcing matrix multiplication in the cloud[C] //Proceedings of the Fifth ACM International Workshop on Security in Cloud Computing. New York: ACM, 2017: 27-33
[8] SANDHU R S, COYNE E J, FEINSTEIN H L, et al. Role-based access control models[J]. Computer, 1996, 29(2):38-47.
[9] 秦静, 张振峰, 冯登国, 等. 一个特殊的安全双方计算协议[J]. 通信学报, 2004, 25(11):35-42. QIN Jing, ZHANG Zhenfeng, FENG Dengguo, et al. A protocol of specific secure two-party computation[J]. Journal of China Institute of Communications, 2004, 25(11):35-42.
[10] 秦静, 张振峰, 冯登国,等. 无信息泄漏的比较协议[J]. 软件学报, 2004, 15(3):421-427. QIN Jing, ZHANG Zhenfeng, FENG Dengguo, et al. A protocol of comparing information without leaking[J]. Journal of Software, 2004, 15(3):421-427.
[11] GOLDREICH O. The foundations of cryptography-volume 2: basic applications[M]. Cambridge: Cambridge University Press, 2004: 600-764.
[12] PINKAS B, SCHNEIDER T, WEINERT C, et al. Efficient circuit-based PSI via cuckoo hashing[C] // EUROCRYPT, 2018, 10822:125-157.
[13] QIN Jing, DUAN Hongwei, HU Jiankun. A new Lagrange solution to the privacy-preserving general geometric intersection problem[J]. Journal of Network and Computer Applications, 2014, 46:94-99.
[14] HAO C, KIM L, PETER R. Fast private set intersection from homomorphic encryption[A]. IACR Cryptology ePrint Archive, 2017: 299.
[15] KALYANASUNDARAM B, SCHINTGER G. The probabilistic communication complexity of set intersection[J]. SIAM Journal on Discrete Mathematics, 1992, 5(4):545-557.
[16] EGERT R, FISCHLIN M, GENS D, et al. Privately computing set-union and set-intersection cardinality via bloom filters[J]. European Journal of Operational Research, 2015, 139(2):371-389.
[17] CRISTOFARO E D, GASTI P, TSUDIK G. Fast and private computation of cardinality of set intersection and union[C] //Proceedings of International Conference on Cryptology and Network Security. Berlin: Springer, 2012: 218-231.
[18] DEBNATH S K, DUTTA R. Efficient private set intersection cardinality in the presence of malicious adversaries[C] //Proceedings of the 9th International Conference on Provable Security. Berlin: Springer, 2015: 326-339.
[19] SHI R H. Efficient quantum protocol for private set intersection cardinality[J]. IEEE Access, 2018, 6:73102-73109.
[20] HAZAY C, LINDELL Y. Efficient secure two-party protocols[M]. Berlin: Springer, 2010: 7-22.
[21] RIVEST R L, ADLEMAN L, DERTOUZOS M L. On data banks and privacy homomorphisms[J]. Foundations of Secure Computation, 1978: 169-179.
[22] PAILLIER P. Public-key cryptosystems based on composite degree residuosity classes[J]. Advances in Cryptology-Eurocrypt, 1999, 547(1):223-238.
[23] ELGAMAL T. A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Transactions on Information Theory, 1984, 31(4):469-472.
[24] DAN B, GOH E J, NISSIM K. Evaluating 2-DNF formulas on ciphertexts[C] //Proceedings of the 2nd International Conference on Theory of Cryptography. Berlin: Springer, 2005: 325-341.
[25] GENTRY C. Fully homomorphic encryption using ideal lattices[C] //Proceedings of the 41st Annual ACM Symposium on Theory of Computing. New York: ACM Press, 2009: 169-178.
[26] VAN DIJK M, GENTRY C, HALEVI S V, et al. Fully homomorphic encryption over the integers[C] //Proceedings of the 29th International Conference on Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2010: 24-43.
[27] BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V.(Leveled)fully homomorphic encryption without bootstrapping[C] //Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. New York: ACM Press, 2012: 309-325.
[28] KHALIL H, ABED E S, MAROUN C. An efficient FHE scheme to secure cloud computing[C] // ICETE(2). [S.l.] :[s.n.] , 2019: 341-349.
[29] 北京大学数学系几何与代数教研室前代数小组. 高等代数[M]. 北京: 高等教育出版社, 2003: 79-81. Pre-algebra Group, Teaching and Research Office of Geometry and Algebra, Department of Mathematics, Peking University. Advanced algebra[M]. Beijing: Higher Education Press, 2003: 79-81.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed