k -min问题安全多方计算方案及应用k -min- 电子学报 2021年49卷第11期 页码：2256-2260
- 作者机构：
陕西师范大学数学与统计学院，陕西西安710119
- 作者简介：
[ "汪榆淋 女，1997年生，四川人. 陕西师范大学数学与统计学院硕士研究生. 主要研究方向为应用数学与密码学. E-mail:yullin@snnu.edu.cn" ]
[ "窦家维(通信作者) 女，1963年生，陕西人. 现为陕西师范大学数学与统计学院副教授, 硕士生导师. 主要研究方向为应用数学与密码学. E-mail: jiawei@snnu.edu.cn" ]
- 基金信息：
DOI：10.12263/DZXB.20200084
中图分类号： TP309收稿：2020-01-13，
修回：2021-06-23，
纸质出版：2021-11-25
- 稿件说明：
移动端阅览
汪榆淋,窦家维.k-min问题安全多方计算方案及应用[J].电子学报,2021,49(11):2256-2260.
WANG Yu-lin,DOU Jia-wei.k-minSecurity Multi-Party Computing Solution and Application[J].ACTA ELECTRONICA SINICA,2021,49(11):2256-2260.
汪榆淋,窦家维.k-min问题安全多方计算方案及应用[J].电子学报,2021,49(11):2256-2260. DOI： 10.12263/DZXB.20200084.
WANG Yu-lin,DOU Jia-wei.k-minSecurity Multi-Party Computing Solution and Application[J].ACTA ELECTRONICA SINICA,2021,49(11):2256-2260. DOI： 10.12263/DZXB.20200084.
摘要
安全多方计算(MPC)是密码学的一个重要研究方向. 保密计算第
<math id="M1"><mi>k</mi></math>
http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=43951872&type=
http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=43951882&type=
1.43933344
2.28600001
小元素是一个重要的MPC问题(简称
k
-min问题).
k
-min值MPC协议在保密的投票选举
保密的招投标以及保密的数据统计分析等方面具有广泛应用. 目前
k
-min问题的MPC解决方案大都需要多次调用保密求和协议以及比较协议
协议效率较低. 也有一些协议基于移动网络通信应用设计
无法解决MPC应用问题. 本文提出新的编码方式
以此为基础并结合Lifted ElGamal门限密码系统设计了简单高效的
k
-min值MPC协议
应用模拟范例严格证明了协议的安全性
并利用实验证明了方案的可行性. 以
k
-min协议为基础进一步设计了多方成绩保密统计与排序协议. 理论分析和实验测试表明本文协议是安全且简单高效的.
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
-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.
关键词
Keywords
references
YAO A C . Protocols for secure computations [A]. Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science [C]. Los Alamitos, USA : IEEE Computer Science Press , 1982 . 160 - 164 .
ROTHBLUM R D , SEALFON A , SOTIRAKI K . Toward non-interactive zero-knowledge proofs for NP from LWE [J]. Journal of Cryptology , 2021 , 34 ( 1 ): 1 - 35 .
侯红霞 , 杨波 , 张丽娜 , 等 . 安全的两方协作SM2签名算法 [J]. 电子学报 , 2020 , 48 ( 1 ): 1 - 8 .
HOU Hong-xia , YANG Bo , ZHANG Li-na , et al . Secure two-party SM2 signature algorithm [J]. Acta Electronica Sinica , 2020 , 48 ( 1 ): 1 - 8 . (in Chinese)
HUANG Yue , ZENG Peng , CHOO K R . An efficient privacy-preserving protocol for computing <math id="M313"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=43954459&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=43954456&type= 1.43933344 2.28600001 th minimum value in P2P networks [J]. Journal of Circuits, Systems and Computers , 2020 , 29 ( 09 ): 1 - 20 .
AGGARWAL G , MISHRA N , PINKAS B . Secure computation of the median (and other elements of specified ranks) [J]. Journal of Cryptology , 2010 , 23 ( 3 ): 373 - 401 .
TUENO A , KERSCHBAUM F , KATZENBEISSER S , et al . Secure computation of the <math id="M314"><msup><mrow><mi>k</mi></mrow><mrow><mi>t</mi><mi>h</mi></mrow></msup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=43954440&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=43954454&type= 3.04800010 2.28600001 -ranked element in a star network [A]. Proceedings of the International Conference on Financial Cryptography and Data Security [C]. Kota Kinabalu, Malaysia : Springer , 2020 . 386 - 403 .
ZHANG Yuan , CHEN Qing-jun , ZHONG Sheng . Efficient and privacy-preserving min and <math id="M315"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=43954459&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=43954456&type= 1.43933344 2.28600001 th min computations in mobile sensing systems [J]. IEEE Transactions on Dependable and Secure Computing , 2015 , 14 ( 1 ): 9 - 21 .
GOLDREICH O . The Fundamental of Cryptography: Basic Applications [M]. London, Britain : Cambridge University Press , 2004 . 599 - 764 .
FREEDMAN M J , HAZAY C , NISSIM K , et al . Efficient set intersection with simulation-based security [J]. Journal of Cryptology , 2016 , 29 ( 1 ): 115 - 155 .
SANG Ying-peng , SHEN Hong . Efficient and secure protocols for privacy-preserving set operations [J]. ACM Transactions on Information and System Security , 2009 , 13 ( 1 ): 9 : 1 - 9 : 35 .
SHEIKH R , MISHRA D K . Secure sum computation using homomorphic encryption [A]. Proceedings of the Data Science and Big Data Analytics , Women in Research [C] . Indore , India : 2018 . 357 - 363 .
李顺东 , 王文丽 , 杜润萌 . 抗恶意敌手的百万富翁问题解决方案 [J]. 中国科学: 信息科学 , 2021 , 51 ( 01 ): 75 - 88 .
LI Shun-dong , WANG Wen-li , DU Run-meng . Protocol for millionaire’s problem in malicious models [J]. Scientia Sinica Informationis , 2021 , 51 ( 01 ): 75 - 88 . (in Chinese)
0
浏览量
21
下载量
0
CSCD
- 网络PDF下载
- Meta-XML下载
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
关联资源
相关文章
相关作者
相关机构
- 技术支持由北京北大方正电子有限公司提供 京ICP备09064830号-19
京公网安备11010802024621 - 本系统建议在Chrome、 IE9+ 以上版本浏览器阅读本站内容，360浏览器请切换至极速模式
- Cookies帮助我们提供服务并提供个性化体验。使用本网站，即表示您同意我们使用Cookies