馬敏耀，左 羽，熊偉程

（貴州師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，貴州 貴陽(yáng) 550018）

基于健忘傳輸?shù)陌踩p方向量相等協(xié)議

馬敏耀，左 羽，熊偉程

（貴州師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，貴州 貴陽(yáng) 550018）

安全多方計(jì)算研究的是如何使一組互不信任的參與方聯(lián)合實(shí)現(xiàn)保護(hù)隱私的協(xié)同計(jì)算問(wèn)題，即在保證計(jì)算結(jié)果正確的同時(shí)，確保任何參與方的隱私輸入都未向任何人泄露。向量相等問(wèn)題是一類重要的安全雙方計(jì)算問(wèn)題，以健忘傳輸協(xié)議為基本密碼學(xué)原語(yǔ)，在半誠(chéng)實(shí)模型下，提出一種安全雙方向量相等協(xié)議，證明了協(xié)議的正確性和安全性，并對(duì)協(xié)議的復(fù)雜度進(jìn)行了說(shuō)明。

安全多方計(jì)算；健忘傳輸；向量相等問(wèn)題

引言

安全多方計(jì)算研究的是如何使一組互不信任的參與方聯(lián)合實(shí)現(xiàn)保護(hù)隱私的協(xié)同計(jì)算問(wèn)題，即在保證計(jì)算結(jié)果正確的同時(shí)，確保任何參與方的隱私輸入都未向任何人泄露。具體地講，安全多方計(jì)算是這樣的一種分布式協(xié)議：n個(gè)參與方A1,A2,…,An分別擁有自己的秘密輸入x1,x2,…，xn，在不借助任何第三方的情況下，它們聯(lián)合計(jì)算某個(gè)n變?cè)δ芎瘮?shù)（functionality）（y1，y2，…，yn）=f（x1，x2，…，xn），且至少滿足兩個(gè)基本特性：（1）正確性，即每個(gè)參與方Ai都得到本方的正確輸出yi；（2）安全性，即任何參與方的輸入xi都未泄露給其它人，包括協(xié)議的其它參與方以及其它任何第三方。

安全多方計(jì)算的思想由圖靈獎(jiǎng)獲得者Yao于1982年在文獻(xiàn)[1]中提出來(lái)的。Yao在該開(kāi)創(chuàng)性工作中提出了著名的“百萬(wàn)富翁問(wèn)題”，即在保證各自的輸入不被泄露的前提下，雙方比較兩個(gè)整數(shù)的大小關(guān)系。文獻(xiàn)[2-4]對(duì)“百萬(wàn)富翁問(wèn)題”展開(kāi)充分的研究。文獻(xiàn)[5]將“百萬(wàn)富翁問(wèn)題”推廣到安全雙方向量占優(yōu)問(wèn)題，即Alice和Bob分別擁有n維向量A=（a1…an）和B=（b1…bn），在保證各自的輸入不被泄露的前提下，輸出A占優(yōu)B（即ai>bi對(duì)所有的i都成立）、B占優(yōu)A或互不占優(yōu)。Du在文獻(xiàn)[5]中對(duì)安全雙方向量占優(yōu)問(wèn)題進(jìn)行了研究。

文獻(xiàn)[6]提出了百萬(wàn)富翁問(wèn)題的一個(gè)變體，即社會(huì)主義百萬(wàn)富翁問(wèn)題：在保證各自的輸入不被泄露的前提下，雙方比較兩個(gè)整數(shù)是否相等。文獻(xiàn)[7]將社會(huì)主義百萬(wàn)富翁問(wèn)題推廣到安全雙方向量相等問(wèn)題，即在保證各自的輸入不被泄露的前提下，雙方比較兩個(gè)向量是否相等。文獻(xiàn)[7]基于向量點(diǎn)積協(xié)議構(gòu)建了一種安全雙方向量相等協(xié)議，但該協(xié)議較難直接計(jì)算出最終結(jié)果。

本文研究安全雙方向量相等問(wèn)題，以健忘傳輸協(xié)議OT1p為基本密碼學(xué)原語(yǔ)，在半誠(chéng)實(shí)模型下，提出一種安全雙方向量相等協(xié)議，證明了協(xié)議的正確性和安全性，并對(duì)協(xié)議的復(fù)雜度進(jìn)行了說(shuō)明。

1 基礎(chǔ)知識(shí)

健忘傳輸協(xié)議OT1p：協(xié)議開(kāi)始前，Bob擁有p個(gè)輸入x1,x2,…,xp，Alice擁有一個(gè)整數(shù)k（1≤k≤p）；協(xié)議執(zhí)行結(jié)束后，Bob不知道k的任何信息，Alice得到xk但不知道xj（1≤j≤p,j≠k）的任何信息。

半誠(chéng)實(shí)模型：假定協(xié)議的參與者嚴(yán)格地遵循協(xié)議規(guī)則，并容許其記錄協(xié)議執(zhí)行過(guò)程中的所有中間結(jié)果，并以此來(lái)分析和推導(dǎo)其它參與者的秘密輸入。

2 安全雙方向量相等協(xié)議

本節(jié)將基于OT1p協(xié)議，構(gòu)建安全雙方向量相等協(xié)議，并在半誠(chéng)實(shí)模型下，證明協(xié)議的正確性和安全性，最后給出協(xié)議的復(fù)雜度說(shuō)明。用F表示階為q（即|F|=q）的有限域，F(xiàn)n表示F上的n（n>1）維行向量空間。

