Privacy-preserving determination of integer point-interval relationship

doi:10.11772/j.issn.1001-9081.2020010091

Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (7): 1983-1988.DOI: 10.11772/j.issn.1001-9081.2020010091

• Cyber security • Previous Articles Next Articles

Privacy-preserving determination of integer point-interval relationship

MA Minyao^1,2, WU Lian^1,2, LIU Zhuo^1,2, XU Yi^1,2

1. School of Mathematics and Big Data, Guizhou Education University, Guiyang Guizhou 550018, China;
2. Key Laboratory of Cyberspace Security, Guizhou Education University, Guiyang Guizhou 550018, China

Received:2020-02-04 Revised:2020-04-21 Online:2020-07-10 Published:2020-06-05
Supported by:
This work is partially supported by the Science and Technology Foundation Project of Guizhou Province (QianKeHeJiChu[2016]1115, QianKeHeJiChu[2019]1249), the Award and Subsidy Project of Ministry of Science and Technology and NSFC (QianKeHePingTaiRenCai[2017]5790-09), the Youth Science and Technology Talent Project of Guizhou Provincial Education Department (QianJiaoHe-KY-Zi[2017]210, QianJiaoHe-KY-Zi[2018]260), the Key Disciplines of Guizhou Province-Computer Science and Technology (ZDXK[2018]007), the Key Supported Disciplines of Guizhou Province-Computer Application Technology (QianXueWeiHeZi ZDXK[2016]20), the Construction Project of Computer Science and Technology of Guizhou Education University (GuiShiYuanFa[2018]99).

隐私保护整数点和区间关系判定问题

马敏耀^1,2, 吴恋^1,2, 刘卓^1,2, 徐艺^1,2

1. 贵州师范学院数学与大数据学院, 贵阳 550018;
2. 贵州师范学院网络空间安全重点实验室, 贵阳 550018

通讯作者: 马敏耀
作者简介:马敏耀(1979-),男,贵州威宁人,副教授,博士,CCF会员,主要研究方向:密码学、信息安全;吴恋(1988-),女,贵州安龙人,副教授,硕士,主要研究方向:深度学习、信息安全;刘卓(1987-),女,河南驻马店人,讲师,博士研究生,主要研究方向:密码学、信息安全;徐艺(1986-),女,贵州石阡人,讲师,博士研究生,主要研究方向:密码学、信息安全。
基金资助:
贵州省科学技术基金计划项目（黔科合基础[2016]1115，黔科合基础[2019]1249）；国家科技部和国家自然科学基金奖励补助项目（黔科合平台人才[2017]5790-09）；贵州省教育厅青年科技人才成长项目（黔教合KY字[2017]210，黔教合KY字[2018]260）；贵州省省级重点学科“计算机科学与技术”（ZDXK[2018]007）；贵州省省级重点支持学科“计算机应用技术”（黔学位合字ZDXK[2016]20）；贵州师范学院专业建设项目“计算机科学与技术”（贵师院发[2018]99）。

Abstract

Abstract: The determination of the relationship between integer point and integer interval in the sense of privacy preserving is an important secure multi-party computation problem, but there are some defects in the existing solutions, such as low efficiency, privacy disclosure, and even possible wrong determination. Aiming at these defects, an improved secure two-party computation protocol for solving this determination problem was constructed. Firstly, analysis of the existing protocols was given and some shortcomings of the protocols were pointed out. Secondly, a new 0-1 coding rule for integer point and integer interval was defined, based on this, a necessary and sufficient condition for an integer point belonging to an integer interval was proved. Finally, by using the necessary and sufficient condition as the determination standard, a secure two-party computation protocol for determining wether the integer point belonging to the integer interval was proposed based on the Goldwasser-Micali encryption system, and its correctness and the security under the semi-honest model were proved. Analysis shows that compared with the existing solutions, the proposed protocol has better privacy preserving feature and will not output wrong results, in addition, both the computation complexity and the communication complexity of the protocol are reduced by about half while the round complexity remains the same.

Key words: point-interval, integer interval, privacy preserving, secure multi-party computation, homomorphic encryption

摘要： 隐私保护地判断整数点和整数区间的属于关系是一类重要的安全多方计算问题，但该问题的现有解决方案存在效率不高、隐私泄露、甚至可能判断错误等缺陷，针对此类不足，构建解决该判定问题的一个安全双方计算协议。首先，分析已有的解决方案并指出不足之处；其次，定义了整数点和整数区间的一种新的0-1编码规则，在此基础上证明了整数点属于整数区间的一个充分必要条件；最后，以此充分必要条件为判定准则，基于Goldwasser-Micali加密体制构建了判断整数点是否属于整数区间的一个安全双方计算协议，并证明了协议的正确性和半诚实模型下的安全性。分析表明，与已有的解决方案相比，所提协议具有更好的隐私保护特性且不会输出错误结果，且在轮复杂度不变的情况下，其计算复杂度和通信复杂度降低了约一半。

