点包含问题的安全多方计算

杨晓艺，刘 新，亢 佳

(陕西师范大学 计算机科学学院，陕西 西安 710119)

点包含问题的安全多方计算

杨晓艺，刘 新，亢 佳

(陕西师范大学 计算机科学学院，陕西 西安 710119)

安全多方计算是近年来国际密码学界研究的热点问题，计算几何的多方保密计算越来越受到重视，点包含问题的多方保密计算作为保密计算几何中的一个重要问题也越来越受到关注。考虑到要保密地解决点包含的问题，基于安全多方计算的几个基础协议，即向量点积协议和姚式百万富翁协议，设计了一个可以保密判断线段是否相交的协议，基于此协议的核心思想同时联系相关几何知识，设计了可以保密判断点包含问题的协议，理论分析结果表明所设计的协议在半诚实模型下是正确的和安全的。它们作为重要的安全多方计算基础协议对解决保密计算几何其他相关问题有着重要的实用价值，可以用来进一步解决两个或多个图形是否相交的问题、多个点是否包含在一个图形中的问题等。

安全多方计算；保密计算几何；点包含问题；线段相交问题

0 引 言

安全多方计算是近年来国际密码学界的一个研究热点。这一研究领域由Yao[1]在1982年提出，Goldreich等[2-3]丰富和发展了安全多方计算的理论。安全多方计算包含了密码学中很多的基本模块，具有很大的实用价值，因此受到了越来越多的关注。

安全多方计算的研究在密码学研究中占有非常重要的地位。Goldwasser曾预言[4]，安全多方计算今天所处的地位正是公开密钥密码学10年前所处的地位，成为密码学领域里一个极端重要的工具;丰富的理论将使它成为计算领域一个必不可少的组成部分；它在现实中的应用才刚刚开始，丰富的理论将使它成为计算科学中一个必不可少的组成部分。Goldwasser的这一预言激励着密码学者的不断研究和探索。Goldreich的工作[2-3,5]奠定了安全多方计算的理论基础，即一般的安全多方计算问题理论上都是可解的。但是Goldreich指出，应用一般条件下导出的通用解决方案解决具体问题是不切实际的-效率问题很难解决，因此对于具体问题需要研究具体的解决方案。

Goldwasser的预言和Goldreich的理论促进了具有实际应用背景的安全多方计算问题的研究，所研究的问题包括比较百万富翁问题[1,6]、保密的计算几何问题[7-8]、保密的数据挖掘问题[9]、保密拍卖问题[10]等等。

几何是科学研究中一个非常重要的分支，现实中的许多问题都可以通过一定的方式转成几何问题进行恰当表达。计算几何问题的保密计算是安全多方计算中一个新的研究方向，这些问题具有广泛的应用背景[11]。Du等研究了保密的计算几何问题中的两线段相交问题并给出了解决方案[12]，Luo等研究了两直线之间的位置关系的保密计算问题[13]。在Du的启发下，很多研究人员也开始对保密计算几何问题进行深入研究[13-18]。点包含问题就是计算几何问题中的一个研究热点，基于此问题的研究已有很多。

利用安全多方计算领域的两个基础协议-向量点积协议与姚式百万富翁协议，在半诚实模型下，设计了一个可以保密地判断一私有点与一私有多边形的包含关系的协议，在很大程度上解决了现实生活中的某些实际问题。

1 预备知识

1.1 安全性定义

半诚实参与者[19]：每个参与者都是完全严格按照协议的规定执行协议的每一步，并且在协议执行过程中不会恶意输入虚假数据，也不会中途退出协议。但是它们可能会通过分析和利用协议交互过程中自己所得到的信息来推断其他参与方的相关私有输入信息。

大部分安全多方计算的研究工作都是假设参与者是半诚实的，这是因为Goldreich曾经指出：只要能够在半诚实参与者模型下设计出保密计算f的协议π，就可以通过位承诺方法将π转换成恶意攻击者参与的模型下保密计算f的协议[3]。在这个转换协议中，一个恶意的参与者将被迫按照半诚实参与者的要求执行协议，否则将会被发现。简单地说，半诚实参与者在协议执行过程中将完全按照协议要求执行协议，但他们可能会保留计算的中间结果试图推导出其他参与者的输入。半诚实模型不仅仅是一个重要的研究方法，而且为许多应用环境提供了一个很好的模型。

