区间关系保密计算若干问题研究

doi:10.12263/DZXB.20191263

电子学报 ›› 2021, Vol. 49 ›› Issue (1): 50-57.DOI: 10.12263/DZXB.20191263

区间关系保密计算若干问题研究

窦家维, 王颖囡, 葛雪

陕西师范大学数学与信息科学学院, 陕西西安 710062

收稿日期:2019-11-11 修回日期:2020-07-12 出版日期:2021-01-25
- 作者简介:
- 窦家维 女,1963年出生,陕西西安人.副教授、硕士生导师.分别在陕西师范大学、西安交通大学获得硕士学位、博士学位.主要研究方向为应用数学和密码学.E-mail:jiawei@snnu.edu.cn;王颖囡 女,1996年出生,河南三门峡人.现为陕西师范大学硕士生.主要研究方向为应用数学和密码学.E-mail:wangyingnan@snnu.edu.cn;葛雪女,1995年出生,山西运城人.现为陕西师范大学硕士生.主要研究方向为应用数学和密码学.
- 基金资助:
- 国家自然科学基金 (No.61272435）

Some Research on Secure Interval Relation Computation

DOU Jia-wei, WANG Ying-nan, GE Xue

School of Mathematics and Information Science, Shaanxi Normal University, Xi'an, Shaanxi 710062, China

Received:2019-11-11 Revised:2020-07-12 Online:2021-01-25 Published:2021-01-25
- Supported by:
- National Natural Science Foundation of China (No.61272435)

摘要/Abstract

摘要： 安全多方计算是密码学界的一个重要研究方向，本文主要研究区间的安全计算问题.首先应用Paillier加密方案设计"点与区间"以及"区间与区间"关系两方保密计算基础协议，协议的特点是判定结果以密文形式输出.将其推广为有理区间关系判定协议时，相比已有协议，本文协议更为安全与高效.在此基础上，进一步研究多维度的"点与区间"以及"区间与区间"关系阈值判定这一类新问题.由于基础协议的输出结果为密文，故以此为基础所设计的多维度问题协议更加安全.最后，应用模拟范例方法严格证明了协议的安全性，并对协议进行了效率分析及模拟实验，理论分析及实验结果都说明本文协议是高效的.

关键词: 密码学, 两方安全计算, 点与区间关系, 区间与区间关系, 阈值问题

Abstract: Secure multi-party computation (SMC) is an important research direction of cryptography. In this paper, we study the secure computation of intervals. Using the Paillier encryption scheme, we design the protocols of relationship between an interval and a point (or an interval). Firstly, the outputs of protocols are ciphertexts. If we extend it to rational intervals, the protocols are safer and more efficient than existing protocols. And then, we study the multi-dimensional problems, that is, the threshold problems of multiple points (or intervals) and intervals, which are new problems in SMC. Since the outputs of the basic protocols are ciphertexts, the multi-dimensional problem protocols are more secure. We strictly prove the security of the protocols using the simulation paradigm method, analyze and demonstrate the efficiency of the protocols through experiments, and compare with the related work to illustrate that the protocols are efficient.

Key words: cryptography, secure two-party computation, relationship between point and interval, relationship between interval and interval, threshold problem

中图分类号:

TP309.7

窦家维, 王颖囡, 葛雪. 区间关系保密计算若干问题研究[J]. 电子学报, 2021, 49(1): 50-57.

DOU Jia-wei, WANG Ying-nan, GE Xue . Some Research on Secure Interval Relation Computation[J]. Acta Electronica Sinica, 2021, 49(1): 50-57.

参考文献

[1] YAO A C.Protocols for secure computations[A].Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science[C].Chicago:IEEE,1982.160-164.
[2] GOLDREICH O,MICALI S,WIGDERSON A.How to play any mental game[A].Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing[C].New York:ACM,1987.218-229.
[3] GOLDREIH O.Foundations of Cryptography:Volume 2,Basic Applications[M].London:Cambridge University Press,2004.599-764.
[4] 李顺东,王道顺.基于同态加密的高效多方保密计算[J].电子学报,2013,41(4):798-803. LI Shun-dong,WANG Dao-shun.Efficient secure multiparty computation based on homomorphic encryption[J].Acta Electronica Sinica,2013,41(4):798-803.(in Chinese)
[5] GRIGORIEV D,SHPILRAIN V.Yao's millionaires' problem and decoy-based public key encryption by classical physics[J].International Journal of Foundations of Computer Science,2014,25(04):409-417.
[6] LI S D,GUO Y M,ZHOU S F,et al.Efficient protocols for the general millionaires' problem[J].Chinese Journal of Electronics,2017,26(4):696-702.
[7] YANG X Y,LI S D,Zuo X J.Secure multi-party geometry computation[J].Journal of Cryptologic Research,2016,3(1):33-41.
[8] 罗永龙,黄刘生,徐维江,等.一个保护私有信息的多边形相交判定协议[J].电子学报,2007,35(4):685-691. LUO Yong-long,HUANG Liu-sheng,XU Wei-jiang,et al.A protocol for privacy preserving intersect determination of two polygons[J].Acta Electronica Sinica,2007,35(4):685-691.(in Chinese)
[9] 李顺东,杨晓莉,左祥建,等.保护私有信息的图形相似判定[J].电子学报,2017,45(9):2184-2189. LI Shun-dong,YANG Xiao-li,ZUO Xiang-jian,et al.Privacy-preserving graphical similarity determination[J].Acta Electronica Sinica,2017,45(9):2184-2189.(in Chinese)
[10] LIU L,CHEN X F,LOU W J.Secure three-party computational protocols for triangle area[J].International Journal of Information Security,2016,15(1):1-13.
[11] LINDELL,PINKAS.Privacy preserving data mining[J].Journal of Cryptology,2008,9(8):616-621.
[12] EGERT R,FISCHLIN M,GENS D,et al.Privately computing set-union and set-intersection cardinality via bloom filters[J].European Journal of Operational Research,2015,139(2):371-389.
[13] 窦家维,陈明艳.多重集的保密计算及应用[J].电子学报,2020,48(1):204-208. DOU Jia-wei,CHEN Ming-yan.Secure multi-set operations and their applications[J].Acta Electronica Sinica,2020,48(1):204-208.(in Chinese)
[14] BONEH D,WATERS B.Conjunctive,subset,and range queries on encrypted data[A].Proceedings of Theory of Cryptography Conference[C].Berlin:Springer,2007.535-554.
[15] NISHIDE T,OHTA K.Multiparty computation for interval,equality,and comparison without bit-decomposition protocol[A].Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography[C].Berlin:Springer,2007.343-360.
[16] 郭奕旻,周素芳,窦家维,等.高效的区间保密计算及应用[J].计算机学报,2017,41(7):1664-1679. GUO Yi-min,ZHOU Su-fang,DOU Jia-wei,et al.Efficient privacy-preserving interval computation and its applications[J].Chinese Journal of Computers,2017,41(7):1664-1679.(in Chinese)
[17] 陈振华,李顺东,陈立朝,等.点和区间关系的全隐私保密判定[J].中国科学:信息科学,2018,48(2):187-204. CHEN Zhen-hua,LI Shun-dong,CHEN Li-zhao,et al.Fully privacy-preserving determination of point-range relationship[J].Scientia Sinica Informationis,2018,48(2):187-204.(in Chinese)
[18] 窦家维,王文丽,刘旭红,等.有理区间的安全多方计算与应用[J].电子学报,2018,46(9):11-16. DOU Jia-wei,WANG Wen-li,LIU Xu-hong,et al.Secure multiparty computation of rational interval and its applications[J].Acta Electronica Sinica,2018,46(9):11-16.(in Chinese)
[19] 窦家维,王文丽,李顺东.区间位置关系的保密判定[J].计算机学报,2019,42(5):1031-1044. DOU Jia-wei,WANG Wen-li,LI Shun-dong.Privately determining interval location relation[J].Chinese Journal of Computers,2019,42(5):1031-1044.(in Chinese)
[20] STEFANA W,DANIELB M,FABIANB F,et al.Designing privacy-preserving interval operations based on homomorphic encryption and secret sharing techniques[J].Journal of Computer Security,2017,25(1):59-81.
[21] SHI L,LUO Y L,ZHANG C Y.Secure two-party multi-dimensional vector comparison protocol[A].International Conference on Management and Service Science[C].Wuhan:IEEE,2009.1-5.
[22] PAILLIER P.Public-key cryptosystems based on composite degree residuosity classes[A].Advances in Cryptology[C].Czech Republic:Springer,1999.223-238.
[23] NERGIZ A E,NERGIZ M E,Pedersen T,et al.Practical and secure integer comparison and interval check[A].2010 IEEE Second International Conference on Social Computing[C].Minneapolis:IEEE,2010.791-799.

区间关系保密计算若干问题研究

Some Research on Secure Interval Relation Computation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	赵璐, 刘春红, 杜蛟, 曹天庆. Z₄上两类具有最优自相关四元序列的线性复杂度研究[J]. 电子学报, 2021, 49(4): 631-636.
[2]	陈露, 相峰, 孙知信. 基于属性密码体制的区块链安全技术研究进展[J]. 电子学报, 2021, 49(1): 192-200.
[3]	戚珉, 陈明. 标准模型下基于身份的混淆乐观公平交换方案[J]. 电子学报, 2020, 48(8): 1516-1527.
[4]	杨启良, 周彦伟, 杨坤伟, 王涛. 标准模型下可公开验证的匿名IBE方案的安全性分析[J]. 电子学报, 2020, 48(2): 291-295.
[5]	李顺东, 杜润萌, 杨颜璟, 魏琼. 有理数相等的保密判定[J]. 电子学报, 2020, 48(10): 1933-1937.
[6]	窦家维, 陈明艳. 多重集的保密计算及应用[J]. 电子学报, 2020, 48(1): 204-208.
[7]	杨小东, 王美丁, 裴喜祯, 李雨潼, 陈春霖, 麻婷春. 一种标准模型下无证书签名方案的安全性分析与改进[J]. 电子学报, 2019, 47(9): 1972-1978.
[8]	杜蛟, 刘春红, 张恩, 尚玉婧, 董乐. 基于拉丁方的GF(p)上q元旋转对称弹性函数的新构造[J]. 电子学报, 2018, 46(9): 2173-2180.
[9]	窦家维, 王文丽, 刘旭红, 李顺东. 有理区间的安全多方计算与应用[J]. 电子学报, 2018, 46(9): 2057-2062.
[10]	董丽华, 曾勇, 王春红, 胡予濮. LFCSR:基于FCSR的新密码学部件[J]. 电子学报, 2018, 46(8): 1924-1930.
[11]	李顺东, 杨晓莉, 左祥建, 周素芳, 亢佳, 刘新. 保护私有信息的图形相似判定[J]. 电子学报, 2017, 45(9): 2184-2189.
[12]	窦家维, 马丽, 李顺东. 最小值问题的安全多方计算及其应用[J]. 电子学报, 2017, 45(7): 1715-1721.
[13]	许艳, 黄刘生, 田苗苗, 仲红, 崔杰. 一种可证安全的紧致无证书聚合签名方案[J]. 电子学报, 2016, 44(8): 1845-1850.
[14]	王健, 戚文峰, 郑群雄. 模m加法的一类线性逼近关系研究[J]. 电子学报, 2015, 43(11): 2194-2199.
[15]	古春生, 景征骏, 于志敏, 吴访升. 基于遍历矩阵的公钥加密方案的安全性分析[J]. 电子学报, 2014, 42(10): 2081-2085.