張俊偉，陳治平，馬建峰，楊　力

(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院，陜西西安710071)

?

可證明安全的基于位置的Prover-to-Prover密鑰交換協(xié)議

張俊偉，陳治平，馬建峰，楊力

(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院，陜西西安710071)

摘要：本文針對(duì)兩個(gè)證明者之間可證明安全的基于位置密鑰交換協(xié)議展開研究.首次將基于位置密鑰交換分為P2V(Prover-to-Verifier)模式和P2P(Prover-to-Prover)模式，并給出P2P模式下基于位置密鑰交換的安全定義.隨后，在1維空間下設(shè)計(jì)了可證明安全的基于位置P2P密鑰交換協(xié)議P2PKE1，并以此為基礎(chǔ)構(gòu)造了d(1≤d≤3)維空間下基于位置P2P密鑰交換協(xié)議P2PKEd.同時(shí)，分別提出了具有密鑰確認(rèn)性質(zhì)的基于位置P2P密鑰交換協(xié)議P2PKEd-c和無密鑰托管的基于位置P2P密鑰交換協(xié)議P2PKEd-e.最后，從安全性和效率兩方面對(duì)所設(shè)計(jì)的協(xié)議進(jìn)行了討論.

關(guān)鍵詞：P2P;基于位置密鑰交換; BRM模型;可證明安全

1　引言

隨著無線設(shè)備的地理位置在無線系統(tǒng)的數(shù)據(jù)采集、安全通信、資源管理、異常處理/維護(hù)等多方面扮演越來越重要的角色，基于位置系統(tǒng)中與地理位置相關(guān)的安全問題也越發(fā)引人關(guān)注［1～3］.

Liu和Ning針對(duì)無線傳感器網(wǎng)絡(luò)提出了一個(gè)基于位置的密鑰預(yù)分發(fā)方案［4］.Yang和Xiao應(yīng)用基于網(wǎng)格多項(xiàng)式密鑰建立方法來解決無線傳感網(wǎng)絡(luò)的安全問題［5］.Huang等針對(duì)無線傳感網(wǎng)絡(luò)提出了一種基于位置的密鑰管理方案［6］，Younis等人則提出了一種基于位置的分布式密鑰管理方案［7］.Zhang等人結(jié)合用戶身份和地理位置得出基于位置密鑰，并提出了一種基于位置的安全機(jī)制［8，9］.

作為基于位置的安全機(jī)制的核心，大多數(shù)的定位協(xié)議無法抵御多個(gè)敵手的共謀攻擊，無法達(dá)到密碼學(xué)意義的可證明安全［10］.

Chandran等人提出了基于位置密碼學(xué)的概念［10］.基于BRM模型(Bounded Retrieval Model)，Chandran等人在BRM模型下實(shí)現(xiàn)了能夠抵制共謀攻擊的可證明安全的定位協(xié)議和基于位置的密鑰交換協(xié)議.隨后，一些量子計(jì)算環(huán)境下基于位置的密碼協(xié)議也隨之出現(xiàn)［11～13］.

然而，現(xiàn)有的基于位置密鑰交換協(xié)議只能夠?qū)崿F(xiàn)證明者和驗(yàn)證者之間的密鑰確立，即Prover-to-Verifier(P2V)模式.這種模式并不能直接應(yīng)用于某些基于位置系統(tǒng)中.例如，參與方A(處于位置pa)希望與參與方B(處于位置pb)進(jìn)行基于位置的密鑰交換.

顯然，在兩個(gè)證明者之間的基于位置密鑰交換，即Prover-to-Prover(P2P)模式，也是基于位置密鑰交換中的一個(gè)重要任務(wù).本文針對(duì)BRM模型下可證明安全的基于位置P2P密鑰交換協(xié)議展開研究.具體如下:

(1)將基于位置密鑰交換分為兩個(gè)模式，即P2V模式和P2P模式.提出基于位置P2P密鑰交換的安全定義.

(2)在BRM模型下，在1維空間下設(shè)計(jì)了一個(gè)基于位置的P2P密鑰交換協(xié)議.

(3)在上述協(xié)議基礎(chǔ)上，構(gòu)建d維(1≤d≤3)空間下基于位置的P2P密鑰交換協(xié)議.

(4)提出滿足密鑰確認(rèn)(With Key Confirmation)的基于位置P2P密鑰交換協(xié)議和無密鑰托管(Without Key Escrow)的基于位置P2P密鑰交換協(xié)議.

2　基于位置密鑰交換的兩種模式

2.1P2V模式

