<italic style="font-style: italic">k</italic>-min<italic style="font-style: italic"> </italic>Security Multi-Party Computing Solution and Application

WANG Yu-lin; DOU Jia-wei

doi:10.12263/DZXB.20200084

您当前的位置：

首页 >

文章列表页 >

k-min Security Multi-Party Computing Solution and Application

PAPERS | 更新时间：2025-12-08

- k-min Security Multi-Party Computing Solution and Application
- ACTA ELECTRONICA SINICA Vol. 49, Issue 11, Pages: 2256-2260(2021)
- 作者机构：
  
  陕西师范大学数学与统计学院，陕西西安710119
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20200084
  CLC： TP309
- Received：13 January 2020，
  
  Revised：2021-06-23，
  
  Published：25 November 2021
- 稿件说明：
移动端阅览
汪榆淋,窦家维.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)是密码学的一个重要研究方向. 保密计算第

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问题(简称

-min问题).

-min值MPC协议在保密的投票选举

保密的招投标以及保密的数据统计分析等方面具有广泛应用. 目前

-min问题的MPC解决方案大都需要多次调用保密求和协议以及比较协议

协议效率较低. 也有一些协议基于移动网络通信应用设计

无法解决MPC应用问题. 本文提出新的编码方式

以此为基础并结合Lifted ElGamal门限密码系统设计了简单高效的

-min值MPC协议

应用模拟范例严格证明了协议的安全性

并利用实验证明了方案的可行性. 以

-min协议为基础进一步设计了多方成绩保密统计与排序协议. 理论分析和实验测试表明本文协议是安全且简单高效的.

Abstract

Secure multi-party computation (MPC) is an important research field of cryptography. Privately computing the

-th minimum element is an important problem of MPC (denoted by

-min

problem). MPC protocol for

-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

-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

-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)

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Secure Computation of Subsets from Tuple Sets

A Two-Party SM2 Signing Protocol with Strict Provable Security

Maximum Value of Sum of Intersection Elements of Secret Calculation

Related Author

LI Shun-dong

DU Ji-xin

YU Jia-tong

WU Chuan-yu

CHENG Yi-fan

LIU Qing-yu

LIANG Ze-yu

YU Sheng

Related Institution

School of Computer Science, Shaanxi Normal University

SSC Holding Company Ltd.， Chengmai

Laboratory of Cryptography， Oxford-Hainan Blockchain Research Institute， Chengmai

School of Computer Science， Shaanxi Normal University

School of Computer Science and Technology, Xi'an University of Science and Technology

⁰

k-min Security Multi-Party Computing Solution and Application

DOI：10.12263/DZXB.20200084

摘要

Abstract

关键词

Keywords

references