基于健忘传输的安全双方向量相等协议

马敏耀，左 羽，熊伟程

（贵州师范学院数学与计算机科学学院，贵州 贵阳 550018）

基于健忘传输的安全双方向量相等协议

马敏耀，左 羽，熊伟程

（贵州师范学院数学与计算机科学学院，贵州 贵阳 550018）

安全多方计算研究的是如何使一组互不信任的参与方联合实现保护隐私的协同计算问题，即在保证计算结果正确的同时，确保任何参与方的隐私输入都未向任何人泄露。向量相等问题是一类重要的安全双方计算问题，以健忘传输协议为基本密码学原语，在半诚实模型下，提出一种安全双方向量相等协议，证明了协议的正确性和安全性，并对协议的复杂度进行了说明。

安全多方计算；健忘传输；向量相等问题

引言

安全多方计算研究的是如何使一组互不信任的参与方联合实现保护隐私的协同计算问题，即在保证计算结果正确的同时，确保任何参与方的隐私输入都未向任何人泄露。具体地讲，安全多方计算是这样的一种分布式协议：n个参与方A1,A2,…,An分别拥有自己的秘密输入x1,x2,…，xn，在不借助任何第三方的情况下，它们联合计算某个n变元功能函数（functionality）（y1，y2，…，yn）=f（x1，x2，…，xn），且至少满足两个基本特性：（1）正确性，即每个参与方Ai都得到本方的正确输出yi；（2）安全性，即任何参与方的输入xi都未泄露给其它人，包括协议的其它参与方以及其它任何第三方。

安全多方计算的思想由图灵奖获得者Yao于1982年在文献[1]中提出来的。Yao在该开创性工作中提出了著名的“百万富翁问题”，即在保证各自的输入不被泄露的前提下，双方比较两个整数的大小关系。文献[2-4]对“百万富翁问题”展开充分的研究。文献[5]将“百万富翁问题”推广到安全双方向量占优问题，即Alice和Bob分别拥有n维向量A=（a1…an）和B=（b1…bn），在保证各自的输入不被泄露的前提下，输出A占优B（即ai>bi对所有的i都成立）、B占优A或互不占优。Du在文献[5]中对安全双方向量占优问题进行了研究。

文献[6]提出了百万富翁问题的一个变体，即社会主义百万富翁问题：在保证各自的输入不被泄露的前提下，双方比较两个整数是否相等。文献[7]将社会主义百万富翁问题推广到安全双方向量相等问题，即在保证各自的输入不被泄露的前提下，双方比较两个向量是否相等。文献[7]基于向量点积协议构建了一种安全双方向量相等协议，但该协议较难直接计算出最终结果。

本文研究安全双方向量相等问题，以健忘传输协议OT1p为基本密码学原语，在半诚实模型下，提出一种安全双方向量相等协议，证明了协议的正确性和安全性，并对协议的复杂度进行了说明。

1 基础知识

健忘传输协议OT1p：协议开始前，Bob拥有p个输入x1,x2,…,xp，Alice拥有一个整数k（1≤k≤p）；协议执行结束后，Bob不知道k的任何信息，Alice得到xk但不知道xj（1≤j≤p,j≠k）的任何信息。

半诚实模型：假定协议的参与者严格地遵循协议规则，并容许其记录协议执行过程中的所有中间结果，并以此来分析和推导其它参与者的秘密输入。

2 安全双方向量相等协议

本节将基于OT1p协议，构建安全双方向量相等协议，并在半诚实模型下，证明协议的正确性和安全性，最后给出协议的复杂度说明。用F表示阶为q（即|F|=q）的有限域，Fn表示F上的n（n>1）维行向量空间。

2.1 协议描述

安全双方向量相等协议

输入：Alice拥有行向量v∈Fn，Bob拥有行向量w∈Fn。

输出：v=w或v≠w。

（1）协议准备阶段

（2）协议执行阶段

第1步：Alice和Bob执行d轮子协议，其中第j（1≤j≤d）轮的协议流程如下（Alice和Bob分别以vj和wj为秘密输入）：

（1）Alice生成本轮的p个行向量{u1,u2,···,up}⊆Fn，其中uk（j）=vj且k（j）是本轮中Alice的秘密下标，其余p-1个向量随机选取。Alice将有序向量列（u1,u2,···,up）发送给Bob。

（2）Bob生成本轮的随机行向量ej∈Fn并计算

hi=（ui-wj）M+ej,i=1,2,···,p。

（3）Alice和Bob分别以k（j）和（h1,h2,···,hp）为输入调用OT1p协议，最终Alice得到本轮的输出hk（j）。

