劉 芳 趙一鳴

(復(fù)旦大學(xué)軟件學(xué)院 上海 201203)

0 引 言

驗(yàn)證協(xié)議是現(xiàn)代密碼學(xué)最重要的應(yīng)用之一，旨在解決傳統(tǒng)基于密碼的身份驗(yàn)證的安全性與隱私性問題。不同于傳統(tǒng)方案，驗(yàn)證協(xié)議是一種零知識協(xié)議，即驗(yàn)證者在不獲取證明者用戶私鑰的前提下通過交互式協(xié)議來驗(yàn)證證明者的合法性。1984年Shamir提出了一種基于身份的驗(yàn)證協(xié)議[1]IBI(Identity-based Identification)，在該協(xié)議中公鑰由一串任意的身份字符串組成，與公鑰基礎(chǔ)設(shè)施PKI(Public Key Infrastructure)相比，用戶無需在每次驗(yàn)證時(shí)從第三方權(quán)威機(jī)構(gòu)獲取公鑰，因此在當(dāng)今廣泛傳播的去中心化網(wǎng)絡(luò)中具有更多的優(yōu)勢[2-3]。

文獻(xiàn)[4]首次闡明基于身份的驗(yàn)證協(xié)議的形式化定義，隨后文獻(xiàn)[5]提出安全模型分為模仿者被動(dòng)攻擊模型、主動(dòng)攻擊模型及并發(fā)主動(dòng)攻擊模型，安全性能依次增強(qiáng)。文獻(xiàn)[6]基于離散對數(shù)問題提出了一種能夠抵抗并發(fā)主動(dòng)攻擊的基于身份的驗(yàn)證方案，并且具有更高的驗(yàn)證效率。文獻(xiàn)[7]提出了一種基于雙線性對的基于身份的驗(yàn)證方案，并將其實(shí)際運(yùn)用到移動(dòng)設(shè)備應(yīng)用中。1994年，Shor提出了一種基于量子計(jì)算機(jī)的算法[8]，可在多項(xiàng)式時(shí)間內(nèi)解決大數(shù)分解和離散對數(shù)問題,對密碼學(xué)及基于公鑰密碼系統(tǒng)的應(yīng)用造成了巨大威脅。因此，構(gòu)建后量子時(shí)代[9-10]高效安全的基于身份的驗(yàn)證方案具有重要意義。

已有的量子安全的基于身份的驗(yàn)證方案有文獻(xiàn)[11-12]提出的基于編碼的方案,文獻(xiàn)[13-14]提出的基于格及理想格的方案。然而，文獻(xiàn)[11]僅能在隨機(jī)預(yù)言機(jī)模型下抵抗被動(dòng)攻擊，安全性能較低。文獻(xiàn)[12]基于文獻(xiàn)[11]將安全性提升至并發(fā)主動(dòng)攻擊模型下安全，但由于編碼技術(shù)的局限性，該方案在主公鑰及協(xié)議交互運(yùn)算方面具有較大劣勢。文獻(xiàn)[13]提出了一種格上基于身份的驗(yàn)證方案，但同樣具有效率較低的缺陷。文獻(xiàn)[14]雖然減少了文獻(xiàn)[13]方案中在線部分的開銷，但密鑰大小仍與實(shí)際應(yīng)用的需求有較大差距。

因此本文提出了一種新的更加高效的標(biāo)準(zhǔn)模型下格上基于身份的驗(yàn)證方案，該方案的安全性基于最壞情況困難性假設(shè)[13-15]，在碰撞問題是困難的情況下可驗(yàn)證模仿者靜態(tài)身份并發(fā)主動(dòng)攻擊安全。本文基于文獻(xiàn)[16]中的驗(yàn)證協(xié)議，利用文獻(xiàn)[14,17]中的盆景樹(Bonsai trees)及文獻(xiàn)[18]中的陷門函數(shù)實(shí)現(xiàn)理想格上的用戶私鑰抽取，并提出疊加承諾與回復(fù)技術(shù)以及文獻(xiàn)[19]簽名方案中的參數(shù)優(yōu)化技術(shù)構(gòu)造了更加高效的驗(yàn)證協(xié)議。相較于文獻(xiàn)[12,14]中的方案，本文方案在密鑰與協(xié)議消息大小，用戶私鑰抽取及協(xié)議交互的運(yùn)算開銷等方面均有所提升。

