基于超奇異同源的指定驗(yàn)證者盲簽名*

趙興波 李夢東 李 杰

北京電子科技學(xué)院，北京市 100070

引言

量子計(jì)算機(jī)的發(fā)展對密碼學(xué)產(chǎn)生了重大影響。 Shor 算法的出現(xiàn)使基于離散對數(shù)問題和大整數(shù)分解問題的經(jīng)典公鑰密碼不再安全，于是研究人員開始關(guān)注后量子密碼。 2016 年美國國家安全局(NIST)開始征集后量子密碼算法并進(jìn)行篩選，并于2020 年7 月公布了篩選算法結(jié)果。后量子密碼的主要類型包括:基于格的、基于糾錯(cuò)碼的、基于多變量的以及基于哈希的密碼，而同源密碼是一種新興的且十分有潛力的后量子密碼[1]。

同源為橢圓曲線之間保持基點(diǎn)(basepoint)的同態(tài)映射，是一種群同態(tài)。 因?yàn)橥ǔＧ€同源問題存在亞指數(shù)時(shí)間的量子算法，而超奇曲線同源問題目前只存在指數(shù)時(shí)間的量子算法，因此目前同源密碼都是超奇橢圓曲線上的方案。 超奇同源密碼與其它后量子密碼類型相比較，密鑰、密文或簽名長度短，但超奇同源密碼也存在計(jì)算時(shí)間稍長的問題。

超奇異同源密碼的最早的結(jié)構(gòu)包括Charles、Goren 和Lauter[2]的抗碰撞哈希函數(shù)、Jao 和De Feo[3]的密鑰交換協(xié)議、De Feo、Jao 和Plut[4]的公鑰加密方案和交互識(shí)別協(xié)議[5]。 在簽名方面，Jao-Soukharevt[6]提出了不可否認(rèn)簽名，而Srinath 和Chandrasekaran 通過在不可否認(rèn)簽名的基礎(chǔ)上加入盲簽名的性質(zhì)，提出了基于同源的不可否認(rèn)盲簽名方案[7]。 但在不可否認(rèn)簽名中，簽名者對驗(yàn)證者沒有控制權(quán)，因?yàn)楹灻呖梢允孪?即在交互之前)識(shí)別授權(quán)的驗(yàn)證者。為了解決不可否認(rèn)盲簽名中的弱點(diǎn)，找到一個(gè)更合適和更實(shí)用的簽名方案，Rajeev、Agnese 和Ankan 提出了基于超奇異同源的指定驗(yàn)證者盲簽名 ( Supersingular Isogeny-based Designated Verifier Blind Signature:SI-DVBS)方案[8]，指定驗(yàn)證者簽名在保護(hù)簽名者的隱私方面具有重要的作用，可用于限定軟件使用范圍、保護(hù)版權(quán)等應(yīng)用。 但該方案在脫盲階段需要額外的信息來計(jì)算對偶同源，所以該指定驗(yàn)證者盲簽名(Designated Verifier Blind Signature:DVBS) 可以在SIDH(Supersingular Isogeny Diffie-Hellman)上實(shí)現(xiàn)，但不能在CSIDH(Commutative Supersingular Isogeny Diffie-Hellman)上實(shí)現(xiàn).

通過對SI-DVBS 方案的研究，將其與Ward、Thorsten 等人提出的CSI-Fish[9]簽名方案中的思想相結(jié)合，本文提出了一個(gè)不需要額外的信息就達(dá)到脫盲目的的指定驗(yàn)證者盲簽名，使DVBS 可以在CSIDH[10]上實(shí)現(xiàn)。 由于CSIDH 問題的特點(diǎn)，所提出的改進(jìn)方案可有效提高原類似方案的實(shí)現(xiàn)效率。

1 背景知識(shí)

1.1 超奇異橢圓曲線和同源

令q＝pn，p 是一個(gè)素?cái)?shù)，橢圓曲線E/Fq是一個(gè)虧格為1 的光滑射影代數(shù)曲線(至少有一個(gè)點(diǎn))，其仿射部分滿足Weierstrass 方程:E:y2＋a1xy＋a3y＝x3＋a2x2＋a4x＋a6，ai∈Fq，另外還有一個(gè)無窮遠(yuǎn)點(diǎn)OE。

橢圓曲線之間的同源φ:E →E1為一個(gè)態(tài)射，也是群同態(tài)且φ(OE1)＝OE2。 非零同源的次數(shù)定義為態(tài)射的次數(shù)。 Tate[11]指出:有限域Fq上的兩條橢圓曲線E，E1是同源的，當(dāng)且僅當(dāng)＃E(Fq)＝＃E1(Fq) 。

對任一非零同源φ:E →E1，都存在一個(gè)唯一的非零同源:E1→E，則稱為φ 的對偶同源。 對于同源φ:E →E1，當(dāng)E ＝E1時(shí)稱為自同態(tài)。 橢圓曲線的自同態(tài)集用End(E)表示，具有點(diǎn)加法和函數(shù)復(fù)合運(yùn)算的環(huán)結(jié)構(gòu)。 End(E)中若d＝deg(φ)，則存在整數(shù)t，使得φ2-tφ＋d＝0，t稱為自同態(tài)的跡。 對于Frobenius 自同態(tài)πq，-tπq＋q＝0，t 稱為Frobenius 跡。 當(dāng)且僅當(dāng)t＝0 時(shí)，曲線是超奇異的。

1.2 CSI-Fish 方案

在CSIDH 的基礎(chǔ)上，Ward 等人提出了一個(gè)高效的簽名方案CSI-Fish[9]，其提出的識(shí)別方案的工作原理如下:設(shè)g 為超奇異橢圓曲線理想類群cl(O)＝I(O)/P(O)的一個(gè)生成元，隨機(jī)選取a∈Z N，使a ＝ga是cl(O)中的一個(gè)隨機(jī)元素。 提供者的公鑰為E1＝a* E。 然后提供者隨機(jī)選取b∈Z N使得b ＝gb，并將E2＝b*E發(fā)送給驗(yàn)證者。 驗(yàn)證者隨機(jī)選取比特c∈{0，1}，然后發(fā)送給提供者。 當(dāng)c ＝0 時(shí)，提供者回復(fù)r＝b，驗(yàn)證者檢查E2是否等于rE；當(dāng)c ＝1 時(shí)，提供者回復(fù)r＝b－amodN，驗(yàn)證者檢查E 是否等于rE1。

在CSI-Fish 還提出了基于同源的類群作用的主要困難假設(shè):

定義(類群作用逆問題):給定兩個(gè)曲線E，E1，其自同態(tài)環(huán)End(E1)＝End(E)＝O， 找到一個(gè)理想a ?O 使得E ＝a*E1。

此問題是DVBS 方案所依賴的計(jì)算困難問題。

2 SI-DVBS 方案

在 [7] 的 DHKE ( Diffie-Hellman key exchange)協(xié)議中，身份的零知識(shí)證明是由基于同源的交換方圖提供的。 [8]也采用了這種方法，并將其擴(kuò)展到了雙立方體(如圖1 所示)，使得每個(gè)面上都有一個(gè)交換方圖。 [8]基于此構(gòu)建了SI-DVBS 方案，其思路是:在三維交換圖中，涉及到的每個(gè)函數(shù)都貢獻(xiàn)了一條路徑，在這條路徑中，需要特定的信息才能向特定的方向移動(dòng)。 [8]中方案的Sign 算法只涉及下立方體，它本質(zhì)上包含盲和脫盲兩個(gè)階段。 但是只有上立方體可以被認(rèn)為是簽名，而不考慮盲性，因此，這種方法通常可以得到基于同源的指定驗(yàn)證者簽名。

圖1 [8]中的立體交換圖

SI-DVBS 方案的安全模型[8]包括三個(gè)參與者:消息請求者A，簽名者B 以及指定驗(yàn)證者V。SI-DVBS 方案包括以下算法:

1. 設(shè)置參數(shù)算法:在輸入安全參數(shù)λ 時(shí)，該算法生成系統(tǒng)的公共參數(shù)params。 在此之后的所有算法中，params 將被視為隱式輸入。

2. 密鑰生成算法:在輸入?yún)?shù)上分別生成簽名者和驗(yàn)證者的(公鑰、私鑰)對(pkS，skS)，(pkV，skV).

3. 簽名算法:在輸入簽名者的簽名密鑰skS、驗(yàn)證者的公鑰pkV和消息m 后，算法最終生成SI-DVBS 的簽名σ。 主算法由以下三個(gè)子算法組成:

(1)盲化:這是一種概率盲算法，由請求者運(yùn)行，根據(jù)輸入的消息m、隨機(jī)選擇r 和驗(yàn)證者的公鑰pkV，輸出盲消息m′。

