基于超奇异同源的指定验证者盲签名*

赵兴波 李梦东 李 杰

北京电子科技学院，北京市 100070

引言

量子计算机的发展对密码学产生了重大影响。 Shor 算法的出现使基于离散对数问题和大整数分解问题的经典公钥密码不再安全，于是研究人员开始关注后量子密码。 2016 年美国国家安全局(NIST)开始征集后量子密码算法并进行筛选，并于2020 年7 月公布了筛选算法结果。后量子密码的主要类型包括:基于格的、基于纠错码的、基于多变量的以及基于哈希的密码，而同源密码是一种新兴的且十分有潜力的后量子密码[1]。

同源为椭圆曲线之间保持基点(basepoint)的同态映射，是一种群同态。 因为通常曲线同源问题存在亚指数时间的量子算法，而超奇曲线同源问题目前只存在指数时间的量子算法，因此目前同源密码都是超奇椭圆曲线上的方案。 超奇同源密码与其它后量子密码类型相比较，密钥、密文或签名长度短，但超奇同源密码也存在计算时间稍长的问题。

超奇异同源密码的最早的结构包括Charles、Goren 和Lauter[2]的抗碰撞哈希函数、Jao 和De Feo[3]的密钥交换协议、De Feo、Jao 和Plut[4]的公钥加密方案和交互识别协议[5]。 在签名方面，Jao-Soukharevt[6]提出了不可否认签名，而Srinath 和Chandrasekaran 通过在不可否认签名的基础上加入盲签名的性质，提出了基于同源的不可否认盲签名方案[7]。 但在不可否认签名中，签名者对验证者没有控制权，因为签名者可以事先(即在交互之前)识别授权的验证者。为了解决不可否认盲签名中的弱点，找到一个更合适和更实用的签名方案，Rajeev、Agnese 和Ankan 提出了基于超奇异同源的指定验证者盲签名 ( Supersingular Isogeny-based Designated Verifier Blind Signature:SI-DVBS)方案[8]，指定验证者签名在保护签名者的隐私方面具有重要的作用，可用于限定软件使用范围、保护版权等应用。 但该方案在脱盲阶段需要额外的信息来计算对偶同源，所以该指定验证者盲签名(Designated Verifier Blind Signature:DVBS) 可以在SIDH(Supersingular Isogeny Diffie-Hellman)上实现，但不能在CSIDH(Commutative Supersingular Isogeny Diffie-Hellman)上实现.

通过对SI-DVBS 方案的研究，将其与Ward、Thorsten 等人提出的CSI-Fish[9]签名方案中的思想相结合，本文提出了一个不需要额外的信息就达到脱盲目的的指定验证者盲签名，使DVBS 可以在CSIDH[10]上实现。 由于CSIDH 问题的特点，所提出的改进方案可有效提高原类似方案的实现效率。

1 背景知识

1.1 超奇异椭圆曲线和同源

令q＝pn，p 是一个素数，椭圆曲线E/Fq是一个亏格为1 的光滑射影代数曲线(至少有一个点)，其仿射部分满足Weierstrass 方程:E:y2＋a1xy＋a3y＝x3＋a2x2＋a4x＋a6，ai∈Fq，另外还有一个无穷远点OE。

椭圆曲线之间的同源φ:E →E1为一个态射，也是群同态且φ(OE1)＝OE2。 非零同源的次数定义为态射的次数。 Tate[11]指出:有限域Fq上的两条椭圆曲线E，E1是同源的，当且仅当＃E(Fq)＝＃E1(Fq) 。

对任一非零同源φ:E →E1，都存在一个唯一的非零同源:E1→E，则称为φ 的对偶同源。 对于同源φ:E →E1，当E ＝E1时称为自同态。 椭圆曲线的自同态集用End(E)表示，具有点加法和函数复合运算的环结构。 End(E)中若d＝deg(φ)，则存在整数t，使得φ2-tφ＋d＝0，t称为自同态的迹。 对于Frobenius 自同态πq，-tπq＋q＝0，t 称为Frobenius 迹。 当且仅当t＝0 时，曲线是超奇异的。

1.2 CSI-Fish 方案

在CSIDH 的基础上，Ward 等人提出了一个高效的签名方案CSI-Fish[9]，其提出的识别方案的工作原理如下:设g 为超奇异椭圆曲线理想类群cl(O)＝I(O)/P(O)的一个生成元，随机选取a∈Z N，使a ＝ga是cl(O)中的一个随机元素。 提供者的公钥为E1＝a* E。 然后提供者随机选取b∈Z N使得b ＝gb，并将E2＝b*E发送给验证者。 验证者随机选取比特c∈{0，1}，然后发送给提供者。 当c ＝0 时，提供者回复r＝b，验证者检查E2是否等于rE；当c ＝1 时，提供者回复r＝b－amodN，验证者检查E 是否等于rE1。