在P2V模式下，d維的基于位置密鑰交換協(xié)議［10，11］包括:一個(gè)證明者，至少(d + 1)個(gè)驗(yàn)證者，以及多個(gè)共謀敵手.在P2V密鑰交換協(xié)議完成之后，位于合法位置的證明者能夠抵御多個(gè)共謀敵手的攻擊，與驗(yàn)證者實(shí)現(xiàn)安全的密鑰交換過程.已有的基于位置密鑰交換協(xié)議都屬于P2V模式，其中包括BRM模型下的密鑰交換協(xié)議［10］，以及量子環(huán)境下的密鑰協(xié)議［11～13］.

2.2P2P模式

與P2V模式不同，P2P模式實(shí)現(xiàn)(在驗(yàn)證者的輔助下)兩個(gè)證明者之間基于位置的密鑰交換，如圖1所示.

令π為d維空間基于位置P2P密鑰交換協(xié)議.該協(xié)議由兩個(gè)算法組成，即π=(Init，Key):位置初始化算法Init(P)和密鑰交換算法Key(Ver，P1，p1，P2，p2).令驗(yàn)證者為Ver = { V0，V1，…，VD}，位置分別為pos0，pos1，…，posD且(D≥d).令PPT(probabilistic polynomial time)的共謀敵手為Adv = { A1，A2，…，AK}，位置分別為apos1，apos2，…，aposK.算法Init(P)可以初始化證明者P的位置，即Init(P)= p表示證明者P的位置為p.算法Key(Ver，P1，p1，P2，p2)能夠抵御共謀敵手Adv = { A1，A2，…，AK}，在兩個(gè)未被攻陷的證明者P1和P2之間建立一個(gè)共享密鑰，即sk = Key(Ver，P1，p1，P2，p2)，其中P1位于p1，P2位于p2.

敵手的攻擊模型如下:

(1)除了BRM模型中具有很高最小熵(high minentropy)的信息，敵手可以獲取所有通過無線信道傳輸?shù)男畔?

(2)敵手可以在無線信道內(nèi)發(fā)送任何偽造的信息.

(3)敵手可以處在除了p1和p2以外的任意位置.

定義1(基于位置P2P密鑰交換)協(xié)議π=(Init，Key)是安全的基于位置P2P密鑰交換協(xié)議(安全參數(shù)為k)當(dāng)且僅當(dāng)給定(Ver，P1，P2，p1= Init(P1)，p2= Init(P2))，對(duì)于任意的PPT共謀敵手Adv = { A1，A2，…，AK}僅能以可忽略概率ε(k)區(qū)分密鑰sk = Key(Ver，P1，p1，P2，p2)和隨機(jī)數(shù)U(|U| = |sk|).即

Pr［Adv(Ver，P1，p1，P2，p2)］- Pr［Adv(Ver，P1，p1，P2，p2)］＜ε(k).

利用P2V模式構(gòu)造P2P密鑰交換.證明者P1和P2可以利用基于位置P2V密鑰交換分別與驗(yàn)證者(扮演可信第三方)協(xié)商密鑰k1和k2.隨后，P1和P2使用基于可信第三方的密鑰分發(fā)協(xié)議，如Needham-Schroeder協(xié)議［14］，實(shí)現(xiàn)P1和P2之間的基于位置密鑰交換.然而，該實(shí)現(xiàn)方法的缺點(diǎn)在于:驗(yàn)證者必須維護(hù)證明者當(dāng)前位置與P2V模式下生成密鑰之間的關(guān)聯(lián).對(duì)于驗(yàn)證者而言，維護(hù)這種密鑰與位置之間關(guān)聯(lián)容易帶來安全隱患，且代價(jià)較大.

3　一維空間下基于位置P2P密鑰交換協(xié)議

3.1BRM模型

BRM模型［10］假設(shè)所有的敵手只能檢索到(具有很高最小熵的)信息的一部分.具體如下:

(1)驗(yàn)證者可以生成具有高最小熵值為(δ+β)n 的n比特串X.

(2)當(dāng)X經(jīng)過時(shí)，所有敵手都可以檢索X的任何部分，但是所有敵手檢索的總信息量不能超過一個(gè)上限βn.

3.2BSM偽隨機(jī)生成器

