基于编码的抗量子广义签密方案*

王 众, 韩益亮

武警工程大学密码工程学院, 西安710086

1 背景

1997 年, Zheng 提出了“签密” 的概念[1], 签密方案可以在一个逻辑步骤内完成加密以及认证的功能,相比于传统的先“加密” 后“签名” 或者先“签名” 后“加密” 的方案能够消耗更少的资源, 也易于操作.签密方案虽然具有加密与签名的功能, 但是签密方案、加密方案以及签名方案三者还是有所不同甚至是互斥的, 因为签密方案要求收发双方都需要具有密钥, 而加密方案只要求接收方有密钥, 签名方案只要求发送方有密钥, 三者是不能相互转换的.2006 年, 韩益亮等人提出了广义签密的概念[2], 实现了签密、加密与签名三者之间自适应的转换.现有的广义签密方案基本都是基于离散对数问题、椭圆曲线离散对数问题来进行构造的, 但是在量子技术快速发展的今天, 基于经典数论问题的公钥密码方案将不再安全可靠, 那么提供一种在量子时代进行安全防护的方案就显得十分必要.

目前已知的抗量子计算攻击的密码体制有以下四种, 分别是基于Hash 函数的密码体制、基于多变量的密码体制、基于编码的密码体制以及基于格的密码体制[3].其中, 基于编码的密码具有抗量子计算特性的同时, 还具有加解密过程简单、易于操作的特点.该密码体制是在有限域上多元多项式环上定义和运算的, 此类密码体制的算法核心是对一种纠错码 C 的应用, 主要的特征即为添加一个错误到码字中或根据码 C 的校验矩阵计算伴随式.最早的基于编码的密码体制是由 McEliece 在 1978 年提出的, 它是对Goppa 码的生成矩阵进行变换来进行隐藏而产生公钥[4].Niederreiter 在 1986 年又提出基于Goppa 码的 Niederreiter 密码体制[5], 它则是对 Goppa 码的校验矩阵进行变换, 两种密码体制在安全性上是对等的.Courtois 等在 2001 年提出了基于校验子译码困难问题的签名方案—CFS 方案[6], Mathew 等人在2013 年通过密钥构造的改变使得 CFS 签名方案的密钥量减少[7].为了能够弥补编码密码密钥量大的特点, 用其他码字来代替Goppa 码已经成为一种趋势, 但是这也会带来一些安全上的弊端, 这些弊端已经出现在基于准循环码 (QC)[8]、LDPC 码[9]、QC-LDPC 码[10]、准二进制码 (QD)[11]、卷积码[12]等码字的第一代 McEliece 变体方案中.还有一些使用 QC-LDPC 码[13]、QC-MDPC 码[14]等码字的一些变体方案能够在不损坏安全性的前提下良好地达到密钥压缩的目的, 如2017 年Jean-Christophe 等人提出的Ouroboros 密钥交换协议[15], 2018 年 Baldi 等人提出的 LEDAkem 密钥封装机制[16]等.

本文将继续研究基于编码的密码体制, 借鉴文献 [16]的相关加密方法, 提出基于 QC-LDPC 码的抗量子广义签密方案, 为后量子时代复杂的网络环境提供强有力的保障.第 2 节将对相关理论知识进行介绍, 第3 节详细描述本文方案, 第4 节进行安全性分析, 第5 节对效率进行分析, 最后第6 节总结全文.

2 相关知识

2.1 SD问题

校验子译码问题(syndrome decoding problem): 给定一个(n,k) 维的线性码, 它的最小汉明距离为d, 该码的校验矩阵为它的纠错能力为 t 且 t 满足方程 d = 2t+1.当给定一个向量时, 寻找一个错误向量它的汉明重量要小于等于 t, 且与向量v 以及矩阵H 满足方程v =eHT, 寻找错误向量e 这个问题已被证明为NP 困难问题.

2.2 广义签密

