基于格的后量子秘密握手方案

安致远 温雅敏 张方国

摘   要：秘密握手协议作为一种新型的密码学应用，允许属于同一组织的个体在保护隐私的前提下进行秘密的双向认证。目前针对秘密握手的方案多基于一些传统困难问题，这些问题在量子算法攻击下都不再安全。文章通过修改已有的基于身份的消息恢复签名[1]，提出了一个基于格上小整数解问题的秘密握手协议，其在随机预言机模型下可证明安全，协议双方协商得到的会话密钥长度适中，整体效率也具有可实践性。

关键词：秘密握手;隐私保护;格密码;消息恢复签名;可证明安全

中图分类号：
TP309          文献标识码：A

Abstract：
Secret handshake scheme allows the members of a certain organization to conduct a two-way authentication under the premise of privacy protection. At present， most secret handshake schemes are based on some traditional difficult problems， which are not secure when faced with quantum computers" attacks. Based on an identity-based message recovery signature[1]， this paper proposes a secret handshake scheme whose security is under lattices short integer solution assumption. Its provably secure in the random oracle model， the length of the private session key negotiated by both participants is suitable for communication， runtime performance is also practically acceptable.

Key words：
secret handshake; privacy protection; lattice cryptography; message recovery signature; provable securit

1 引言

秘密握手方案是一种满足隐私保护安全需求的双向认证协议，最早是由Balfanz等人[2]在2003年提出，它允許属于同一组织的不同成员可以进行秘密的认证而不泄露彼此的隐私信息，当且仅当协议双方拥有相同的组织公钥证书时，认证过程才能成功，而如果通信双方属于不同组织，则认证过程不会暴露双方彼此的组织信息。在当今互联网迅猛发展的时代，大量用户认证和接入服务尤其需要满足用户的隐私保护需求，这使得秘密握手的应用前景变得非常广泛，一个典型的例子就是网上办公的两名公司员工在传输公司高级机密时的秘密双向认证。

近些年有许多两方/多方秘密握手方案被提出[3～11]，但这些基于传统困难问题（离散对数，平方根剩余等）的方案在量子攻击下不再安全。而随着量子计算的飞速发展，具有抗量子攻击特性的格密码体制则受到更多的青睐。

本文通过借鉴一种通用构造：将基于身份的消息恢复签名（Identity-based Message Recovery Signature， ID-MRS）转化为基于一次性伪名的秘密握手方案[3]，修改格上的ID-MRS[1]设计了一个后量子的两方秘密握手方案，该方案在随机预言机模型下可证明安全，协议会话密钥适中，整体运行效率具有可实践性。

2 预备知识

2.1 符号和定义

文中正整数n均表示秘密握手方案中的安全参数，，表示整数集合，表示实数集合。令，，对任意，表示多项式c的第i个系数，满足。比特函数的功能是计算由多项式c的系数中的最高有效位组成的比特字符串，即为1，当且仅当，否则为0。黑体小写字母如代表列向量，为的转置;黑体大写字母如代表矩阵。向量的欧几里得范数记为。表示矩阵的第i列向量，。满秩方阵的Gram-Schmidt正交化矩阵为。文中所有对数函数底数都为2。

4 安全和效率分析

4.1 安全分析

文献[1]中已经证明了在SIS困难问题前提下，本文运用的ID-MRS方案在随机预言机模型下是EU-ACMA的，类似文献[3]中的证明思路，下面给出本文秘密握手方案的安全证明。

定理3  若基础的ID-MRS方案在随机预言机模型下是EU-ACMA的，则本文提出的秘密握手方案满足防伪造性。

证明：秘密握手方案的防伪造性是通过攻击者和挑战者实施的一个攻击游戏来形式化定义的，详细的攻击游戏描述可参考文献[17]。若存在一个适应性攻击者试图伪造为一名合法成员，与属于同一组织的某一个诚实用户B（伪名为）进行一次秘密握手协议，且可以在多项式时间界限t内以一个不可忽略的概率验证成功，则在协议过程中一定向B发送了正确的回应标签，其中是由和恢复出来的共同计算得到的。也就是说被B验证通过了，则一定事先向预言机询问了关于的映射结果。为了使得与B通过发送的ID-MRS（）恢复出来的计算得到的会话密钥相同，本文可以得知，在秘密握手第一轮步骤中由发送的ID-MRS（）是在没有组织证书前提下伪造的可验证成功的消息恢复签名，因此挑战者可以利用构造一个算法来攻击上述ID-MRS的适应性存在不可伪造性。