关键词: 点和区间, 整数区间, 隐私保护, 安全多方计算, 同态加密

CLC Number:

TP309

MA Minyao, WU Lian, LIU Zhuo, XU Yi. Privacy-preserving determination of integer point-interval relationship[J]. Journal of Computer Applications, 2020, 40(7): 1983-1988.

马敏耀, 吴恋, 刘卓, 徐艺. 隐私保护整数点和区间关系判定问题[J]. 计算机应用, 2020, 40(7): 1983-1988.

References

[1] YAO A C. Protocols for secure computations[C]//Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. Piscataway:IEEE,1982:160-164.
[2] GOLDREICH O,MICALI S,WIGDERSON A. How to play ANY mental game[C]//Proceedings of the 19th Annual ACM Symposium on Theory of Computing. New York:ACM,1987:218-229.
[3] BEN-OR M,GOLDWASSER S,WIGDERSON A. Completeness theorems for non-cryptographic fault-tolerant distributed computation[C]//Proceedings of the 20th Annual ACM Symposium on Theory of Computing. New York:ACM,1988:1-10.
[4] YAO A C C. How to generate and exchange secrets[C]//Proceedings of the 27th Annual Symposium on Foundations of Computer Science. Piscataway:IEEE,1986:162-167.
[5] MOHASSEL P,WEINREB E. Efficient secure linear algebra in the presence of covert or computationally unbounded adversaries[C]//Proceedings of the 28th Annual International Cryptology Conference,LNCS 5157. Berlin:Springer,2008:481-496.
[6] 马敏耀, 徐艺, 刘卓. 隐私保护DNA序列汉明距离计算问题[J]. 计算机应用,2019,39(9):2636-2640.(MA M Y,XU Y,LIU Z. Privacy preserving Hamming distance computing problem of DNA sequences[J]. Journal of Computer Applications,2019,39(9):2636-2640.)
[7] 李占利, 陈立朝, 陈振华, 等. 基于1-r编码的高效百万富翁问题协议及应用[J]. 密码学报,2019,6(1):50-60.(LI Z L,CHEN L C,CHEN Z H,et al. Design and applications of efficient protocol of millionaires'problem based on 1-r encoding[J]. Journal of Cryptologic Research,2019,6(1):50-60.)
[8] LIU W,WANG Y,SUI A,et al. Quantum protocol for millionaire problem[J]. International Journal of Theoretical Physics,2019,58(7):2106-2114.
[9] ZHOU Y,SHI W,YANG Y. A quantum protocol for millionaire problem with continuous variables[J]. Communications in Theoretical Physics,2014,61(4):452-456.
[10] SHI R,MU Y,ZHONG H,et al. An efficient quantum scheme for private set intersection[J]. Quantum Information Processing, 2016,15(1):363-371.
[11] CHUN J Y,HONG D,JEONG I R,et al. Privacy-preserving disjunctive normal form operations on distributed sets[J]. Information Sciences,2013,231:113-122.
[12] RINDAL P, ROSULEK M. Improved private set intersection against malicious adversaries[C]//Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 10210. Cham:Springer, 2017:235-259.
[13] 罗小双, 杨晓元, 王绪安. 一类可抵抗恶意攻击的隐私集合交集协议[J]. 计算机应用,2017,37(6):1593-1598.(LUO X S, YANG X Y,WANG X A. A private set intersection protocol against malicious attack[J]. Journal of Computer Applications, 2017,37(6):1593-1598.)
[14] 张恩, 金刚刚. 基于同态加密和Bloom过滤器的云外包多方隐私集合比较协议[J]. 计算机应用,2018,38(8):2256-2260. (ZHANG E,JIN G G. Cloud outsourcing multiparty private set intersection protocol based on homomorphic encryption and Bloom filter[J]. Journal of Computer Applications,2018,38(8):2256-2260.)
[15] 马敏耀, 陈松良, 左羽. 基于Goldwasser-Micali加密系统的隐私交集基数协议研究[J]. 计算机应用研究,2018,35(9):2748-2751.(MA M Y,CHEN S L,ZUO Y. Research on private set intersection cardinality protocol based on Goldwasser-Micali encryption system[J]. Application Research of Computers,2018,35(9):2748-2751.)
[16] MOHASSEL P,RINDAL P. ABY3:a mixed protocol framework for machine learning[C]//Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM,2018:35-52.
[17] 郭奕旻, 周素芳, 窦家维, 等. 高效的区间保密计算及应用[J]. 计算机学报,2017,40(7):1664-1679.(GUO Y M,ZHOU S F, DOU J W,et al. Efficient privacy-preserving interval computation and its applications[J]. Chinese Journal of Computers,2017,40(7):1664-1679.)
[18] 窦家维, 王文丽, 李顺东. 区间位置关系的保密判定[J]. 计算机学报,2019,42(5):1031-1044.(DOU J W,WANG W L,LI S D. Privately determining interval location relation[J]. Chinese Journal of Computers,2019,42(5):1031-1044.)
[19] 陈振华, 李顺东, 陈立朝, 等. 点和区间关系的全隐私保密判定[J]. 中国科学:信息科学,2018,48(2):187-204.(CHEN Z H,LI S D,CHEN L C,et al. Fully privacy-preserving determination of point-range relationship[J]. SCIENTIA SINICA Informationis,2018,48(2):187-204.)
[20] GOLDWASSER S,MICALI S. Probabilistic encryption & how to play mental poker keeping secret all partial information[C]//Proceedings of the 14th Annual ACM Symposium on Theory of Computing. New York:ACM,1982:365-377.
[21] GOLDREICH O. Foundations of Cryptography:Volume II Basic Applications[M]. Cambridge:Cambridge University Press, 2004:599-634.

Privacy-preserving determination of integer point-interval relationship

隐私保护整数点和区间关系判定问题

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	ZHENG Shangwen, LIU Yao, ZHOU Tanping, YANG Xiaoyuan. Optimized CKKS scheme based on learning with errors problem [J]. Journal of Computer Applications, 2021, 41(6): 1723-1728.
[2]	ZHANG Lihua, WANG Xinyi, HU Fangzhou, HUANG Yang, BAI Jiayi. Data sharing model of smart grid based on double consortium blockchains [J]. Journal of Computer Applications, 2021, 41(4): 963-969.
[3]	ZHANG En, LI Huimin, CHANG Jian. Verifiable k-means clustering scheme with privacy-preserving [J]. Journal of Computer Applications, 2021, 41(2): 413-421.
[4]	WANG Yunye, CHENG Yage, JIA Zhijuan, FU Junjun, YANG Yanyan, HE Yuchu, MA Wei. Auditable signature scheme for blockchain based on secure multi-party [J]. Journal of Computer Applications, 2020, 40(9): 2639-2645.
[5]	MA Minyao, LIU Zhuo, XU Yi, WU Lian. Private-preserving determination problem of integer-interval positional relationship [J]. Journal of Computer Applications, 2020, 40(9): 2657-2664.
[6]	CHE Xiaoliang, ZHOU Haonan, ZHOU Tanping, LI Ningbo, YANG Xiaoyuan. Decryption structure of multi-key homomorphic encryption scheme based on NTRU [J]. Journal of Computer Applications, 2020, 40(7): 1959-1964.
[7]	LONG Yangyang, CHEN Yuling, XIN Yang, DOU Hui. Secure energy transaction scheme based on alliance blockchain [J]. Journal of Computer Applications, 2020, 40(6): 1668-1673.
[8]	MA Minyao, XU Yi, LIU Zhuo. Privacy preserving Hamming distance computing problem of DNA sequences [J]. Journal of Computer Applications, 2019, 39(9): 2636-2640.
[9]	YU Qingfei, TU Guangsheng, LI Ningbo, ZHOU Tanping. Multi-hop multi-policy attributed-based fully homomorphic encryption scheme [J]. Journal of Computer Applications, 2019, 39(8): 2326-2332.
[10]	ZHANG Shuxuan, KANG Haiyan, YAN Han. Privacy preserving for social network relational data based on Skyline computing [J]. Journal of Computer Applications, 2019, 39(5): 1394-1399.
[11]	TU Guangsheng, YANG Xiaoyuan, ZHOU Tanping. Efficient identity-based multi-identity fully homomorphic encryption scheme [J]. Journal of Computer Applications, 2019, 39(3): 750-755.
[12]	SHI Zhicai, WANG Yihan, ZHANG Xiaomei, CHEN Shanshan, CHEN Jiwei. Provable radio frequency identification authentication protocol with scalability [J]. Journal of Computer Applications, 2019, 39(3): 774-778.
[13]	ZHANG En, JIN Ganggang. Cloud outsourcing multiparty private set intersection protocol based on homomorphic encryption and Bloom filter [J]. Journal of Computer Applications, 2018, 38(8): 2256-2260.
[14]	BAI Ping, ZHANG Wei. Fully homomorphic encryption scheme based on learning with errors under multi-attribute environment [J]. Journal of Computer Applications, 2018, 38(5): 1377-1382.
[15]	DAI Xiaokang, CHEN Changbo, WU Wenyuan. New voting protocol based on homomorphic threshold cryptography [J]. Journal of Computer Applications, 2018, 38(4): 1036-1040.