1 預(yù)備知識

1.1 格

定義1格是向量空間Rn中能夠組成加法子群的離散點(diǎn)的集合。一個(gè)格Λ可以定義為Rn中n個(gè)線性無關(guān)向量b1,b2,…,bn與整數(shù)系數(shù)xi∈的線性組合：

矩陣B=[b1,b2,…,bn]是格Λ的一組基，n為基的秩，由矩陣B生成的格記作Λ(B)。

定義2環(huán)R中的每個(gè)多項(xiàng)式都有n個(gè)屬于q的系數(shù)，因此在環(huán)R與之間存在雙射，即環(huán)R的理想(Ideals)能夠映射到中的一個(gè)格，此格即為理想格，定義為：

1.2 困難性問題

本文中主要的一般情況下難解性問題為碰撞問題。

1.3 基于身份的驗(yàn)證方案形式化定義

一個(gè)基于身份的驗(yàn)證方案IBI包含四個(gè)算法，定義為IBI=(Setup,KG,P,V)：

1) 主密鑰生成算法Setup(1κ)：輸入安全參數(shù)1κ，輸出主公鑰mpk和主私鑰msk。

2) 用戶私鑰抽取算法KG(msk,id)：輸入主私鑰msk和id，輸出與id相對應(yīng)的用戶私鑰skid。

3) 證明者算法P(mpk,id,skid)：輸入主公鑰mpk，id和用戶私鑰skid，并與算法V進(jìn)行交互。

4) 驗(yàn)證者算法V(mpk,id)：輸入主公鑰mpk和id，與算法P進(jìn)行交互，最終輸出結(jié)果dec={accept,reject}。

1.4 安全模型

初始化階段：

在該階段之初，CV輸入安全參數(shù)1κ，并在接收主公鑰mpk之前對不同的{id1,id2,…,idt}向挑戰(zhàn)者發(fā)出用戶私鑰抽取詢問。挑戰(zhàn)者輸入安全參數(shù)1κ，通過Setup(1κ)得到(mpk,msk)；通過KG(msk,idi)計(jì)算出對應(yīng)的用戶私鑰skidi，其中1≤i≤t；設(shè)置CU← {id1,id2,…,idt}；將{skid1,skid2,…,skidt}返回給CV。挑戰(zhàn)者初始化TU,PS←?。TU表示目標(biāo)用戶，CU表示已經(jīng)被詢問過的用戶，PS表示證明者會(huì)話集合。CV得到主公鑰mpk。

學(xué)習(xí)階段：

CV向PROV預(yù)言機(jī)發(fā)出詢問。PROV預(yù)言機(jī)接收輸入id、session和Min。如果id?CU，返回⊥。如果(id,session)?PS，則將(id,session)添加到PS中去，選擇一個(gè)隨機(jī)硬幣記為ρ，將證明者的狀態(tài)stP[(id,session)]設(shè)置為(mpk,skid,ρ)。然后通過P(Min,stP[(id,session)])得到對應(yīng)的輸出和狀態(tài)(Mout,stP[(id,session)])。最終返回Mout。

挑戰(zhàn)階段：

CV輸出一個(gè)目標(biāo)身份id*和狀態(tài)信息stCP。如果id*∈CU，挑戰(zhàn)者輸出拒絕reject并終止，否則，挑戰(zhàn)者將{id*}加入到TU中，并將stCP發(fā)給CP。與學(xué)習(xí)階段相同，CP可以向PROV預(yù)言機(jī)詢問。最終，挑戰(zhàn)者運(yùn)行Run[CP(stCP)PROV?V(mpk,id*)]得到結(jié)果dec，并輸出dec。

