辮子群是一種新興的適用于量子計算機時代的公鑰密碼平臺，辮子群上已知的用于公鑰密碼系統(tǒng)的一些難解問題和基于這些難解問題的公鑰加密算法都受到不同程度的攻擊。辮子群上公鑰密碼系統(tǒng)的安全性不能僅僅依靠共軛問題的難解性，結(jié)合辮子群上非共軛變換和多變量方程組的特點所構(gòu)造的難解問題，通過增加變量數(shù)量來增加問題的難解程度。辮子群上新的公鑰加密算法可以抵抗已知的各種攻擊，將簡單問題復(fù)合成多變量難解問題的思路，對公鑰密碼算法的設(shè)計起到一定的啟發(fā)作用。

一、辮子群和辮子群上的難解問題?

定義1（辮子群）：

辮子群是一類特殊的Artin群，一個由n?1（n≥3，由單個初等辮子生成的辮子群是無限循環(huán)群，本文不予考慮）個初等辮子生成的辮子群Bn表示為 ：

辮子群是一類無限、非交換的無紐群。一根辮子，如果其表達(dá)式中不出現(xiàn)初等辮子的負(fù)次冪，這樣的辮子叫?做正辮子，單位元ε也屬于正辮子，所有的正辮子形成一個獨異點（monoid），記作B+n。

令?1=σ1，遞歸地定義?i=σ1σ2…σi?i?1（2≤i≤n?1），則?=?n?1稱為辮子群Bn的基本辮子。

在Bn上可以定義一種偏序關(guān)系“≤”，任何（x，y）∈Bn×Bn，x≤y當(dāng)且僅當(dāng)存在（α，β）∈B+n×B+n，使得y=αxβ。任何滿?足ε≤α≤?的辮子α稱作標(biāo)準(zhǔn)因子。

如果w，α，β∈B+n，w=αβ，則稱β是w的一個尾部。進一步地，如果α是標(biāo)準(zhǔn)因子，則稱w的這種分解是“左加權(quán)”的是指α在所有的分解中根據(jù)偏序關(guān)系“≤”，長度最長。根據(jù)這種“左加權(quán)”分解，任何辮子w可以唯一地表示成Garside范式：

其中，αi（1≤i≤s）均為不等于ε和?的標(biāo)準(zhǔn)因子，且αiαi+1是左加權(quán)的。我們將s稱作辮子w的標(biāo)準(zhǔn)長度，r=inf（w）稱作w的下確界，r+s=sup（w）稱作w的上確界。

辮子群中的任何辮子都可以在多項式時間內(nèi)有效地表示成Garside范式的形式，兩根辮子相等，是指它們有相同的Garside范式表示。

辮子群之間有一些顯而易見的關(guān)系，對于正整數(shù)m≤n，Bm是Bn的子群；如果l和r是正整數(shù)，Bl+r是由σ1，σ2，…，?σl+r?1這l+r?1個元生成的辮子群，由σ1，σ2，…，σl?1生成的群，記作LBl，由σl+1，…，σl+r?1生成的群記作RBr，則它們都是Bl+r的子群，而且滿足關(guān)系:任意（a，b）∈LBl×RBr，均有ab=ba。

定義2（共軛）：

辮子群Bn中的兩個元素x和y共軛是指存在a∈Bn，使得y=a?1xa。

辮子群上有很多數(shù)學(xué)上“難解”的問題，這些問題均可被用作構(gòu)造公鑰密碼系統(tǒng)，下面僅列舉與共軛相關(guān)的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。

就目前的研究狀況來看，這些問題都遭到不同程度的攻擊，依賴于這些“難解”問題所構(gòu)造的公鑰加密算法，其安全性是不夠的。

二、辮子群上的公鑰加密算法?

1、已有公鑰加密算法?

一個實用的辮子群上的公鑰加密算法BPKE1是由Ko和Lee等人提出來的，其安全性是基于上述的Diffie-Hellman共軛問題，該公鑰加密算法的一個更一般的版本是由Cha和Cheon等人提出來的，下面我們描述這個更一般的算法。