定義2(BSM偽隨機(jī)生成器)令存儲(chǔ)率為β，最小熵率為α.PRG: { 0，1}n×{ 0，1}r→{ 0，1}t是ε-secure的BSM偽隨機(jī)生成器(BSM pseudorandom generators，BSM PRG)，當(dāng)且僅當(dāng)對(duì)于{ 0，1}n上任意的αnsource的X，對(duì)于任意A: { 0，1}n→{ 0，1}βn，隨機(jī)變量(PRG(X，K)，A(X)，K)對(duì)(W，A(X)，K)是ε-close的，其中K為{ 0，1}r上的隨機(jī)數(shù)，W是ψ-source的.根據(jù)εsecure的BSM PRG的定義［10］可得，對(duì)于任意算法F，給定A(X)和K，算法F(A(X)，K)能正確計(jì)算PRG(X，K)的最大概率為ε+2-ψ，其中2-ψ是可忽略的.

在安全參數(shù)為κ的情況下，如果r≥(2/δ)κlb(n)，那么ε+ 2-ψ是可忽略的.在BRM模型下，只要選擇合適的r，敵手能夠正確計(jì)算PRG(X，K)的概率是可忽略的.

3.3前提假設(shè)

假設(shè)1(保密信道)在基于位置密碼學(xué)中，假設(shè)所有驗(yàn)證者之間都存在一條保密信道，即驗(yàn)證者之間可以安全的進(jìn)行信息傳輸.

假設(shè)2(廣播認(rèn)證)假設(shè)每一個(gè)驗(yàn)證者已存在認(rèn)證的廣播信道，即任何敵手都不能更改或者偽造驗(yàn)證者發(fā)送的信息.

已有的研究存在很多可用于基于位置密碼學(xué)的高效廣播認(rèn)證協(xié)議，如μTESLA［15］、一次簽名協(xié)議［16］等.

需要說明的是，文獻(xiàn)［10］以及本文所提出的基于位置密碼協(xié)議都假設(shè)除了傳播時(shí)延外，其他時(shí)延均為零，即所有參與方都能夠即時(shí)收發(fā)和處理數(shù)據(jù)而沒有延遲.

3.4協(xié)議P2PKE1

在1維空間中，使用兩個(gè)驗(yàn)證者V0和V1(令Ver = { V0，V1} )，二者傳輸?shù)臄?shù)據(jù)以無線電波的速度進(jìn)行傳播.本文假設(shè)證明者P1和P2的位置p1和p2都處于V0和V1之間.P2PKE1協(xié)議的具體描述如下:

證明者P1和P2分別運(yùn)行Init(P1)和Init(P2):

(1 )令P1位置為p1= Init(P1)，P2位置為p2= Init(P2).

(2)令s =(sid，p1，p2)，其中sid是會(huì)話標(biāo)識(shí).令t(Vi，p)為信息從驗(yàn)證者Vi到達(dá)位置p所傳播的時(shí)間.令T1和T2分別為驗(yàn)證者V0發(fā)送的信息到達(dá)p1和p2的時(shí)刻，其中T1- T2= t(V0，p1)- t(V0，p2).

Key Exchange

證明者P1和P2運(yùn)行Key(Ver，P1，p1，P2，p2):

(1)V0生成最小熵為(δ+β)n的X0和隨機(jī)數(shù)r，V1生成最小熵為(δ+β)n的X1和X2，V0和V1安全共享X0，X1，X2和r.

(2)V0計(jì)算y1= F(X1，r)，z1= F(X0，y1)，y2= F(X2，r)，z2= F(X0，y2)，令z = z1⊕z2.V0在時(shí)刻T1-t(V0，p1)通過認(rèn)證的廣播信道發(fā)送(X0，r，z，s).

(3)V1分別在時(shí)刻T1- t(V1，p1)和T2- t(V1，p2)通過認(rèn)證的廣播信道發(fā)送(X1，s)和(X2，s).

(4)在T1時(shí)刻收到(X0，r，z，s)和(X1，s)，P1計(jì)算y1= F(X1，r)，z1=F(X0，y1)，z2=z⊕z1，sk =f(z1，z2，1).

(5)當(dāng)在T2時(shí)刻收到(X0，r，z，s)和(X2，s)，P2計(jì)算y2=F(X2，r)，z2=F(X0，y2)，z1=z⊕z2，sk =f(z1，z2，1).

3.5安全性分析

定理1如果F是ε-secure BSM PRG，f是PRF，Xi(0≤i≤2)具有最小熵(δ+β)n，βn是檢索上限，那么協(xié)議P2PKE1在共謀攻擊下是安全的基于位置P2P密鑰交換協(xié)議.

證明不失一般性，令所有的共謀敵手{ A1，A2，…，AK}被敵手G控制.令S0，S1，S2分別為所有敵手對(duì)X0，X1，X2所檢索的總信息，且| S0|≤βn，| S1|≤βn，|S2|≤βn.

