保护隐私的有理数科学计算

doi:10.11959/j.issn.2096-109x.2022038

摘要/Abstract

摘要：

安全多方计算作为密码学的基本组成部分，是各种密码协议的基础，是国际密码学界的研究热点。近年来，许多学者研究了各种各样的安全多方计算问题，包括保密的信息比较、保密的集合问题和保密的计算几何等，并提出相应的解决方案。而在许多实际应用场景中，安全多方计算问题需要应用有理数进行描述，因此研究有理数域上的安全多方计算问题具有重要的理论与实际意义。但现有的安全多方计算问题的研究成果大多数局限于整数范围，且研究的数据主要是单维度数据。关于有理数域上多维度数据安全多方计算问题的研究较少且无法推广应用。基于有理数的分数表示形式，设计了新的编码方案（有理数编码方案和有理向量编码方案），可将有理数域上任意维数的数据进行编码，为研究有理数域上其他安全多方计算问题提供了新的解决思路。以该编码方案和单向哈希函数为基础，分别设计了有理数相等、有理向量相等和集合问题的保密判定协议。所设计的协议仅采用基本算术运算和单向哈希函数进行计算，不需要使用公钥加密算法，使得协议的计算效率较高；且协议对研究问题中的数据范围没有限制，适用范围更广。进一步应用模拟范例严格证明了协议在半诚实模型下的安全性；并通过理论分析和模拟实验验证了协议的高效性和适用性。通过具体实例说明协议具有广泛适用性，可以推广应用于其他有理数域的安全多方计算几何问题。

关键词: 安全多方计算, 编码方法, 单向哈希函数, 有理数, 模拟范例

Abstract:

As a fundamental part of cryptography, secure multiparty computation (SMC) is a building block of various cryptographic protocols, and it is also a hot topic in the international cryptographic community.In recent years, many SMC problems, such as secret information comparison, secret set problems and secure multiparty computational geometry, have been widely studied.As many practical problems need to be described by rational numbers, it is both theoretically and practically important to study the SMC problems in the rational number field.However, most of the existing researches focus on integers and the studied data are mainly one-dimensional data.There are few researches on secure multiparty computation of multi-dimensional data in the rational number field, but they can’t be generalized.Based on the fractional representation of rational numbers, the new encoding schemes about rational numbers and rational number vectors were proposed, which could encode multi-dimensional data in the rational number field and provided new solutions for other SMC problems in the rational number field.Based on the encoding scheme and one-way hash function, some protocols were designed for equality problems and set problems in the rational number field.These protocols used basic arithmetic operation and hash operation to guarantee efficiency than existing related protocols.And these protocols didn’t limit the range of research data and they were more widely applicable.It proves that these protocols are secure in the semi-honest model using simulation paradigm, and demonstrates the efficiency and the applicability of these protocols by theoretical analysis and experiment.A practical example was also given to illustrate that approaches are more versatile, and they could also be directly used to solve some secure multiparty computational geometry problems in the rational number field.

Key words: secure multiparty computation, encoding scheme, one-way hash function, rational numbers, simulation paradigm

中图分类号:

TP309

刘旭红, 孙晨. 保护隐私的有理数科学计算[J]. 网络与信息安全学报, 2022, 8(3): 97-110.

Xuhong LIU, Chen SUN. Private-preserving scientific computation of the rational numbers[J]. Chinese Journal of Network and Information Security, 2022, 8(3): 97-110.

图/表 3

参考文献 25

[1]	YAO A C , . Protocols for secure computations[C]// Proceedings of the 23th Annual Symposium on Foundations of Computer Science. 1982: 160-164.
[2]	GOLDWASSER S , . Multi-party computations:past and present[C]// The 16th Annual ACM Symposium on Principles of Distributed Computing. 1997: 1-6.
[3]	CRAMER R , DAMGARD IB , NIELSEN J B . Secure multiparty computation[M]. London: Cambridge University Press, 2015.
[4]	GOLDREICH O , MICALI S , WIGDERSON A . How to play any mental game[C]// Proceedings of the 19th Annual ACM Conference on Theory of Computing. 1987: 218-229.
[5]	GOLDREICH O . The fundamental of cryptography:basic applications[M]. London: Cambridge University Press, 2004.
[6]	张兴兰, 郑炜 . 基于博弈论的安全多方计算的研究[J]. 网络与信息安全学报, 2018,4(1): 52-56.
	ZHANG X L , ZHENG W . Research on security multi-party computing based on game theory[J]. Chinese Journal of Network and Information Security, 2018,4(1): 52-56.
[7]	HIROFUMI M , NORITAKA S , HIROMI M . A proposal of profit sharing method for secure multiparty computation[J]. International Journal of Innovative Computing Information and Control, 2018,14(2): 727-735.
[8]	邢欢, 张琳 . 基于 paillier 的隐私保护下关联规则挖掘方法[J]. 网络与信息安全学报, 2016,2(1): 53-59.
	XING H , ZHANG L . Privacy-preserving mining of association rules based on paillier encryption algorithm[J]. Chinese Journal of Network and Information Security, 2016,2(1): 53-59.
