基于超奇異同源的零知識證明及群簽名方案

收稿日期：2021-12-19；修回日期：2022-02-01" 基金項目：教育部信息安全一流專業建設點項目

作者簡介：趙興波（1996-），男，遼寧凌源人，碩士研究生，主要研究方向為密碼學；李夢東（1964-），男（通信作者），山東利津人，教授，主要研究方向為密碼算法及其應用（lmd@best.edu.cn）；王穎（1998-），女，北京懷柔人，碩士研究生，主要研究方向為密碼學；朱屹霖（1998-），女，河南新鄉人，碩士研究生，主要研究方向為密碼學．

摘 要：Bullens等人在CSI-Fish中留下了一個開放問題，即設計一個識別協議，允許系統挑戰空間是Euclid Math TwoZApN，而不是小集合{-S，…，S}。提出了一個基于超奇異同源的零知識證明方案。該方案將挑戰C作為一個同源，從而解決了這一問題，并實現了更小的穩固性誤差以及公鑰長度。該方案也可以通過Fiat-Shamir變換為非交互零知識證明，進而可以在量子隨機預言下實現基于超奇異同源的簽名方案以及群簽名方案，最后分析了方案的安全性以及正確性。

關鍵詞：零知識證明；超奇異；同源；群簽名

中圖分類號：TP393.04"" 文獻標志碼：A

文章編號：1001-3695（2022）09-041-2826-06

doi：10.19734/j.issn.1001-3695.2021.12.0705

Zero-knowledge proof and group signatures based on supersingular isogeny

Zhao Xingbo，Li Mengdong，Wang Ying，Zhu Yilin

（Dept. of Cryptology Science amp; Technology，Beijing Electronic Science amp; Technology Institute，Beijing 100070，China）

Abstract：Bullens et al.left an open problems in CSI-Fish was to devise an identification protocol that allowed for the challenge set to beEuclid Math TwoZApN rather than the small set {-S，…，S}.This paper proposed a zero-knowledge proof scheme based on super-singular isogeny.This scheme addressed the open problem by taking the challenge C as an isogeny，and reduced the soundness error and the size of public key.This scheme could be turned into non-interactive zero-knowledge proof scheme using the Fiat-Shamir transform.Then signature scheme and group signature scheme based on supersingular isogeny could be implemented under the quantum random oracles model.And this paper analyzed the security and correctness of these schemes.

Key words：zero-knowledge proof；supersingular；isogeny；group signature

0 引言

同源密碼是后量子密碼學一個很有發展前景和研究價值的候選者。同源是兩條橢圓曲線之間保持基點的同態映射，是一種群同態［1］。早期，基于同源的密碼系統主要研究通常曲線［2，3］，但因為通常曲線同源問題存在亞指數時間的量子算法，而Biasse等人［4］研究發現超奇異同源問題的量子算法為指數時間，所以目前同源密碼大多是超奇異橢圓曲線上的方案。

目前構造同源簽名的基礎主要是計算超奇異同源（CSSI）問題［5］和類群作用逆問題（GAIP）［6］，且基于同源的簽名大多是結合Fiat-Shamir變換來構造的［7，8］。在文獻［9，10］中提出的基于CSSI的簽名方案，即使在最優化的變體［10］中也產生至少12 KB大小的簽名。另一方面，依靠GAIP并采用Fiat-Shamir with aborts方法，De Feo等人［11］提出了一個新的簽名方案，稱為SeaSign。SeaSign提供的簽名非常小，在128 bit安全級別下小于1 KB。最近，Beullens等人［12］通過計算理想類群，改進了SeaSign并獲得了第一個實用的基于同源的簽名方案，命名為CSI-FiSh。它允許從理想類群中進行均勻抽樣，并對其元素進行規范表示。CSI-FiSh只需要390 ms來簽名或驗證消息，簽名大小只有263 Byte。因此，基于CSI-FiSh同源特征的簽名是非常實用的。

通過對CSI-FiSh方案以及其他基于超奇異同源簽名方案的研究與分析，本文提出了一種基于超奇異同源的零知識證明系統。該系統改進了CSI-Fish中的證明系統，解決了CSI-Fish中提出的開放問題，即將系統的挑戰空間由小集合{-S+1，S-1}提升為CSIDH-512中理想類群的階數N。本文方案與CSI-FiSh方案相比，具有更小的穩固性誤差以及公鑰長度，本文僅需一個橢圓曲線作為公鑰。基于該證明系統，本文構造了基于超奇異橢圓曲線同源的簽名方案以及群簽名方案，并對簽名方案進行了安全性證明。

1 背景知識

1.1 超奇異橢圓曲線及同源

橢圓曲線之間的同源φ：E→E1為一個態射，也是群同態，且φ（Euclid Math OneOApE）=Euclid Math OneOApE1。Tate指出［13］：有限域Euclid Math TwoFApp上的兩條橢圓曲線E、E1是同源的，當且僅當#E（Euclid Math TwoFApq）=#E1（Euclid Math TwoFApq）。