假設(shè)P2PKE1協(xié)議是不安全的，即敵手G能以不可忽略的概率εG區(qū)分由Key(Ver，P1，p1，P2，p2)生成的密鑰sk和隨機(jī)比特串U.根據(jù)P2PKE1協(xié)議，會(huì)話密鑰sk應(yīng)等于f(z1，z2，1).如果敵手G成功攻擊P2PKE1協(xié)議，則存在以下兩種可能的事件:

事件1沒有z1和z2的情況下，敵手G能夠區(qū)分密鑰sk和隨機(jī)比特串U.

用ε1表示事件1發(fā)生的概率，如果ε1不可忽略，則可構(gòu)造敵手Af，以概率εf(ε1=εf)來攻擊f.很明顯，這與PRF的定義相矛盾，即事件1發(fā)生的概率是忽略的.

事件2敵手G可以計(jì)算正確的z1和z2.

令ε2表示事件2發(fā)生的概率，如果敵手G可以計(jì)算出(z1，z2)，則存在以下五個(gè)可能的情況:

情況1給定(S1，r)，敵手G計(jì)算y1= F(X1，r).

令A(yù)1為V1和p1之間的敵手.由于G能夠計(jì)算y1，當(dāng)X0經(jīng)過時(shí)A1能夠計(jì)算z1= F(X0，y1)和z2= z⊕z1，進(jìn)一步可以計(jì)算出密鑰sk = f(z1，z2，1).由此可見，如果敵手G計(jì)算出y1，則敵手A1就能夠區(qū)分密鑰sk和隨機(jī)數(shù).

假設(shè)給定(S1，r)，敵手G以不可忽略的概率計(jì)算出y1= F(X1，r)，則可以構(gòu)造一個(gè)敵手AF1，給定(S*，r*)，AF1能夠區(qū)分y*= F(X*，r*)和隨機(jī)比特串U，其中F是ε-secure的BSM PRG(ε是可忽略的).

用ε21表示敵手G能夠計(jì)算y1= F(X1，r)的概率，則敵手AF1能夠區(qū)分y*= F(X*，r*)和U的概率是:

如果ε21是不可忽略的，則εF1也是不可忽略的，這與ε-secure的BSM PRG定義相矛盾.

情況2給定(S1，r)后，敵手G可以計(jì)算y2= F(X2，r).

令A(yù)2為V1和p2之間的敵手.如果敵手G能夠以概率ε22計(jì)算出y2，則敵手A2也能夠計(jì)算z1和z2.

同樣，可以構(gòu)造敵手AF2以εF2的概率來攻破BSM PRG的偽隨機(jī)性，即εF2=ε22-1/2m≈ε22.

如果ε22的概率不可忽略，則εF2也不可忽略.

情況3給定(S0，y1)，敵手G可以計(jì)算z1= F(X0，y1).

令A(yù)3為V0和p1之間的敵手.A3可以計(jì)算y1= F(X1，r).假設(shè)敵手G以不可忽略的概率ε23計(jì)算z1= F(X0，y1)，則能構(gòu)造敵手AF3以不可忽略的概率εF3成功攻擊BSM PRG，即εF3=ε23- 1/2m≈ε23.這與BSM PRG的定義相矛盾.

情況4給定(S0，y2)，敵手G可以計(jì)算z2= F(X0，y2).

令A(yù)4為V0和p2之間的敵手.如果敵手G能以不可忽略的概率ε24計(jì)算z2= F(X0，y2)，則能構(gòu)造敵手AF4以不可忽略的概率εF4成功攻擊F，其中εF4=ε24-1/2m≈ε24.

情況5敵手G能成功猜測(cè)隨機(jī)數(shù)r.

令A(yù)5為V1和p1之間的敵手.如果敵手G可以成功猜測(cè)r，則當(dāng)X1經(jīng)過時(shí)敵手A5可以計(jì)算y1= F(X1，r).然而，r是隨機(jī)數(shù)，則敵手G能夠猜出r的概率ε25是可忽略的.因此，敵手A5在情況5下計(jì)算出y1的概率也是可忽略的.

綜上所述，敵手G能夠攻擊P2PKE1協(xié)議的概率為:

因此，如果f是PRF，F(xiàn)是ε-secure BSM PRG，那么εf，εF1，εF2，εF3，εF4以及εG都是可以忽略的.定理1得證.

4　d維空間下基于位置P2P密鑰交換協(xié)議

在d維空間中，協(xié)議P2PKEd需要至少(d + 1)個(gè)驗(yàn)證者才能實(shí)現(xiàn)P2P密鑰交換.在BRM模型下，P2PKEd協(xié)議的具體描述如下:

與P2PKE1協(xié)議的Initialization相同.

Key Exchange

(1)驗(yàn)證者V0生成具有高最小熵(δ+β)n的比特串X0以及m比特的隨機(jī)數(shù)r，驗(yàn)證者Vi生成具有高最小熵(δ+β)n(1≤i≤d)的比特串X(i，1)和X(i，2).所有驗(yàn)證者通過保密信道共享X0，{ X(i，j)}(1≤i≤d，1≤j≤2)以及r.

(2)V0計(jì)算z1= F(X0，r(0，1))和z2= F(X0，r(0，2))，其中r(i -1，j)= F(X(i，j)，r(i，j))，r(d，j)= r(1≤i≤d，1≤j≤2)，z = z1⊕z2.V0在T1- t(V0，p1)時(shí)刻通過認(rèn)證的廣播信道發(fā)送(X0，r，z，s).

(3)Vi分別在T1- t(Vi，p1)和T2- t(Vi，p2)時(shí)刻通過認(rèn)證的廣播信道發(fā)送(X(i，1)，s)和(X(i，2)，s)(1≤i≤d).

(4)當(dāng)在T1時(shí)刻收到(X0，r，z，s)和{ X(1，1)，…，X(d，1)}時(shí)，證明者P1計(jì)算z1= F(X0，r(0，1))，其中r(i -1，1)= F(X(i，1)，r(i，1))，r(d，1)= r(1≤i≤d).令z2= z⊕z1，并計(jì)算sk = f(z1，z2，1).

(5)當(dāng)在T2時(shí)刻收到(X0，r，z，s)和{ X(1，2)，…，X(d，2)}時(shí)，證明者P2計(jì)算z2= F(X0，r(0，2))，其中r(i -1，2)= F(X(i，2)，r(i，2))，r(d，2)= r(1≤i≤d).令z1= z⊕z2，并計(jì)算sk = f(z1，z2，1).

定理2如果F是ε- secure的BSM PRG，f是PRF，X0和{ X(i，j)}具有最小熵(δ+β)n(1≤i≤d，1≤j≤2)且βn為檢索上界，則P2PKEd協(xié)議在共謀攻擊下是安全的.

定理2的證明與定理1的證明相似，此處不再贅述.另外，Chandran已經(jīng)討論了2維或者3維空間中可用于基于位置密鑰交換的有效區(qū)域問題.無論是P2V模式還是P2P模式，除了靠近驗(yàn)證者的很小區(qū)域之外，大部分區(qū)域都可以用于基于位置密鑰交換［10］.

5　協(xié)議的擴(kuò)展

5.1密鑰確認(rèn)

基于P2PKEd協(xié)議，本節(jié)提出具有密鑰確認(rèn)性質(zhì)的P2P基于位置密鑰交換協(xié)議P2PKEd-c.與協(xié)議P2PKEd相比，協(xié)議P2PKEd-c添加了Rekey階段，如下所示:

與P2PKE1協(xié)議的Initialization相同.

Key Exchange

(1)，(2)，(3)步驟與P2PKEd協(xié)議中(1)，(2)，(3)相同.

(4)在T1時(shí)刻收到(X0，r，z，s)和{ X(1，1)，…，X(d，1)}后，P1計(jì)算z1= F(X0，r(0，1))，其中r(i -1，1)= F(X(i，1)，r(i，1))，r(d，1)= r(1≤i≤d)，z2= z⊕z1.令ak = f1(z1，z2，0)，ek = f1(z1，z2，1).

(5)在T2時(shí)刻收到(X0，r，z，s)和{ X(1，2)，…，X(d，2)}后，P2計(jì)算z2= F(X0，r(0，2))，其中r(i -1，2)= F(X(i，2)，r(i，2))，r(d，2)= r(1≤i≤d)，令z1= z⊕z2.令ak = f1(z1，z2，0)，ek = f1(z1，z2，1).

Rekey

(1)P1選擇隨機(jī)數(shù)r1，發(fā)送(P1，s，r1)給P2.

(2)收到(P1，s，r1)，P2選擇隨機(jī)數(shù)r2，計(jì)算sk = f2(ek，(r1，r2))，c2= f2(ak，(P2，s，r2，r1))，發(fā)送(P2，s，r2，c2)給P1.

(3)收到(P2，s，r2，c2)，P1首先驗(yàn)證c2的正確性.如果驗(yàn)證成功，計(jì)算sk = f2(ek，(r1，r2))和c1= f2(ak，(P1，s，r1，r2))，發(fā)送(P1，s，c1)給P2，將sk作為共享密鑰.

