电子学报 ›› 2017, Vol. 45 ›› Issue (7): 1715-1721.DOI: 10.3969/j.issn.0372-2112.2017.07.023

• 学术论文 • 上一篇    下一篇

最小值问题的安全多方计算及其应用

窦家维1, 马丽1, 李顺东2   

  1. 1. 陕西师范大学数学与信息科学学院, 陕西西安 710062;
    2. 陕西师范大学计算机科学学院, 陕西西安 710062
  • 收稿日期:2015-08-28 修回日期:2016-09-20 出版日期:2017-07-25
    • 作者简介:
    • 窦家维,女,1963年3月生于西安.副教授,硕士生导师.研究方向为密码学、信息安全.E-mail:jiawei@snnu.edu.cn;马丽,女,1983年6月生于陕西渭南.陕西师范大学数学与信息科学学院硕士研究生.研究方向为密码学及其应用.E-mail:mary@snnu.edu.cn
    • 基金资助:
    • 国家自然科学基金 (No.61272435)

Secure Multi-Party Computation for Minimum and Its Applications

DOU Jia-wei1, MA Li1, LI Shun-dong2   

  1. 1. School of Mathematics and Information Science, Shaanxi Normal University, Xi'an, Shaanxi 710062, China;
    2. School of Computer Science, Shaanxi Normal University, Xi'an, Shaanxi 710062, China
  • Received:2015-08-28 Revised:2016-09-20 Online:2017-07-25 Published:2017-07-25
    • Supported by:
    • National Natural Science Foundation of China (No.61272435)

摘要:

安全多方计算是国际密码学界近年来的研究热点.本文主要研究科学计算中最小值问题的安全多方计算,目前尚没有见到关于这个问题的解决方案.本文设计了一种新的编码方法,应用该编码方法和ElGamal乘法同态加密算法,并结合秘密分享以及门限密码体制,在半诚实模型下设计了三个能够抵抗合谋攻击的最小值安全多方计算方案,并应用模拟范例证明了方案的安全性.以最小值解决方案为基础还可以解决最大值安全计算以及并集的安全计算等科学计算问题.效率分析表明所设计的安全计算方案是高效的方案.

关键词: 密码学, 安全多方计算, 最小值, 同态加密, 秘密分享, 门限密码体制

Abstract:

Secure multi-party computation is a focus in the international cryptographic community.This paper studies how to privately compute the minimum of some private numbers.We have not read a solution to this problem.In this study,we introduce a new encoding scheme,and then,based on this new encoding scheme and ElGamal multiplicatively homomorphic encryption scheme,using secret sharing and threshold decryption,devise protocols for this problem.We prove,using the simulation paradigm,that these protocols are secure in the semi-honest model.These protocols can resist collision attack.Based on the computing methods for minimum problem,secure multi-party computation for maximum and union of sets can also be solved.Efficiency analysis shows that these schemes are efficient.

Key words: cryptography, secure multi-party computation, minimum, homomorphic encryption, secret sharing, threshold decryption

中图分类号: