Private-preserving determination problem of integer-interval positional relationship

doi:10.11772/j.issn.1001-9081.2020020149

Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (9): 2657-2664.DOI: 10.11772/j.issn.1001-9081.2020020149

• Cyber security • Previous Articles Next Articles

Private-preserving determination problem of integer-interval positional relationship

MA Minyao^1,2, LIU Zhuo^1,2, XU Yi^1,2, WU Lian^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-17 Revised:2020-05-19 Online:2020-04-24 Published:2020-09-10
Supported by:
This work is partially supported by the Program of 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会员,主要研究方向:密码学、信息安全;刘卓(1987-),女,河南驻马店人,讲师,博士研究生,主要研究方向:密码学、信息安全;徐艺(1986-),女,贵州石阡人,讲师,博士研究生,主要研究方向:密码学、信息安全;吴恋(1988-),女,贵州安龙人,副教授,硕士,主要研究方向:深度学习、信息安全。
基金资助:
贵州省科学技术基金计划项目（黔科合基础［2016］1115，黔科合基础［2019］1249）；国家科技部和国家自然科学基金奖励补助项目（黔科合平台人才［2017］5790-09）；贵州省教育厅青年科技人才成长项目（黔教合KY字［2017］210，黔教合KY字［2018］260）；贵州省省级重点学科“计算机科学与技术”（ZDXK［2018］007）；贵州省省级重点支持学科“计算机应用技术”（黔学位合字ZDXK［2016］20）；贵州师范学院专业建设项目“计算机科学与技术”（贵师院发［2018］99）。

Abstract

Abstract: Integer-interval means the set of the left and right endpoints of the interval (which are integers) and all integers between them. The positional relationship between integer-intervals is the relation between the positions of two integer-intervals. Aiming at the positional relationship between integer-intervals, a secure two-party computation problem was proposed, in other words, a private-preserving determination problem of integer-interval positional relationship was proposed. In this problem, two users with private-preserving integer-intervals were helped to correctly determine the positional relationship between the two integer-intervals of them with the private preserved. Six positional relationships between two integer-intervals were defined, the 0-1 coding scheme of integer-intervals was given, and a determination rule for integer-interval positional relationship was proved. Then, based on the Goldwasser-Micali cryptosystem and semi-honest attacker model, a secure two-party computation protocol for solving the private-preserving determination problem of integer-interval positional relationship was designed. The protocol was proved to be both correct and secure, and the performance of the protocol was analyzed and explained.

Key words: interval position, integer, private-preserving, secure multi-party computation, homomorphic encryption

摘要： 整数区间是指区间的左右端点都是整数，由左右端点及它们之间的所有整数构成的集合。整数区间的位置关系是指两个整数区间在数轴上的位置的相对关系。针对整数区间位置关系提出一种安全两方计算问题，即隐私保护整数区间位置关系判定问题，该问题旨在帮助拥有隐私整数区间的两个用户，在保护输入隐私的前提下，正确地判断出他们的整数区间的位置关系。定义了整数区间的6种位置关系，给出了整数区间的0-1编码方案，并证明了整数区间位置关系的一种判定准则。基于Goldwasser-Micali加密体制在半诚实攻击者模型下设计了解决整数区间位置关系判定问题的一个两方计算协议，证明了协议的正确性和安全性，并对协议的性能进行了分析和说明。

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

CLC Number:

TP309

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.

马敏耀, 刘卓, 徐艺, 吴恋. 隐私保护整数区间位置关系判定问题[J]. 计算机应用, 2020, 40(9): 2657-2664.

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-a completeness theorem for protocols with honest majority[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] NISSIM K,WEINREB E. Communication efficient secure linear algebra[C]//Proceedings of the 3rd Theory of Cryptography Conference,LNCS 3876. Berlin:Springer,2006:522-541.
[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] LI S,WANG D,DAI Y. Symmetric cryptographic protocols for extended millionaires'problem[J]. Science in China Series F:Information Sciences,2009,52(6):974-982.
[8] LIU W,WANG Y B,SUI A N,et al. Quantum protocol for millionaire problem[J]. International Journal of Theoretical Physics,2019,58(7):2106-2114.
[9] JIA H,WEN Q,SONG T,et al. Quantum protocol for millionaire problem[J]. Optics Communications,2011,284(1):545-549.
[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] RINDAL P, ROSULEK M. Malicious-secure private set intersection via dual execution[C]//Proceedings of the 24th ACM Conference on Computer and Communications Security. New York:ACM,2017:1229-1242.
[12] FREEDMAN M J,HAZAY C,NISSIM K,et al. Efficient setintersection with simulation-based security[J]. Journal of Cryptology,2016,29(1):115-155.
[13] FREEDMAN M J, NISSIM K, PINKAS B. Efficient private matching and set intersection[C]//Proceedings of the 2004 International Conference on the Theory and Applications of Cryptographic Techniques,LNCS 3027. Berlin:Springer,2004:1-19.
[14] HAZAY C,LINDELL Y. Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries[C]//Proceedings of the 5th Theory of Cryptography Conference,LNCS 4948. Berlin:Springer,2008:155-175.
[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] 马敏耀, 吴恋, 刘卓, 等. 隐私保护整数点和区间关系判定问题[J]. 计算机应用,2020, 40(7):1983-1988.(MA M Y,WU L, LIU Z,et al. Privacy-preserving determination of integer pointinterval relationship[J]. Journal of Computer Applications,2020, 40(7):1983-1988.)
[21] GOLDREICH O. Foundations of Cryptography:Basic Applications:Volume Ⅱ Basic Applications[M]. Cambridge:Cambridge University Press,2004:599-764.
[22] 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.

Private-preserving determination problem of integer-interval positional relationship

隐私保护整数区间位置关系判定问题

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	Kaiming SUN, Dongfeng CAI, Yu BAI. Symbolic regression method for integer sequence based on self-learning [J]. Journal of Computer Applications, 2024, 44(10): 3158-3166.
[2]	Jing ZHANG, He TIAN, Kun XIONG, Yongli TANG, Li YANG. Fair multi-party private set intersection protocol based on cloud server [J]. Journal of Computer Applications, 2023, 43(9): 2806-2811.
[3]	Jinbo LI, Ping ZHANG, Ji ZHANG, Muhua LIU. Identity-based ring signature scheme on number theory research unit lattice [J]. Journal of Computer Applications, 2023, 43(9): 2798-2805.
[4]	Dongdong LIN, Manman LI, Shaozhen CHEN. Conditional differential cryptanalysis method of KATAN48 algorithm based on neural distinguishers [J]. Journal of Computer Applications, 2023, 43(8): 2462-2470.
[5]	Yipeng SHI, Jie LIU, Jinyuan ZU, Tao ZHANG, Guoqun ZHANG. Compact constraint analysis of SPONGENT S-box based on mixed integer linear programming model [J]. Journal of Computer Applications, 2023, 43(5): 1504-1510.
[6]	Zhoubo XU, Puqing CHEN, Huadong LIU, Xin YANG. Deep graph matching model based on self-attention network [J]. Journal of Computer Applications, 2023, 43(4): 1005-1012.
[7]	Teng WANG, Zheng HUO, Yaxin HUANG, Yilin FAN. Review on privacy-preserving technologies in federated learning [J]. Journal of Computer Applications, 2023, 43(2): 437-449.
[8]	Xiaohan GUO, Zhongyuan YAO, Yong ZHANG, Shangkun GUO, Chao WANG, Xueming SI. Cross-chain privacy protection scheme of consortium blockchain based on improved notary mechanism [J]. Journal of Computer Applications, 2023, 43(10): 3028-3037.
[9]	Yang ZHONG, Renwan BI, Xishan YAN, Zuobin YING, Jinbo XIONG. Efficient homomorphic neural network supporting privacy-preserving training [J]. Journal of Computer Applications, 2022, 42(12): 3792-3800.
[10]	Chuyu JIANG, Lixi FANG, Ning ZHANG, Jianming ZHU. Cross-chain interaction safety model based on notary groups [J]. Journal of Computer Applications, 2022, 42(11): 3438-3443.
[11]	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.
[12]	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.
[13]	ZHANG En, LI Huimin, CHANG Jian. Verifiable k-means clustering scheme with privacy-preserving [J]. Journal of Computer Applications, 2021, 41(2): 413-421.
[14]	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.
[15]	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.