(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111626748.9 (22)申请日 2021.12.28 (71)申请人 青岛科技大 学 地址 266000 山东省青岛市崂山区松岭路 99号 (72)发明人 王玲玲　赵雪芹　曹中达　耿克　 (74)专利代理 机构 青岛中天汇智知识产权代理 有限公司 37241 代理人 孟琦 (51)Int.Cl. G06F 21/60(2013.01) G06F 21/64(2013.01) (54)发明名称 基于zk-SNARK的轻量级环签名方法 (57)摘要 本发明涉及环签名方法。 针对环签名方案大 都存在签名长度过大， 实现效率低的缺点， 本发 明提供一种基于zk ‑SNARK的轻量级环 签名方法， 步骤如下： 首先使用Merkle树计算由n个环成员 公钥得到的根节点值， 再采用满足 需求的签名方 法Sig生成标识签名人身份的单个签名， 最后选 择满足需求的公钥加密方法PKE对签名加密得到 和签名人关联的密文ct， 通过上述构造过程可得 合法环签名的约束条件， 验证算法的所有输入对 应zk‑SNARK方法的公开陈述(1,m,πroot,ct)和 证据(VK,πMerkle,σ,rct)， 若零知识证明验证通 过， 即证明以上约束条件成立， 反之不然。 本发明 仅需三个群元素和两大整数， 相较于其他的环签 名方法， 涉及的公共参数长度从O(n)减缩减到O (log n)。 权利要求书3页 说明书6页 附图1页 CN 114329551 A 2022.04.12 CN 114329551 A 1.一种基于 zk‑SNARK的轻量级环签名方法， 其特 征在于， 包括如下步骤： 首先使用Merkle树计算由n个环成员公钥得到的根节点值， 再采用满足需求的签名方 法Sig生成标识签名人身份的单个签名， 最后选择满足 需求的公钥加密方法PKE对签名加密 得到和签名人关联的密文ct， 整个签名生成和验证过程满足环签名的安全性要求， 通过上 述构造过程可 得合法环签名必须通过以下三个验证算法： 算法1： Merk le.Verify( πroot, πMerkle,VK)＝1 算法2： Sig.Verify( σ,m,vk)＝1 算法3： PKE.Enc(pk, σ,rct)＝ct， 它们构成zk ‑SNARK的约束条件， 验证算法的所有输入对应zk ‑SNARK方法的公开陈述 (1,m, πroot,ct)和证据(VK, πMerkle, σ,rct)， 若零知识证明验证通过， 即证明以上约束条件成 立， 对应的环签名是合法的， 反 之不然。 2.根据权利要求1所述的轻量级环签名方法， 其特征在于， 采用哈希函数SHA ‑256构建 Merkle树。 3.根据权利要求2所述的轻量级环签名方法， 其特征在于， 所述签名方法采用Schnorr 签名方法。 4.根据权利要求3所述的轻量级环签名方法， 其特征在于， 所述公钥加密方法采用 ElGamal方法。 5.根据权利要求4所述的轻量级环签名方法， 其特征在于， 所述零知识证明采用Groth 提出的zk ‑SNARK方法。 6.根据权利要求1 ‑5任一项所述的轻量级环签名方法， 其特征在于， 所述算法1： Merkle.Verify( πroot, πMerkle,VK)＝1 输入： 验证密钥VK、 merk le证明πmerkle， 根节点 πroot 输出： 1/0 ①从VK对应的叶子节点和兄弟节点进行哈希运算， 再依次将哈希结果和对应的兄弟节 点进行哈希， 直到得到根节点； ②验证得到的根节点与ct＝(y1,y2)是否相等； 所述算法2.Sig.Verify( σ,m,vk)＝1 输入： 信息m、 签名 σ ＝(x1,x2)和签名公钥vk 输出： 1/0 验证等式 是否成立； 所述算法3.PKE.Enc(pk, σ,rct)＝ct 输入： 签名 σ 、 随机数rct、 密文ct＝(y1,y2)和加密公钥pk 输出： 1/0 ①对签名σ和伪随机数rc t进行公钥加密， 生成密文ct ′＝(y′1,y′2) ， 其中 ②判断ct′与输入密文ct是否相等。 7.根据权利要求6所述的轻量级环签名方法， 其特 征在于， 包括如下步骤： (1)初始化权　利　要　求　书 1/3 页 2 CN 114329551 A 2输入： 关系R 输出： 公共参数crs 输入的关系R是通过所述约束条件生成二次算术程序来构成一个NILP， 输出关系为 关系R中F是指有限域， aux用于指定双线性 群， 4为公开陈述的个数， ui(X),vi(X),wi(X),t(X)是zk ‑SNARK构成的多项式； 陈述是x＝ (a0,...,a3)＝(1,m, πroot,ct)， 证据是ω＝(a4,...,am)＝(VK, πmerkle, σ )， 使以下等式成立 调用(crs, τ) ←ZS.Setup(R))， 丢弃τ， 返回 crs； (2)密钥生成 输入： 安全参数 λ 输出： 签名密钥SK和验证密钥VK； ①计算(vk,sk) ←Sig.KeyGen(1λ) ②选择随机数 置pk←rpk ③置VK←(vk,pk)和SK ←(sk,VK) ④返回(VK,SK)； (3)签名 输入： 关系R， 签名密钥SK， 信息m， 公共参数crs 输出： 环签名Σ ＝( π,ct) ①选择环成员Ri ng＝(VK1,...,VKn) ②计算签名 σ ＝Sig.Sign(sk,m) ③令签名人 下标ind∈{1,. ..,n}， 且VKind＝VK ④计算根节点 πroot←Merkle.GenH(Ring)， 计算VKind对应的成员证明： πmerkle←Merkle.Prove(Ri ng,ind) ⑤选择随机数rct， 计算密文ct ←PKE.Enc(pk, σ ) ⑥置x＝(1,m, πroot,ct)和ω＝(VK, πMerkle, σ ) ⑦计算 π←ZS.Prove(R,crs,x,ω) ⑧返回Σ←( π,ct)； (4)签名验证 输入： 关系R， 信息m， 环Ri ng， 公共参数crs， 签名∑ 输出： 0/1 ①解析Σ＝( π,ct) ②计算根节点 πroot←Merkle.GenH(Ring) ③置x＝(1,m, πroot,ct) ④返回ZS.Verify(R,crs,x, π )； 参数含义如下： p是一个大素数， q是能被p ‑1整除的素数， 是群生成元， sk是私 钥， vk是Schnorr签名方法的公钥， pk是Elgamal公钥加密方法的公钥； zk ‑SNARK在非对称双权　利　要　求　书 2/3 页 3 CN 114329551 A 3