一种格上基于身份的高效验证方案

刘 芳 赵一鸣

(复旦大学软件学院 上海 201203)

0 引 言

验证协议是现代密码学最重要的应用之一，旨在解决传统基于密码的身份验证的安全性与隐私性问题。不同于传统方案，验证协议是一种零知识协议，即验证者在不获取证明者用户私钥的前提下通过交互式协议来验证证明者的合法性。1984年Shamir提出了一种基于身份的验证协议[1]IBI(Identity-based Identification)，在该协议中公钥由一串任意的身份字符串组成，与公钥基础设施PKI(Public Key Infrastructure)相比，用户无需在每次验证时从第三方权威机构获取公钥，因此在当今广泛传播的去中心化网络中具有更多的优势[2-3]。

文献[4]首次阐明基于身份的验证协议的形式化定义，随后文献[5]提出安全模型分为模仿者被动攻击模型、主动攻击模型及并发主动攻击模型，安全性能依次增强。文献[6]基于离散对数问题提出了一种能够抵抗并发主动攻击的基于身份的验证方案，并且具有更高的验证效率。文献[7]提出了一种基于双线性对的基于身份的验证方案，并将其实际运用到移动设备应用中。1994年，Shor提出了一种基于量子计算机的算法[8]，可在多项式时间内解决大数分解和离散对数问题,对密码学及基于公钥密码系统的应用造成了巨大威胁。因此，构建后量子时代[9-10]高效安全的基于身份的验证方案具有重要意义。

已有的量子安全的基于身份的验证方案有文献[11-12]提出的基于编码的方案,文献[13-14]提出的基于格及理想格的方案。然而，文献[11]仅能在随机预言机模型下抵抗被动攻击，安全性能较低。文献[12]基于文献[11]将安全性提升至并发主动攻击模型下安全，但由于编码技术的局限性，该方案在主公钥及协议交互运算方面具有较大劣势。文献[13]提出了一种格上基于身份的验证方案，但同样具有效率较低的缺陷。文献[14]虽然减少了文献[13]方案中在线部分的开销，但密钥大小仍与实际应用的需求有较大差距。

因此本文提出了一种新的更加高效的标准模型下格上基于身份的验证方案，该方案的安全性基于最坏情况困难性假设[13-15]，在碰撞问题是困难的情况下可验证模仿者静态身份并发主动攻击安全。本文基于文献[16]中的验证协议，利用文献[14,17]中的盆景树(Bonsai trees)及文献[18]中的陷门函数实现理想格上的用户私钥抽取，并提出叠加承诺与回复技术以及文献[19]签名方案中的参数优化技术构造了更加高效的验证协议。相较于文献[12,14]中的方案，本文方案在密钥与协议消息大小，用户私钥抽取及协议交互的运算开销等方面均有所提升。

1 预备知识

1.1 格

定义1格是向量空间Rn中能够组成加法子群的离散点的集合。一个格Λ可以定义为Rn中n个线性无关向量b1,b2,…,bn与整数系数xi∈的线性组合：

矩阵B=[b1,b2,…,bn]是格Λ的一组基，n为基的秩，由矩阵B生成的格记作Λ(B)。

定义2环R中的每个多项式都有n个属于q的系数，因此在环R与之间存在双射，即环R的理想(Ideals)能够映射到中的一个格，此格即为理想格，定义为：

1.2 困难性问题

本文中主要的一般情况下难解性问题为碰撞问题。

1.3 基于身份的验证方案形式化定义

一个基于身份的验证方案IBI包含四个算法，定义为IBI=(Setup,KG,P,V)：

1) 主密钥生成算法Setup(1κ)：输入安全参数1κ，输出主公钥mpk和主私钥msk。

2) 用户私钥抽取算法KG(msk,id)：输入主私钥msk和id，输出与id相对应的用户私钥skid。