(2)盲簽名:這是簽名者運(yùn)行的一種簽名算法，它接收盲消息m′ 和簽名者的密鑰skS。 該算法在盲消息m′上輸出簽名σ′。

(3)脫盲:這是一個(gè)確定性的脫盲算法，由請求者運(yùn)行，根據(jù)輸入的盲簽名σ′ 和隨機(jī)選擇r，輸出消息m 上的無盲簽名σ。

4. 驗(yàn)證:這是一個(gè)由指定驗(yàn)證者運(yùn)行的確定性驗(yàn)證算法。 當(dāng)輸入驗(yàn)證者的密鑰skv、簽名者的公鑰pkS、簽名σ 和消息m 時(shí)，根據(jù)該算法的輸出位b 判斷簽名是否有效，當(dāng)輸出位b ＝1時(shí)，簽名有效；輸出位b ＝0 時(shí)，則簽名無效。

5.模擬簽名:這是一個(gè)由指定驗(yàn)證者運(yùn)行的模擬簽名算法。 該算法在輸入驗(yàn)證者的密鑰skV、簽名者的公鑰pkS和消息m 后，輸出與原始簽名不可區(qū)分的相同文本。 此算法是為了使任何人都不能區(qū)分簽名是簽名者所做，還是指定驗(yàn)證者所做。

3 改進(jìn)的SI-DVBS 方案

在Ward 等人提出的CSI-Fish 的方案基礎(chǔ)上，將其簽名方案中的思想與Rajeev[8]等人提出的SI-DVBS 相結(jié)合，本文設(shè)計(jì)了一個(gè)改進(jìn)的SIDVBS 方案。 與[8]相比，本方案不需要額外的信息來計(jì)算對偶同源即可脫盲，從而達(dá)到了DVBS可以在CSIDH 中實(shí)現(xiàn)的目的。 下面介紹該方案的詳細(xì)算法:

3.1 建立參數(shù)

3.2 密鑰生成

B 和V 生成各自的公鑰和私鑰，如下所示:

B 隨機(jī)選擇b∈Z N，計(jì)算[b]＝b ＝gb以及E2＝b*E。 B 的公鑰為E2，私鑰為b。

V 隨機(jī)選擇a∈Z N，計(jì)算[a]＝a ＝ga以及E1＝a*E。 V 的公鑰為E1，私鑰為a。

3.3 盲簽名

為了獲得消息m 上的DVBS，A 首先將消息盲化并將其發(fā)送給B，B 對盲消息進(jìn)行簽名并將其發(fā)送回A。 最后，A 對從B 處接收到的簽名進(jìn)行解密，在m 上輸出簽名。 盲簽名由以下三部分組成:

1.盲化過程(如圖2 所示):設(shè)m 為要簽名的消息。 A 計(jì)算散列h＝H(m)，[h]＝k＝gh和E13＝k*E1，然后A 隨機(jī)選擇m，n∈Z N并計(jì)算u＝[m-n]＝gm-n和E134＝u*E13

掩蔽曲線E134發(fā)送給簽名者，并秘密保存m，n。

注意:[8]中的方案在進(jìn)行完以上步驟后，在此處需要計(jì)算從曲線E13到曲線E134的同源的對偶，使脫盲成為可能。 為了計(jì)算對偶同源，需要額外的信息，而本方案不需要計(jì)算對偶同源，因?yàn)閇n-m][b][m-n]E ＝[b] E，所以只需要保存好m，n，在脫盲時(shí)計(jì)算[n-m]即可。

2.盲簽名(如圖3 所示):B 用私鑰b 進(jìn)行簽名，計(jì)算曲線E1342＝b*E134。

然后將E1342給A 作為B 在盲消息E134上的簽名。

圖2 請求者計(jì)算曲線E13、E134 進(jìn)行盲化

3. 脫盲(如圖4 所示):A 接收到盲消息上的簽名，在原始消息m 上生成簽名，通過計(jì)算u′＝[n－m] ＝gn－m以及E13424′＝u′*E1342，且將簽名σ＝(m，j(E13424′)) 發(fā)送給指定驗(yàn)證者V。

盲簽名驗(yàn)證:E13424′＝u′*E1342＝[n-m][b]E134＝[n－m][b ][m－n]E13＝[b ]E13＝E123。

圖3 簽名者計(jì)算曲線E1342 進(jìn)行簽名

圖4 請求者計(jì)算曲線E13424′ 進(jìn)行脫盲

3.4 驗(yàn)證

