保护私有信息的点线关系判定协议及其应用

doi:10.13190/jbupt.200802.72.liuw

北京邮电大学学报 ›› 2008, Vol. 31 ›› Issue (2): 72-75.doi: 10.13190/jbupt.200802.72.liuw

保护私有信息的点线关系判定协议及其应用

刘文1,3，罗守山2,3，陈萍4

1. 北京邮电大学计算机科学与技术学院, 北京100876; 2. 北京邮电大学软件学院, 北京100876; 3. 西安电子科技大学综合业务网理论及关键技术国家重点实验室, 西安 710071; 4. 北京邮电大学电信工程学院, 北京100876

收稿日期:2007-06-13 修回日期:1900-01-01 出版日期:2008-04-28 发布日期:2008-04-28
通讯作者: 刘文

Privacy-Preserving Point-Line Relation Determination Protocol and Its Applications

LIU Wen1,3, LUO Shou-shan2,3, CHEN Ping4

. School of Computer Science and Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China; 2. School of Software Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China; 3. National Key Laboratory of Integrated Service Networks, Xidian University, Xi’an 710071,China; 4.School of Telecommunication Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China;

Received:2007-06-13 Revised:1900-01-01 Online:2008-04-28 Published:2008-04-28
Contact: LIU Wen

摘要/Abstract

摘要：

在半诚实模型下利用加法同态加密体制设计了一个保护私有信息的点线关系判定协议，并且利用上述协议设计了保护私有信息的线段相交判定问题和保护私有信息的点包含判定问题的解决方案。保护私有信息的点线关系判定协议可以保密地判断点在直线正侧、负侧、在直线上，保护私有信息的线段相交判定协议可以保密地判断不同参与方拥有的直线是否相交，保护私有信息的点包含判定协议可以保密判断不同参与方拥有点和多边形之间的包含关系；分析和证明了这些协议的正确性、安全性和复杂性。

关键词: 安全多方计算, 计算几何, 点线关系判定, 加法同态加密体制

Abstract:

A privacy-preserving point-line relation determination protocol based on additive homomorphism encryption is developed in semi-honest model. The privacy-preserving point-line relation determination protocol can be used to solve many privacy-preserving computational geometry problems, such as segments intersection problem and point inclusion problem. The privacy-preserving point-line relation determination protocol can be also used to determine either the point is at the positive side, negative side, or on the line privately. Further more, the privacy-preserving segments intersection protocol can be used to determine two lines supplied by different users intersect securely; and the privacy-preserving point inclusion protocol can be used to determine the relation of a point and a polygon supplied by different users. Finally, the correctness, security and efficiency of these protocols are analyzed.

Key words: secure multi-party computation, computational geometry, point-line relation determination, additive homomorphic encryption

中图分类号:

TP390

刘文，罗守山，陈萍. 保护私有信息的点线关系判定协议及其应用[J]. 北京邮电大学学报, 2008, 31(2): 72-75.

LIU Wen1,3, LUO Shou-shan2,3, CHEN Ping4. Privacy-Preserving Point-Line Relation Determination Protocol and Its Applications[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2008, 31(2): 72-75.

参考文献

[1] Yao Qizhi. Protocols for secure computations//Proceedings of 23rd Annual IEEE Symposium on Foundations of Computer Science. Los Alamitos: IEEE Computer Society Press, 1982: 160-164.
[2] Goldreich O, Micali S, Wigderson A. How to play any mental game//The 19th Annual ACM Conference on Theory of Computing. New York: ACM, 1987: 218-229.
[3] Du Wenliang, Atallah M J. Privacy-preserving cooperative scientific computations//Proceedings of the 14th IEEE Computer Security Workshop. Nova Scotia: IEEE Computer Society Press, 2001: 273-282.
[4] Mikhail J A, Du Wenliang. Secure multi-party computational geometry//Proceedings of the 7th International Workshop on Algorithms and Data Structures. Berlin: Springer, 2001: 165-179.
[5] Lindell Y, Pinkas B. Privacy preserving data mining[J]. Journal of Cryptology, 2002, 15(3): 177-206.
[6] 刘文, 罗守山, 陈萍. 利用El Gamal密码体制解决安全多方多数据排序问题[J]. 通信学报, 2007, 28(10):1-5. Liu Wen, Luo Shoushan, Chen Ping. Solution for secure multi-party multi-data ranking problem based on El Gamal encryption[J]. Journal of China Institute of Communications, 2007, 28(10): 1-5.
[7] 刘文, 罗守山, 陈萍. 基于滑动窗口和交换加密函数解决SMP的新方案[J]. 计算机工程, 2007, 33(22): 163-171. Liu Wen, Luo Shoushan, Chen Ping. Solution to SMP based on sliding window and commutation encryption function[J]. Computer Engineering, 2007, 33(22): 163-171.
[8] 罗永龙, 黄刘生, 荆巍巍, 等. 空间几何对象相对位置判定中的私有信息保护[J]. 计算机研究与发展, 2006, 43(3): 410-416. Luo Yonglong, Huang Liusheng, Jing Weiwei, et al. Privacy protection in the relative position determination for two spatial geometric objects[J]. Journal of Computer Research and Development, 2006, 43(3): 410-416.

[1]	李涛, 张静, 杨皓. 一种车载网隐私保护方案的分析与改进[J]. 北京邮电大学学报, 2020, 43(1): 104-110.
[2]	张静, 罗守山, 杨义先, 辛阳. 安全两方集合交集云外包计算协议[J]. 北京邮电大学学报, 2019, 42(2): 13-18.
[3]	马敏耀, 吴恋, 陈松良, 左羽, 汤艳玲. 基于加法同态加密体制的安全变换相等判定协议[J]. 北京邮电大学学报, 2017, 40(s1): 140-144.
[4]	宋成, 张明月, 彭维平, 贾宗璞, 刘志中. 基于安全多方计算的车载网隐私保护机制[J]. 北京邮电大学学报, 2017, 40(3): 67-71.
[5]	庞雷，罗守山，耿涛，王柏，辛阳. 保护隐私的逢低买入拍卖协议及其推广[J]. 北京邮电大学学报, 2012, 35(3): 99-102.
[6]	耿涛,李海成,罗守山，贾哲. 保护私有信息的动点距离判定协议及其推广[J]. 北京邮电大学学报, 2012, 35(3): 47-51.
[7]	许芬,庞雷,罗守山，王枞. 扩展代理多方计算及其协议[J]. 北京邮电大学学报, 2011, 34(4): 118-121.
[8]	刘文罗守山肖倩杨义先辛阳. 安全两方圆计算问题的研究[J]. 北京邮电大学学报, 2009, 32(3): 32-35.
[9]	肖倩罗守山杨文川郑康锋. 安全多方模糊综合评判模型及协议[J]. 北京邮电大学学报, 2009, 32(3): 5-9.
[10]	罗守山廖干才刘文. 保护私有信息的三角不等式判定协议及其应用[J]. 北京邮电大学学报, 2009, 32(1): 47-51.
[11]	郑强罗守山辛阳. 无条件安全的隐私保护的集合模式匹配协议[J]. 北京邮电大学学报, 2009, 32(1): 99-102.
[12]	马敏耀1, 罗守山1,2, 王励成1. 映射相等问题的安全双方计算协议[J]. 北京邮电大学学报, 2008, 31(6): 5-8.

保护私有信息的点线关系判定协议及其应用

Privacy-Preserving Point-Line Relation Determination Protocol and Its Applications

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

本文评价