• 学术论文 •

### k-min问题安全多方计算方案及应用

1. 陕西师范大学数学与统计学院，陕西 西安 710119
• 收稿日期:2020-01-13 修回日期:2021-06-23 出版日期:2021-11-25
• 作者简介:
• 汪榆淋　女，1997年生，四川人. 陕西师范大学数学与统计学院硕士研究生. 主要研究方向为应用数学与密码学. E-mail:yullin@snnu.edu.cn
窦家维(通信作者)　女，1963年生，陕西人. 现为陕西师范大学数学与统计学院副教授, 硕士生导师. 主要研究方向为应用数学与密码学. E-mail: jiawei@snnu.edu.cn

### k-minSecurity Multi-Party Computing Solution and Application

WANG Yu-lin, DOU Jia-wei

1. School of Mathematics and Statistics, Shaanxi Normal University, Xi’an, Shaanxi 710119, China
• Received:2020-01-13 Revised:2021-06-23 Online:2021-11-25 Published:2021-11-25

Abstract:

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-minproblem). MPC protocol for k-minproblem 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-minproblem. 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-minprotocol 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.