3) 证明者算法P(mpk,id,skid)：输入主公钥mpk，id和用户私钥skid，并与算法V进行交互。

4) 验证者算法V(mpk,id)：输入主公钥mpk和id，与算法P进行交互，最终输出结果dec={accept,reject}。

1.4 安全模型

初始化阶段：

在该阶段之初，CV输入安全参数1κ，并在接收主公钥mpk之前对不同的{id1,id2,…,idt}向挑战者发出用户私钥抽取询问。挑战者输入安全参数1κ，通过Setup(1κ)得到(mpk,msk)；通过KG(msk,idi)计算出对应的用户私钥skidi，其中1≤i≤t；设置CU← {id1,id2,…,idt}；将{skid1,skid2,…,skidt}返回给CV。挑战者初始化TU,PS←∅。TU表示目标用户，CU表示已经被询问过的用户，PS表示证明者会话集合。CV得到主公钥mpk。

学习阶段：

CV向PROV预言机发出询问。PROV预言机接收输入id、session和Min。如果id∉CU，返回⊥。如果(id,session)∉PS，则将(id,session)添加到PS中去，选择一个随机硬币记为ρ，将证明者的状态stP[(id,session)]设置为(mpk,skid,ρ)。然后通过P(Min,stP[(id,session)])得到对应的输出和状态(Mout,stP[(id,session)])。最终返回Mout。

挑战阶段：

CV输出一个目标身份id*和状态信息stCP。如果id*∈CU，挑战者输出拒绝reject并终止，否则，挑战者将{id*}加入到TU中，并将stCP发给CP。与学习阶段相同，CP可以向PROV预言机询问。最终，挑战者运行Run[CP(stCP)PROV↔V(mpk,id*)]得到结果dec，并输出dec。

2 本文方案

本文提出了一种新的基于格的IBI构造。方案使用文献[14,17]中的盆景树技术，将主密钥所对应的格作为盆景树的根节点拓展至任意用户身份所对应的高维格，结合文献[18]中的陷门函数实现用户私钥的抽取。同时提出叠加承诺与回复技术将文献[19]中的高效参数设置方法应用于扩展格相关算法及文献[16]的验证协议中，使得新的基于身份的验证方案的空间效率与运算效率均得到了提升，并且证明该方案是stat-id-imp-ca安全。

2.1 陷门函数及扩展格相关算法

本文方案中所使用的陷门函数及扩展格相关算法描述如下:

本方案利用文献[19]中提出的m≥2n的参数设置方法，结合身份id的长度λ，设置扩展格算法的参数为：m=m1+(λ+1)m2=2n，m1=2nmod(λ+1)，m2=(m-m1)/(λ+1)，σ=1，r=log3(q)+1。

2.2 方案描述

本文格上基于身份的验证方案包含主密钥生成算法，用户私钥抽取算法以及验证协议。

2.2.1 主密钥生成算法

1) 输入安全参数1κ。

3) 定义集合B

2.2.2 用户私钥抽取算法

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

2) 选取密码学安全的哈希函数G，令id=G(id)=ID1‖ID2‖…‖IDλ∈{1,0}λ。

2.2.3 验证协议

3 方案分析

本文提出了格上基于身份的高效验证方案，本章将从完整性、可靠性及效率三方面进行具体分析，证明该方案是stat-id-imp-ca安全，并且空间效率与运算效率均有所提升。

3.1 完整性分析

定理2本文提出的格上基于身份的高效验证方案具备完整性。

具体证明如下：

因此，验证者能够返回dec=accept。故该IBI方案具备完整性。

3.2 可靠性分析

定理3如果碰撞问题Col(H(R,m),D)是困难的，则本文提出的格上基于身份的高效验证方案在stat-id-imp-ca模型下是安全的。

具体证明过程如下：

初始化阶段：

1) 在该阶段之初，CV输入安全参数1κ，并在接收主公钥mpk之前对不同的id1,…,idt向挑战者发出用户私钥抽取询问。