算法1：

辮子群上的公鑰加密算法BPKE2。

私鑰:辮子對（x1，x2）∈LBl×LBl。

公鑰:辮子對（a，b），

其中：a∈Bn；b=x1ax2。

加密過程：

假設(shè)消息為M∈{0，1}k，加密算法所使用的散列函數(shù)為H:Bn→{0，1}k， ｝

1）?隨機選擇（y1，y2）∈RBr×RBr。

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

解密過程:?

給定密文（c，d），明文為M=H（x1cx2）⊕d。

BPKE1規(guī)定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算法進行了改進，實驗結(jié)果表明：隨著n以及a和b的標(biāo)準(zhǔn)長度的增加，線性表示攻擊成功的概率會顯著減小。

Cheon和Jun利用辮子群的Lawrence-Krammer表示，可以在多項式時間內(nèi)解決Diffie-Hellman共軛問題，因而也可以用來攻擊BPKE1。

BPKE2公鑰加密算法已經(jīng)回避了利用共軛問題來構(gòu)造加密算法，因此，一些基于辮子群共軛性的攻擊方法，如Hofheinz-Steinwandt共軛搜索攻擊、SSS（super?summit?set）和USS（ultra?summit?set）集合攻擊等，是不能奏效的。

此外，由Hughes等人提出的長度攻擊，后來經(jīng)Garber等人一般化，可以用來求解辮子群上的一般性方程。這種方法是一種概率攻擊方法，成功的前提是同一變量必須提供足夠的概率累積，不能用于BPKE2。

三、新的難解問題?

本節(jié)我們提出兩種新的辮子群上的難解問題，它們均通過增加問題中變量的個數(shù)來增加難解性。

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）。

當(dāng)所有xi（0≤i≤k）相等時，多重P-BPKE問題就是MSCP（multiple?simultaneous?conjugacy?problem）問題。MSCP問題首先被應(yīng)用在AAG密鑰協(xié)商協(xié)議之中，下面我們來分析多重P-BPKE問題的安全性。

首先，由于xi（0≤i≤k）的生成元為初等辮子，而且每個xi（0≤i≤k）和它的逆僅在最多兩個等式中出現(xiàn)，所以不能提供概率累積，因而，長度攻擊不能解決多重P-BPKE問題。

此外，多重P-BPKE問題不涉及明顯的共軛變換，通過等式wi=xi?1vi1?ix（1≤i≤k）唯一能夠構(gòu)造出的非平凡的一類共軛關(guān)系為wi+1wi=?xi（vi+111?+ixxi?1vi），但是v1?ixi+111?+ixxi?1vi
未知，共軛搜索攻擊和基于Diffie-Hellman共軛問題的攻擊都不能用于求解此類問題。

設(shè)ρ為Bn上的任一線性表示，E為多重P-BPKE問題在ρ表示下的矩陣方程組，如果沒有有效的算法可以判斷某一矩陣是否為像集ρ（Bn）中的元素，那么，當(dāng)E沒有唯一確定解的時候，基于ρ表示的攻擊不能解決多重P-BPKE問題，因為我們無法從E的無數(shù)個矩陣解中判斷哪一個解才是像集ρ（Bn）中的元素，“提升”回辮子群的過程就會失效.Burau表示、著色Burau表示和Lawrence-Krammer表示都屬于此類線性表示。

我們可以看出：Burau線性表示攻擊成功的必要條件是通過矩陣方程能夠求得所求解對象的一個唯一確定的Burau表示，然后才能“提升”回辮子群。AAFG密鑰交換協(xié)議提供了足夠多的共軛辮子對，使得方程的個數(shù)超過了變元的個數(shù)，因而矩陣方程可解；由于BPKE2加密算法的特殊性，使得矩陣方程（在系數(shù)為滿秩的情況下）可以利用矩陣變換直接求解。

