Page 51 - 《软件学报》2025年第10期

4448 软件学报 2025 年第 36 卷第 10 期

 ( ) 
λ
 V (crs, x,π) = 1 crs ← Setup 1 
 

  = 1.
Pr   : 
 
(x,π) ← A(crs)
∃x < L R
● 零知识性 (honest-verifier zero-knowledge). 对于任意陈述 x ∈ L R 及所有满足 R(x,w) = 1 的证据 w, 存在一个
模拟器 S 使得其输出与诚实验证者 V 的视图 V (crs, x,π) 满足计算不可区分性.
2.3 基于陷门的对偶 Regev (dual-Regev) 加密方案 [21]
本文方案中用到了对偶 Regev 加密方案, 这里对其进行描述. 令安全参数为 , χ 为上界为 B
λ m,q 为陷门参数,
( )
,
的噪声分布, B = O(q/m) Π PKE PKE.keyGen,PKE,Enc,PKE.Dec 描述如下.
( )
m
n
λ
,
(1) PKE.keyGen 1 : 输入安全参数 λ, 输出陷门 (A,T A ) ← TrapGen(1 ,1 ,q) A ∈ Z n×m . 输出密钥对 (sk, pk) =
q
(T A , A).
(2) PKE,Enc(pk,m) : 输入公钥 pk, 以及一个消息 m ∈ {0,1}, 随机选取向量 d, s ← Z , 噪声向量 e ← χ m+1 . 计算
n
q
[ ⌈ ⌉ ]

T q
b = [A|d] s+e+ 0 ·m . 输出密文 ct = (d, b).
2
T
(3) PKE.Dec(sk,ct) : 输入私钥 sk 以及密文 ct, 解析 b = (b 0 ,b 1 ), 计算 s ← Inv(A,T A , b) m = b 1 − d s.
′
,
本节所描述的 dual-Regev 方案满足正确性及选择明文安全下的不可区分性 (indistinguishability against chosen-
plaintext attacks, IND-CPA). 详细证明过程可参考文献 [21].
2.4 可更新默克尔树累加器
可更新默克尔树累加器 [15] 可看作 Libert 等人 [6] 所提出的格上默克尔树累加器的扩展, 为构建格上动态群签
名提供了高效的密码学组件. 与文献 [6] 中提出的原始累加器适用于静态群 (环) 签名不同, 可更新默克尔树累加
器方案给出了一个高效的更新算法, 使得对于给定的待修订叶子结点, 可以简单地对该结点所涉及的路径进行修
改, 从而更新累加值. 如图 1 所示, 对于一个叶子结点树为 2 = 8 的默克尔树, 将 R = {d 0 ,..., d 7 } 累加到根结点 u 中.
3
j = 011 以及黄色部分结点 (路径) 作为 w. 若需要更新 d 3 为 , 则需要更新其中绿色的
∗
图中 d 3 累加到 u 中的证据 d 3
结点.

u
u 0 u 1
u 00 u 01 u 10 u 11

u 000 u 001 u 010 u 011 u 100 u 101 u 110 u 111
d 0 d 1 d 2 d 3 d 4 d 5 d 6 d 7

图 1 可更新默克尔树累加器

定义 7 (可更新默克尔树累加器 (updatable Merkle-tree accumulator)). 一个可更新默克尔树累加器由以下 5
个多项式时间算法构成.
(1) pp ← TSetup(λ) : 输入安全参数 λ, 输出公共参数 pp.
(2) u ← TAcc pp (R) : 输入一个包含 N 个数据的集合 R = {d 0 ,..., d N−1 }, 输出累加值 u.
(3) w/⊥ ← TWitness pp (R, d) : 输入集合 R 及一个数据 d, 若 d < R 则输出 ⊥, 否则, 输出一个证据 w 说明数据 d