2 本文方案

本文提出了一種新的基于格的IBI構(gòu)造。方案使用文獻(xiàn)[14,17]中的盆景樹技術(shù)，將主密鑰所對應(yīng)的格作為盆景樹的根節(jié)點(diǎn)拓展至任意用戶身份所對應(yīng)的高維格，結(jié)合文獻(xiàn)[18]中的陷門函數(shù)實(shí)現(xiàn)用戶私鑰的抽取。同時(shí)提出疊加承諾與回復(fù)技術(shù)將文獻(xiàn)[19]中的高效參數(shù)設(shè)置方法應(yīng)用于擴(kuò)展格相關(guān)算法及文獻(xiàn)[16]的驗(yàn)證協(xié)議中，使得新的基于身份的驗(yàn)證方案的空間效率與運(yùn)算效率均得到了提升，并且證明該方案是stat-id-imp-ca安全。

2.1 陷門函數(shù)及擴(kuò)展格相關(guān)算法

本文方案中所使用的陷門函數(shù)及擴(kuò)展格相關(guān)算法描述如下:

本方案利用文獻(xiàn)[19]中提出的m≥2n的參數(shù)設(shè)置方法，結(jié)合身份id的長度λ，設(shè)置擴(kuò)展格算法的參數(shù)為：m=m1+(λ+1)m2=2n，m1=2nmod(λ+1)，m2=(m-m1)/(λ+1)，σ=1，r=log3(q)+1。

2.2 方案描述

本文格上基于身份的驗(yàn)證方案包含主密鑰生成算法，用戶私鑰抽取算法以及驗(yàn)證協(xié)議。

2.2.1 主密鑰生成算法

1) 輸入安全參數(shù)1κ。

3) 定義集合B

2.2.2 用戶私鑰抽取算法

1) 輸入主私鑰S*，及身份id∈{1,0}*。

2) 選取密碼學(xué)安全的哈希函數(shù)G，令id=G(id)=ID1‖ID2‖…‖IDλ∈{1,0}λ。

2.2.3 驗(yàn)證協(xié)議

3 方案分析

本文提出了格上基于身份的高效驗(yàn)證方案，本章將從完整性、可靠性及效率三方面進(jìn)行具體分析，證明該方案是stat-id-imp-ca安全，并且空間效率與運(yùn)算效率均有所提升。

3.1 完整性分析

定理2本文提出的格上基于身份的高效驗(yàn)證方案具備完整性。

具體證明如下：

因此，驗(yàn)證者能夠返回dec=accept。故該IBI方案具備完整性。

3.2 可靠性分析

定理3如果碰撞問題Col(H(R,m),D)是困難的，則本文提出的格上基于身份的高效驗(yàn)證方案在stat-id-imp-ca模型下是安全的。

具體證明過程如下：

初始化階段：

1) 在該階段之初，CV輸入安全參數(shù)1κ，并在接收主公鑰mpk之前對不同的id1,…,idt向挑戰(zhàn)者發(fā)出用戶私鑰抽取詢問。

3) 定義集合Wω1,…,ωp滿足以下三個(gè)條件：①ωi∈，1≤i≤p；②ωi不是任何idj的前綴，其中1≤i≤p，1≤j≤t；③ 對于集合W中任意兩個(gè)不相同的元素(ωi,ωj)，ωi不是ωj的前綴，1≤i≤p，1≤j≤p。集合W中最多有λt個(gè)元素，即p≤λt。

證明者詢問階段：

模仿者攻擊階段：

1) 模仿者CV輸出一個(gè)挑戰(zhàn)身份id*，并且id*并沒有在之前的用戶私鑰抽取預(yù)言機(jī)詢問過。如果該身份id*已經(jīng)向用戶私鑰抽取預(yù)言機(jī)詢問過，則預(yù)言機(jī)返回終止⊥。

