复数域上的隐私保护集合交集势计算
The Computation of Private Set Intersection Cardinality over Complex Number
DOI: 10.12677/CSA.2021.116170, PDF,  被引量    国家自然科学基金支持
作者: 唐 桐：中国科学院重庆绿色智能技术研究院，重庆;中国科学院大学，北京；李 轶, 吴文渊, 冯 勇：中国科学院重庆绿色智能技术研究院，重庆
关键词: 安全多方计算；隐私保护集合交集计算；复数；结式；Secure Multi-Party Computation； Private Set Intersection Computation； Complex Number； Resultant
摘要: 安全多方计算是密码学领域的研究热点，集合交集问题是其重要研究方向之一。由于现实中众多应用场景可以抽象成数学上的集合关系计算，故集合保密计算具有重要的实际意义。整数环上的集合交集保密计算目前已存在较多研究成果，但针对复数域上集合交集保密计算的研究却很少。本文主要研究复数域上的集合保密计算问题。由于复数上的集合交集计算与整数上的集合交集计算存在差异，故本文引入代数计算中的结式来解决该问题。首先使用牛顿公式来构造复数域上的多项式，再将保护隐私的两方求解集合交集势问题转化为安全两方求解结式中参变元最低次数问题。最后，利用随机哈希和西尔维斯特结式的性质降低计算开销。
Abstract: Secure multi-party computation is a hotspot in the field of cryptography, and the problem of private set intersection is a significant research direction. Since many practical problems can be abstracted as set relation computation in mathematics, the computation of private set intersection has important practical significance. There are many works to study secure integer set computation, but there are little researches in the complex field. This paper focuses on the computation of private set intersection in the complex number. Because of the difference between complex numbers and integers, we need to find a method to compute complex numbers. For this reason, we use the polynomial theory to construct the related polynomial according to the set elements, and introduce resultant in algebraic calculations to transform the two-party private set intersection cardinality problem into a problem of calculating the lowest order of the parameter argument, finally, use random hashing and the properties of Sylvester resultant to calculate it quickly, further reducing the computational overhead.
文章引用：唐桐, 李轶, 吴文渊, 冯勇. 复数域上的隐私保护集合交集势计算[J]. 计算机科学与应用, 2021, 11(6): 1649-1661. https://doi.org/10.12677/CSA.2021.116170

参考文献