1.2 向量点积协议

1.3 姚式百万富翁协议

问题描述：Alice有一个私有数据a，Bob有一个私有数据b，双方希望在不泄露自身数据的情况下可以保密地比较两个数据的大小，即得到a>b,a

1.4 向量叉积

两个向量的叉积由下面的行列式确定：

两个向量的叉积具有以下性质：

若叉积为正，那么v1在v2的顺时针方向；若叉积为负，那么v1在v2的逆时针方向；若叉积为零，那么v1与v2共线。

定理1：若两线段的端点分别在对方线段的两侧，则两线段必相交。

2 问题描述及协议实现

基于预备知识中介绍的密码学中的基本协议，对如何保密地判断两线段相交问题及点包含问题进行了描述，并对所提出协议的正确性和安全性进行了分析和讨论。

2.1 线段相交问题的描述

协议1：线段相交问题的保密协议。

输出：P与Q是否相交。

(3)Alice与Bob共同执行向量点积协议。

其中Alice得到u1,u3,v2,v4，Bob得到u2,u4,v1,v3。

(4)Alice与Bob共同执行4次姚式百万富翁协议得到对应的ui,vi的大小。

(5)若下式中存在一个成立，则输出P与Q是否相交，否则输出不相交。

u1>v1∧u2v3∧u4

u1v2∧u3v4

u1>v1∧u2v4

u1v2∧u3>v3∧u4

协议1的正确性：Alice与Bob构造的向量做点积运算得到：

这正是一个叉积，因此可以根据叉积的正负也就是ui和vi的大小来判断这两向量的顺逆时针。因此，若协议1步骤(5)中任一成立，则说明Alice的私有线段端点在Bob线段的两侧且Bob的私有线段端点在Alice线段的两侧，由定理1可知两线段相交。

协议1的安全性：在协议1步骤(3)中，点积协议的结果分别是两个人交叉得到，因此两人无法根据一个结果推出对方线段的端点坐标信息。根据向量点积协议的安全性与姚式百万富翁协议的安全性以及步骤(3)中的交叉处理可知，协议1在半诚实模型下是安全的。

2.2 点包含问题的描述

Alice有一个私有的多边形Q，Q=(x1,y1),(x2,y2),…,(xn,yn)，其中每一对(xi,yi)表示多边形各端点的坐标值。Bob有一个私有的点P，P=(xp,yp)。Alice与Bob想判断点P是否在多边形Q中，又不想泄露自己的私有信息，这一问题即为保密的判断点包含的问题。

协议2：保密判断点包含的协议。

输入：Alice输入多边形Q=(x1,y1),(x2,y2),…,(xn,yn)，Bob输入点P=(xp,yp)。

输出：P在Q中或P不在Q中。

(1)Bob选择一个随机大整数r，构造一点P'=(r,yp)，令PP'近似看作一条射线；

(2)Alice与Bob共同执行协议1求得PP'与多边形的各边是否有交点(其中多边形汇总的水平边不参与计算)；

(3)若交点数为奇数，则输出P在Q中，否则输出P不在Q中。

协议2的正确性：由图1可得协议2的正确性。

图1 协议2的正确性说明

协议2的安全性：由协议1的安全性可知协议2在半诚实模型下是安全的。

3 结束语

保密计算几何中的问题在现实生活的实际意义越来越重要，应用价值越来越高。通过利用向量点积协议、姚式百万富翁协议以及其他一些相关几何知识，提出了在半诚实模型下判断两线段是否相交问题和点包含问题的保密解决方案，同时分析和讨论了这些协议的正确性和安全性。这两个协议可以作为研究其他某些保密计算几何问题的基础协议，对于解决安全多方计算领域的其他相关问题也有重要的理论意义。在后面的工作中，将对协议的性能进行深入分析，进而提出更加安全、高效的解决方案，也会进一步研究多个点是否包含在一个图形中的问题以及两个或多个图形是否相交的问题等。

[1]YaoA.Protocolsforsecurecomputations[C]//23rdannualsymposiumonfoundationsofcomputerscience.[s.l.]:IEEE,1982:160-164.

[2]GoldreichO，MicaliS，WigdersonA.Howtoplayanymentalgame[C]//ProceedingsofthenineteenthannualACMsymposiumontheoryofcomputing.[s.l.]:ACM,1987:218-229.