若企图攻破秘密握手方案的防伪造性，则可以自适应的访问关于秘密握手方案的预言机，这些预言机对应模拟方案中的算法CreateGroup，AddMember，Handshake以及所有哈希函数，参考文献[1]中指出这些预言机的模拟类似ID-MRS方案中的Setup，Extract Queries，Sign Queries以及Verify Queries。因此，攻击者的成功蕴含了挑战者B可以成功攻破ID-MRS的EU-ACMA，这样可以将文中提出的秘密握手方案的防伪造性归约到ID-MRS的安全性，由于本文所采用的ID-MRS方案基于格上SIS困难问题证明是EU-ACMA安全的，因此，本文提出的秘密握手方案在随机预言机模型下满足防伪造性。

定理4  若基础的ID-MRS方案在随机预言机模型下是EU-ACMA的，则本文提出的秘密握手方案满足防侦测性。

证明：定理证明思路类似定理3。若存在一个攻击者可以以不可忽略的概率攻破秘密握手方案的防侦测性，则敌手可以利用产生一个算法以一个不可忽略的概率伪造出可验证成功的消息恢复签名，这就攻破了ID-MRS方案的EU-ACMA。秘密握手方案防侦测性的形式化安全证明通过和攻击者完成一个攻击游戏实现，攻击游戏的详细说明可参考文献[17]。类似于防伪造性证明，攻击者 以不可忽略的概率优势成功赢得游戏胜利（也就是秘密握手方案的防侦测性）可以归约到ID-MRS的安全性。由于本文采用的ID-MRS方案基于格上SIS困难问题证明是EU-ACMA安全的，因此，本文提出的秘密握手方案满足防侦测性。

定理5  若基础的ID-MRS方案在随机预言机模型下是EU-ACMA的，则本文提出的秘密握手方案满足不可关联性。

证明：一般来说，本文可以通过使用一次性伪名证书来达到不可关联性，也就是说，若一个攻击者作为某一个组织的合法成员执行了两次不同的秘密握手协议，那么在每次协议中它所使用的身份信息是不相同的，这就保证了两次秘密握手协议的内容之间是不可关联的。与防侦测性和防伪造性的安全证明类似，不可关联性的形式化安全证明通过一个攻击游戏定义，完整的攻击游戏和预言机定义可参考文献[17]，攻击者以不可忽略的概率优势成功区分两次握手协议是否来自于同一个用户也依赖于攻击者能否成功攻破握手方案中的ID-MRS的安全性。由于本文采用的ID-MRS方案基于格上SIS困难问题证明是EU-ACMA安全的，因此，本文提出的秘密握手方案满足不可关联性。

4.2 效率分析

通信复杂度：假设协议双方所需的组织证书，已由GA事先颁发，则协议用户发送一个签名的比特长度为，产生的消息验证码的比特长度为，运行一次协议总的通信复杂度（比特长度）为 。对于一些合理的安全参数，例如，令，参考[18]中公共参数取值：，，，，，，可知，这表明方案需要的通信负载量是具有可实践性的。

计算复杂度：方案只在CreateGroup和AddMember阶段用到了两种抽样技术，在一个实时在线的秘密握手系统中，可以将所有的抽样操作线下完成，这样系统在线的计算操作只包括矩阵/向量之间的乘法和加法，此外，本文使用SHA-512作为方案中的哈希函数。将与生成签名相关的一次矩阵/向量之间的乘法（如或）记为，则，加/减法（如）記为，则将与消息验证相关的一次矩阵/向量之间的乘法（如）记为，则加/减法（例如）记为，则，其中是中两个多项式相乘的计算开销，而是中两个多项式相加的计算开销。协议生成一次成功签名重复次数的期望值为M[19]。综上执行一次秘密握手协议的计算复杂度如表所1示。

由上可知，当安全参数为一些合理的数值（）时，运行一次秘密握手协议的计算总开销约为。

与基于传统困难问题的方案[3，6，7，8]相比，本文提出的方案不需要更加耗时的双线性对运算（椭圆曲线上）和模指数运算，而只需进行向量间的加乘法，实践中将更适用于现代并行式操作系统，但对应的是GA对于用户群身份的储存开销变大，约为。

5 结束语