3) 定义集合Wω1,…,ωp满足以下三个条件：①ωi∈，1≤i≤p；②ωi不是任何idj的前缀，其中1≤i≤p，1≤j≤t；③ 对于集合W中任意两个不相同的元素(ωi,ωj)，ωi不是ωj的前缀，1≤i≤p，1≤j≤p。集合W中最多有λt个元素，即p≤λt。

证明者询问阶段：

模仿者攻击阶段：

1) 模仿者CV输出一个挑战身份id*，并且id*并没有在之前的用户私钥抽取预言机询问过。如果该身份id*已经向用户私钥抽取预言机询问过，则预言机返回终止⊥。

由以上证明过程可得：

3.3 效率比较

本文提出的格上基于身份的高效验证方案与文献[14]中提出的格上基于身份的验证方案,以及文献[12]中提出的基于编码的基于身份的验证方案相比，空间效率与运算效率均有所提升，结果如表1所示。三种方面均在并发主动攻击模型下可证明安全，并抵抗量子计算机攻击。

表中的每种方案，第一行为渐进大小与复杂度第二行为实际开销大小与运算次数。本文基于文献[19]的参数选取计算实际大小与运算开销，以达到2100安全性级别，参数具体选取如下：对于文献[14]中基于格的方案，n=512，m1=1，m2=467，m=9 808，λ=20，q=225；对于文献[12]中基于编码的方案，编码长度n=262 144，纠错能力t=9，并行度λ=2；对于本文方案，n=512，m1=4，m2=51，m=1 024，λ=20，q=224。

表1 效率比较

续表1

在渐进大小与复杂度方面，基于编码的文献[12]在主私钥大小和用户私钥大小方面具有优势，而本文方案与基于理想格的文献[14]方案保持一致。

在实际大小与运算开销方面，虽然本文方案在协议交互部分相对于前两种方案需要计算额外的承诺与回复消息，但由此可使参数m的选取值降低，从而本文方案在各方面均优于文献[16]方案与文献[14]方案。其中，主公钥大小由1.44 MB降至0.16 MB，主私钥大小由731.25 KB降至82.50 KB，用户私钥大小由3.80 KB降至0.38 KB。即使承诺与回复消息增加，协议消息大小与协议交互复杂度仍分别由21.32 KB与217级运算次数降至7.13 KB与216，用户私钥抽取运算次数由227降至224。文献[12]在主私钥大小，用户私钥大小方面具有较大优势分别仅需162 bits与324 bits，但由于编码长度的问题，该案在主公钥大小，用户私钥抽取复杂度与协议交互复杂度上劣势明显，分别需要5 MB，238与226级运算次数，需要长时间进行身份验证。相比于文献[12]，本文方案的应用场景更为广泛。

综上诉述，本文提出的格上基于身份的高效验证方案不仅在stat-id-imp-ca模型下可证明安全，并较为显著地减少了密钥大小与用户私钥抽取及协议交互的运算开销。

4 结 语

格上的验证协议是后量子时代重要的密码学应用之一，本文提出了一种格上基于身份的高效验证方案，并在标准模型下取得stat-id-imp-ca可证明安全，使得后量子时代下该应用的实用性进一步增强。另外，如何继续在保持安全性的条件下选取更小的参数以及实现基于层级身份的验证协议将是今后研究的重点。

参考文献

[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]. 南京：南京邮电大学, 2016.

[3] 康元基, 顾纯祥, 郑永辉, 等. 利用特征向量构造基于身份的全同态加密体制[J]. 软件学报, 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] 吴立强, 杨晓元, 韩益亮. 基于理想格的高效模糊身份加密方案[J]. 计算机学报, 2015, 38(4):775-782.

[10] 孙意如, 梁向前, 商玉芳. 理想格上基于身份的环签名方案[J]. 计算机应用, 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.