广义签密, 可以实现签名、加密以及签密三者之间的自适应转换.一个广义签密方案 GSC=(Gen,SC, DSC) 包含三个算法.首先是随机化的密钥生成算法Gen(X,1k)→(SDKX, VEKX), 通过输入安全参数k, 来产生用户x 的密钥对, SDK 为私钥用于签名与解密, VEK 为公钥, 用于认证与加密.然后是概率性的签密算法 SC(m, SDKS, VEKR) →θ, 输入待签密消息 m, 与发送者的私钥 SDKS和接受者的公钥 VEKR, 输出签密文 θ.最后是确定性的解签密算法 DSC(θ, SDKR, VEKS) →m ∪ ⊥, 输入签密文 θ,发送者公钥以及接受者私钥, 输出消息m 或者⊥, 其中⊥代表非法明文.

当发送者S 没有密钥时, 整个广义签密方案相当于一个加密方案ENC=(Gen, Enc, Dec).

签密算法即为:

解签密算法即为:

当接受者R 没有密钥时, 整个广义签密方案为签名方案SIG=(Gen,Sig,Ver).

签密算法即为:

解签密算法为:

其中T 代表签名合法, 而⊥代表非法签名.若说明一个广义签密方案GSC=(Gen, SC, DSC) 是正确可行的当且仅当DSC(SC(m,SDKS,VEKR),SDKR,VEKS)=m.

有关广义签密方案的安全性主要涉及两方面.机密性: 自适应攻击者获取关于密文内容的任何部分信息在计算上是不可行的.自适应攻击者可以是发送者和接收者以外的任何一方.不可伪造性: 自适应伪造者在计算上是不可行的, 他们可能是不被信任的接收者, 并且允许查询发送者的签密算法, 伪装发送者以创建真实的密文.当广义签密方案在签密模式下运行时, 必须满足这两个安全概念.在仅加密模式下运行时只需要机密性, 并且在仅签名模式下运行时只需要不可伪造性.

2.3 签密安全模型

根据文献[17,18], 可以得到本文基于编码方案所需的安全模型, 使用下述的攻击游戏进行说明.

定义1如果在下面的攻击游戏中, 攻击者能够取得胜利的优势是可以忽略的, 那么说明此基于编码的广义签密方案在选择明文攻击下满足IND-CPA 安全.

该机密性游戏包含以下三个阶段:

(1) 挑战者选择合适参数, 运行密钥生成算法, 产生发送方以及接收方的公私钥对 (pkS,skS)、(pkR,skR), 并将公钥对(pkS,pkR) 以及发送方的私钥skS发送给攻击者.

(2) 攻击者向挑战者提交两个合法明文(m1,m2), 以及挑战收发双方的公钥对(pkS,pkR), 挑战者收到挑战明文对后, 通过随机选择1 bit b, 将明文mb以及挑战收发双方的公钥对(pkS,pkR) 发送给签密预言机, 进行签密操作产生密文n, 并将该密文返回给挑战者, 再由其返回给攻击者.

(3) 攻击者最后输出1 bit b1.

当b1=b 时, 攻击者赢得该游戏, 其优势为:

定义2如果在下面的攻击游戏中, 攻击者能够取得胜利的优势是可以忽略的, 那么说明此基于编码的广义签密方案在适应性选择消息攻击下满足EUF-CMA 安全.

该不可伪造性游戏包含以下三个阶段:

(1) 挑战者选择合适参数, 运行密钥生成算法, 产生发送方以及接收方的公私钥对对 (pkS,skS)、(pkR,skR), 并将公钥对 (pkS,pkR) 以及发送方的公钥 pkS发送给攻击者, 将发送方的公私钥对(pkS,skS) 发送给签密预言机.

(2) 攻击者进行签密询问和验证询问, 验证密文是否合法.

(3) 攻击者产生挑战消息 m, 以及伪造的签密文 n, 向挑战者提交 (m,n,pkS,skS), 挑战者运行解签密算法解签密(n,skR,pkS), 并输出结果m, 如果之前攻击者都未对(m,pkS,skS) 进行过签密询问, 则说明攻击者伪造成功, 其优势为:

2.4 CFS签名方案

Courtois, Finiasz 和 Sendrier 提出的基于 Niederreiter 密码体制的 CFS 签名方案是为数不多的安全编码基签名方案.具体的初始化与签名验证过程如下:

初始化过程: 取 C 是有限域 GFq上线性 (n,k,d)Goppa 码, n = 2a, d = 2t + 1, k = n −at.(n −k)×n 阶矩阵 H 为二元 (n,k,d)Goppa 码的校验矩阵, 随机选取 GF(2) 上的可逆矩阵 S, 其阶为(n −k)×(n −k), 再选取置换矩阵 T, 其阶为 n×n.设一个哈希函数即将任意长度的 0, 1 串映射到长度为 n −k 的 0, 1 串上.Goppa 的快速译码算法为 βHt(), σ 为待签名消息.将公开, 将 (S,T,H,βHt()) 保密.

签名过程:

(1) 计算 σ 的哈希值 m:m=h(σ) .

(2) 在集合 {0,1,2,···} 中选择一个 i, 计算 mi=S−1h(m||i), 找到一个最小的 i0使得 βHt(mi) 存在, 则 mi0=S−1h(m||i0).

(3) 令 v = βHt(mi0), 签名即为 (i0||vT).

验证过程:

(2) 如果a=b, 则签名成功, 否则失败.

2.5 LEDAkem方案 [16]

2018 年Baldi 等人提出的基于QC-LDPC 码的密钥封装方案采用的是Niederreiter 密码体制, 具体的密钥生成、加解密过程如下:

密钥生成: 首先输入循环块的尺寸 p, 则循环块大小为 p×p, 输入 QC-LDPC 码的校验矩阵 H 中循环块的数量 n0, 数字 dv代表矩阵 H 的行/列重量, 向量 v = (v0,v1,··· ,vn0−1) 代表由个循环块Qi,j所组成的矩阵Q 的行/列重量.具体表示如下,

矩阵H 由个循环块组成, 其维度为p×pn0.矩阵Q 如下所示,

矩阵Q 的行列重量如下所示可知, 其每行每列的重量相等为

其私钥SK 即为(H,Q), 公钥PK 进行如下运算可得,

得到矩阵 L 再利用 Ln0−1, 对其做运算即可得公钥 PK, 矩阵 Ml.

加密过程: 将明文 m 转换为长度为 n, 重量为 t 的错误向量 e, 其中 t 满足 QC-LDPC 码的纠错重量.对其运用公钥进行运算即得密文s.

解密过程: 运用私钥对密文进行如下处理.

3 基于编码密码的抗量子广义签密方案

3.1 方案构造

i.密钥生成: 在有限域 GFq上随机选取 (n,k,d) 的 QC-LDPC 码, n = 2a, d = 2t+1, k = n −at.其译码算法为βHt(), 允许的最大重量为t, (n −k)×n 阶矩阵H 为QC-LDPC 码的校验矩阵, 随机选取GF(2) 上的可逆矩阵 S, 其阶为 (n −k)×(n −k), 再选取置换矩阵 T, 其阶为那么用户U 的公钥即为其中MlU为2.4 节中所描述方案中的矩阵Ml, 用于加密.对应的私钥为矩阵 QU, HU, S, T.再定义两个 Hash 函数

ii.定义区分函数 f(x): 根据用户 U 是否存在密钥来进行赋值操作.当用户 U 的公钥时,则 f(x) = 0, 其中 0 代表 n 维零向量; 当用户 U 的公钥时, 则函数 f(x) = 1, 其中 1 代表 n维单位向量.

iii.签密过程(GSC): R 代表接收者, S 代表发送者, 待签密消息为n 维m.符号表示在集合中随机选取一个元素, ⊕表示异或运算, ||表示级联运算.

3.2 自适应性

(1) 当收发双方均无密钥时.由上述对方案的描述可知, 发送方 S 将不能对待签密消息 m 进行签名以及加密的操作, 所发送的三元组(s,c1,c2) 即为(∅,r,m), 相当于直接把消息发送给了接收者.这种没有任何保密措施的情况适用于匿名用户与匿名计算机系统或者传感器之间进行通信, 并且传输的信息是公开的.

(2) 当发送方 S 有密钥而接收方 R 无密钥时, 此时相当于纯签名的过程.发送方 S 所发送的三元组即为(s,r,m), s 即为利用发送方私钥进行操作所得到的关于消息m 的签名.当接收方收到该三元组后,即可利用r 和m 进行如解签密过程步骤(3) 中所示的验证方式, 来验证签名s 是否合法.这种情况适用于发送方S 是确定性的用户或是已经注册认证的用户、计算机系统或者传感器, 而接收方R 则是匿名用户或者设备.进而防止对所传输的信息进行篡改, 以及对用户或者设备的冒名顶替, 保障了可认证性.

