辫子群上的公钥加密算法

辫子群是一种新兴的适用于量子计算机时代的公钥密码平台，辫子群上已知的用于公钥密码系统的一些难解问题和基于这些难解问题的公钥加密算法都受到不同程度的攻击。辫子群上公钥密码系统的安全性不能仅仅依靠共轭问题的难解性，结合辫子群上非共轭变换和多变量方程组的特点所构造的难解问题，通过增加变量数量来增加问题的难解程度。辫子群上新的公钥加密算法可以抵抗已知的各种攻击，将简单问题复合成多变量难解问题的思路，对公钥密码算法的设计起到一定的启发作用。

一、辫子群和辫子群上的难解问题 

定义1（辫子群）：

辫子群是一类特殊的Artin群，一个由n−1（n≥3，由单个初等辫子生成的辫子群是无限循环群，本文不予考虑）个初等辫子生成的辫子群Bn表示为 ：

辫子群是一类无限、非交换的无纽群。一根辫子，如果其表达式中不出现初等辫子的负次幂，这样的辫子叫 做正辫子，单位元ε也属于正辫子，所有的正辫子形成一个独异点（monoid），记作B+n。

令∆1=σ1，递归地定义∆i=σ1σ2…σi∆i−1（2≤i≤n−1），则∆=∆n−1称为辫子群Bn的基本辫子。

在Bn上可以定义一种偏序关系“≤”，任何（x，y）∈Bn×Bn，x≤y当且仅当存在（α，β）∈B+n×B+n，使得y=αxβ。任何满 足ε≤α≤∆的辫子α称作标准因子。

如果w，α，β∈B+n，w=αβ，则称β是w的一个尾部。进一步地，如果α是标准因子，则称w的这种分解是“左加权”的是指α在所有的分解中根据偏序关系“≤”，长度最长。根据这种“左加权”分解，任何辫子w可以唯一地表示成Garside范式：

其中，αi（1≤i≤s）均为不等于ε和∆的标准因子，且αiαi+1是左加权的。我们将s称作辫子w的标准长度，r=inf（w）称作w的下确界，r+s=sup（w）称作w的上确界。

辫子群中的任何辫子都可以在多项式时间内有效地表示成Garside范式的形式，两根辫子相等，是指它们有相同的Garside范式表示。

辫子群之间有一些显而易见的关系，对于正整数m≤n，Bm是Bn的子群；如果l和r是正整数，Bl+r是由σ1，σ2，…， σl+r−1这l+r−1个元生成的辫子群，由σ1，σ2，…，σl−1生成的群，记作LBl，由σl+1，…，σl+r−1生成的群记作RBr，则它们都是Bl+r的子群，而且满足关系:任意（a，b）∈LBl×RBr，均有ab=ba。

定义2（共轭）：

辫子群Bn中的两个元素x和y共轭是指存在a∈Bn，使得y=a−1xa。

辫子群上有很多数学上“难解”的问题，这些问题均可被用作构造公钥密码系统，下面仅列举与共轭相关的4个问题。

1） 共轭判断问题：给定（x，y）∈Bn×Bn，判断x和y是否共轭。

2） 共轭搜索问题：给定（x，y）∈Bn×Bn，x和y共轭，求解一个a∈Bn，使得y=a−1xa。

3） 一般化共轭搜索问题（问题2）的一般情况）：给定（x，y）∈Bn×Bn和m&lt；n，若存在b∈Bm，使得y=b−1xb，求解一 a∈Bm，使得y=a−1xa。

4） Diffie-Hellman共轭问题：给定p∈Bn，对任意（a，b）∈LBl×RBr，若已知a−1pa和b−1pb，求a−1b−1pab。

就目前的研究状况来看，这些问题都遭到不同程度的攻击，依赖于这些“难解”问题所构造的公钥加密算法，其安全性是不够的。

二、辫子群上的公钥加密算法 

1、已有公钥加密算法 

一个实用的辫子群上的公钥加密算法BPKE1是由Ko和Lee等人提出来的，其安全性是基于上述的Diffie-Hellman共轭问题，该公钥加密算法的一个更一般的版本是由Cha和Cheon等人提出来的，下面我们描述这个更一般的算法。

算法1：

辫子群上的公钥加密算法BPKE2。

