摘要
安全多方计算是目前国际密码学界研究的热点,有理数与有理区间以及两个有理区间位置关系的保密计算问题属于安全多方科学计算中的重要问题,在保密的计算几何以及商品价格商议等方面有重要的应用前景.目前关于这类问题的研究结果还很少,仅有少量关于有理数与有理区间位置关系保密判定问题的研究结果,关于两个有理区间位置关系保密计算问题尚未见到任何研究.本文首先采用以多项式表示区间的技巧,将有理数域内点与区间的保密计算问题转化为整数集上向量内积值的正负判定问题,设计构造了关于有理数域内点与区间位置关系判定问题安全高效的新协议,并以此为基础设计构造了保密判定两区间位置关系的判定协议,首次研究解决了两个有理区间位置关系判定问题.本文还将两个有理数的大小比较问题转化为整数集上向量内积值的正负判定问题,设计了有理数大小比较问题高效的判定协议.严格证明了本文协议在半诚实模型下的安全性,并进一步设计了恶意模型下点与区间位置关系的安全判定协议.文中最后举例说明了有理区间保密判定协议在解决实际问题中的应用,并将本文所设计的协议与已有相关结果进行了分析比较及实例验证,理论分析和实验结果都表明本文协议具有较高的计算效率.
Secure multiparty computation is a focus in the international cryptographic community in recent years, which has wide application in both information security and privacy-preserving practice. Secure multiparty computation can be classified into the following fields: secure scientific computation;secure geometric computation;secure multiparty statistical analysis;privacy-preserving data mining;and secure multiparty computation application system construction. Secure multiparty scientific computation is an important field of secure multiparty computation. In this field, cryptographic scholars have studied many secure multiparty scientific computation problems such as private comparing, sorting, maximum computing, set operations, scalar product, Hamming distance computing, and there are still many secure multiparty scientific computation problems need to be further studied. In this paper, we study how to privately determine the relation between a rational number and a rational interval, and the relation between two rational intervals. They are two secure multiparty scientific computation problems which have important application prospect in secure multiparty computational geometry and e - commerce. As far as we know, there hardly are works on these problems. There are a few literatures addressing the relation between a rational number and a rational interval. The relation between two rational intervals has not been investigated in the scenarios of secure multiparty computation. Representing an interval as a polynomial, we reduce privately determining the relation between a rational number and a rational interval to privately determining the sign of the scalar product of two integer vectors, and design, using the Paillier additively homomorphic cryptosystem, an efficient protocol to privately compute the sign of the scalar product of two private vectors, and further use it to construct a protocol to privately determine the relation between a rational number and a rational interval. This protocol achieves constant com
作者
窦家维
王文丽
李顺东
DOU Jia-Wei;WANG Wen-Li;LI Shun-Dong(School of Mathematics and Information Science, Shaanxi Normal University, Xi’an 710062;School of Computer Science, Shaanxi Normal University, Xi’an 710062)
出处
《计算机学报》
EI
CSCD
北大核心
2019年第5期1031-1044,共14页
Chinese Journal of Computers
基金
国家自然科学基金面上项目(61272435)资助~~
关键词
密码学
安全多方计算
有理数
有理区间
区间保密计算
安全性
cryptography
secure multiparty computation
rational number
rational interval
privacy-preserving interval evaluation
security