對于Burau線性表示，我們可以估算多重P-BPKE問題抵抗線性表示攻擊的參數(shù)取值。首先，我們證明關(guān)于Burau線性表示的一個性質(zhì)：

定理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出現(xiàn)在主對角線上第i行和i列的位置.當(dāng)i&lt；l時，σi∈LBl；而當(dāng)i&gt；n?r時，σi∈RBr.兩種情況下，ρ（σi）（t）顯然均為定理中所述的分塊對角矩陣.根據(jù)矩陣乘法的性質(zhì)，分塊對角矩陣對于矩陣乘法是封閉的，再由Burau表示的線性性質(zhì)，即可得到結(jié)論。

定理2：?如果l&gt；（2kn+2k+2）/（2k+1），則在多重P-BPKE問題的Burau線性表示中，變元的個數(shù)多于方程的個數(shù)。

證明：假設(shè)利用Burau表示形成的關(guān)于多重P-BPKE問題的k個矩陣方程為：

其中：所有矩陣均是n階方陣；Wi，Vi分別是wi和vi（1≤i≤k）的Burau表示；Xi是xi（0≤i≤k）的Burau表示。為了便于分析，我們對方程組（1）進行化簡，變形為：

由于xi∈LBl，所以，根據(jù)定理1，可以將Xi看成是具有l(wèi)2個簡單變量的未知元，這樣，方程組（2）總共有（k+1）l2個簡單變量。將方程組（2）中的所有矩陣方程分塊表示為：

也就是：

對比矩陣中的各個元素，每個矩陣方程可以得到l2+2l（n?l）個關(guān)于簡單變量的方程，k個矩陣方程總共有k（l2+2l（n?l））個方程。由資料還得知:Burau表示的每個行向量和列向量均滿足一個線性約束條件，這些約束條件的總個數(shù)為2l（k+1）。將它們加上之后，我們共可以得到k（l2+2l（n?l））+2l（k+1）個關(guān)于變元的方程。如果要求k（l2+2l（n?l））+2l（k+1）&lt；（k+1）l2，即有l(wèi)&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問題一樣，我們有下面的結(jié)論：長度攻擊、共軛搜索攻擊和基于Diffie-Hellman共軛問題的攻擊不能解決BFHP問題。

利用Burau表示，我們計算BFHP問題抵抗Burau表示攻擊的能力。

定理3：

如果（r?1）2&gt；n2/（k+1）+1，則在BFHP問題的Burau線性表示中，變元的個數(shù)多于方程的個數(shù).?證明:利用Burau表示，我們將方程w=x0v1x1v2…vkxk映射成矩陣方程.由于xi（0≤i≤k）∈RBr，其Burau表示中變元的個數(shù)為r2，所以，矩陣方程中總共有（k+1）r2個變元.矩陣方程再加上Burau表示的約束條件，方程的總個數(shù)為n2+2r（k+1）。為了使變元的個數(shù)多于方程的個數(shù)，只需（k+1）r2&gt；n2+2r（k+1），即：

實事上，如果n=l+r，定理2和定理3的條件是不可能同時滿足的。因為由（r?1）2&gt；n2/（k+1）+1和n=l+r，我們有：

結(jié)合定理2，我們可以得到 ：

但是：

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

但是，BFHP問題中的方程是Z[t，t?1]上的高次多變量方程，即使方程的個數(shù)多于變元的個數(shù)（overdefined），求解這樣的系統(tǒng)也是一個NP困難的問題。

四、新的公鑰加密算法?

1、新加密算法描述?

根據(jù)第3節(jié)所描述的兩個辮子群上的難解問題，我們提出如下新的公鑰加密算法。

算法2、辮子群上新的公鑰加密算法NBPKE。選擇正整數(shù)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。

加密過程：

假設(shè)消息為M∈{0，1}m，加密算法所使用的散列函數(shù)為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），則對應(yīng)的明文為H（x01w′x12w′…kw′xk）⊕c。