(4)收到(P1，s，c1)，P2驗(yàn)證c1的正確性.如果驗(yàn)證成功，P2輸出的sk作為共享密鑰.

顯而易見，P2PKEd-c協(xié)議具有密鑰確認(rèn)的性質(zhì).下面分析P2PKEd-c協(xié)議的安全性.

定理3如果F是ε-secure BSM PRG，f1和f2都是PRFs，X0和{ X(i，j)}具有最小熵(δ+β)n(1≤i≤d，1≤j ≤2)且βn為檢索上界，那么協(xié)議P2PKEd-c在共謀攻擊下是安全的.

證明證明分為以下兩個(gè)步驟:

(1)ak和ek的機(jī)密性

由定理1可得，共謀敵手只能在可忽略概率下得到sk，同理可得在P2PKEd-c協(xié)議中，共謀敵手也只能在可忽略概率下得到ak和ek.

(2)Rekey階段的安全性

引理1 Rekey階段可以為證明者P1和P2實(shí)現(xiàn)安全的密鑰交換.

基于ak和ek的機(jī)密性，引理1的證明與文獻(xiàn)［17］對(duì)REKEY協(xié)議的分析類似，這里不再贅述.

綜上，P2PKEd-c協(xié)議滿足定義1.定理3得證.

5.2無密鑰托管

在之前的協(xié)議中，假設(shè)所有驗(yàn)證者都是可信的.由 P2PKEd協(xié)議(以及P2PKEd-c協(xié)議)可知，所有驗(yàn)證者都能得到P1和P2之間的共享密鑰，即存在密鑰托管問題.

假設(shè)3(DDH假設(shè))令G為循環(huán)群，秩為素?cái)?shù)q，本原根為g，α和β是Zq上的隨機(jī)數(shù).任意的PPT敵手A只能以可忽略的概率來區(qū)分{ gα，gβ，gαβ}和{ gα，gβ，R}，其中R是隨機(jī)數(shù)且|R| = |gαβ|.

基于DDH(Decision Diffie-Hellman)假設(shè)，通過添加DH Exchange階段可以實(shí)現(xiàn)無密鑰托管的基于位置P2P密鑰交換協(xié)議P2PKEd-e.P2PKEd-e協(xié)議如下:

循環(huán)群G:秩為素?cái)?shù)q，本原根為g.

Initialization＆Key Exchange

與P2PKEd-c協(xié)議相似.唯一的不同之處在于證明者P1和P2只計(jì)算ak，不計(jì)算ek.

DH Exchange

(1)P1從Zq中隨機(jī)選擇α，并發(fā)送(P1，s，gα)給P2.

(2)收到(P1，s，gα)后，P2從Zq中隨機(jī)選擇β，計(jì)算sk =(gα)β，c2= f2(ak，(P2，s，gβ，gα))，發(fā)送(P2，s，gβ，c2)給P1.

(3)收到(P2，s，gβ，c2)后，P1首先驗(yàn)證c2的正確性.如果驗(yàn)證成功，計(jì)算sk =(gβ)α以及c1= f2(ak，(P1，s，gα，gβ)).然后P1發(fā)送(P1，s，c1)給P2并輸出sk作為共享密鑰.

(4)收到(P1，s，c1)后，P2驗(yàn)證c1的正確性.如果驗(yàn)證成功，P2輸出sk作為共享密鑰.

顯然，協(xié)議P2PKEd-e具有密鑰確認(rèn)的性質(zhì).此外，該協(xié)議還滿足無密鑰托管的需求.

定理4如果DDH假設(shè)成立，則在P2PKEd-e協(xié)議中，所有半可信的驗(yàn)證者都只能以可忽略的概率區(qū)分共享密鑰sk和隨機(jī)數(shù)，即協(xié)議具有無密鑰托管的性質(zhì).

證明該定理的證明可以直接規(guī)約為DDH假設(shè).如果存在一個(gè)半可信的驗(yàn)證者V以不可忽略的概率區(qū)分sk和隨機(jī)數(shù)，那么就能構(gòu)造一個(gè)PPT敵手A來解決DDH問題.顯然，這與DDH假設(shè)相矛盾.定理4得證.

定理5如果DDH假設(shè)成立，F(xiàn)是ε-secure BSM PRG，f1和f2都是PRFs，X0和{ X(i，j)}具有最小熵(δ+ β)n(1≤i≤d，1≤j≤2)且βn為檢索上界，P2PKEd-e協(xié)議是安全的.