本文提出了一个格上后量子的两方秘密握手方案，在随机预言机模型下可证明安全，且通信复杂度和计算开销具有可实践性。为了实现简便的可追踪和可撤回性，方案在用户身份信息的管理上使用了一次性伪名证书。作为格上的方案，研究也为使用其他困难问题构造秘密握手方案提供了新的思路。未来的工作包括探寻如何使用可重用证书来构造后量子的秘密握手方案，以及如何将本文构造拓展成多方用户参与的方案。

基金项目：

1.国家重点研发计划（项目编号：2017YFB0802500）;

2.国家自然科学基金（项目编号：61672550，61972429）;

3.广东省基础与应用基础研究重大项目（项目编号：2019B030302008）;

4.广东省基础与应用基础研究基金（项目编号：2019A1515011797）。

参考文献

[1] Tian Miaomiao， Huang Liusheng. Identity-based signatures from lattices：
Simpler， Faster， Shorter [J]. Fundamenta Informaticae， 2016， 145（2）：
171-187.

[2] Balfanz D ， Durfee G ， Shankar N ， et al. Secret handshakes from pairing-based key agreements [C]. Symposium on Security & Privacy. Berkeley， CA：
IEEE， 2003. 180-196.

[3] Wen Yamin， Zhang Fangguo， Xu Lingling. Secret handshakes from id-based message recovery signatures：
a new generic approach [J]. Computers and Electrical Engineering， 2012， 38（1）：
96-104.

[4] Wen Yamin， Zhang Fangguo， Wang Huaxiong， et al. A new secret handshake scheme with multi-symptom intersection for mobile healthcare social networks [J]. Information Sciences， 2020， 520：
142-154.

[5] Wen Yamin， Zhang Fangguo. A new revocable secret handshake scheme with backward unlinkability [C]. EUROPKI 2010. Berlin， Heidelberg：
Springer， 2010. 45-56.

[6] Hou Lin， Lai Junzuo， Liu Lixian. Secret handshakes with dynamic expressive matching policy [C]. Australasian Conference on Information Security and Privacy. Berlin：
Springer， 2016. 461–476.

[7] 王聞博，程庆丰，陆思奇，等.一种基于混沌映射的秘密握手协议 [J].信息网络安全，2015， （11）：
40-46.

[8] Tian Yangguang， Li Yingjiu， Deng R H， et al. A new construction for linkable secret handshake [J]. The Computer Journal， 2020， 63（4）：
536-538.

[9] Panja S， Dutta S， Sakurai K. Deniable secret handshake protocol - revisited. [C]. Advanced Information Networking and Applications. Cham：
Springer， 2019. 1266-1278.

[10] Jarecki S， Kim J， Tsudik G. Group secret handshakes or affiliation-hiding authenticated group key agreement [C]. Topics in Cryptology – CT-RSA 2007. Berlin， Heidelberg：
Springer， 2007. 287-308.

[11] 汪维家，李勇，刘云.一种短密钥环境下多方秘密握手方法 [P].中国：101908961A， 2010-12-08.

[12] Lyubashevsky V. Lattice signatures without trapdoors [C]. Advances in Cryptology-EUROCRYPT 2012. Berlin， Heidelberg：
Springer， 2012. 738-755.

[13] Ajtai M. Generating hard instances of lattice problems [C]. Proc. STOC 1996. New York：
ACM， 1996. 99-108.

[14] Alwen J，Peikert C. Generating shorter bases for hard random lattices [J]. Theory of Computing Systems， 2011， 48（3）：
535–553.

[15] Zhang Fangguo， Willy Susilo， Mu Yi. Identity-based partial message recovery signatures （or how to shorten id-based signatures） [C]. Financial Cryptography and Data Security. Berlin， Heidelberg：
Springer， 2005. 45–56.

[16] Jing Zhengjun，Gu Chunsheng，Yu Zhimin， et al. Cryptanalysis of lattice-based key exchange on small integer solution problem and its improvement [J]. Cluster Computing， 2019， 22（1）：
1717-1727.

[17] Yutaka Kawai， Kazuki Yoneyama， Kazuo Ohta. Secret handshake：
strong anonymity definition and construction [C]. Information Security Practice and Experience， 5th International Conference. Berlin， Heidelberg：
Springer， 2009. 219–229.

[18] Micciancio D，  Regev O. Worst-case to average-case reductions based on gaussian measures [J]. SIAM Journal on Computing， 2007， 37（1）：
267– 302.

[19] Von Neumann J. Various techniques used in connection with random digits [J]. Journal of Research of the National Bureau of Standards， 1951， 12（1）：
36-38.