2、算法分析

（1） l的存在性?

從算法參數(shù)的選擇可知，l必須滿足n?2&gt；l&gt；（2kn+2k+2）/（2k+1）.適當(dāng)?shù)剡x擇n和k，在n?2和（2kn+2k+2）/（2k+1）之間必然有這樣的整數(shù)l存在，這是因為n?2?（2kn+2k+2）/（2k+1）=（n?1）/（2k+1）??3，當(dāng)n?1&gt；5（2k+1）時，?（n?1）/（2k+1）??3&gt；5?3=2.即n?2和（2kn+2k+2）/（2k+1）的差比2大，它們之間至少存在一個整數(shù)。

例如，當(dāng)n=150時，k取10，l可以取從143~147的所有整數(shù)，相應(yīng)地，r的取值為7~3。

（2）加解密過程的正確性

假設(shè)密文為：

則：

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

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

（3）算法的安全性?

NBPKE公鑰加密算法的安全基礎(chǔ)恰好是第3節(jié)中描述的兩個辮子群上的難解問題.攻擊者企圖從公鑰恢復(fù)私鑰，也就是從vi（1≤i≤k）和w恢復(fù)xi（0≤i≤k），等價于要解決BFHP問題；而企圖從密文恢復(fù)隨機辮子或者明文，?也就是從wi=yi?1vi1?iy（1≤i≤k）或者H（y0w）⊕M中恢復(fù)y1?kyi（0≤i≤k）或者M，只要散列函數(shù)足夠安全，就等價于要解?決多重P-BPKE問題。

從第3節(jié)的討論可知:多重P-BPKE問題和BFHP問題可以抵抗長度攻擊、共軛搜索攻擊和基于Diffie-Hellman共軛問題的攻擊，而且通過Burau表示來求解BFHP問題是一個NP難的問題。

在方程組（2）中，當(dāng)所有方程的個數(shù)不少于變元的個數(shù)時，由于這些方程均為線性方程，可以以非零的概率通過線性方程組求解的方法求得所有變元。而當(dāng)所有方程的個數(shù)少于變元的個數(shù)時，方程組（2）就沒有確定的解。此時，若選擇方程組（1）的任意一個特解，由于我們不能判斷它是否屬于Burau表示的像集，因此，Burau表示攻擊將失效。這說明適當(dāng)?shù)剡x擇參數(shù)，多重P-BPKE問題可以抵抗基于Burau表示的線性攻擊。從算法2的描述中我們可以知道:由于n?2&gt；l&gt；（2kn+2k+2）/（2k+1），算法滿足定理2的條件。

綜上所述，NBPKE對于目前已知的這些攻擊方法都具有免疫能力。

（4）算法參數(shù)選擇?

BFHP問題的Burau表示中共有（k+1）r2個變元和n2+2r（k+1）個方程，為了增加BFHP問題的難度，變元的個數(shù)應(yīng)該盡可能地多，這就要求k和r要盡可能地大。但是，由r+l=n和n?2&gt；l&gt；（2kn+2k+2）/（2k+1）可知：當(dāng)k增大時，n必須取得足夠大才能保證l的存在性；而當(dāng)r增大時，l又必須相應(yīng)地減小。為此，我們建議NBPKE公鑰加密算法中n的取值要充分大，而l只需取比（2kn+2k+2）/（2k+1）稍大的整數(shù)即可。例如：對于以上n=150的情況，k取10，l和r的取值可分別為143和7。

（5） ?隨機辮子的生成?

定義6（方陣的帶寬）：

一個方陣的帶寬是指該方陣中與主對角線最遠(yuǎn)的非零元素的距離。

例如:任意σi（1≤i≤n?1）及其逆的Burau表示的帶寬為1；任意（1≤i，j≤n?1），當(dāng)|i?j|=1時，其Burau?1±iσ1±jσ表示的帶寬為2；否則為0或者1。