(3) 当发送方 S 没有密钥而接收方 R 有密钥时, 此时相当于纯加密的过程.发送方 S 运用接收方 R的公钥MlR对随机数r 加密后, 再利用加密结果对消息m 进行加密, 输出的三元组即为(∅,c1,c2).接收者收到该三元组后利用自己的私钥进行解密操作即可得明文消息m.这种情况适用于发送方S 为匿名用户、计算机系统或者传感器, 它所发出的消息只想让指定的接收方 R 收到, 且R 为确定的用户或已经注册认证的用户或者设备.

(4) 当接收方 R, 发送方 S 都有各自密钥时, 该方案即为一个签密方案.发送方发送的三元组即为(s,c1,c2), 其中 s 为发送者 S 用自己的私钥进行运算所得到的签名信息, c1,c2为发送者 S 运用接受者R 的公钥进行运算所得到的加密信息, 只有拥有相应私钥的接收者 R 可以对信息进行解密.解签密的过程是接收者运用自己的私钥对c1,c2, 进行解密得到r,m, 再利用发送者 S 的公钥通过r,m 对签名进行验证.这种情况适用于收发双方均为确定的用户或已经注册验证的用户、设备之间进行信息的保密通信.

综上分析可知, 本文的广义签密方案, 能够实现在加密方案、签名方案以及签密方案三者之间自适应的转换, 并且基于编码密码理论, 能够在后量子时代为越发复杂的网络环境提供强有力的保障.

4 安全性分析

对本文广义签密方案进行安全性分析从两个方面入手: 一是对签密信息的机密性进行分析; 二是对签密信息的不可伪造性进行分析.这样不论是纯粹的签名过程还是纯粹的加密过程的安全性都可以包含在内, 机密性从 IND-CPA 安全入手, 不可伪造性从 EUF-CMA 安全入手, 证明过程在文献 [17–19]的基础上进行, 游戏模型如图1 所示.

图1 攻击游戏模型Figure 1 Attack game model

4.1 不可伪造性

从随机数的选取, 游戏模拟成功的概率, 以及对SD 困难问题进行成功求解来对所得签密文进行验证的角度, 对攻击者成功伪造签密文的概率进行分析.

定理1在随机预言机模型下, 假定存在一个EUF-CMA 的攻击者 α, 它能够以优势赢得如下定义的游戏, 那么就存在一个算法β, 它解决SD 问题的优势表示如下:

qSC,qDSC,qh1,qh2分别代表攻击者α 所能进行的签密询问、解签密询问、以及对随机预言机h1和h2的询问的最大次数.为了方便回答这四种询问, 并分别设立四个询问列表来对询问进行记录.

证明:给定一个本文广义签密方案的SD 问题实例, 攻击者α 为攻击算法β 的子程序, 而β 则作为攻击者α 在挑战过程中的挑战者.攻击者α 可以进行以下询问:

(1) 预言机 h1询问: 如 3.1 中对方案描述的那样, 向预言机 h1中输入 (m,r), 首先查询表, 是否存在相应记录, 不存在则随机产生一个入d 值, 并将该值记录在表中.

(2) 预言机h2询问: 向预言机h2中输入(d,i), 进行询问, 首先查询中是否存在相应的记录, 不存在则随机产生一个值, 并将其记录在表中.

(3) SC 签密询问: 将消息m 输入 SC 预言机, 首先查询 SCList表中是否有对应的记录, 若存在相应记录, 返回给攻击者 α 该签密文 n.若没有, 则先进行预言机 h1询问, 如 (1) 中所述那样产生 d 值, 再调用预言机h2, 并进行方案中相应的签密操作, 最后产生一个签密文 n, 记录在SCList中, 并将其返回给攻击者α.需要注意的是, 当SCList表中没有相应记录但是预言机h1或预言机h2存在相应记录时, 签密模拟的过程则是失败的.