對于同源φ：E→E1，當E=E1時稱為自同態。橢圓曲線的自同態集用End（E）表示，具有點加法和函數復合運算的環結構［14］。在Endp（E）中，E的Frobenius自同態π滿足特征方程：π2-tπ+q=0，t稱為Frobenius跡。當且僅當t=0時，曲線E是超奇異的。Fp-有理自同態環Endp（E）是虛二次域K=Euclid Math TwoQAp（-p）的序Euclid Math OneOAp。Endp（E）中總是包含Z［πq］這個子環。

設ελλ（Euclid Math OneOAp，π）表示在Euclid Math TwoFApp上定義的所有超奇異橢圓曲線E的集合，設Euclid Math OneOAp是虛二次域的序，π∈Euclid Math OneOAp使得ελλ（O，π）非空。理想類群cl（Euclid Math OneOAp）自由地和傳遞地作用于集合ελλ（Euclid Math OneOAp，π），在Euclid Math OneOAp和Endp（E）之間存在一個Frobenius映射使得φ（Euclid Math OneOApE）=Euclid Math OneOApE且（x，y）→（xp，yp），用*表示這一作用［15］。最近，該作用*被用來設計幾種密碼源語——CSIDH及其延伸簽名方案SeaSign、CSI-Fish等。這幾種方案的安全性都是基于類群作用逆問題，定義如下：

問題1類群作用逆問題（group action inverse problem，GAIP）給定兩個曲線E0、E1，其自同態環End（E0）=End（E1） =Euclid Math OneOAp，找到一個理想αEuclid Math OneOAp使得E1=α*E。

1.2 CSI-Fish

Beullens等人提出了一種基于CSIDH-512困難性的有效簽名方案。對于在CSIDH中為CSIDH-512參數集選擇的素數集l1…l74，Beullens等人確定了自同態環的相關類群是循環的，由g生成，且階數N=cl（Euclid Math OneOAp）由下式給出

N=3×37×140718×51593604295295

867744293584889×31599414504681

99585300827874558732204909

對于任何理想α∈cl（Euclid Math OneOAp），可以寫做α=ga，其中a∈Euclid Math TwoZApN，因為群是循環的。只要使用CSIDH-512參數集，任何人都可以對類群元素進行均勻采樣，并擁有唯一的表示。對于與E0同源的橢圓曲線E′，簡化符號α*E0=［a］E0，有了這個符號，就有了［a］（［b］E0）=［a+b］E0［12］。

1.3 零知識證明

零知識證明（zero-knowledge proof，ZKP）是證明者和驗證者之間的雙方協議，證明者通過和驗證者交互，向驗證者證明他知道一些秘密信息，而除了聲明本身已經揭示的之外，不透露任何關于秘密的信息。

對于一個語言L{0，1}*，其中的串x都伴隨著一個二元關系R{0，1}*×{0，1}*，存在w使得（x，w）∈R，w稱為x∈L的證據（witness）。參考文獻［16］，下面對零知識證明進行定義。

定義1 設（P，V）是一個雙方協議，其中V是概率多項式時間（probabilistic polynomial time，PPT）算法，設L，L′{0，1}*是具有二元關系R、R′的語言，使得RR′當且僅當它滿足下列條件，那么（P，V）稱為L，L′是具有完全性誤差α、挑戰集C、公共輸入x和秘密輸入w的Σ協議。

三輪形式（three-move form）：證明者P在輸入（x，w）時，計算承諾t并將其發送給驗證者V。驗證者V在輸入x時，選擇一個挑戰c←C并將其發送給P。證明者向驗證者發送一個響應r。根據協議文本（t，c，r），驗證者最終接受或拒絕證明。

證明系統需要具有以下三個性質：

a）完全性（completeness）。對于一個誠實的證明者P和驗證者V，當任一（x，w）∈R，則驗證者接受的概率至少為1-α。

b）特殊穩固性（special soundness）。存在一種PPT算法K（知識提取器），其將滿足c≠c′的兩個接受文本（t，c，r），（t，c′，r′）作為輸入，并輸出w′，使得（x，w′）∈R′。穩固性誤差δ=1/C。

誠實驗證者零知識（honest-verifier zero knowledge，HVZK）。存在以x∈L和c∈C為輸入的PPT模擬器，該算法輸出（t，r），使得三元組（t，c，r）與由真實協議運行生成的協議文本不可區分［16］。

一個3輪—特殊穩固的—誠實驗證者零知識證明協議，可以應用Fiat-Shamir轉換，將其轉換為非交互式零知識證明協議。

定義2 一個規范的認證方案ID=（K，P，V，c），其中K是概率多項式時間的密鑰生成算法，在輸入安全參數λ時輸出一對（pk，sk）；P也是PPT算法，輸入sk輸出一條消息m；c≥1是挑戰的整數位長度；V是一種確定性多項式時間驗證算法，將pk和證明文本作為輸入，輸出0或1［17］。

1.4 簽名

一個簽名方案S=（KeyGen，Sign，Verify）由如下三個算法組成：

a）KeyGen（1λ）。密鑰生成算法輸入安全參數λ，輸出一對公/私鑰對（pk，sk）。

b）Sign（sk，m）。簽名算法輸入私鑰sk和消息m，輸出一個簽名σ。

c）Verify（pk，m，s）。驗證算法輸入公鑰pk、消息m和簽名σ，輸出1 bit，1 代表σ是消息m的一個合法簽名，0代表不合法。

定義3 選擇消息攻擊下的不可偽造性：EUF-CMA安全。如果對于所有PPT敵手A，有AdvEUF-CMAA，S（1λ）=Pr［A win］=negl（1λ），則一個簽名方案S是EUF-CMA安全的［18］。

定理1［10］ 設R與生成算法K是困難關系，令（P，V）是Σ協議中R的證明者和驗證者，對于某些整數c≥1具有c bit挑戰。假設Σ協議是完整的，特殊穩固的以及誠實驗證者零知識的。那么（K，P，V，c）是一個規范的識別方案，在被動攻擊下是安全的。

定理2［10］ 令ID是一個規范的認證方案，在被動攻擊下是安全的。設S為使用Fiat-Shamir變換從ID中導出的簽名方案。在隨機預言模型下，S在選擇消息攻擊下是不可偽造的。

1.5 群簽名

下面介紹群簽名的定義以及安全模型。

定義4 群簽名。群簽名方案由下面的五個多項式時間算法組成：

a）GSetup：輸入安全參數，生成系統公共參數和群公、私鑰對（GMpk，GMsk）。

b）GJion：成員加入是由用戶和群管理員執行的交互式算法，若算法成功，則用戶成為有效的群成員，并得到公、私鑰對（Upk，Usk）。

c）GSign：對于給定的消息m，其簽名由管理員和群成員共同合作完成。

d）GVerify：驗證者根據群公鑰和消息m對簽名進行驗證。

e）GTrace：通過該算法，管理員GM可以找出對消息m真正的簽名者。

群簽名的安全性定義需滿足以下性質：

a）正確性。對于給定的消息m，只有經合法的群成員運行簽名算法產生的群簽名才能夠被正確驗證。

b）不可偽造性。只有合法的群成員通過和管理員交互才能夠產生被驗證正確的群簽名。

c）匿名性。只有群管理員能夠確定簽名者的身份，其他人只能驗證群簽名是否正確。

d）可跟蹤性。當出現矛盾爭端的時候，管理員可以通過追蹤算法打開群簽名，識別出具體的簽名者身份，并給出證據。

e）抗合謀性。即使多個群成員合謀在一起，也不能產生有效的被管理員追蹤不到的群簽名。

2 新的零知識證明以及簽名方案

2.1 零知識證明的身份認證協議

對于CSIDH-512參數集，CSI-FiSh指出其理想類群是循環的，具有已知階數N和生成元g。只要使用CSIDH-512參數集，任何人都可以對類群元素進行均勻采樣，并擁有唯一的表示。在此基礎上，本文描述了新的基于超奇異同源問題的身份認證協議（圖1），與CSI-Fish中的身份認證協議相比，本文的認證協議實現了更小的穩固性誤差（soundness error），且具有更小的公鑰長度。

零知識證明協議的設置如下：

a）參數設置。選取大素數p=4·l1…ln-1，其中 li是小的不同的奇素數，給定集合ελλ（Euclid Math OneOAp，π）和理想類群以及在Euclid Math TwoFApp上具有自同態環的超奇異橢圓曲線E0。為了證明秘密a的知識，證明者與驗證者進行如下Σ協議操作，如圖2所示。

b）密鑰生成。選取一個隨機的同源［a］：E0→E1，得到一個隨機橢圓曲線E1。公鑰為E1，密鑰為a。

識別協議如下：

a）承諾： 證明者隨機選取b∈REuclid Math TwoZApN ，且b≠a，將E=［b］E0發送給驗證者。

b）挑戰：驗證者檢驗E是否等于E1，若相等，則拒絕；否則隨機選取挑戰c∈Euclid Math TwoZApN，然后發送給證明者。

c）響應：證明者發送r=c+b-a mod N給驗證者。

d）驗證：驗證者檢查是否［r］E1=［c］E=E2，相等則接受；否則拒絕。

2.2 安全性分析

定理3 基于同源的識別協議是一個完整和安全的Σ協議，它具有完全性、特殊穩固性以及誠實驗證者零知識。

證明 完全性。假設證明者的行為總是誠實的，即其知道一個秘密E1=［a］E0。驗證者檢查［r］E1=［c］E=E2是否成立，因為［r］E1=［c］［b］［a］E1=［c］［b］［a］［-a］E0=［c］［b］E0=［c］E，這證明了驗證者總是接受誠實生成的證明。

特殊穩固性。給定兩個具有不同挑戰的有效證明，即π=（E，c，r）和π′=（E，c′，r′），其中c≠c′，那么r≠r′。本文有［r］E1=［c］E以及［r′］E1=［c′］E，因此可以提取（c-c′）+（r-r′），其為GAIP問題的一個解。與此同時，作弊證明者不能通過驗證，除非他成功猜測挑戰c。特別是，由于挑戰空間現在是Euclid Math TwoZApN，其中包含N個元素，所以該協議實現了1/N的穩固性誤差。

誠實驗證者零知識。為了模擬證明，從Euclid Math TwoZApN中隨機抽取樣本c，模擬器從Euclid Math TwoZApN中隨機抽取r。計算E2=［r］E1并輸出證明π=（E，c，r）。根據決策GAIP問題，模擬器生成的證明與誠實執行的挑戰等于c的協議證明是無法區分的，因為真實證明和模擬證明都具有r以及E2=［r］E1的均勻隨機分布值作為響應，所以該認證協議是誠實驗證者零知識的。

2.3 簽名方案

在算法1～3中描述了基于同源的簽名方案，該方案的安全性基于GAIP困難假設。它是通過對2.1節中介紹的零知識證明協議應用Fiat-Shamir變換得到的。其主要思想是用臨時密鑰E以及消息m的哈希值來替換挑戰c，即c=H（E‖m）。簽名σ由r、E組成，驗證者計算c′=H（E‖m），并檢查是否［r］E1=［c′］E。為了減少了簽名的大小，下面詳細描述了基于超奇異同源的簽名方案，具體如下。

算法1 KeyGen

輸入：初始曲線E0以及理想類群的階數N。

輸出：公、私鑰對（sk，pk）。

a←REuclid Math TwoZApN

E1=［a］E0

pk=E1

return（sk=a，pk=E1）

算法2 Sign

輸入：消息m以及私鑰sk。

輸出：簽名σ=（r，E）。

b←REuclid Math TwoZApN，b≠a

E=［b］E0

c=H（E‖m）

r=c+b-a mod N

return σ=（r，E）

算法3 Verify

輸入：消息m，E0，公鑰pk以及簽名σ。

輸出：Valid或Invalid。

（r，E）←σ

c′=H（E‖m）

if ［r］E1=［c′］E then

return Valid

else

return Invalid

2.4 安全性分析

定理4 在隨機預言模型中，上述基于超奇異同源的簽名方案具有選擇消息攻擊下的不可偽造性，即EUF-CMA安全。

證明 如2.4節所示，該身份認證方案（Σ協議）具有特殊穩固性和誠實驗證者零知識。因此，定理1意味該認證方案是安全的，可以抵御假冒被動攻擊。由定理2可知，該簽名方案在隨機預言模型中是EUF-CMA安全的。

2.5 對比分析

CSI-Fish中描述的基礎身份認證協議如下：證明者為了證明其知道一個群元素α使得E1=［a］E0，然后證明者隨機選取b∈Euclid Math TwoZApN，并將E=［b］E0發送給驗證者。驗證者隨機選取比特c∈{0，1}，然后發送給證明者。當c=0時，證明者回復r=b，驗證者檢查是否E=［r］E0；當c=1時，證明者回復r=b-a mod N，驗證者檢查E是否等于［r］E1。該協議的挑戰空間僅為二進制比特c∈{0，1}，公鑰長度為1個曲線。

為了降低穩固性誤差，CSI-Fish增加了挑戰空間，但這也增加了公鑰的大小。其方法為選擇一個正整數S，密鑰是S-1維的向量，如（a1，…，aS-1），公鑰為（E0，［a1］E0，…，［aS-1］E0）。證明者現在必須證明他知道一個秘密s∈Euclid Math TwoZApN，使得Ej=［s］Ei出現在公鑰列表中的某對橢圓曲線上。證明者再次隨機選擇b∈Euclid Math TwoZApN，并通過E=［b］E0來對他進行承諾。驗證者從集合{-S+1，S-1}中均勻地采樣挑戰c，證明者用r=b-ac mod N來響應。驗證檢查E=［r］Ec，當c為負值時，有E-c=Etc。CSI-FiSh的這種適應方案實現了1/2S-1的安全穩固性，公鑰長度為S-1個曲線。

在CSI-FiSh的基礎上，證明者可以簡單地模仿基于離散對數的構造，因為現在可以在環Euclid Math TwoZApN中工作，所以可以創建特有的響應來表達臨時密鑰、秘密密鑰和挑戰的組合。然而，主要的問題是驗證者如何驗證這個組合是正確的，因為當考慮曲線ga*E時，群作用只允許在g的指數上增加一個已知的常數。也就是，若在經典DH中進行系數乘（r=b+ac）的形式，則群作用就成為了映射ga→（ga）c，但在環Euclid Math TwoZApN的環境下是不存在這種類似映射的［18］。

本文方案將挑戰c視做一個同源，這樣做的好處是可以將臨時密鑰b和挑戰c結合到一起，變為［b+c］的形式，避免出現ga→（ga）c的情況。且這樣做使得挑戰c可以在環Euclid Math TwoZApN中隨機選取，也就使得挑戰空間變為類群階數N，從而實現了1/N的安全穩固性。但是采用這種方案的缺點是需要多計算一次同源，即E2=［c］E，這增加了計算時間、提高了額外計算量。本文方案公鑰長度為1個橢圓曲線。表1、2分別給出了本文方案與CSI-Fish中的識別協議與簽名方案的比較結果。

3 基于新ZK的群簽名方案

在群簽名中，為了代表群簽名，群成員需要生成一個NIZK來證明他有一個有效的密鑰/公鑰對。簽名包括密文和證明（消息嵌入在證明中）。為了驗證簽名，驗證者只是檢查證明的有效性。下面給出了本文群簽名方案的詳細描述。它與文獻［19］ 一樣借助狀態列表的方法實現群簽名，文獻［19］中采用雙線性映射來實現成員的身份認證，但本文采用上述提出的同源ZK來實現。用同源來實現群簽名方案的優點是密鑰短、抗量子攻擊等，但缺點是計算量更大、計算時間較長。

本文群簽名方案存在公鑰狀態列表LPK、群管理員GM、群成員Ui以及可信時間戳機構四類實體。其中，公鑰狀態列表中顯示當前群成員的身份信息IDi、公鑰Ei、授權簽名起始時間timestart和終止時間timeend；管理員GM負責群成員的加入、群簽名的追蹤以及實時更新維護，并向所有群成員廣播最新的LPK；可信時間戳機構負責向群管理員及群成員提供時間戳服務；群成員Ui負責完成群簽名。

3.1 基于超奇異同源的群簽名方案

本文方案包含系統建立、成員加入、簽名、驗證和追蹤五個步驟。

a）系統建立。選取大素數p=4·l1…ln-1，其中 li是小的不同的奇素數，給定集合ελλ（Euclid Math OneOAp，π）和理想類群以及在Euclid Math TwoFApp上具有自同態環的超奇異橢圓曲線E0，H1：{0，1}*→Euclid Math TwoZApN，H2：{0，1}*→Euclid Math TwoZApN。對于GM：取x←REuclid Math TwoZApN，計算EGM=［x］E0，其中x為群管理員私鑰，EGM為公鑰。故群公共參數為{p，N，E0，H1，H2}，群公鑰為EGM。

b）成員加入。成員Ui想要加入，先隨機選取xi，ai←REuclid Math TwoZApN，計算Ei=［xi］E0，hi=ai+ H1（IDi） mod N，EIDi=［ai］E0，最后將（IDi，EIDi，Ei，hi）發送給GM。其中IDi代表成員Ui的現實身份信息。

收到（IDi，EIDi，Ei，hi）后，GM先驗證等式［H1（IDi）］EIDi=［hi］E0是否成立，確認IDi的有效性。若成立，計算EGMi=［x］Ei，將EGMi發送給Ui，并存儲IDi、Ei。其中IDi、Ei以及時戳time構成公開的公鑰狀態列表LPK，如表3所示。公鑰狀態列表LPK的實時維護由群管理員GM負責，每當群成員加入或撤銷，都要實時更新LPK，并向所有群成員廣播最新的LPK，同時將（IDi，Ei，timestart-i，timeend-i）發送給群成員Ui，作為群成員Ui的群簽名證書。設計一個公鑰狀態列表LPK可以實現動態地增加和撤銷群成員，提高執行效率。在撤銷某個群成員時，只需將LPK中群成員對應的終止時間修改為當時的時間即可。當成員被撤銷后，它不可以生成新的合法群簽名。當群成員公鑰有效時，可以將其終止時間設置為一個足夠大的值。

成員Ui收到EGMi后，計算EGMi=［xi］EGM是否成立。若成立，則成員Ui公鑰為Ei，私鑰為xi。

c）群簽名過程。群成員Ui對消息m進行簽名，需要和管理員GM共同完成。群成員Ui隨機選擇bi←REuclid Math TwoZApN，并向可信時間戳機構請求當前時間time，然后計算Ebi=［bi］E0，ti=H2（Ei‖E0‖Ebi‖m），si=ti+bi-xi mod N，群成員Ui將（time，Ei，m，Ebi，si）發送給GM。

GM接收到（Ei，m，Ebi，si）后，先根據Ei值查找LPK，看其在當前時間是否為有效值。若有效，則檢驗t′i=H2（Ei∥E0∥Ebi∥m），且［t′i］Ebi=［si］Ei是否成立。若成立，則管理員GM計算Evi=［x+t′］E0，并將IDTra=（IDi，m，Evi，t′i，si）存儲到追蹤列表，如表4所示。群成員對消息m的簽名記為σi=（Evi，t′i，si）。

d）驗證。驗證者接收到簽名后，檢驗Evi=［t′i］EGM是否成立。若成立，則接受σi=（Evi，t′i，si）為消息m的群簽名；否則，不接受。

e）追蹤。關于簽名σi=（Evi，t′i，si）產生矛盾分歧時，群管理員可以通過查詢追蹤列表中對應的t′i、si追蹤到該簽名的簽名人Ui的身份，GM根據簽名追蹤列表中的IDTra=（IDi，m，Evi，t′i，si）信息查找相應IDi，證明該簽名確實是群成員Ui產生的。

3.2 正確性分析

該方案中的系統建立存在管理員與成員雙向驗證身份的過程。

a）成員加入過程中管理員與成員互驗身份。管理員GM接收到成員Ui發送的（IDi，EIDi，Ei，hi）后，檢驗［H1（IDi）］EIDi=［H1（IDi）］［ai］E0=［hi］E0成立，則證明了IDi的有效性。管理員完成對成員的檢驗后，計算EGMi=［x］Ei并將其發送給Ui，Ui驗證EGMi=［xi］EGM是否成立，確認GM的身份。

b）簽名過程中驗證成員身份。群管理員GM和群中成員Ui協作生成群簽名。在GM接收到（time，Ei，m，Ebi，si）后，首先檢驗Ui在當前時間內是否存在，若成立，則檢驗t′i=H2（Ei‖E0‖Ebi‖m），且［t′i］Ebi=［si］Ei是否成立，若成立，則證明發送方確實為群中成員Ui。

c）簽名的正確性。驗證簽名中Evi的有效性，即檢驗Evi=［x+t′i］E0=［t′i］EGM，證明群管理員參與了簽名過程。

驗證t′i=H2（Ei‖E0‖Ebi‖m）的正確性，即驗證t′i=H2（Ei‖E0‖Ebi‖m）=H2（Ei‖E0‖［bi］E0‖m）=H2（Ei‖E0‖［si+xi-ti］E0‖m）。僅需驗證［bi］E0=［si+xi-ti mod N］E0。因為si=ti+bi-xi mod N，所以［bi］E0=［si+xi-ti mod N］E0=［si-ti mod N］Ei=［si-t′i mod N］Ei。

通過以上分析，證明了本文方案的正確性。

3.3 安全性分析

定理5 匿名性。對于任意多項式時間敵手A，本文方案在隨機預言模型下是匿名的。

證明 通過挑戰者C和敵手A之間的游戲完成證明。

G0游戲如下：

a）挑戰者C輸入安全參數p=4·l1…ln-1，其中li是小的不同的奇素數，給定集合ελλ（Euclid Math OneOAp，π）和理想類群cl（Euclid Math OneOAp）以及在Euclid Math TwoFApp上具有自同態環的超奇異橢圓曲線E0，H1：{0，1}*→Euclid Math TwoZApN，H2：{0，1}*→Euclid Math TwoZApN。隨機選取x←REuclid Math TwoZApN，計算EGM=［x］E0。公開群公共參數為{p，N，E0，H1，H2}以及群公鑰EGM，保留私鑰x。

b）敵手A 輸入需簽名的消息m，兩個群成員Ui0、Ui1∈Lpk給挑戰者 C，挑戰者C選取b=0，其中b∈{0，1}，生成群成員Uib對應的私鑰xi0∈REuclid Math TwoZApN，令實際群成員Ui=Ui0執行簽名算法。

c）挑戰者C運行簽名算法，生成簽名σi=（Evi，t′i，si），并發送給敵手A。

d）敵手A收到簽名后給出關于b的猜測。

G1游戲如下：

G1游戲與G0游戲的過程類似，其區別在于挑戰者C選取b=1，其中b∈{0，1}，生成群成員Uib對應的私鑰xib∈REuclid Math TwoZApN，并用群成員Ui1對應的私鑰執行簽名算法，生成簽名σ*i=（E*vi，t′*i，s*i），并發送給敵手A。敵手A接收到簽名后給出關于b的猜測。

下面說明假設敵手A贏得匿名性攻擊游戲的優勢AdvanonA=（|Pr［b*=b］-1/2|=ε是可忽略的，只需要證明挑戰者C用成員Uib的私鑰計算生成的群簽名σi=（Evi，t′i，si）與用群成員Ui1-b的私鑰計算生成的群簽名σ*i=（E*vi，t′*i，s*i）是不可區分的即可。

對于簽名σi，由簽名過程易知，當挑戰者C用成員Uib的私鑰計算簽名時，均勻抽樣bi←REuclid Math TwoZApN，ti=H2（Ei‖E0‖Ebi‖m），si=ti+bi-xi mod N，最終生成簽名σi=（Evi，t′i，si）；當挑戰者C用成員Ui1-b的私鑰計算簽名時，均勻抽樣并最終生成簽名σ*i" =（E*vi ，t′*i，s*i）。根據決策CSIDH，簽名σi=（Evi，t′i，si）與σ*i=（E*vi，t′*i，s*i）是不可區分的。因此，敵手A的優勢是可以忽略AdvanonA。

綜上所述，本文提出的基于超奇異同源的群簽名滿足隨機預言模型下的匿名性。

定理6 不可偽造性。如果GAIP問題是困難的，本文提出的基于超奇異同源的群簽名在隨機預言模型下是不可偽造的。

證明 通過挑戰者C和敵手A之間的游戲完成證明。假設敵手A能夠以不可忽略的概率ε成功偽造簽名，下面將展示挑戰者C如何利用敵手A的偽造結果找到一個理想e，構造一個GAIP問題的解。敵手A與挑戰者C之間的游戲如下：

a）setup。輸入安全參數，挑戰者C 進行如下操作：

挑戰者C輸入安全參數p=4·l1…ln-1，其中 li是小的不同的奇素數，集合ελλ（Euclid Math OneOAp，π）和理想類群以及在Fp上具有自同態環的超奇異橢圓曲線E0，H1：{0，1}*→Euclid Math TwoZApN，H2：{0，1}*→Euclid Math TwoZApN。將群公共參數{p，N，E0，H1，H2}發送給敵手A。

b）query。敵手A可以進行多項式次訪問預言機并進行如下詢問，挑戰者C作出響應，挑戰者C分別建立列表L1～L4來存儲敵手A的H1詢問、H2詢問、私鑰詢問及簽名詢問，所有列表初始化為空。設在進行私鑰及簽名詢問之前，已進行過所有相關的hash詢問。

（a）哈希詢問。

H1詢問：A可以選擇群成員身份IDi進行詢問，C檢查列表L1，若A進行過此詢問，則返回相同結果。否則令hi=ai+H1（IDi） mod N，將hi返回給 A，并將（IDi，hi，ai）加入列表L1。

H2詢問：接收到A查詢輸入（m，Ebi）時，C檢查列表L2，若A進行過此詢問，則返回相同結果。否則C隨機選擇ti←REuclid Math TwoZApN返回給A，并將（m，Ebi，ti）加入列表L2。

（b）私鑰詢問。

A可以選擇群成員身份IDi進行私鑰詢問，C隨機地選取私鑰xi←REuclid Math TwoZApN，并輸出（Upki，Uski）=（Ei，xi），將私鑰返回給A，并將（IDi，Ei，xi）加入列表L3。

（c）簽名詢問。

A可以選擇群成員身份IDi，提交待簽消息m的簽名詢問，C查詢列表L2、L3找到對應記錄并用簽名算法計算對消息m的簽名結果σi，隨機選取bi←REuclid Math TwoZApN，計算ti=H2（Ei‖E0Ebi‖m），si=ti+bi-xi mod N，最終生成簽名σi=（Evi，t′i，si）。

c）forgery。敵手A向挑戰者C提交一個消息m*、群成員身份為ID*i以及偽造的群簽名σ*i=（E*vi，t′*i，s*i），且滿足敵手A沒有詢問過用戶ID*i的簽名私鑰；敵手A沒有詢問過（E*vi，t′*i，s*i）的簽名兩個條件。

如果簽名σ*i=（E*vi，t′*i，s*i）是合法簽名，下面將展示挑戰者C如何利用敵手A的偽造結果求得理想e，其為GAIP問題的一個解。挑戰者C查詢敵手A的詢問列表L2，若不存在集合（m*，E*bi，t*i），挑戰者C放棄并終止游戲。否則，因為σ*i=（E*vi，t′*i，s*i）是合法簽名，由簽名的驗證過程得

Evi=［t′i］EGM

E*vi=［t′*i］EGM

若ti-t*i=0，則挑戰者放棄游戲，否則可以計算出Evi=［ti-t*i mod N］E*vi。令e=ti-t*i mod N，則有Evi=［e］E*vi=eE*vi，即理想e是GAIP問題的一個解。

綜上所述，如果GAIP問題是困難的，本文方案在隨機預言模型下是不可偽造的。

定理7 抗合謀性。對于任意多項式時間敵手A，本文方案在隨機預言模型下是抗合謀的。

證明 抗合謀攻擊是指即使部分成員聯合起來也無法產生GM追蹤不到的合法群簽名。在本文方案的群成員加入算法中，管理員GM將成員身份信息存儲在群成員列表中，簽名時先通過搜索列表中的存儲信息驗證成員的身份合法性，驗證成功才提供簽名幫助，與群成員合作產生簽名，避免了群中成員合謀產生無法追蹤的簽名；此外基于GAIP問題的困難性，使得群管理員GM無法獲知群成員的私鑰，且群成員之間無法得出其他成員的私鑰；最后，群中所有成員以及管理員GM的私鑰都完全保密；且互相無關。所以，該方案具有抗合謀性。

定理8 可追蹤性。對于任意多項式時間敵手A，本文方案在隨機預言模型下是可追蹤的。

證明 方案的可追蹤性是指管理員可以通過打開簽名來找到簽名者的真實身份。本文方案的簽名由管理員和群成員共同完成，在執行簽名算法時，用戶會先聲稱自己的部分簽名，然后將其發送給GM，GM收到簽名后，查詢用戶 Ui是否在群成員列表中，并通過判斷［t′i］Ebi=［si］Ei是否成立來驗證用戶簽名的合法性。在通過驗證之后，管理員才會計算簽名；同時將其存儲到追蹤列表里。由此可以看出，管理員GM只需通過搜索追蹤列表來打開簽名，即可查出簽名者身份。

此外，攻擊者無法在沒有群管理員的情況下獨自生成合法簽名。假設敵手A具有增加和撤銷群成員的權力以及獲得群私鑰和群中任意成員私鑰的能力。此外，A還可以運行簽名預言機和打開預言機。

若在IDi下對于消息M，A偽造群成員i的簽名σi，但只要群管理GM是安全的，GM的私鑰不被獲取，那么A就無法偽造出不能被GM追蹤到的簽名。因為群簽名是由群成員和群管理員共同合作完成的。Ui只有在GM協助下才可以產生有效的群簽名，而GM在協助Ui時，將Ui的相關身份信息記錄在追蹤列表Ltrack中；此外因為GAIP問題是困難的、是計算不可行的，那么即使群成員被攻破，只要GM的私鑰未被泄露，簽名仍然不可偽造，所以本文方案滿足可跟蹤性。

3.4 性能分析

將本文群簽名方案與文獻［19］方案進行比較。文獻［19］方案采用雙線性映射，實現群管理員對群成員的身份認證，而本文方案為提出的基于同源的零知識身份認證，且同樣具有以下優點：

a）工作效率高。本文提出的簽名方案中群簽名長度是固定不變的，不隨群中成員個數的變化而變化且簽名長度短，公鑰和簽名長度均與群成員的數量n無關，所以整體群簽名效率較高。本文方案適合大群組的群簽名方案。