Burau表示的帶寬是Burau線性表示攻擊能否成功的一個非常重要的因素，因為如果帶寬很小，那么Burau表示方陣中偏離對角線較遠(yuǎn)的未知元是可以事先預(yù)知的，這就降低了線性方程組中未知元的個數(shù)，從而增加了求解唯一確定解的可能性.文獻(xiàn)[5]正是利用了Burau表示的這一特點，簡化了方程求解過程。

NBPKE中的辮子都是隨機產(chǎn)生的，假設(shè)RNG是一個取值范圍為[1?n，??1]∪[1，n?1]的隨機數(shù)發(fā)生器，一個直接的生成隨機辮子的方法是:當(dāng)RNG取值為i（1≤i≤n?1）時，我們就選擇初等辮子σi；當(dāng)RNG取值為j（1?n≤j≤?1）?時，我們就選擇初等辮子σ?j的逆，經(jīng)過k次這樣的處理，我們就可以得到一個由k個初等辮子或它們的逆的?1??jσ乘積所形成的隨機的辮子。

根據(jù)以上對于Burau表示方陣的帶寬的討論，兩個初等辮子相乘，只有當(dāng)|i?j|=1時，帶寬才會增加，因此，我們得出了下面帶寬增加較快的隨機辮子生成算法。

算法3、?隨機辮子生成算法

輸入：正整數(shù)n≥3。

輸出：由k個初等辮子或它們的逆相乘生成的隨機辮子w。

1）?選擇一個取值范圍為[1，n?1]的隨機數(shù)發(fā)生器RNG，初始化w=ε。

2）?調(diào)用RNG產(chǎn)生一個隨機的正整數(shù)i。

3）?調(diào)用RNG產(chǎn)生一個隨機的正整數(shù)j，令j=j?mod?5。

如果i=1：j為0或者1，則跳轉(zhuǎn)到步驟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，則跳轉(zhuǎn)到步驟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即為所求；否則跳轉(zhuǎn)到步驟3）。

利用此算法，由于相鄰元素的序號多數(shù)僅相差1，因此，其Burau表示的帶寬增長更快。

值得注意的是：算法3雖然較快地增加了帶寬，但是在隨機性上是有所損失的，建議在生成隨機辮子的過程中，對算法3的結(jié)果作進一步的混亂。

（6）效率分析?

如果用s表示辮子的最大標(biāo)準(zhǔn)長度（這里假設(shè)s為NBPKE中隨機辮子的最大標(biāo)準(zhǔn)長度），用n表示辮子群的指標(biāo)，而且Bn中的辮子采用Artin表示，那么，辮子群上的乘法、逆運算和隨機辮子生成的復(fù)雜度均為O（sn），將辮子表示成范式的復(fù)雜度為O（s2nlogn）.在算法2中，由于要計算H（y0w），必須將y1?ky0w表示成范式，所以，加密和解密過程均涉及到一次表示成范式運算，復(fù)雜度為O（k1?ky2s2nlogn）。此外，加密過程?共用了2k+2次乘法和k次求逆運算，解密過程共用了2k次乘法，所以，除了表示成范式，其他運算的算法復(fù)雜度均為O（ksn）。

一個由s個標(biāo)準(zhǔn)因子相乘所形成的辮子可以用snlogn比特來表示.由于存儲一根辮子的空間復(fù)雜度為O（snlogn），所以，算法的總體空間復(fù)雜度為O（ksnlogn）。經(jīng)過簡單計算可知:NBPKE的私鑰大小為（k+1）srlogr；公鑰大小最多為ksnlogn+（2k+1）snlogn=（3k+1）snlogn。

當(dāng)n=150，s=20時，在Pentium?III?866MHZ機器上，BPKE2的加密速度為163.40KB/s，解密速度為206.94KB/s；而NBPKE算法的加解密速度大致為BPKE2的1/k.因此在實用過程中，參數(shù)k的選取應(yīng)兼顧安全性和效率兩方面的因素，綜合加以考慮。

admin

收藏 海報分享