在CSI-Fish 还提出了基于同源的类群作用的主要困难假设:

定义(类群作用逆问题):给定两个曲线E，E1，其自同态环End(E1)＝End(E)＝O， 找到一个理想a ⊂O 使得E ＝a*E1。

此问题是DVBS 方案所依赖的计算困难问题。

2 SI-DVBS 方案

在 [7] 的 DHKE ( Diffie-Hellman key exchange)协议中，身份的零知识证明是由基于同源的交换方图提供的。 [8]也采用了这种方法，并将其扩展到了双立方体(如图1 所示)，使得每个面上都有一个交换方图。 [8]基于此构建了SI-DVBS 方案，其思路是:在三维交换图中，涉及到的每个函数都贡献了一条路径，在这条路径中，需要特定的信息才能向特定的方向移动。 [8]中方案的Sign 算法只涉及下立方体，它本质上包含盲和脱盲两个阶段。 但是只有上立方体可以被认为是签名，而不考虑盲性，因此，这种方法通常可以得到基于同源的指定验证者签名。

图1 [8]中的立体交换图

SI-DVBS 方案的安全模型[8]包括三个参与者:消息请求者A，签名者B 以及指定验证者V。SI-DVBS 方案包括以下算法:

1. 设置参数算法:在输入安全参数λ 时，该算法生成系统的公共参数params。 在此之后的所有算法中，params 将被视为隐式输入。

2. 密钥生成算法:在输入参数上分别生成签名者和验证者的(公钥、私钥)对(pkS，skS)，(pkV，skV).

3. 签名算法:在输入签名者的签名密钥skS、验证者的公钥pkV和消息m 后，算法最终生成SI-DVBS 的签名σ。 主算法由以下三个子算法组成:

(1)盲化:这是一种概率盲算法，由请求者运行，根据输入的消息m、随机选择r 和验证者的公钥pkV，输出盲消息m′。

(2)盲签名:这是签名者运行的一种签名算法，它接收盲消息m′ 和签名者的密钥skS。 该算法在盲消息m′上输出签名σ′。

(3)脱盲:这是一个确定性的脱盲算法，由请求者运行，根据输入的盲签名σ′ 和随机选择r，输出消息m 上的无盲签名σ。

4. 验证:这是一个由指定验证者运行的确定性验证算法。 当输入验证者的密钥skv、签名者的公钥pkS、签名σ 和消息m 时，根据该算法的输出位b 判断签名是否有效，当输出位b ＝1时，签名有效；输出位b ＝0 时，则签名无效。

5.模拟签名:这是一个由指定验证者运行的模拟签名算法。 该算法在输入验证者的密钥skV、签名者的公钥pkS和消息m 后，输出与原始签名不可区分的相同文本。 此算法是为了使任何人都不能区分签名是签名者所做，还是指定验证者所做。

3 改进的SI-DVBS 方案

在Ward 等人提出的CSI-Fish 的方案基础上，将其签名方案中的思想与Rajeev[8]等人提出的SI-DVBS 相结合，本文设计了一个改进的SIDVBS 方案。 与[8]相比，本方案不需要额外的信息来计算对偶同源即可脱盲，从而达到了DVBS可以在CSIDH 中实现的目的。 下面介绍该方案的详细算法:

3.1 建立参数

3.2 密钥生成

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

B 随机选择b∈Z N，计算[b]＝b ＝gb以及E2＝b*E。 B 的公钥为E2，私钥为b。

V 随机选择a∈Z N，计算[a]＝a ＝ga以及E1＝a*E。 V 的公钥为E1，私钥为a。

3.3 盲签名

为了获得消息m 上的DVBS，A 首先将消息盲化并将其发送给B，B 对盲消息进行签名并将其发送回A。 最后，A 对从B 处接收到的签名进行解密，在m 上输出签名。 盲签名由以下三部分组成:

1.盲化过程(如图2 所示):设m 为要签名的消息。 A 计算散列h＝H(m)，[h]＝k＝gh和E13＝k*E1，然后A 随机选择m，n∈Z N并计算u＝[m-n]＝gm-n和E134＝u*E13

掩蔽曲线E134发送给签名者，并秘密保存m，n。