私钥:辫子对（x1，x2）∈LBl×LBl。

公钥:辫子对（a，b），

其中：a∈Bn；b=x1ax2。

加密过程：

假设消息为M∈{0，1}k，加密算法所使用的散列函数为H:Bn→{0，1}k， ｝

1） 随机选择（y1，y2）∈RBr×RBr。

2） 密文为（y1ay2，H（y1by2）⊕M。

解密过程: 

给定密文（c，d），明文为M=H（x1cx2）⊕d。

BPKE1规定x2=x1-1，y2=y1-1。

显然，由于（x1，x2）∈LBl×LBl，（y1，y2）∈RBr×RBr，所以，x1y1=y1x1，x2y2=y2x2，

因此， H（x1y1ay2x2）⊕H（y1by2）⊕M=H（y1x1ax2y2）⊕H（y1by2）⊕M=H（y1by2）⊕H（y1by2）⊕M=M，

所以，解密是正确的。

2、已知攻击 

定义3（P-BPKE问题）。

给定（x，y）∈Bn+×Bn+，如果存在（a，b）∈LB×LBl+使得y=axb，求出至少一对这样的（a，b）。

显然，如果P-BPKE问题可解，那么BPKE2公钥加密算法就可以破译。

有资料给出了两种P-BPKE问题的概率解法。这些解法用辫子群的Burau表示，对Hughes算法进行了改进，实验结果表明：随着n以及a和b的标准长度的增加，线性表示攻击成功的概率会显著减小。

Cheon和Jun利用辫子群的Lawrence-Krammer表示，可以在多项式时间内解决Diffie-Hellman共轭问题，因而也可以用来攻击BPKE1。

BPKE2公钥加密算法已经回避了利用共轭问题来构造加密算法，因此，一些基于辫子群共轭性的攻击方法，如Hofheinz-Steinwandt共轭搜索攻击、SSS（super summit set）和USS（ultra summit set）集合攻击等，是不能奏效的。

此外，由Hughes等人提出的长度攻击，后来经Garber等人一般化，可以用来求解辫子群上的一般性方程。这种方法是一种概率攻击方法，成功的前提是同一变量必须提供足够的概率累积，不能用于BPKE2。

三、新的难解问题 

本节我们提出两种新的辫子群上的难解问题，它们均通过增加问题中变量的个数来增加难解性。

1、 多重P-BPKE问题 

定义4（多重P-BPKE问题）：

给定wi和vi∈Bn，1≤i≤k，如果存在xi（0≤i≤k）∈LBl，使得wi=xi−1vi1−ix（1≤i≤k），求出 至少一组这样的xi（0≤i≤k）。

当所有xi（0≤i≤k）相等时，多重P-BPKE问题就是MSCP（multiple simultaneous conjugacy problem）问题。MSCP问题首先被应用在AAG密钥协商协议之中，下面我们来分析多重P-BPKE问题的安全性。

首先，由于xi（0≤i≤k）的生成元为初等辫子，而且每个xi（0≤i≤k）和它的逆仅在最多两个等式中出现，所以不能提供概率累积，因而，长度攻击不能解决多重P-BPKE问题。

此外，多重P-BPKE问题不涉及明显的共轭变换，通过等式wi=xi−1vi1−ix（1≤i≤k）唯一能够构造出的非平凡的一类共轭关系为wi+1wi= xi（vi+111−+ixxi−1vi），但是v1−ixi+111−+ixxi−1vi
未知，共轭搜索攻击和基于Diffie-Hellman共轭问题的攻击都不能用于求解此类问题。

设ρ为Bn上的任一线性表示，E为多重P-BPKE问题在ρ表示下的矩阵方程组，如果没有有效的算法可以判断某一矩阵是否为像集ρ（Bn）中的元素，那么，当E没有唯一确定解的时候，基于ρ表示的攻击不能解决多重P-BPKE问题，因为我们无法从E的无数个矩阵解中判断哪一个解才是像集ρ（Bn）中的元素，“提升”回辫子群的过程就会失效.Burau表示、着色Burau表示和Lawrence-Krammer表示都属于此类线性表示。