[9]	SHAO Y , HONG W J , LI Z J . A new method to compute ratio of secure summations and its application in privacy preserving distributed data mining[J]. IEEE Access, 2019,7 20756-20766.
[10]	窦家维, 王颖囡, 葛雪 . 区间关系保密计算若干问题研究[J]. 电子学报, 2021,49(1): 50-57.
	DOU J W , WANG Y N , GE X . Some research on secure interval relation computation[J]. Acta Electronica Sinica, 2021,49(1): 50-57.
[11]	张明武, 冷文韬, 沈华 . 隐私保护的点与任意多边形位置关系判定[J]. 密码学报, 2019,6(4): 443-454.
	ZHANG M W , LENG W T , SHEN H . Privacy preservation protocol to determine position relation between pointsand arbitrary- polygons[J]. Journal of Cryptologic Research, 2019,6(4): 443-454.
[12]	何贤芒 . 基于差分隐私保护技术的多方求和查询方法[J]. 网络与信息安全学报, 2020,6(3): 14-18.
	HE X M . Multi-party summation query method based on differential privacy[J]. Chinese Journal of Network and Information Security, 2020,6(3): 14-18.
[13]	QAOSAR M , ZAMAN A , SIDDIQUE M A ,et al. Privacy-preserving secure computation of skyline query in distributed multi-party databases[J]. Information, 2019,10(3): 119.
[14]	DU W L . A study of several specific secure two-party computation problems[D]. West Lafayette:Purdue University, 2001.
[15]	CHEN X B , XU G , NIU X X ,et al. An efficient protocol for the private comparison of equal information based on the triplet entangled state and single-particle measurement[J]. Optics Communications, 2010,283(7): 1561-1565.
[16]	GONG L M , YANG B , TA O X ,et al. Secure rational numbers equivalence test based on threshold cryptosystem with rational numbers[J]. Information Sciences, 2018,466: 44-54.
[17]	李顺东, 杨晓莉, 左祥建 ,等. 保护私有信息的图形相似判定[J]. 电子学报, 2017,45(9): 2184-2189.
	LI S D , YANG X L , ZUO X J ,et al. Privacy protecting similitude determination for graphics similarity[J]. Chinese Journal of Electronics, 2017,45(9): 2184-2189.
[18]	李顺东, 杜润萌, 杨颜璟 ,等. 有理数相等的保密判定[J]. 电子学报, 2020,48(10): 1933-1937.
	LI S D , DU R M , YANG Y J ,et al. Privately determining equality of rational numbers[J]. Chinese Journal of Electronics, 2020,48(10): 1933-1937.
[19]	FREEDMAN M J , NISSIM K , PINKAS B . Efficient private matching and set intersection[C]// Advances in Cryptology- Eurocrypt. 2004: 1-19.
[20]	LI S D , WANG D S , DAI Y Q . Symmetric cryptographic protocols for extended millionaires’ problem[J]. Science in China(Series F:Information Sciences), 2009,52(6): 974-982.
[21]	窦家维, 刘旭红, 王文丽 . 有理数域上两方集合的高效保密计算[J]. 计算机学报, 2020,43(8): 1397-1413.
	DOU J W , LIU X H , WANG W L . Privacy preserving two-party rational set computation[J]. Chinese Journal of Computers, 2020,43(8): 1397-1413.
[22]	HIDAKA A , SASAZUKI S , GOTO A ,et al. Plasma insulin,C-peptide and blood glucose and the risk of gastric cancer:the Ja pan public health center-based prospective study[J]. International Journal of Cancer Journal International Du Cancer, 2015,136(6): 1402-1410.
[23]	LIU X , CHOO K K R , DENG R H ,et al. Efficient and privacy-preserving outsourced calculation of rational numbers[J]. IEEE Transactions on Dependable and Secure Computing, 2018,15(1): 27-39.
[24]	巩林明, 李顺东, 邵连合 ,等. 数轴上保密关系测定协议[J]. 软件学报, 2020,31(12): 3950-3967.
	GONG L M , LI S D , SHAO L H ,et al. Protocols for secure test on relationship on number axis[J]. Journal of Software, 2020,31(12): 3950-3967.
[25]	窦家维, 王文丽, 刘旭红 ,等. 有理区间的安全多方计算与应用[J]. 电子学报, 2018,46(9): 2057-2062.
	DOU J W , WANG W L , LIU X H ,et al. Secure multiparty computation of rational interval and its applications[J]. Chinese Journal of Electronics, 2018,46(9): 2057-2062.

协议	计算功能	计算复杂性	通信复杂性	适用范围	抵抗穷举攻击
协议1	REq	2(H)	2	有理数	抵抗
协议3	RVEq	2(H)	2	有理数	抵抗
协议4	ReES	l+ 1(H)	1	有理数	抵抗
文献[17]协议1	IEq	2(H)	2	正整数	不抵抗
文献[17]协议2	IVEq	2(H)	2	正整数	不抵抗
文献[18]	REq	6 (M)	2	有理数	/
文献[21]	ReES	3l+8(M)	2	有理数	/

协议	平均耗时/ms
本文协议4	2.269
文献[21]	189.136