2.1 協(xié)議描述

安全雙方向量相等協(xié)議

輸入：Alice擁有行向量v∈Fn，Bob擁有行向量w∈Fn。

輸出：v=w或v≠w。

（1）協(xié)議準(zhǔn)備階段

（2）協(xié)議執(zhí)行階段

第1步：Alice和Bob執(zhí)行d輪子協(xié)議，其中第j（1≤j≤d）輪的協(xié)議流程如下（Alice和Bob分別以vj和wj為秘密輸入）：

（1）Alice生成本輪的p個(gè)行向量{u1,u2,···,up}?Fn，其中uk（j）=vj且k（j）是本輪中Alice的秘密下標(biāo)，其余p-1個(gè)向量隨機(jī)選取。Alice將有序向量列（u1,u2,···,up）發(fā)送給Bob。

（2）Bob生成本輪的隨機(jī)行向量ej∈Fn并計(jì)算

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

（3）Alice和Bob分別以k（j）和（h1,h2,···,hp）為輸入調(diào)用OT1p協(xié)議，最終Alice得到本輪的輸出hk（j）。

第4步：Alice將比較結(jié)果發(fā)送給Bob，協(xié)議結(jié)束。

2.2 協(xié)議正確性說(shuō)明

定理1 在半誠(chéng)實(shí)模型下，協(xié)議1執(zhí)行結(jié)束后輸出正確的結(jié)果。

證明 在半誠(chéng)實(shí)模型下，Alice和Bob都嚴(yán)格遵守協(xié)議規(guī)則。由協(xié)議描述，有

由于M是可逆矩陣，有

v=w?v-w=0?（v-w）M=0?α=0，故結(jié)論正確。

2.3 協(xié)議安全性說(shuō)明

定理2 假設(shè)調(diào)用的OT1p協(xié)議是安全的，且p和d的選取滿足pd≥qn（其中q是域的階，n是向量長(zhǎng)度），則協(xié)議1在半誠(chéng)實(shí)模型下是安全的。

證明 對(duì)“v=w”的情形，協(xié)議結(jié)束后，Alice和Bob都得到了正確的結(jié)果，即雙方都知道對(duì)方的輸入與自己的輸入相同。因此下面僅討論“v≠w”的情形。

（1）Bob被腐敗的情況

在第4步中，Alice將結(jié)果“v≠w”發(fā)送給Bob，Bob由此沒(méi)法得到有關(guān)v額外信息。

（2）Alice被腐敗的情況

2.4 協(xié)議復(fù)雜度說(shuō)明

協(xié)議準(zhǔn)備階段，雙方均產(chǎn)生d-1個(gè)隨機(jī)向量，且Bob產(chǎn)生1個(gè)可逆矩陣；協(xié)議執(zhí)行階段，雙方需執(zhí)行d次OT1p協(xié)議，此外，Alice需產(chǎn)生（p-1）d個(gè)隨機(jī)向量，Bob需執(zhí)行n2pd次乘法運(yùn)算。

3 總結(jié)與展望

本文研究安全雙方向量相等問(wèn)題，以健忘傳輸協(xié)議OT1p為基本密碼學(xué)原語(yǔ)，在半誠(chéng)實(shí)模型下，提出一種安全雙方向量相等協(xié)議，證明了協(xié)議的正確性和安全性，對(duì)協(xié)議的復(fù)雜度進(jìn)行了說(shuō)明。

[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]耿濤.安全多方計(jì)算若干問(wèn)題以及應(yīng)用研究[D].北京郵電大學(xué)，2012.

[責(zé)任編輯：莊 鵬]

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

貴州省科學(xué)技術(shù)基金計(jì)劃項(xiàng)目（項(xiàng)目編號(hào)：黔科合基礎(chǔ)[2016]1115）；貴州省科技平臺(tái)及人才團(tuán)隊(duì)計(jì)劃-科普示范基地項(xiàng)目（黔科合平臺(tái)人才[2017]5503）；貴州省教育廳青年科技人才成長(zhǎng)項(xiàng)目（項(xiàng)目編號(hào)：黔教合KY字[2016]220）；貴州省教育科學(xué)規(guī)劃課題項(xiàng)目（項(xiàng)目編號(hào)：2015B222）；貴州師范學(xué)院“一體兩翼”學(xué)科專業(yè)發(fā)展專項(xiàng)科學(xué)研究項(xiàng)目（項(xiàng)目編號(hào)：2016YTLY10）；貴州師范學(xué)院2015 年度校級(jí)博士課題研究成果（項(xiàng)目編號(hào)：2015BS011）；2016年貴州省省級(jí)重點(diǎn)支持學(xué)科“計(jì)算機(jī)應(yīng)用技術(shù)”（黔學(xué)位合字ZDXK[2016]20號(hào)）;2016年度貴州省科技平臺(tái)及人才團(tuán)隊(duì)專項(xiàng)資金項(xiàng)目（項(xiàng)目編號(hào)：黔科合平臺(tái)人才[2016]5609）。

馬敏耀（1979-），男，貴州威寧人，博士，貴州師范學(xué)院副教授，高級(jí)工程師，研究方向：密碼學(xué)與網(wǎng)絡(luò)安全、大數(shù)據(jù)隱私保護(hù)、物聯(lián)網(wǎng)安全。

TN918.1

A

1674-7798（2016）12-0019-03