我们可以看出：Burau线性表示攻击成功的必要条件是通过矩阵方程能够求得所求解对象的一个唯一确定的Burau表示，然后才能“提升”回辫子群。AAFG密钥交换协议提供了足够多的共轭辫子对，使得方程的个数超过了变元的个数，因而矩阵方程可解；由于BPKE2加密算法的特殊性，使得矩阵方程（在系数为满秩的情况下）可以利用矩阵变换直接求解。

对于Burau线性表示，我们可以估算多重P-BPKE问题抵抗线性表示攻击的参数取值。首先，我们证明关于Burau线性表示的一个性质：

定理1：如果x∈LBl，那么，x的Burau表示是一个分块对角矩阵：

如果x∈RBr，那么，x的Burau表示是一个分块对角矩阵：

其中：xl，xr是l阶和r阶方阵；In−1，In−r是n−l阶和n−r阶单位矩阵；

证明：由Burau表示的定义，初等辫子σi的Burau表示为：

其中：Ii−1，In−i−1分别为i−1和n−i−1阶单位矩阵；元素1−t出现在主对角线上第i行和i列的位置.当i&lt；l时，σi∈LBl；而当i&gt；n−r时，σi∈RBr.两种情况下，ρ（σi）（t）显然均为定理中所述的分块对角矩阵.根据矩阵乘法的性质，分块对角矩阵对于矩阵乘法是封闭的，再由Burau表示的线性性质，即可得到结论。

定理2： 如果l&gt；（2kn+2k+2）/（2k+1），则在多重P-BPKE问题的Burau线性表示中，变元的个数多于方程的个数。

证明：假设利用Burau表示形成的关于多重P-BPKE问题的k个矩阵方程为：

其中：所有矩阵均是n阶方阵；Wi，Vi分别是wi和vi（1≤i≤k）的Burau表示；Xi是xi（0≤i≤k）的Burau表示。为了便于分析，我们对方程组（1）进行化简，变形为：

由于xi∈LBl，所以，根据定理1，可以将Xi看成是具有l2个简单变量的未知元，这样，方程组（2）总共有（k+1）l2个简单变量。将方程组（2）中的所有矩阵方程分块表示为：

也就是：

对比矩阵中的各个元素，每个矩阵方程可以得到l2+2l（n−l）个关于简单变量的方程，k个矩阵方程总共有k（l2+2l（n−l））个方程。由资料还得知:Burau表示的每个行向量和列向量均满足一个线性约束条件，这些约束条件的总个数为2l（k+1）。将它们加上之后，我们共可以得到k（l2+2l（n−l））+2l（k+1）个关于变元的方程。如果要求k（l2+2l（n−l））+2l（k+1）&lt；（k+1）l2，即有l&gt；2kn+2k+2）/（2k+1）。

2、因子隐藏问题（BFHP） 

定义5（因子隐藏问题BFHP）。给定w和vi∈Bn，1≤i≤k，如果存在xi（0≤i≤k）∈RBr使得w=x0v1x1v2…vkxk，求出至少一组这样的xi（0≤i≤k）。

首先，与多重P-BPKE问题一样，我们有下面的结论：长度攻击、共轭搜索攻击和基于Diffie-Hellman共轭问题的攻击不能解决BFHP问题。

利用Burau表示，我们计算BFHP问题抵抗Burau表示攻击的能力。

定理3：

如果（r−1）2&gt；n2/（k+1）+1，则在BFHP问题的Burau线性表示中，变元的个数多于方程的个数. 证明:利用Burau表示，我们将方程w=x0v1x1v2…vkxk映射成矩阵方程.由于xi（0≤i≤k）∈RBr，其Burau表示中变元的个数为r2，所以，矩阵方程中总共有（k+1）r2个变元.矩阵方程再加上Burau表示的约束条件，方程的总个数为n2+2r（k+1）。为了使变元的个数多于方程的个数，只需（k+1）r2&gt；n2+2r（k+1），即：

实事上，如果n=l+r，定理2和定理3的条件是不可能同时满足的。因为由（r−1）2&gt；n2/（k+1）+1和n=l+r，我们有：

结合定理2，我们可以得到 ：

但是：

这要求（2kn+2k+2）/（2k+1）&gt；n−1−11）/（2++kn，矛盾。

但是，BFHP问题中的方程是Z[t，t−1]上的高次多变量方程，即使方程的个数多于变元的个数（overdefined），求解这样的系统也是一个NP困难的问题。

四、新的公钥加密算法 