(4) DSC 解签密询问: 输入签密文 n, 首先对表 DSCList进行查询, 若存在对应的明文 m 则返回给攻击者α, 若不存在则进行方案所述的解签密过程求解出相应的r 值, 再询问表找到相应的记录, 返回m, 否则说明该签密文不合法.

不可伪造性攻击游戏进行以下三个阶段:

(1) 运行系统, 选择合适参数, 产生收发双方的公私钥对.

(2) 攻击者 α 可以向挑战者 β 进行预言机 h1询问、预言机 h2询问.

(3) 攻击者向挑战者提交挑战消息m, 以及伪造的签密文 n, 挑战者对 n 运行解签密算法求出结果,若该结果即为m 且之前没有对其进行过签密询问, 则说明攻击者伪造成功.

首先模拟成功的话, 需要译码成功才能产生合适的签名, 这就取决于选择合适的i 值, 当询问h2预言机输入 (d,i), i 值总共有 2n−k种可能, 签密询问的最大次数为 qSC, 那么模拟成功的概率为 qSC/2n−k,那么攻击者成功进行预言机 h2询问的概率为 Pr[M1]= qSC/2n−k.在成功完成预言机 h2询问后, 才能继续下面的签密询问, 在qh2中的某一次询问成功后, 继续进行签密询问, 二者都成功的概率为Pr[M2]=(1/(qh2+qSC)).签密询问后得到签名 s 后, 还需要对签名的正确性进行验证, 模拟一个正确的签名也即能够通过验证需要破解 SD 问题, 因此该事件的成功概率不会大于成功解决 SD 问题的概率 Pr[M3]≤(此处未在考虑QC-LDPC(n,k,t) 码的参数选择, 方案在构造时的参数选择一般较大).

综上所述, 攻击算法 β 得该游戏的优势 Pβ为:

据上述分析, 可以看出本文方案满足EUF-CMA 安全.

4.2 机密性

从随机数选取, SD 问题的难解性以及游戏模拟的成功概率方面进行证明.

定理2在随机预言机模型下, 假定存在一个IND-CPA 的攻击者 α, 它能够以优势赢得如下定义的游戏, 那么就存在一个算法β, 它能够在多项时间内以优势解决SD 问题.

证明:算法 β 得到本文广义签密方案的一个 SD 问题实例 Y = P(X), 攻击者 α 作为攻击算法 β的一个子程序, 而β 则作为攻击者α 在询问过程中的挑战者.

具体攻击过程如下:

阶段 1: 算法β 获得了该SD 问题实例中的公私钥对, 并将公钥发送给攻击者α, 攻击者α 可以向挑战者β 进行三种询问, 即预言机h1询问、预言机h2询问、SC 签密询问.

挑战阶段: 攻击者 α 向挑战者 β 提交两个合法明文 (m1,m2), 挑战者收到挑战明文对后, 通过随机选择1bit b, 对明文mb运用合法用户的私钥进行加密产生密文n, 并将该密文返回给攻击者α.

猜测阶段: 攻击者α 根据询问的结果, 输出b.

从上述攻击游戏以及本文方案中可以看出, 即使是对同一个明文m 进行加密, 由于随机数r 的选取,使得二者相同的概率极低.通过直接攻击, 来对SD 问题进行运算成功的概率是极低的, 因为, 当 LRPC码的维度较大时, SD 问题作为一个困难问题以及编码密码体制的理论基础, 是很难被攻破的.因此在多项式时间内, 不断地对 (m1,m2) 进行签密询问, 是难以区分出 m1与 m2的.还有需要注意的一点就是模拟游戏成功的概率, 在签密询问时有可能产生Hash 函数的碰撞, 导致模拟过程的失败, 即是向预言机 h1中输入 (m,r) 进行询问时, r 值已经存在于预言机 h1的询问记录表中.在签密询问时, 询问的最大次数为qSC, 哈希预言机产生的结果有2n种, 那么产生碰撞的概率即为qSC/2n, 因此记模拟成功为事件 Msuc, 它成功的概率为 (1 −qSC/2n), 这又进一步减少了优势.综上所述, 攻击者可以根据签密文成功猜得的 mb概率为1/2, 也即:

据上述分析, 可以看出本文方案满足IND-CPA 安全.

