計算合數(shù)階群中低重量離散對數(shù)的低存儲算法*

朱玉清, 劉吉強(qiáng)

1. 北京交通大學(xué) 智能交通數(shù)據(jù)安全與隱私保護(hù)技術(shù)北京市重點(diǎn)實(shí)驗室, 北京 100044 2. 北京交通大學(xué) 計算機(jī)與信息技術(shù)學(xué)院, 北京 100044

1 引言

設(shè)G=〈g〉是有限循環(huán)群,h ∈G, 離散對數(shù)問題(discrete logarithm problem, DLP) 是計算使得h=gx成立的最小正整數(shù)x. 當(dāng)G是有限域的乘法群或橢圓曲線點(diǎn)群時, 離散對數(shù)問題通常是困難的. 基于離散對數(shù)問題的難解性, 研究學(xué)者設(shè)計了許多公鑰密碼方案, 如Diffie-Hellman 密鑰交換協(xié)議[1]、ElGamal 加密方案[2]、Schnorr 簽名算法[3]、數(shù)字簽名標(biāo)準(zhǔn)(DSS)、國密SM2 和SM9 算法以及基于pairing 的相關(guān)密碼方案.

本文的余下章節(jié)安排如下: 在第2 節(jié), 回顧計算低Hamming 重量離散對數(shù)的相關(guān)算法. 在第3 節(jié), 給出計算低Hamming 重量離散對數(shù)的低存儲算法. 在第4 節(jié), 對算法的復(fù)雜度進(jìn)行分析, 并給出并行實(shí)施的方法. 在第5 節(jié), 對本文進(jìn)行總結(jié).

2 相關(guān)工作

本節(jié)我們首先回顧計算低Hamming 重量離散對數(shù)的相關(guān)算法, 更多細(xì)節(jié)可以參考文獻(xiàn)[8,10]. 接著我們介紹針對合數(shù)階群的May-Ozerov 算法[11].

圖1 May-Ozerov 算法碰撞搜索策略Figure 1 Collision search in May-Ozerov algorithm

在2020 年歐密會上, Esser 和May[12]提出首個低Hamming 重量的低存儲碰撞搜索算法, 通過構(gòu)造低Hamming 重量集上的偽隨機(jī)函數(shù), 使用ρ方法進(jìn)行碰撞搜索, 以達(dá)到降低存儲的目的. 本文將該技術(shù)用在合數(shù)階群中, 以改進(jìn)May-Ozerov 算法.

3 合數(shù)階群中低Hamming 重量離散對數(shù)問題的低存儲算法

本節(jié)我們給出合數(shù)階群中低Hamming 重量離散對數(shù)問題的低存儲算法. 我們將目標(biāo)元素的離散對數(shù)分成兩段, 記前n ?t比特為v, 后t比特為w, 則x=v2t+w. 我們希望根據(jù)圖2 搜索x1,x2使得x=x1+x2. 設(shè)xi的前n ?t比特為vi, 后t比特為wi,i=0,1.

圖2 本文的碰撞搜索策略Figure 2 Collision search in this paper

與May-Ozerov 算法類似, 我們首先利用Polig-Hellman 計算群G1中的離散對數(shù)x′, 則w= [x′?v2t]M, 其中|G1|=M, [·]M表示取模M的最小非負(fù)代表元. 也就是說我們已知x的前n ?t比特v便可利用x′計算出后t比特w.

接著我們借鑒低存儲的Esser-May 算法計算x的前n ?t比特. 我們使用文獻(xiàn)[11] 中同樣的啟發(fā)性假設(shè):x的前n ?t比特重量接近δ(n ?t). 因此我們需要搜索v1,v2使得他們的和的重量接近δ(n ?t).由于w=[x′?v2t]M, 我們隨機(jī)地選取群中形如gv12t+[?v12t]M和hg?v22t?[x′?v22t]M的兩類元素, 如果兩類元素發(fā)生碰撞, 則我們可以得到x的離散對數(shù).

為此, 我們需要定義v1,v2的搜索集合V以及其上的偽隨機(jī)函數(shù)F. 我們定義集合V為Hamming

由此我們便可構(gòu)造V到V自身的映射F(v)=π ?fs(v)(v).

有了V上的偽隨機(jī)函數(shù), 我們可以使用ρ方法計算x. 由于x的前n ?t比特v分裂成v1+v2時,[?v12t]M+[x′?v22t]M與w=[x′?v2t]M相等或相差M, 因此我們用ρ方法搜索使得f0(v1)=f1(v2)或f0(v1)=f1(v2)gM成立的(v1,v2) 對, 從而恢復(fù)出x.

注意到π是G到V的Hash 函數(shù), 因此π(f0(v1)) =π(f1(v2)) 未必能推出gx12t+[?x12t]M=hg?x22t?[x′?x22t]M. 所以, 我們需要重復(fù)多次ρ方法直到找到有效的(v1,v2) 對.