1、新加密算法描述 

根据第3节所描述的两个辫子群上的难解问题，我们提出如下新的公钥加密算法。

算法2、辫子群上新的公钥加密算法NBPKE。选择正整数l，n，k满足n−2&gt；l&gt；（2kn+2k+2）/（2k+1）。

私钥：随机选取的k+1个辫子xi（0≤i≤k）∈RBr。

公钥：随机选取k个辫子vi（1≤i≤k）∈Bn，并公开vi（1≤i≤k）和w=x0v1x1v2…vkxk。

加密过程：

假设消息为M∈{0，1}m，加密算法所使用的散列函数为H:Bn→{0，1}m，

1） 随机选择yi（0≤i≤k）∈LBl，计算wi=yi−1vi1−iy（1≤i≤k）。

2） 密文为（w1，w2，…，wk，H（y0w）⊕M）。

解密过程：

若给定密文为（w′1，w′2，…，w′k，c），则对应的明文为H（x01w′x12w′…kw′xk）⊕c。

2、算法分析

（1） l的存在性 

从算法参数的选择可知，l必须满足n−2&gt；l&gt；（2kn+2k+2）/（2k+1）.适当地选择n和k，在n−2和（2kn+2k+2）/（2k+1）之间必然有这样的整数l存在，这是因为n−2−（2kn+2k+2）/（2k+1）=（n−1）/（2k+1） −3，当n−1&gt；5（2k+1）时， （n−1）/（2k+1） −3&gt；5−3=2.即n−2和（2kn+2k+2）/（2k+1）的差比2大，它们之间至少存在一个整数。

例如，当n=150时，k取10，l可以取从143~147的所有整数，相应地，r的取值为7~3。

（2）加解密过程的正确性

假设密文为：

则：

由于xi（0≤i≤k）∈RBr，yi（0≤i≤k）∈LBl，所以，xi和yi是可以交换的，因此，

所以，H（x0w1x1w2…wkxk）⊕H（y0wyk-1）⊕M=M，解密成功。

（3）算法的安全性 

NBPKE公钥加密算法的安全基础恰好是第3节中描述的两个辫子群上的难解问题.攻击者企图从公钥恢复私钥，也就是从vi（1≤i≤k）和w恢复xi（0≤i≤k），等价于要解决BFHP问题；而企图从密文恢复随机辫子或者明文， 也就是从wi=yi−1vi1−iy（1≤i≤k）或者H（y0w）⊕M中恢复y1−kyi（0≤i≤k）或者M，只要散列函数足够安全，就等价于要解 决多重P-BPKE问题。

从第3节的讨论可知:多重P-BPKE问题和BFHP问题可以抵抗长度攻击、共轭搜索攻击和基于Diffie-Hellman共轭问题的攻击，而且通过Burau表示来求解BFHP问题是一个NP难的问题。

在方程组（2）中，当所有方程的个数不少于变元的个数时，由于这些方程均为线性方程，可以以非零的概率通过线性方程组求解的方法求得所有变元。而当所有方程的个数少于变元的个数时，方程组（2）就没有确定的解。此时，若选择方程组（1）的任意一个特解，由于我们不能判断它是否属于Burau表示的像集，因此，Burau表示攻击将失效。这说明适当地选择参数，多重P-BPKE问题可以抵抗基于Burau表示的线性攻击。从算法2的描述中我们可以知道:由于n−2&gt；l&gt；（2kn+2k+2）/（2k+1），算法满足定理2的条件。

综上所述，NBPKE对于目前已知的这些攻击方法都具有免疫能力。

（4）算法参数选择 

BFHP问题的Burau表示中共有（k+1）r2个变元和n2+2r（k+1）个方程，为了增加BFHP问题的难度，变元的个数应该尽可能地多，这就要求k和r要尽可能地大。但是，由r+l=n和n−2&gt；l&gt；（2kn+2k+2）/（2k+1）可知：当k增大时，n必须取得足够大才能保证l的存在性；而当r增大时，l又必须相应地减小。为此，我们建议NBPKE公钥加密算法中n的取值要充分大，而l只需取比（2kn+2k+2）/（2k+1）稍大的整数即可。例如：对于以上n=150的情况，k取10，l和r的取值可分别为143和7。

（5）  随机辫子的生成 