根据文献 [20]中的相关内容可知, 由于 LRPC 码在译码时具有不可忽略的错误率, 其错误率大概为 10−7.这个错误率虽然不会对方案的可靠性造成大的影响, 但是成为方案安全性评估所不可忽略的因素, 这也使得很多基于编码的密码方案不能满足 IND-CCA2 安全.文献 [20]还给出了一种将基于 QCMDPC 码的方案进行转换而满足 IND-CCA2 安全的方法, 那就是将待加密信息利用同一公钥进行多次加密, 进而产生关于明文的一组相互独立的密文, 那么在进行解密工作时, 只有当这些密文都出现译码错误时, 才会导致方案的错误, 这种方法也就将译码错误率10−7变小为10−7n, 大大减小了译码错误率对方案安全的影响程度, 根据文献 [20], n 的取值一般在 3 到 12, 具体细节参考文献 [20].本文广义签密方案也可以根据这种对明文信息进行多次加密的方法来转换为IND-CCA2 安全, 也即多次运行签密过程中的(1) 到 (3) 步, 相应的密文 c2也就变成了一组密文 (c21,c22,··· ,c2n), 相应地在解签密过程中, 就需要对(c21,c22,··· ,c2n) 分别进行解签密, 只有当这 n 次解签密全部出现错误时, 方案才会受到译码错误的影响, 而这发生的概率是极低的.

5 效率分析

本文方案采用 QC-LDPC 码进行构造, 由于 QC-LDPC 码的准循环性以及稀疏性, 因此它的存储只需要校验矩阵中的非零循环子矩阵与循环的位数, 要比 Goppa 码等码字的容量小许多, 并具有较高的信息率, 进而保障本文方案的密钥量较小.根据文献[16,21]将采用Goppa 码的Niederreiter 密码方案与采用 QC-LDPC 码的 Niederreiter 方案以及采用 QC-LDPC 码的 LEDAkem 方案进行比较, 如表1.

表1 方案性能对比Table 1 Scheme comparison

从表1 可知, 所选 QC-LDPC 码的n0为4, k0为3, 循环子矩阵的维度p 值为4032, 因此公钥量即为p×k0×n0.QC-LDPC 码在公钥量的大小以及加密数据的处理量和信息率方面都要比传统Niederreiter密码方案所采用的 Goppa 码有较大的提升, 而采用 QC-LDPC 码的 LEDAkem 方案相比二者在密钥量方面又有较大的优势.

本文方案在实现签名功能时选择的方法为CFS 签名方法, 采用经过密钥构造改造过的P-CFS[22]签名方法也可以达到同样的效果, 并且能够选择更小的参数, 减少方案的密钥量, 因此在P-CFS 签名方法下,仍然选择 (16 128, 12 096) 的 QC-LDPC 码, 根据文献 [16,22], 进行密钥量的比较分析, 如表2.

表2 密钥量对比Table 2 Key Size Comparison

表2 中的签名加密方案是指先进行签名再进行加密的方案, 两步是分离的, 因此其密钥量即为签名方案与加密方案的和.本文广义签密方案是将二者进行融合, 在私钥量这一方面, 有部分私钥是P-CFS 签名方案与LEDAkem 方案共用的, 因此私钥量有所下降.综上分析可知, 本文方案实现了签密、签名、加密三者之间的自适应转换, 又由于QC-LDPC 码与LEDAkem 加密方法的采用, 使得新方案能够在消耗较少存储资源的前提下为后量子时代的网络通信提供较好的保障作用.

6 结束语

本文通过对编码密码中的 LEDAkem 密钥封装机制以及 CFS 签名方案进行研究, 将二者进行结合,运用LEDAkem 密钥封装机制中的加密方法与CFS 签名的方法进行结合, 进而提出了基于编码密码的广义签密方案.该方案采用QC-LDPC 码, 保证了密钥量在适宜范围内, 通过安全性分析, 新方案在适应性选择密文攻击下满足IND-CCA2 安全, 在适应性选择消息攻击下满足EUF-CMA 安全, 并具有能够在加密方案、签密方案、签名方案或者普通通信方式 (未采用保护措施) 下的自适应性转换, 减少了安全防护的代价, 可以适应日益复杂的通信环境, 并能够在后量子时代为网络通信提供安全保障.