[1] Yao, A.C. (1982) Protocols for Secure Computation. 23rd Annual Symposium on Foundations of Computer Science, Chicago, 3-5 November 1982, 160-164. [Google Scholar] [CrossRef] 
[2] Goldreich, O., Micali, S. and Wigderson, A. (1987) How to Play ANY Mental Game. Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, New York, January 1987, 218-229. [Google Scholar] [CrossRef] 
[3] Goldreich, O. (2004) Foundations of Cryptography II: Basic Applica-tions. Journal of the ACM, 10, 359-364. [Google Scholar] [CrossRef] 
[4] Cristofaro, E.D., Kim, J. and Tsudik, G. (2010) Line-ar-Complexity Private Set Intersection Protocols Secure in Malicious Model. 16th International Conference on the Theo-ry and Application of Cryptology and Information Security, Singapore, 5-9 December 2010, 213-231. [Google Scholar] [CrossRef] 
[5] Jarecki, S. and Liu, X. (2010) Fast Secure Computation of Set Intersection. International Conference on Security & Cryptography for Networks, Amalfi, 13-15 September 2010, 418-435. [Google Scholar] [CrossRef] 
[6] Freedman, M.J., et al. (2016) Efficient Set Intersec-tion with Simulation-Based Security. Journal of Cryptology, 29, 115-155. [Google Scholar] [CrossRef] 
[7] Cristofaro, E.D., Gasti, P. and Tsudik, G. (2012) Fast and Private Computation of Cardinality of Set Intersection and Union. International Conference on Cryptology and Network Security, Darmstadt, 12-14 December 2012, 218-231. [Google Scholar] [CrossRef] 
[8] Pinkas, B., Schneider, T. and Zohner, M. (2018) Scalable Pri-vate Set Intersection Based on OT Extension. ACM Transactions on Privacy and Security, 21, 7:1-7:35. [Google Scholar] [CrossRef] 
[9] Dong, C.Y., Chen, L.Q. and Wen, Z.K. (2013) When Private Set Intersection Meets Big Data: An Efficient and Scalable Protocol. Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, Berlin, 4-8 November 2013, 128-144.
[10] Kolesnikov, V., et al. (2016) Efficient Batched Oblivious PRF with Applications to Private Set Intersection. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Association for Computing Machinery, New York, 818-829. [Google Scholar] [CrossRef] 
[11] Seo, J.H., Cheon, J.H. and Katz, J. (2012) Constant-Round Mul-ti-Party Private Set Union Using Reversed Laurent Series. International Conference on Practice & Theory in Public Key Cryptography, Darmstadt, 21-23 May 2012, 398-412. [Google Scholar] [CrossRef] 
[12] Blanton, M. and Aguiar, E. (2016) Private and Oblivious Set and Multiset Operations. International Journal of Information Security, 15, 493-518. [Google Scholar] [CrossRef] 
[13] Chun, J.Y., et al. (2013) Privacy-Preserving Disjunctive Normal Form Operations on Distributed Sets. Information Sciences, 231, 113-122. [Google Scholar] [CrossRef] 
[14] Clifton, C., et al. (2002) Tools for Privacy Preserving Distributed Data Mining. ACM SIGKDD Explorations Newsletter, 4, 28-34. [Google Scholar] [CrossRef] 
[15] Pohlig, S. and Hellman, M. (1978) An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance. IEEE Transactions on Information Theory, 24, 106-110. [Google Scholar] [CrossRef] 
[16] Freedman, M.J., Nissim, K. and Pinkas, B. (2004) Efficient Private Matching and Set Intersection. 23rd Annual Eurocrypt Conference, Interlaken, 2-6 May 2004, 1-19. [Google Scholar] [CrossRef] 
[17] Paillier, P. (1999) Public-Key Cryptosystems Based on Com-posite Degree Residuosity Classes. International Conference on the Theory and Application of Cryptographic Tech-niques, Prague, 2-6 May 1999, 223-238.
[18] Elgamal, T. (1985) A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans on Information Theory, 31, 469-472. [Google Scholar] [CrossRef] 
[19] Kissner, L. and Song, D. (2005) Privacy-Preserving Set Operations. In: Shoup, V., Ed., Advances in Cryptology-Crypto’05, Vol. 3621 of LNCS, Springer-Verlag, Berlin, 241-257. [Google Scholar] [CrossRef] 
[20] Xia, F. (2012) Secure Two-Party Computation for Set Intersection and Set Equality Problems Based on LWE. Journal of Electronics & Information Technology, 34, 462-467.
[21] 窦家维, 刘旭红, 王文丽. 有理数域上两方集合的高效保密计算[J]. 计算机学报, 2020, 43(8): 1397-1413.
[22] 巩林明, 等. 基于无匹配差错的PSI计算[J]. 计算机学报, 2020, 43(9): 1769-1790.
[23] Huang, Y., Evans, D. and Katz, J. (2012) Private Set Intersection: Are Garbled Circuits Better than Custom Protocols? NDSS 2012, San Diego, 5-8 February 2012.
[24] Pinkas, B., Schneider, T. and Zohner, M. (2014) Faster Private Set Intersection Based on OT Extension. Proceedings of the 23rd USENIX Security, San Diego, 20-22 August 2014, 797-812.
[25] Lv, S., et al. (2020) Unbal-anced Private Set Intersection Cardinality Protocol with Low Communication Cost. Future Generation Computer Sys-tems, 102, 1054-1061. [Google Scholar] [CrossRef] 
[26] 侯晓荣, 杨张. 非线性代数方程组与定理机器证明[M]. 上海: 上海科技教育出版社, 2001.
[27] Du, W., Han, Y. and Chen, S. (2004) Privacy-Preserving Multivariate Statistical Analysis: Linear Regression and Classification. [Google Scholar] [CrossRef] 
[28] Du, W. and Zhan, Z. (2003) A Practical Approach to Solve Se-cure Multi-Party Computation Problems. Proceedings of the 2002 Workshop on New Security Paradigms, Virginia Beach, 23-26 September 2002, 127-135. [Google Scholar] [CrossRef] 
[29] 孙彦飞, 等. 保护私有信息的集合交集协议[J]. 计算机应用, 2010, 30(2): 506-509.
[30] Tzeng, W. (2001) Efficient Oblivious Transfer Schemes. IACR Cryptology ePrint Archive, 73.