定义6（方阵的带宽）：

一个方阵的带宽是指该方阵中与主对角线最远的非零元素的距离。

例如:任意σi（1≤i≤n−1）及其逆的Burau表示的带宽为1；任意（1≤i，j≤n−1），当|i−j|=1时，其Burau 1±iσ1±jσ表示的带宽为2；否则为0或者1。

Burau表示的带宽是Burau线性表示攻击能否成功的一个非常重要的因素，因为如果带宽很小，那么Burau表示方阵中偏离对角线较远的未知元是可以事先预知的，这就降低了线性方程组中未知元的个数，从而增加了求解唯一确定解的可能性.文献[5]正是利用了Burau表示的这一特点，简化了方程求解过程。

NBPKE中的辫子都是随机产生的，假设RNG是一个取值范围为[1−n， −1]∪[1，n−1]的随机数发生器，一个直接的生成随机辫子的方法是:当RNG取值为i（1≤i≤n−1）时，我们就选择初等辫子σi；当RNG取值为j（1−n≤j≤−1） 时，我们就选择初等辫子σ−j的逆，经过k次这样的处理，我们就可以得到一个由k个初等辫子或它们的逆的 1−−jσ乘积所形成的随机的辫子。

根据以上对于Burau表示方阵的带宽的讨论，两个初等辫子相乘，只有当|i−j|=1时，带宽才会增加，因此，我们得出了下面带宽增加较快的随机辫子生成算法。

算法3、 随机辫子生成算法

输入：正整数n≥3。

输出：由k个初等辫子或它们的逆相乘生成的随机辫子w。

1） 选择一个取值范围为[1，n−1]的随机数发生器RNG，初始化w=ε。

2） 调用RNG产生一个随机的正整数i。

3） 调用RNG产生一个随机的正整数j，令j=j mod 5。

如果i=1：j为0或者1，则跳转到步骤2）；

j为2，则w=wσi；

j为3，则w=wσi+1，i=i+1；

j为4，则w=w，i=i+1，1−+iσ：

如果i=n−1：

j为0，则w=wσi−1，i=i−1；

j为1，则w=w，i=i−1；

j为2，则w=wσ11−−iσi；j为3或4，则跳转到步骤2）。

如果1&lt；i&lt；n−1：

j为0，则w=wσi−1，i=i−1；

j为1，则w=w，i=i−1；

j为2，则w=wσ11−−iσi；

j为3，则w=wσi+1，i=i+1；

j为4，则w=w，i=i+1

4） k=k−1：如果k=0，w即为所求；否则跳转到步骤3）。

利用此算法，由于相邻元素的序号多数仅相差1，因此，其Burau表示的带宽增长更快。

值得注意的是：算法3虽然较快地增加了带宽，但是在随机性上是有所损失的，建议在生成随机辫子的过程中，对算法3的结果作进一步的混乱。

（6）效率分析 

如果用s表示辫子的最大标准长度（这里假设s为NBPKE中随机辫子的最大标准长度），用n表示辫子群的指标，而且Bn中的辫子采用Artin表示，那么，辫子群上的乘法、逆运算和随机辫子生成的复杂度均为O（sn），将辫子表示成范式的复杂度为O（s2nlogn）.在算法2中，由于要计算H（y0w），必须将y1−ky0w表示成范式，所以，加密和解密过程均涉及到一次表示成范式运算，复杂度为O（k1−ky2s2nlogn）。此外，加密过程 共用了2k+2次乘法和k次求逆运算，解密过程共用了2k次乘法，所以，除了表示成范式，其他运算的算法复杂度均为O（ksn）。

一个由s个标准因子相乘所形成的辫子可以用snlogn比特来表示.由于存储一根辫子的空间复杂度为O（snlogn），所以，算法的总体空间复杂度为O（ksnlogn）。经过简单计算可知:NBPKE的私钥大小为（k+1）srlogr；公钥大小最多为ksnlogn+（2k+1）snlogn=（3k+1）snlogn。

当n=150，s=20时，在Pentium III 866MHZ机器上，BPKE2的加密速度为163.40KB/s，解密速度为206.94KB/s；而NBPKE算法的加解密速度大致为BPKE2的1/k.因此在实用过程中，参数k的选取应兼顾安全性和效率两方面的因素，综合加以考虑。