由以上證明過程可得：

3.3 效率比較

本文提出的格上基于身份的高效驗(yàn)證方案與文獻(xiàn)[14]中提出的格上基于身份的驗(yàn)證方案,以及文獻(xiàn)[12]中提出的基于編碼的基于身份的驗(yàn)證方案相比，空間效率與運(yùn)算效率均有所提升，結(jié)果如表1所示。三種方面均在并發(fā)主動(dòng)攻擊模型下可證明安全，并抵抗量子計(jì)算機(jī)攻擊。

表中的每種方案，第一行為漸進(jìn)大小與復(fù)雜度第二行為實(shí)際開銷大小與運(yùn)算次數(shù)。本文基于文獻(xiàn)[19]的參數(shù)選取計(jì)算實(shí)際大小與運(yùn)算開銷，以達(dá)到2100安全性級別，參數(shù)具體選取如下：對于文獻(xiàn)[14]中基于格的方案，n=512，m1=1，m2=467，m=9 808，λ=20，q=225；對于文獻(xiàn)[12]中基于編碼的方案，編碼長度n=262 144，糾錯(cuò)能力t=9，并行度λ=2；對于本文方案，n=512，m1=4，m2=51，m=1 024，λ=20，q=224。

表1 效率比較

續(xù)表1

在漸進(jìn)大小與復(fù)雜度方面，基于編碼的文獻(xiàn)[12]在主私鑰大小和用戶私鑰大小方面具有優(yōu)勢，而本文方案與基于理想格的文獻(xiàn)[14]方案保持一致。

在實(shí)際大小與運(yùn)算開銷方面，雖然本文方案在協(xié)議交互部分相對于前兩種方案需要計(jì)算額外的承諾與回復(fù)消息，但由此可使參數(shù)m的選取值降低，從而本文方案在各方面均優(yōu)于文獻(xiàn)[16]方案與文獻(xiàn)[14]方案。其中，主公鑰大小由1.44 MB降至0.16 MB，主私鑰大小由731.25 KB降至82.50 KB，用戶私鑰大小由3.80 KB降至0.38 KB。即使承諾與回復(fù)消息增加，協(xié)議消息大小與協(xié)議交互復(fù)雜度仍分別由21.32 KB與217級運(yùn)算次數(shù)降至7.13 KB與216，用戶私鑰抽取運(yùn)算次數(shù)由227降至224。文獻(xiàn)[12]在主私鑰大小，用戶私鑰大小方面具有較大優(yōu)勢分別僅需162 bits與324 bits，但由于編碼長度的問題，該案在主公鑰大小，用戶私鑰抽取復(fù)雜度與協(xié)議交互復(fù)雜度上劣勢明顯，分別需要5 MB，238與226級運(yùn)算次數(shù)，需要長時(shí)間進(jìn)行身份驗(yàn)證。相比于文獻(xiàn)[12]，本文方案的應(yīng)用場景更為廣泛。

綜上訴述，本文提出的格上基于身份的高效驗(yàn)證方案不僅在stat-id-imp-ca模型下可證明安全，并較為顯著地減少了密鑰大小與用戶私鑰抽取及協(xié)議交互的運(yùn)算開銷。

4 結(jié) 語

格上的驗(yàn)證協(xié)議是后量子時(shí)代重要的密碼學(xué)應(yīng)用之一，本文提出了一種格上基于身份的高效驗(yàn)證方案，并在標(biāo)準(zhǔn)模型下取得stat-id-imp-ca可證明安全，使得后量子時(shí)代下該應(yīng)用的實(shí)用性進(jìn)一步增強(qiáng)。另外，如何繼續(xù)在保持安全性的條件下選取更小的參數(shù)以及實(shí)現(xiàn)基于層級身份的驗(yàn)證協(xié)議將是今后研究的重點(diǎn)。

參考文獻(xiàn)

