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

陈颖 等: 具有用户自主链接及验证者条件撤销的格基群签名 4447

ρ σ,c (y)
∀y ∈ Λ, D Λ,σ,c (y) = ,
ρ σ,c (λ)
其中, ρ σ,c 是以 c 为中心, σ 为参数的高斯函数, 这里, 以 c 为中心, σ 为参数的高斯函数. 当 c = 0 时, 可以省略不写.
定理 1 (陷门生成 (trapdoor generation, TrapGen) [21] ). 令 q ⩾ 3 为一个奇数, 整数 l = logq . 当 m ⩾ O nlogq )
(
⌉
⌈
n m n×m ⊥ m×nl . 这里,
时, 存在一个多项式时间算法 TrapGen(1 ,1 ,q) 可输出一个矩阵 A ∈ Z q 及其陷门, 即 Λ (A) 的基 B ∈ Z q
( √ )
′
矩阵 A 与从 Z n×m 上均匀选择的矩阵 A 不可区分, 且 ||B|| 2 = O m , 以压倒性概率成立.
q
n m [22] R = Z[X]/
由于本方案设计的需要, 这里描述陷门生成算法的一个特殊形式 GenTrap(1 ,1 ,q) . 令环
n ( ) 1 T [ ζ−1 ] GenTrap(1 ,1 ,q) 可
m
n
(X +1), 给定 ζ ∈ N, m = O nlogq , g = q ζ ∈ R q , g = 1|g|...|g , 存在一个多项式时间算法
T 1×m m×ζ T T T Z 1×m a T ′ 不可区分.
输出一个矩阵 a ∈ R q 及其陷门 T a ∈ R 满足 a T a =g . 这里, 矩阵 a 与从 q 上均匀选择的矩阵
Λ (A) 的基, 存在一个多项式时间算法可以解决 (I)SIS 问题, 有以下定理.
⊥
给定
( √ )
定理 2 (原像采样 (SamPre) [21] ). 令 q ⩾ 3 为一个素数, 整数 m ⩾ n,k ⩾ 1. 高斯参数 σ ⩾ ˜ B ·ω logn , 矩阵

U ∈ Z n×k , 存在多项式时间算法 SamPre(A, B,σ,U) 输出 S ∈ Z m×k 满足 AS = U mod q. 这里, A, B 是 TrapGen 的输出,
q q
√
S 统计上接近分布 G Λ u 1 (A),σ ×...×G Λ u k (A),σ 且 ||S|| ⩽ σ m 以压倒性概率成立.
( T ) [22] T 1×m
类似于陷门生成, 这里描述原像采样算法的一个特殊形式 PreSample a ,T a ,σ,u 输入矩阵 a ∈ R 及其陷
q
√ √
m×ζ 2 2 T
门 T a ∈ R , u ∈ R q , 高斯参数 σ ⩾ η ϵ (Z) g +1 ||R|| , 输出 v 在统计上接近分布 G R m ,σ 满足 a v = u mod q.
q
定义 5 (同态陷门函数 (homomorphic trapdoor functions, HTDF) [23] ). 定义索引空间 X , 输入空间 , 输出空
U
V, 一个 HTDF 由以下 4 个多项式时间算法构成.
间
( )
λ
(1) (pk, sk) ← HTDF.KeyGen 1 : 一个密钥生成过程. 输入安全参数 λ, 输出密钥对 (pk, sk).
(2) f pk,x : U → V : 一个确定性函数由 x ∈ X, pk 索引.
(3) Inv sk,x : V → U : 一个概率性逆向函数由 x ∈ X, sk 索引.
in
(4) u = HTDF.Eval (g,(x 1 ,u 1 ),...,(x l ,u l )),v = HTDF.Eval Out (g,v 1 ,...,v l ): 确定性的输入/输出同态评估算法. 皆
∗
∗
l ∗ ∗
以函数 g : X → X 及数值 x i ∈ X,u i ∈ U,v i ∈ V 作为输入, 分别以 u ∈ U,v ∈ V 作为输出.
一个 HTDF 需要满足与无爪性相似的性质, 即找到两个 u,u ∈ U 且 x , x ∈ X , 满足 f pk,x (u) = f pk,x ′ (u ) 是困难
′
′
′
的. 正式地, 我们要求对于任意多项式时间内的敌手 A 需满足:

 ( ) 
λ
 f pk,x (u) = f pk,x ′ (u ) (pk, sk) ← HTDF.KeyGen 1 
′
 
 

Pr  :  ⩽ negl(λ).
 ( ) 
 λ 
′
′
′
′
u,u ∈ U, x, x ∈ X, x , x ′ (u,u , x, x ) ← A 1 , pk
2.2 零知识证明
零知识证明系统包括两个参与方: 证明者 P 和验证者 . x ∈ L R 为真之外任何信息
V P 需要在不透露某个陈述
的前提下说服 V 相信 x, 在此过程中, V 不知道除了 x 之外的任何信息. 零知识证明最早由 Goldwasser 等人 [24] 提
出, 对于各类密码方案的构建有着重要的作用. 本节对非交互式零知识证明系统进行回顾, 其包含 3 个多项式时间
算法.
定义 6 (非交互式零知识证明系统 (non-interactive zero knowledge system, NIZK)). 一个 NIZK 系统包含以
下 3 个多项式时间算法.
( )
λ
(1) crs ← Setup 1 : 输入安全参数 λ, 输出公共参考串 crs.
(2) π ← P(crs,w, x) : 输入公共参考串 crs, 陈述 x 和证据 w, 生成证明 π.
(3) 1/0 ← V (crs, x,π) : 输入公共参考串 crs, 陈述 x 和证明 x, 验证证明是否合法.若合法则返回 1; 否则, 返回 0.
通常, NIZK 系统需要满足完备性, 可靠性以及诚实验证者零知识性. 具体定义如下.
● 完备性 w, 我们有:
(completeness). 对于正确陈述 x ∈ L R 及所有满足 R(x,w) = 1 的证据
[ ( ( ))]
Pr (x,π) ← P(crs,w, x) = 1 : V crs ← Setup 1 λ = 1.
● 可靠性 A, 我们有:
(soundness). 对于任意多项式时间内的敌手