[3]GoldreichO.Foundationsofcryptography:volume2，basicapplications[M].[s.l.]:CambridgeUniversityPress，2004.

[4]GoldwasserS.Multipartycomputations:pastandpresent[C]//ProceedingsofthesixteenthannualACMsymposiumonprinciplesofdistributedcomputing.[s.l.]:ACM,1997:1-6.

[5]GoldreichO.Securemulti-partycomputation(workingdraft)[EB/OL].2002.http://www.wisdom.weizmann.ac.ilhomeodedpublic-htmlfoc.html.

[6] 李顺东,戴一奇,游启友.姚氏百万富翁问题的高效解决方案[J].电子学报,2005,33(5):769-773.

[7]ShenC，ZhangHG，FengDG，etal.Surveyofinformationsecurity[J].ScienceinChinaSeriesF:InformationSciences，2007，50(3):273-298.

[8]CaoZ，ZhuH，LuR.Provablysecurerobustthresholdpartial

blindsignature[J].ScienceinChinaSeriesF:InformationSciences，2006，49(5):604-615.

[9]LindellY，PinkasB.Privacypreservingdatamining[J].JournalofCryptology，2002，15(3):177-206.

[10]CachinC.Efficientprivatebiddingandauctionswithanobliviousthirdparty[C]//Proceedingsofthe6thACMconferenceoncomputerandcommunicationssecurity.[s.l.]:ACM，1999:120-127.

[11]LiSD，WuCY，WangDS，etal.Securemultipartycomputationofsolidgeometricproblemsandtheirapplications[J].InformationSciences，2014，282:401-413.

[12]DuW，AtallahMJ.Securemulti-partycomputationproblemsandtheirapplications:areviewandopenproblems[C]//Proceedingsofnewsecurityparadigmsworkshop.NewYork:ACMPress，2001:13-22.

[13] 罗永龙,黄刘生,荆巍巍,等.空间几何对象相对位置判定中的私有信息保护[J].计算机研究与发展,2006,43(3):410-416.

[14] 罗永龙，黄刘生，荆巍巍，等.保护私有信息的叉积协议及其应用[J].计算机学报，2007，30(2):248-254.

[15] 李顺东,司天歌,戴一奇.集合包含与几何包含的多方保密计算[J].计算机研究与发展,2005,42(10):1647-1653.

[16] 李顺东,戴一奇,王道顺,等.几何相交问题的多方保密计算[J].清华大学学报:自然科学版,2007,47(10):1692-1695.

[17] 杨晓莉,李顺东,左祥建.计算几何问题的多方保密计算[J].密码学报,2016,3(1):33-41.

[18] 罗永龙,黄刘生,徐维江,等.一个保护私有信息的多边形相交判定协议[J].电子学报,2007,35(4):685-691.

[19] 李顺东,王道顺,戴一奇,等.两个集合相等的多方保密计算[J].中国科学:信息科学,2009,39(3):305-310.

Secure Multi-party Computation for Point Inclusion Problems

YANG Xiao-yi，LIU Xin，KANG Jia

(School of Computer Science，Shaanxi Normal University，Xi’an 710119，China)

Secure multi-party computation is one of the hot spots in international cryptography research community in recent years，and more and more attention has been paid to the secure computational geometry.As an important problem of secure computational geometry,more interests have been paid on point-inclusion problem.A secure protocol for determining whether two segments are intersecting with several basic protocols,Scalar Product Protocol and Yao’s Millionaire’s Protocol,has been developed.Thus based on core of the protocol designed and related geometric knowledge,a secure protocol to solve the point-inclusion problem has been developed.Theoretical analysis results show that these two protocols are correct and secure under semi honest model.As a part of important secure multi-party computational protocols,they both imply important practical value in solving the problem of secure multi-party computational geometry and can be used to solve the problems,whether two or more graphics are intersected and whether multiple points are contained in a graphic etc..

secure multi-party computation;computational geometry;point-inclusion problem;segment-intersection problem

2016-06-17

2016-09-28 网络出版时间：2017-03-13

中央高校基本科研业务费专项(GK20150417)；内蒙古自治区包头市科技计划项目(2014S2004-2-1-15)

杨晓艺(1993-)，女，硕士研究生，研究方向为计算机与网络安全。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170313.1547.098.html

TP31

A

1673-629X(2017)05-0120-03

10.3969/j.issn.1673-629X.2017.05.025