b）動態性。本文方案設置了公鑰狀態列表，可以實現動態地增加和撤銷群成員，其加入、撤銷代價較小，群成員可以隨機地加入和撤銷。群成員的撤銷簡單快捷，只要修改群成員對應的終止時間便能實現群成員的即時撤銷。

不同之處在于：

a）本文群簽名方案基于同源的GAIP問題，由公鑰求出私鑰是困難的，規避了被撤銷成員聯合得出其他成員私鑰的風險。

b）本文群簽名中，群成員的私鑰由自己隨機選擇生成，因此可以抵擋群管理員的陷害攻擊。

c）本文群簽名方案包含了超奇異同源的特殊性質，如密鑰短、抗量子攻擊等，但計算時間長。

4 結束語

本文在Bullens等人提出的CSI-Fish的基礎上，提出了一個新的零知識證明方案。與CSI-Fish中的方案相比，該方案在僅有一個公鑰的前提下，將挑戰空間提升為類群階數N，實現了更強的穩固性。同時本文通過應用Fiat-Shamir變換，在量子隨機預言模型下得到了基于超奇異同源的簽名方案以及群簽名方案，并對提出的簽名方案進行了安全性證明。

參考文獻：

［1］Silverman J H.The arithmetic of elliptic curves［M］.Berlin：Springer，2009.

［2］Rostovtsev A，Stolbunov A.Public-key cryptosystem based on isogenies［EB/OL］.（2006-05-02）.https：//eprint.iacr.org/2006/145.

［3］Childs A，Jao D，Soukharev V.Constructing elliptic curve isogenies in quantum subexponential time［J］.Journal of Mathematical Crypto-logy，2014，8（1）：1-29.

［4］Biasse J F，Jao D，Sankar A.A quantum algorithm for computing isogenies between supersingular elliptic curves［C］//Proc of International Conference on Cryptology in India.Cham：Springer，2014：428-442.

［5］Jao D，De Feo L.Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies［C］//Proc of International Workshop on Post-Quantum Cryptography.Berlin：Springer，2011：19-34.

［6］Castryck W，Lange T，Martindale C，et al.CSIDH：an efficient post-quantum commutative group action［C］//Proc of International Confe-rence on Theory and Application of Cryptology and Information Security.Cham：Springer，2018：395-427.

［7］Fiat A，Shamir A.How to prove yourself：practical solutions to identification and signature problems［C］//Proc of Conference on Theory and Application of Cryptographic Techniques.Berlin：Springer，1986：186-194.

［8］Abdalla M，An J H，Bellare M，et al.From identification to signatures via the Fiat-Shamir transform：minimizing assumptions for security and forward-security［C］//Proc of International Conference on Theory and Applications of Cryptographic Techniques.Berlin：Springer，2002：418-433.

［9］Yoo Y，Azarderakhsh R，Jalali A，et al.A post-quantum digital signature scheme based on supersingular isogenies［C］//Proc of International Conference on Financial Cryptography and Data Security.Cham：Springer，2017：163-181.

［10］Galbraith S D，Petit C，Silva J.Identification protocols and signature schemes based on supersingular isogeny problems［C］//Proc of International Conference on Theory and Application of Cryptology and Information Security.Cham：Springer，2017：3-33.

［11］De Feo L，Galbraith S D.SeaSign：compact isogeny signatures from class group actions［C］//Proc of Annual International Conference on Theory and Applications of Cryptographic Techniques.Cham：Sprin-ger，2019：759-789.

［12］Beullens W，Kleinjung T，Vercauteren F.CSI-FiSh：efficient isogeny based signatures through class group computations［C］//Proc of International Conference on Theory and Application of Cryptology and Information Security.Cham：Springer，2019：227-247.

［13］Galbraith S D.Mathematics of public key cryptography［M］.Cambridge：Cambridge University Press，2012.

［14］De Feo L.Mathematics of isogeny based cryptography［EB/OL］.（2017-11-11）.http：//doi.org/10.48550/arxiv.1711.04062.

［15］Cozzo D，Smart N P.Sashimi：cutting up CSI-FiSh secret keys to produce an actively secure distributed signing protocol［C］//Proc of International Conference on Post-Quantum Cryptography.Cham：Sprin-ger，2020：169-186.

［16］Benhamouda F，Camenisch J，Krenn S，et al.Better zero-knowledge proofs for lattice encryption and their application to group signatures［C］//Proc of International Conference on Theory and Application of Cryptology and Information Security.Berlin：Springer，2014：551-572.

［17］Bellare M，Poettering B，Stebila D.From identification to signatures，tightly：a framework and generic transforms［C］//Proc of International Conference on Theory and Application of Cryptology and Information Security.Berlin：Springer，2016：435-464.

［18］EI Kaafarani A，Katsumata S，Pintore F.Lossy CSI-FiSh：efficient signature scheme with tight reduction to decisional CSIDH-512［C］//Proc of IACR International Conference on Public-Key Cryptography.Cham：Springer，2020：157-186.

［19］于璇，侯書會.一種高效安全的群簽名方案［J］.通信技術，2018，51（2）：413-418.（Yu Xuan，Hou Shuhui.Efficient and secure group signature scheme［J］.Communications Technology，2018，51（2）：413-418.）