注意:[8]中的方案在进行完以上步骤后，在此处需要计算从曲线E13到曲线E134的同源的对偶，使脱盲成为可能。 为了计算对偶同源，需要额外的信息，而本方案不需要计算对偶同源，因为[n-m][b][m-n]E ＝[b] E，所以只需要保存好m，n，在脱盲时计算[n-m]即可。

2.盲签名(如图3 所示):B 用私钥b 进行签名，计算曲线E1342＝b*E134。

然后将E1342给A 作为B 在盲消息E134上的签名。

图2 请求者计算曲线E13、E134 进行盲化

3. 脱盲(如图4 所示):A 接收到盲消息上的签名，在原始消息m 上生成签名，通过计算u′＝[n－m] ＝gn－m以及E13424′＝u′*E1342，且将签名σ＝(m，j(E13424′)) 发送给指定验证者V。

盲签名验证:E13424′＝u′*E1342＝[n-m][b]E134＝[n－m][b ][m－n]E13＝[b ]E13＝E123。

图3 签名者计算曲线E1342 进行签名

图4 请求者计算曲线E13424′ 进行脱盲

3.4 验证

为了验证消息m 上接收到的签名σ，V 首先计算h ＝H(m)，然后通过计算k＝gh、E12＝a*E2和E123＝k*E12(如图5 所示)。 最后，V 接受σ作为一个对m 的有效签名，当且仅当j(E13424′)＝j(E123) 。

3.5 模拟签名

为了输出与接收到的在消息m 上的签名σ无法区分的相同的副本，V 用与验证算法完全相同的方式进行计算，模拟一个签名σ︿，即一个与E13424′同构的椭圆曲线。

4 正确性与安全性分析

以下对所提出的方案进行分析。

4.1 正确性分析

E123＝kE12＝kaE2＝kabE ＝kbE1＝bE13＝[n－m][b][m－n]E13＝E13424′，因此它们对应的j－不变量是相同的，所以指定验证者的签名(m，j(E123)) 与 签 名 者 的 签 名σ(m，j(E13424′)) 是相同的。

图5 验证者计算曲线E123 来检查签名是否有效

且盲性正确， 因为E13424′＝u′*E1342＝[n-m][b]E134＝[n－m][b][m－n]E13＝[b]E13＝E123。

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

4.2 安全性分析

根据SI-DVBS 方案的安全性要求，本文将从以下几个方面论述签名方案的安全性。

1. 不可伪造性

除了签名者和指定验证者，其他人不能以签名者的名义伪造签名，即在不知道签名者或指定的验证者的私钥的情况下，构造一个有效的SIDVBS 在计算上是不可行的。 由对消息m 的签名过程可知，签名(m，σ)可以由签名者或指定验证者生成。 只有知道签名者或指定验证者的私钥b 或a 才能伪造出符合条件的签名。 而由类群作用逆问题以及hash 函数H 的单向陷门性可知，在私钥保密的情况下，其他人无法由曲线E及其同源曲线得到私钥。 所以，该方案满足不可伪造性。

2. 盲性

签名者不应该了解关于请求者的真正消息的任何信息。 为了实现对消息m 的盲化，请求者随机选取m，n∈Z N并计算u＝[m－n]＝gm－n和E134＝u*E3，由于m，n 是随机选取的，所以u是类群中的一个随机元素，签名者无法从E134知晓H(m)，从而达到了对消息m 进行盲化的目的。

3. 不可验证性

为了验证签名的正确性，必须根据参数的知识和提供的公钥计算出椭圆曲线E123。 从上一节描述的方案可以看出，计算与E2同源的曲线E12需要指定验证者的私钥a， 而在计算曲线E123的时候，需用到E12。 因此，很明显，没有指定验证者的私钥的用户无法实际验证签名的有效性。 此外，在模拟签名过程中生成了一个与签名者所提供的签名相同的模拟签名，因此， 可以确定，在不知道签名者或指定验证者的私钥的情况下，从计算上验证所提议的SI-DVBS 的有效性是不可行的[8]。

4. 不可传递性

对给定的一个消息和签名(m，σ)，任何人不能区分是签名者的签名还是指定验证者所做的签名。 而签名方案中的模拟签名过程就是为了实现这一安全性质。

5 总结

本文提出并实现了一种基于超奇异椭圆曲线同源的指定验证者盲签名方案。 该方案是在Rajeev 等人提出的签名方案的基础上，与CSIFish 的思想相结合，使DVBS 可以在CSIDH 的设置下实现；此外，方案的脱盲阶段不需要额外的信息来计算对偶同源，就可以达到脱盲的目的。