[1] Shamir A. Identity-based cryptosystems and signature schemes[C]//Workshop on the Theory and Application of Cryptographic Techniques. Santa Barbara, USA: Springer Berlin Heidelberg, 1984: 47-53.

[2] 楊紅塵. 基于身份簽密算法的研究[D]. 南京：南京郵電大學(xué), 2016.

[3] 康元基, 顧純祥, 鄭永輝, 等. 利用特征向量構(gòu)造基于身份的全同態(tài)加密體制[J]. 軟件學(xué)報(bào), 2016, 27(6):1487-1497.

[4] Kurosawa K, Heng S H. From digital signature to ID-based identification/signature[C]//International Workshop on Public Key Cryptography. Springer Berlin Heidelberg, 2004: 248-261.

[5] Kurosawa K, Heng S H. Identity-Based Identification Without Random Oracles[J]. Lecture Notes in Computer Science, 2005, 3481:603-613.

[6] Chin J J, Tan S Y, Heng S H, et al. Twin-Schnorr: A Security Upgrade for the Schnorr Identity-Based Identification Scheme[J]. The Scientific World Journal, 2015, 2015(1):237514.

[7] Teh T Y, Lee Y S, Cheah Z Y, et al. IBI-Mobile Authentication: A Prototype to Facilitate Access Control Using Identity-Based Identification on Mobile Smart Devices[J]. Wireless Personal Communications, 2017, 94(1): 127-144.

[8] Shor P W. Algorithms for quantum computation: Discrete logarithms and factoring[C]// Proceedings of 35th Annual Symposium on Foundations of Computer Science. Santa Fe, USA: IEEE, 1994: 124-134.

[9] 吳立強(qiáng), 楊曉元, 韓益亮. 基于理想格的高效模糊身份加密方案[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(4):775-782.

[10] 孫意如, 梁向前, 商玉芳. 理想格上基于身份的環(huán)簽名方案[J]. 計(jì)算機(jī)應(yīng)用, 2016, 36(7): 1861-1865.

[11] Cayrel P L, Gaborit P, Galindo D, et al. Improved identity-based identification using correcting codes[DB]. arXiv preprint arXiv:0903.0069, 2009.

[12] Song B, Zhao Y. Provably Secure Identity-Based Identification and Signature Schemes with Parallel-PVR[M]//Information and Communications Security. Springer International Publishing, 2016: 227-238.

[13] Stehlé D, Steinfeld R, Tanaka K, et al. Efficient public key encryption based on ideal lattices[C]//International Conference on the Theory and Application of Cryptology and Information Security. Tokyo, Japan: Springer Berlin Heidelberg, 2009: 617-635.

[14] Rückert M. Adaptively secure identity-based identification from lattices without random oracles[C]//International Conference on Security and Cryptography for Networks. Amalfi, Italy: Springer Berlin Heidelberg, 2010: 345-362.

[15] Peikert C. A decade of lattice cryptography[J]. Foundations and Trends? in Theoretical Computer Science, 2016, 10(4): 283-424.

[16] Lyubashevsky V. Lattice-based identification schemes secure under active attacks[C]//International Workshop on Public Key Cryptography. Barcelona, Spain: Springer Berlin Heidelberg, 2008: 162-179.

[17] Cash D, Hofheinz D, Kiltz E, et al. Bonsai trees, or how to delegate a lattice basis[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Monaco and Nice, France: Springer Berlin Heidelberg, 2010: 523-552.

[18] Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions[C]//Proceedings of the fortieth annual ACM symposium on Theory of computing. New York, NY, USA; ACM, 2008: 197-206.

[19] Lyubashevsky V. Lattice signatures without trapdoors[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cambridge, UK: Springer Berlin Heidelberg, 2012: 738-755.

[20] Lyubashevsky V, Micciancio D. Generalized compact knapsacks are collision resistant[C]// International Colloquium on Automata, Languages, and Programming. Venice, Italy: Springer Berlin Heidelberg, 2006: 144-155.