為了驗(yàn)證消息m 上接收到的簽名σ，V 首先計(jì)算h ＝H(m)，然后通過計(jì)算k＝gh、E12＝a*E2和E123＝k*E12(如圖5 所示)。 最后，V 接受σ作為一個(gè)對m 的有效簽名，當(dāng)且僅當(dāng)j(E13424′)＝j(luò)(E123) 。

3.5 模擬簽名

為了輸出與接收到的在消息m 上的簽名σ無法區(qū)分的相同的副本，V 用與驗(yàn)證算法完全相同的方式進(jìn)行計(jì)算，模擬一個(gè)簽名σ︿，即一個(gè)與E13424′同構(gòu)的橢圓曲線。

4 正確性與安全性分析

以下對所提出的方案進(jìn)行分析。

4.1 正確性分析

E123＝kE12＝kaE2＝kabE ＝kbE1＝bE13＝[n－m][b][m－n]E13＝E13424′，因此它們對應(yīng)的j－不變量是相同的，所以指定驗(yàn)證者的簽名(m，j(E123)) 與 簽 名 者 的 簽 名σ(m，j(E13424′)) 是相同的。

圖5 驗(yàn)證者計(jì)算曲線E123 來檢查簽名是否有效

且盲性正確， 因?yàn)镋13424′＝u′*E1342＝[n-m][b]E134＝[n－m][b][m－n]E13＝[b]E13＝E123。

所以提出的SI-DVBS 方案是正確的。

4.2 安全性分析

根據(jù)SI-DVBS 方案的安全性要求，本文將從以下幾個(gè)方面論述簽名方案的安全性。

1. 不可偽造性

除了簽名者和指定驗(yàn)證者，其他人不能以簽名者的名義偽造簽名，即在不知道簽名者或指定的驗(yàn)證者的私鑰的情況下，構(gòu)造一個(gè)有效的SIDVBS 在計(jì)算上是不可行的。 由對消息m 的簽名過程可知，簽名(m，σ)可以由簽名者或指定驗(yàn)證者生成。 只有知道簽名者或指定驗(yàn)證者的私鑰b 或a 才能偽造出符合條件的簽名。 而由類群作用逆問題以及hash 函數(shù)H 的單向陷門性可知，在私鑰保密的情況下，其他人無法由曲線E及其同源曲線得到私鑰。 所以，該方案滿足不可偽造性。

2. 盲性

簽名者不應(yīng)該了解關(guān)于請求者的真正消息的任何信息。 為了實(shí)現(xiàn)對消息m 的盲化，請求者隨機(jī)選取m，n∈Z N并計(jì)算u＝[m－n]＝gm－n和E134＝u*E3，由于m，n 是隨機(jī)選取的，所以u是類群中的一個(gè)隨機(jī)元素，簽名者無法從E134知曉H(m)，從而達(dá)到了對消息m 進(jìn)行盲化的目的。

3. 不可驗(yàn)證性

為了驗(yàn)證簽名的正確性，必須根據(jù)參數(shù)的知識(shí)和提供的公鑰計(jì)算出橢圓曲線E123。 從上一節(jié)描述的方案可以看出，計(jì)算與E2同源的曲線E12需要指定驗(yàn)證者的私鑰a， 而在計(jì)算曲線E123的時(shí)候，需用到E12。 因此，很明顯，沒有指定驗(yàn)證者的私鑰的用戶無法實(shí)際驗(yàn)證簽名的有效性。 此外，在模擬簽名過程中生成了一個(gè)與簽名者所提供的簽名相同的模擬簽名，因此， 可以確定，在不知道簽名者或指定驗(yàn)證者的私鑰的情況下，從計(jì)算上驗(yàn)證所提議的SI-DVBS 的有效性是不可行的[8]。

4. 不可傳遞性

對給定的一個(gè)消息和簽名(m，σ)，任何人不能區(qū)分是簽名者的簽名還是指定驗(yàn)證者所做的簽名。 而簽名方案中的模擬簽名過程就是為了實(shí)現(xiàn)這一安全性質(zhì)。

5 總結(jié)

本文提出并實(shí)現(xiàn)了一種基于超奇異橢圓曲線同源的指定驗(yàn)證者盲簽名方案。 該方案是在Rajeev 等人提出的簽名方案的基礎(chǔ)上，與CSIFish 的思想相結(jié)合，使DVBS 可以在CSIDH 的設(shè)置下實(shí)現(xiàn)；此外，方案的脫盲階段不需要額外的信息來計(jì)算對偶同源，就可以達(dá)到脫盲的目的。