第4步：Alice将比较结果发送给Bob，协议结束。

2.2 协议正确性说明

定理1 在半诚实模型下，协议1执行结束后输出正确的结果。

证明 在半诚实模型下，Alice和Bob都严格遵守协议规则。由协议描述，有

由于M是可逆矩阵，有

v=w⟺v-w=0⟺（v-w）M=0⟺α=0，故结论正确。

2.3 协议安全性说明

定理2 假设调用的OT1p协议是安全的，且p和d的选取满足pd≥qn（其中q是域的阶，n是向量长度），则协议1在半诚实模型下是安全的。

证明 对“v=w”的情形，协议结束后，Alice和Bob都得到了正确的结果，即双方都知道对方的输入与自己的输入相同。因此下面仅讨论“v≠w”的情形。

（1）Bob被腐败的情况

在第4步中，Alice将结果“v≠w”发送给Bob，Bob由此没法得到有关v额外信息。

（2）Alice被腐败的情况

2.4 协议复杂度说明

协议准备阶段，双方均产生d-1个随机向量，且Bob产生1个可逆矩阵；协议执行阶段，双方需执行d次OT1p协议，此外，Alice需产生（p-1）d个随机向量，Bob需执行n2pd次乘法运算。

3 总结与展望

本文研究安全双方向量相等问题，以健忘传输协议OT1p为基本密码学原语，在半诚实模型下，提出一种安全双方向量相等协议，证明了协议的正确性和安全性，对协议的复杂度进行了说明。

[1]A.C.C.Yao.Protocolsforsecurecomputations[C].In：FOCS’82，1982：80-91.

[2]I.Ioannidis，A.Grama.Anefficientprotocolforyao’smillionaires’problem[C].In：Proceedingsofthe36thHawaiiInternatinalConferenceonSystemSciences，2003：205-210.

[3]I.F.Blake，V.Kolesnikov.Strongconditionaloblivioustransferandcomputingonintervals[C].In：ASIACRYPT’04，2004：515-529.

[4]S.D.Li，D.S.Wang，Y.Q.Dai，etal.SymmetriccryptographicsolutiontoYao'smillionaires'problemandanevaluationofsecuremultipartycomputations[J].InformationSciences，2008：178，244-255.

[5]WLDu.Astudyofseveralspecificsecuretwo-partycomputationproblems[D].PurdueUniversity，USA，2000.

[6]M.Jakobsson，M.Yung.Provingwithoutknowing：Onoblivious，agnosticandblindfoldedprovers[C].In：CRYPTO’96.1996，186-200.

[7]耿涛.安全多方计算若干问题以及应用研究[D].北京邮电大学，2012.

[责任编辑：庄 鹏]

Secure two-party vector-equivalence protocol based on oblivious transfer

MA Min-yao, ZUO Yu, XIONG Wei-cheng

（Guizhou Education University, Guiyang, Guizhou, 550018）

Secure multi-party computation is to enable a set of players to compute an arbitrary agreed function of their private inputs.The computation must guarantee the correctness of the outputs while preserving the secrecy of the players' inputs, even if some of the players are corrupted.Vector-equivalence problem is an important secure two-party computation problem.Based on the 1-out-of-n oblivious transfer protocol, the secure two-party vector-equivalence protocol is proposed in the presence of semi-honest adversaries.Furthermore, the correctness, security and completeness of the protocol are proved.

Secure multi-party computation; oblivious transfer; vector-equivalence problem

2016-07-10

贵州省科学技术基金计划项目（项目编号：黔科合基础[2016]1115）；贵州省科技平台及人才团队计划-科普示范基地项目（黔科合平台人才[2017]5503）；贵州省教育厅青年科技人才成长项目（项目编号：黔教合KY字[2016]220）；贵州省教育科学规划课题项目（项目编号：2015B222）；贵州师范学院“一体两翼”学科专业发展专项科学研究项目（项目编号：2016YTLY10）；贵州师范学院2015 年度校级博士课题研究成果（项目编号：2015BS011）；2016年贵州省省级重点支持学科“计算机应用技术”（黔学位合字ZDXK[2016]20号）;2016年度贵州省科技平台及人才团队专项资金项目（项目编号：黔科合平台人才[2016]5609）。

马敏耀（1979-），男，贵州威宁人，博士，贵州师范学院副教授，高级工程师，研究方向：密码学与网络安全、大数据隐私保护、物联网安全。

TN918.1

A

1674-7798（2016）12-0019-03