證明與定理3類似，定理5的證明也分為兩個(gè)步驟:

(1)ak的機(jī)密性

由定理1的可得，共謀攻擊者無法得到ak.

(2)DH Exchange階段的安全性

引理2 DH Exchange階段可以為證明者P1和P2實(shí)現(xiàn)安全的密鑰交換.

本質(zhì)上，DH Exchange階段是基于MAC的DH密鑰交換協(xié)議.根據(jù)基于MAC認(rèn)證器和DDH假設(shè)，DH Exchange階段可以實(shí)現(xiàn)安全的密鑰交換［17］.

綜上可得，P2PKEd-e協(xié)議是安全的基于位置P2P密鑰交換協(xié)議，定理5得證.

6　性能比較

以3維空間的協(xié)議為例，對(duì)協(xié)議P2PKE3，P2PKE3-c 和P2PKE3-e進(jìn)行比較，結(jié)果如表1所示.

表1　比較結(jié)果

安全性顯然，在BRM模型以及假設(shè)1、假設(shè)2下，協(xié)議P2PKE3，P2PKE3-c和P2PKE3-e都是安全的.此外，P2PKE3-c協(xié)議具有密鑰確認(rèn)的性質(zhì)，而P2PKE3-e協(xié)議在DDH假設(shè)下具有密鑰確認(rèn)和無密鑰托管的性質(zhì).

效率從驗(yàn)證者角度，通信開銷和計(jì)算代價(jià)在三個(gè)協(xié)議中都是一樣的.換言之，P2PKE3-c協(xié)議和P2PKE3-e協(xié)議不會(huì)對(duì)驗(yàn)證者有額外的代價(jià).

P2PKE3協(xié)議中證明者沒有通信開銷，因此P2PKE3協(xié)議更適用于能量受限的應(yīng)用環(huán)境.

P2PKE3-c協(xié)議在Rekey階段給證明者增加了額外的通信開銷和計(jì)算代價(jià).

在P2PKE3-e協(xié)議中，證明者引入了計(jì)算代價(jià)較高的模指運(yùn)算.可以使用橢圓曲線或者其他更高效的密鑰交換來減少計(jì)算開銷.

7　結(jié)論

本文首次給出了基于位置P2P密鑰交換的概念和安全定義.設(shè)計(jì)了1維空間下基于位置P2P密鑰交換協(xié)議P2PKE1，并以此為基礎(chǔ)提出了在d維空間中的基于位置P2P密鑰交換協(xié)議P2PKEd.結(jié)合P2P模式下的密鑰交換的安全需求，進(jìn)一步提出了具有密鑰確認(rèn)性質(zhì)的P2PKEd-c協(xié)議以及無密鑰托管性質(zhì)的P2PKEd-e協(xié)議.

參考文獻(xiàn)

［1］B Rao，L Minakakis.Evolution of mobile location-based services［J］.Communications of the ACM，2003，46(12): 61 -65.

［2］肖竹，王勇超，田斌，于全，易克初.超寬帶定位研究與應(yīng)用:回顧和展望［J］.電子學(xué)報(bào)，2011，39(1): 133 -141.Xiao Zhu，Wang Yongchao，Tian Bin，Yu Quan，Yi Kechu.UWB positioning research and application: review and outlook［J］.Acta Electronica Sinica，2011，39(1): 133 - 141.(in Chinese)

［3］林云松，孫卓振，彭良福.基于Bancroft算法的多點(diǎn)定位TOA-LS估計(jì)［J］.電子學(xué)報(bào)，2012，40(3): 621 -624.Lin Yunsong，Sun Zhuozhen，Peng Liangfu.Multipoint positioning TOA-the LS estimate of the algorithm based on the Bancroft［J］.Acta Electronica Sinica，2012，40(3): 621 -624.(in Chinese)

［4］D Liu，P Ning.Location-based pairwise key establishments for static sensor networks［A］.Proceedings of the 1st ACM Workshop on Security of ad hoc and Sensor Networks［C］.ACM，2003.72 -81.

［5］C Yang，J Xiao.Location-based pairwise key establishment and data authentication for wireless sensor networks［A］.Information Assurance Workshop［C］.IEEE，2006.247 -252.

［6］D Huang，M Mehta，D Medhi，L Harn.Location-aware key management scheme for wireless sensor networks［A］.2nd ACM Workshop on Security of ad hoc and Sensor Networks［C］.ACM，2004.29 -39.

［7］M Younis，K Ghumman，M Eltoweissy.Location-aware combinatorial key management scheme for clustered sensor networks［J］.IEEE Transactions on Parallel and Distributed Systems，2006，17(8): 865 -882.