算法流程如下:

算法1 合數(shù)階群的低重量離散對數(shù)算法Input: (G,|G1|,|G2|,g,h,δ,V,f0,f1,s,π)Output: x, 滿足gx = h 1: n ←「log2(|G1|·|G2|)■2: t ←■log2(|G1|)■3: M ←|G1|4: x′ ←PH(|G1|,g|G2|,h|G2|) ?調(diào)用Pohig-Hellman 算法計算x′5: repeat 6: 隨機(jī)選取起始元素α ∈V 7: (v1,v2) ←Rho(α,f0,f1,s,π) ?滿足π(f0(v1)) = π(f1(v2)) 或π(f0(v1)) = π(f1(v2)gM)8: x ←(v1 +v2)2t +[x′ ?v12t ?v22t]M 9: until gx = h 10: return x

算法在第4 步調(diào)用Pohig-Hellman 算法計算x模M的值x′. 算法在第5 步至第9 步使用基于ρ方法的碰撞搜索算法計算x的前n ?t比特. 在第7 步, 我們僅要求輸出的候選(v1,v2) 滿足π(f0(v1))=π(f1(v2))或π(f0(v1))=π(f1(v2)gM). 這是因為若x的前n?t比特v能表示成v1+v2,則x=(v1+v2)2t+[x′?v12t?v22t]M,而此時f0(v1)?f1(v2)=[?v12t]M+[x′?v22t]M ?[x′?v12t?v22t]M,其值可能為0 也可能等于M. 為了避免丟失后一種情形, 因此在碰撞搜索時放松了判斷條件.

4 復(fù)雜度分析與相關(guān)改進(jìn)

本節(jié)我們給出算法的復(fù)雜度分析和相關(guān)參數(shù)的選取, 接著將算法與已有算法進(jìn)行比較, 并給出算法的并行版本.

4.1 復(fù)雜度估計

4.2 與已有算法的比較和算法的并行改進(jìn)

我們將說明利用文獻(xiàn)[13] Section 4.2 的并行搜索技巧, 通過適當(dāng)犧牲空間復(fù)雜度, 可以降低本算法的時間復(fù)雜度. 該方法的流程與算法1 基本一致, 僅在第7 步有所不同, 即如何利用ρ方法搜索合適的(v1,v2). 該方法的具體描述如下:

首先, 將群G中部分元素劃分為特殊元素, 并給出判定一個元素是否是特殊元素的高效算法, 我們稱這些元素為“特殊點(diǎn)(distinguished point)”. 這可以通過引入一個具有較好統(tǒng)計性質(zhì)的Hash 函數(shù)得到.例如我們可以定義前k比特為0 的元素為特殊點(diǎn).

接著, 調(diào)用偽隨機(jī)函數(shù)F進(jìn)行碰撞搜索. 我們隨機(jī)選取搜索空間中的一個元素a0, 使用函數(shù)F進(jìn)行迭代, 得到一個偽隨機(jī)序列{a0,a1,···}, 其中ai=F(ai?1). 當(dāng)函數(shù)迭代到某個特殊點(diǎn)時, 停止迭代并記錄該序列的起始點(diǎn)、終點(diǎn)和迭代次數(shù)對應(yīng)的三元組(a0,ad,d), 接著重新選取一個隨機(jī)的起始點(diǎn)進(jìn)行新的一輪迭代. 與ρ方法不同, 此時我們得到的元素序列不會形成一個完整的ρ形.

當(dāng)存在同一個終點(diǎn)被記錄兩次時, 我們便得到了一個碰撞. 若這兩個三元組不能給出有效的(v1,v2),刪除前一個三元組, 僅存儲最新的三元組. 算法重復(fù)執(zhí)行上述操作直至得到有效的(v1,v2), 從而恢復(fù)出正確的離散對數(shù)x.

利用上述并行搜索技巧, 我們得到定理1.

4.3 G1 和G2 的選取

時, 算法的總復(fù)雜度最低. 特別地, 對于e ≥1 的特殊情形, 此時最優(yōu)的選擇是令G1=G, 即對G直接使用Pohlig-Hellman 算法復(fù)雜度最低.

證明:事實(shí)上, 該定理的證明與文獻(xiàn)[11] Theorem 2 類似, 這里我們簡述證明. 可以看出

是(0,1] 區(qū)間的一個劃分, 因此滿足條件的l最多一個. 設(shè)l使得上述不等式成立. 我們只需證明當(dāng)取l′?=l時, 復(fù)雜度不會降低.

當(dāng)l′

當(dāng)l′>l時, 只需證明τl和(τl+1+···+τk)e均不大于τl′. 前者自然成立. 對于后者, (τl+1+···+τk)e ≤τl+1≤τl′. 因此, 取l′>l不會降低復(fù)雜度.

5 小結(jié)