k-minSecurity Multi-Party Computing Solution and Application

被引：0

作者：

Wang Y.-L. ^{[1
]}

Dou J.-W. ^{[1
]}

机构：

[1] School of Mathematics and Statistics, Shaanxi Normal University, Xi'an

来源：

Tien Tzu Hsueh Pao/Acta Electronica Sinica | 2021年 / 49卷 / 11期

关键词：

Homomorphic encryption; k-min problem; Privacy-preserving score statistics and sorting; Secure multi-party computation; Security;

D O I：

10.12263/DZXB.20200084

中图分类号：

学科分类号：

摘要：

Secure multi-party computation (MPC) is an important research field of cryptography. Privately computing the k-th minimum element is an important problem of MPC (denoted by k-min problem). MPC protocol for k-min problem can be widely applied to secure voting, secure bid and auction, secure statistical analysis, etc. At present, most solutions to this problem need to repeatedly invoke secure sum protocol and secure comparison protocol. Therefore, the efficiency of the protocols is low. Some solutions designed for mobile network are not applicable to MPC settings. In this paper, we propose a new encoding scheme. Based on this encoding scheme and threshold Lifted ElGamal cryptosystem, we design a simple and efficient MPC protocol for k-min problem. The security of the protocol is strictly proved by using the simulation paradigm and the feasibility of the scheme is proved by the experiment. Using k-min protocol as a building block, we further design a protocol for privacy-preserving score statistics and sorting. Theoretical analysis and experimental result show that our protocols are secure and efficient. © 2021, Chinese Institute of Electronics. All right reserved.

引用

页码：2256 / 2260

页数：4

共 12 条

[1] YAO A C., Protocols for secure computations, Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pp. 160-164, (1982)
[2] ROTHBLUM R D, SEALFON A, SOTIRAKI K., Toward non-interactive zero-knowledge proofs for NP from LWE, Journal of Cryptology, 34, 1, pp. 1-35, (2021)
[3] HOU Hong-xia, YANG Bo, ZHANG Li-na, Et al., Secure two-party SM2 signature algorithm, Acta Electronica Sinica, 48, 1, pp. 1-8, (2020)
[4] HUANG Yue, ZENG Peng, CHOO K R., An efficient privacy-preserving protocol for computing kth minimum value in P2P networks [J], Journal of Circuits, Systems and Computers, 29, pp. 1-20, (2020)
[5] AGGARWAL G, MISHRA N, PINKAS B., Secure computation of the median (and other elements of specified ranks), Journal of Cryptology, 23, 3, pp. 373-401, (2010)
[6] TUENO A, KERSCHBAUM F, KATZENBEISSER S, Et al., Secure computation of the kth-ranked element in a star network, Proceedings of the International Conference on Financial Cryptography and Data Security, pp. 386-403, (2020)
[7] ZHANG Yuan, CHEN Qing-jun, ZHONG Sheng, Efficient and privacy-preserving min and kth min computations in mobile sensing systems, IEEE Transactions on Dependable and Secure Computing, 14, 1, pp. 9-21, (2015)
[8] GOLDREICH O., The Fundamental of Cryptography: Basic Applications, pp. 599-764, (2004)
[9] FREEDMAN M J, HAZAY C, NISSIM K, Et al., Efficient set intersection with simulation-based security, Journal of Cryptology, 29, 1, pp. 115-155, (2016)
[10] SANG Ying-peng, SHEN Hong, Efficient and secure protocols for privacy-preserving set operations, ACM Transactions on Information and System Security, 13, 1, pp. 9:1-9:35, (2009)

← 1 2 →