［8］Y Zhang，W Liu，W Lou，Y Fang.Securing sensor networks with location-based keys［A］.IEEE Wireless Communications and Networking Conference［C］.IEEE，2005.1909 -1914.

［9］Yanchao Zhang，Wei Liu，Wenjing Lou，Yuguang Fang.Location-based compromise-tolerant security mechanismsfor wireless sensor networks［J］.IEEE J Select Areas Commun，2006，24(2): 247 -260.

［10］N Chandran，V Goyal，R Moriarty，R Ostrovsky.Positionbased Cryptography［A］.Advances in Cryptology-CRYPTO 2009［C］.Berlin: Springer-Verlag，2009.391 -407.

［11］H Buhrman，N Chandran，S Fehr，R Gelles，V Goyal，R Ostrovsky，C Schaffner.Position-based quantum cryptography: impossibility and constructions［A］.Advances in Cryptology-CRYPTO 2011［C］.Berlin: Springer-Verlag，2011.429 -446.

［12］H K Lau，H K Lo.Insecurity of position-based quantumcryptography protocols against entanglement attacks［J］.Physical Review A，2011，83(1): 012322.

［13］M Tomamichel，S Fehr，J Kaniewski，S Wehner.One-sided device-independent QKD and position-based cryptography from monogamy games［A］.Advances in Cryptology-EUROCRYPT 2013［C］.Berlin: Springer-Verlag，2013.609 -625.

［14］Junwei Zhang，Jianfeng Ma，Chao Yang.Protocol derivation system for the Needham-Schroeder family［J］.Wiley Online Library，2012.DOI:10.1002/sec.565.

［15］A Perrig，R Szewczyk，J D Tygar，V Wen，D E Culler.SPINS: security protocols for sensor networks［A］.ACM Conference on Mobile Computing and Networks［C］.ACM，2001.189 -199.

［16］J Zhang，J Ma，S Moon.Universally composable one-time signature and broadcast authentication［J］.Sci China Inf Sci，2010，53(3): 567 -580.

［17］R Canetti，H Krawczyk.Analysis of key-exchange protocols and their use for building secure channels［A］.Advances in Cryptology-EUROCRYPT 2001［C］.Berlin: Springer-Verlag，2001.2045:453 -474.

張俊偉男，1982年2月生于陜西西安.博士，西安電子科技大學(xué)副教授，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全、密碼學(xué)等.

E-mail: jwzhang@ xidian.edu.cn

陳治平男，1990年2月生于安徽阜陽(yáng).西安電子科技大學(xué)碩士研究生，主要研究方向?yàn)闊o線網(wǎng)絡(luò)安全.

Provably Secure Position-BasedProver-to-Prover Key Exchange Protocols

ZHANG Jun-wei，CHEN Zhi-ping，MA Jian-feng，YANG Li
(School of Computer Science and Technology，Xidian University，Xi’an，Shaanxi 710071，China)

Abstract:This paper investigates provably secure position-based key exchange protocols between two provers.To begin with，this paper presents the notions of the prover-to-verifier mode and the prover-to-prover mode，which is the first to distinguish between the two modes for position-based key exchange.At the same time，this paper formalizes the definition of secure prover-to-prover position-based key exchange.Then，a provably secure prover-to-prover position-based key exchange protocol P2PKE1in 1-dimension is proposed in this paper.Based on the above protocol，a generic prover-to-prover positionbased key exchange protocol P2PKEdin d-dimensions is constructed(1≤d≤3).In addition，this paper extends the proposed protocol and proposes protocol P2PKEd-c with key confirmation and protocol P2PKEd-e without key escrow in d-dimensions.Finally，we discuss the proposed protocols in 3-dimensions from both security and performance perspectives.

Key words:prover-to-prover; position-based key exchange; bounded retrieval model; provable security

作者簡(jiǎn)介

基金項(xiàng)目:長(zhǎng)江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃(No.IRT1078);國(guó)家科技重大專項(xiàng)(No.2011ZX03005-002);國(guó)家自然科學(xué)基金(No.U1135002，No.61100230，No.61100233，No.61202389，No.61202390，No.61372075，No.61472310);中央高?；究蒲袠I(yè)務(wù)費(fèi)(No.JY10000903001，No.K5051303003)

收稿日期:2014-07-01;修回日期: 2014-11-15;責(zé)任編輯:李勇鋒

DOI:電子學(xué)報(bào)URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.003

中圖分類號(hào)：TN911.7

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：0372-2112(2016)01-0014-07