文章目录

• Encryption
• • 私钥
  • 公钥
• Signature
• MAC

Encryption

私钥

1. 一次一密（one-time pad）：$Enc(s,m)=s\oplus m$，密钥过长。

2. 准一次一密：设 $G$ 是 PRG，$Enc(s,m)=G(s)\oplus m$，密钥不可重用。可以证明它是单消息 IND 的，归约到 PRG 与 Un U_nUn​ 的计算不可区分上。如果询问两次 ( m0, m1) , ( m0′, m1′)(m_0,m_1),(m_0′,m_1′)(m0​,m1​),(m0′​,m1′​)，其中 m0⊕ m1≠ m0′⊕ m1′ m_0 \oplus m_1 \neq m_0′ \oplus m_1′m0​⊕m1​​=m0′​⊕m1′​，获得 c , c′ c,c’c,c′，只需计算 c ⊕ c′= mb⊕ mb′ c \oplus c’ = m_b \oplus m_b’c⊕c′=mb​⊕mb′​ 便可识别 $b$，因此不是多消息 IND 的。

3. 若 PRF 存在，那么多消息 IND 的私钥加密方案存在。设 { Fs}\{F_s\}{Fs​} 是 PRF。加密时随机选取 $r$，令
   Enc(s,m)=(r, F s(r)⊕m)Enc(s,m) = (r,F_s(r) \oplus m) Enc(s,m)=(r,Fs​(r)⊕m)

   那么 $\Pi$ 是多消息密文不可区分的。归约时，分别证明 Fs( r ) ⊕ mF_s(r) \oplus mFs​(r)⊕m 与 R Fn( r ) ⊕ mRF_n(r) \oplus mRFn​(r)⊕m 计算不可区分， R Fn( r ) ⊕ mRF_n(r) \oplus mRFn​(r)⊕m 与 Un⊕ mU_{n} \oplus mUn​⊕m 计算不可区分， Un⊕ mU_n \oplus mUn​⊕m 与 Un U_nUn​ 统计不可区分，于是 E x p t A , Π I N D( 1n, U1)Expt_{A,\Pi}^{IND}(1^n,U_1)ExptA,ΠIND​(1n,U1​) 的优势 $Adv$ 可忽略。

4. 任意单消息 IND 的私钥加密方案，都可以利用 PRF 提升到多消息 IND。设 Π′ \Pi’Π′ 是 IND 的， { fk}\{f_k\}{fk​} 是 PRF。加密时随机选取 $r$，令
   Enc(k,x)=(r,   En c ′( f k(r),x))Enc(k,x) = (r,\, Enc'(f_k(r),x)) Enc(k,x)=(r,Enc′(fk​(r),x))

   那么 $\Pi$ 是多消息 IND 的。

5. 单消息 IND 的私钥加密方案存在 $⟺$ OWF 存在。令 $\Pi$ 是安全的加密方案，那么 { E n ck} k ∈ K \{Enc_k\}_{k \in K}{Enck​}k∈K​ 就是 OWF。

6. 若 PRF 存在，那么 IND-CPA 的私钥加密方案存在。第 3 条的 E n c ( s , m ) = ( r , Fs( r ) ⊕ m )Enc(s,m) = (r,F_s(r) \oplus m)Enc(s,m)=(r,Fs​(r)⊕m) 的构造，就是 IND-CPA 的（自然也是 IND-Multiple 的），PRF + One time pad -> IND-CPA。归约证明时，用 R Fn RF_nRFn​ 替换 Fn F_nFn​，得到的方案是 IND-CPA 的。如果使用 Fn F_nFn​ 时它不是 IND-CPA 的，那么就可以区分 Fn, R Fn F_n,RF_nFn​,RFn​

7. 若 PRF 存在，任意 IND 的私钥加密方案都可以提升到 IND-CPA。第 4 条的 E n c ( k , x ) = ( r ,  E n c′( fk( r ) , x ) )Enc(k,x) = (r,\, Enc'(f_k(r),x))Enc(k,x)=(r,Enc′(fk​(r),x)) 的构造，就是 IND-CPA 的，PRF + IND -> IND-CPA。

8. 若 PRF 存在，那么是 IND-CCA1 但不是 IND-CCA2 的私钥加密方案存在。第 3 条的 E n c ( s , m ) = ( r , Fs( r ) ⊕ m )Enc(s,m) = (r,F_s(r) \oplus m)Enc(s,m)=(r,Fs​(r)⊕m) 的构造，是 IND-CCA1 的，但不是 IND-CCA2 的。CCA1 安全的证明，与第 6 条类似。不是 CCA2 安全的，可以构造敌手，挑战 ( x0, x1)(x_0,x_1)(x0​,x1​) 获得 c = ( r , σ = fk( r ) ⊕ xb)c=(r,\sigma=f_k(r)\oplus x_b)c=(r,σ=fk​(r)⊕xb​)，然后随机选择 σ′≠ σ\sigma’ \neq \sigmaσ′​=σ 并以 ( r , σ′)(r,\sigma’)(r,σ′) 询问解密 Oracle（强制 one time pad 密钥重用），得到 x ’ = σ′⊕ fk( r )x’=\sigma’ \oplus f_k(r)x’=σ′⊕fk​(r)，于是异或可得 x = σ ⊕ ( x′⊕ σ′)x=\sigma \oplus (x’ \oplus \sigma’)x=σ⊕(x′⊕σ′)，从而以概率 $1$ 区分 $b$

9. 若 PRF 存在，那么 IND-CCA2 安全的私钥加密方案存在。设 { Fn} , { Fn′}\{F_n\},\{F_n’\}{Fn​},{Fn′​} 是 PRF，抽样 Fk, F k ′′ F_k,F’_{k’}Fk​,Fk′′​（前者为 one time pad，后者为 MAC）。加密时随机选择 $r$，计算
   En c sk (x)=(r,   f(k,r)⊕x,  f ′( k ′,(r,   f(k,r)⊕x)))=(r,c,t)Enc_{sk}(x) = (r,\, f(k,r) \oplus x,\, f'(k’,(r,\, f(k,r) \oplus x))) = (r,c,t) Encsk​(x)=(r,f(k,r)⊕x,f′(k′,(r,f(k,r)⊕x)))=(r,c,t)

   解密时，先判断 t=?f′( k′, ( r , c ) )t \overset{?}{=} f'(k’,(r,c))t=?f′(k′,(r,c))，不满足则解密失败，从而阻止敌手利用一个合法密文做出另一个合法密文（敌手必须拥有明文的知识，才可以做出合法密文）。归约时，如果不是 IND-CCA2 的，那么要么 $(r,f(k,r)\oplus x)$ 不是 IND-CCA1 的，要么 { Fn′}\{F_n’\}{Fn′​} 不是 PRF。

公钥

1. 若 trapdoor OWP 存在，那么 IND 的公钥加密方案存在。设 { fe, fd − 1}\{f_e,f_d^{-1}\}{fe​,fd−1​} 是单向陷门置换，$B(x)$ 是其硬核。加密时随机选取 $x\leftarrow Simple(e)$，令
   $$Enc(e,\sigma )=(f(e,x),B(x)\oplus \sigma )$$

   此方案 $\Pi$ 是 IND 的（因为是公钥系统，它同时也是多消息 IND 的）。令 σ0= 0 , σ1= 1\sigma_0=0,\sigma_1=1σ0​=0,σ1​=1，归约时 A′ A’A′ 为 $A$ 提供 ( e , Y , α ← U1)(e,Y,\alpha \leftarrow U_1)(e,Y,α←U1​)，假设 $A$ 在输入 $(e,Y,B(X))$ 时输出 $b=0$ 的概率，比在输入 ( e , Y , B‾( X ) = B ( x ) ⊕ 1 )(e,Y,\overline B(X)=B(x) \oplus 1)(e,Y,B(X)=B(x)⊕1) 时输出 $b=0$ 的概率要显著的大，由于 $\alpha =B(X)\oplus b$，因此 A′ A’A′ 输出 $b\oplus \alpha$ 作为对 $B(X)$ 的回应。

2. 更高效的 IND 的公钥加密方案：设 { fe, fd − 1}\{f_e,f_d^{-1}\}{fe​,fd−1​} 是单向陷门置换，$B(x)$ 是其硬核。加密时随机选取 x0← S i m p l e ( e )x_0 \leftarrow Simple(e)x0​←Simple(e)，类似 PRG 的构造，
   x j+1 =f(e, x j),  τ j=B( x j)⊕ σ jx_{j+1}=f(e,x_j),\, \tau_j = B(x_j) \oplus \sigma_j xj+1​=f(e,xj​),τj​=B(xj​)⊕σj​

   输出 E n c ( e , σ ) = ( xl, τ0⋯ τ l − 1)Enc(e,\sigma) = (x_l, \tau_0\cdots \tau_{l-1})Enc(e,σ)=(xl​,τ0​⋯τl−1​)，其中 $|\sigma |=l$。归约中把 c0, c1 c_0,c_1c0​,c1​ 计算不可区分，转化为 G ( x0) , Ut G(x_0),U_tG(x0​),Ut​ 计算不可区分，然后类似 PRG 的证明，使用混合技术。

3. 若 trapdoor OWP 存在，那么 IND-CPA 的公钥加密存在。第 1 条的 $Enc(e,\sigma )=(f(e,x),B(x)\oplus \sigma )$ 的构造，就是 IND-CPA 的（自然是 IND–Multiple 的），trapdoor OWP + One time pad -> IND-CPA。这不是 IND-CCA2 的，敌手发送挑战 ( σ0= 0 , σ1= 1 )(\sigma_0=0,\sigma_1=1)(σ0​=0,σ1​=1) 获得回应 $(y,c)$，以 $(y,c\oplus 1)$ 询问解密预言机得到 σ′ \sigma’σ′，比较 σ′⊕ 1 = σb \sigma’\oplus 1=\sigma_bσ′⊕1=σb​ 从而区分出 $b$。它不一定是 IND-CCA1 的，除非 { Fn, Fn − 1}\{F_n,F_n^{-1}\}{Fn​,Fn−1​} 是 strong OWF。

4. 若 NIZKP 存在，那么 IND 的公钥加密方案可以提升到 IND-CCA1、IND-CCA2。这里的 NIZKP 用于约束敌手确实知道某密文的明文知识，从而解密预言机对敌手无帮助。定义双加密的关系（确保敌手知道随机带 s0, s1 s_0,s_1s0​,s1​ 的知识）
   R={(( e 0, e 1, c 0, c 1),(x, s 0, s 1)):  c 0=En c e0 (x; s 0),  c 1=En c e1 (x; s 1)}R=\{ ((e_0,e_1,c_0,c_1),(x,s_0,s_1)):\, c_0=Enc_{e_0}(x;s_0),\, c_1=Enc_{e_1}(x;s_1) \} R={((e0​,e1​,c0​,c1​),(x,s0​,s1​)):c0​=Ence0​​(x;s0​),c1​=Ence1​​(x;s1​)}

   令

   <P,V> 是 NIZKP 的双方，$r$ 是 CRS。调用 IND 的 Π′ \Pi’Π′ 的 G e n′ Gen’Gen′ 两次，公钥是 ( e0, e1, r )(e_0,e_1,r)(e0​,e1​,r)，私钥是 ( d0, d1, r )(d_0,d_1,r)(d0​,d1​,r)，加密过程中选择随机数 s0, s1 s_0,s_1s0​,s1​，计算
   c 0=En c e0 (x; s 0)c 1=En c e1 (x; s 1) π←P(( e 0, e 1, c 0, c 1),(x, s 0, s 1),r)\begin{aligned} &c_0 = Enc_{e_0}(x;s_0)\\ &c_1 = Enc_{e_1}(x;s_1)\\ &\pi \leftarrow P((e_0,e_1,c_0,c_1),(x,s_0,s_1),r) \end{aligned} ​c0​=Ence0​​(x;s0​)c1​=Ence1​​(x;s1​)π←P((e0​,e1​,c0​,c1​),(x,s0​,s1​),r)​

   输出 E n c p k( x ) = ( c0, c1, π )Enc_{pk}(x) = (c_0,c_1,\pi)Encpk​(x)=(c0​,c1​,π)，在解密时先验证 V ( π , ( e0, e1, c0, c1) , r ) = 1V(\pi,(e_0,e_1,c_0,c_1),r)=1V(π,(e0​,e1​,c0​,c1​),r)=1，然后再解密 x = D e c d 0′( c0) = D e c d 1′( c1)x=Dec’_{d_0}(c_0)=Dec’_{d_1}(c_1)x=Decd0​′​(c0​)=Decd1​′​(c1​)

5. RO 模型下，基于单向陷门置换和 IND 安全的对称加密方案，高效的 IND-CPA 公钥加密方案。令 $H$ 是 Hash 函数（归约时被 Random Oracle 取代）， { Fn, Fn − 1}\{F_n,F_n^{-1}\}{Fn​,Fn−1​} 是 trapdoor OWP， Π′ \Pi’Π′ 是 IND 的私钥加密方案，加密时随机选择 $x$，计算
   y=F(pk,x),  k ′=H(x)y=F(pk,x),\, k’=H(x) y=F(pk,x),k′=H(x)

   输出 E n c ( p k , m ) = ( y ,  E n c′( k′, m ) )Enc(pk,m) = (y,\, Enc'(k’,m))Enc(pk,m)=(y,Enc′(k′,m))，除了计算 k′ k’k′ 速度较慢，执行对称加密 E n c ( k′, m )Enc(k’,m)Enc(k′,m) 时速度很快。归约时，要么 OWP 被求逆，要么 Priv-IND 被区分。

6. RO 模型下，基于单向陷门置换和 IND-CCA 安全的对称加密方案，高效的 IND-CCA 公钥加密方案。与第 5 条完全相同，除了将 Π′ \Pi’Π′ 提升为 IND-CCA 的私钥加密方案。

7. RSA 方案：简单输出 E n c ( e , x ) = xe( modN )Enc(e,x)=x^e \pmod{N}Enc(e,x)=xe(modN)，确定性加密算法，不是 IND 的。

8. Padded RSA 方案：对于 $|x|=l$，随机选择 r ∈ { 0 , 1 } ∣ N ∣ − l − 1 r \in \{0,1\}^{|N|-l-1}r∈{0,1}∣N∣−l−1，设置 E n c ( e , x ) = ( r ∥ x )e( modN )Enc(e,x)=(r\|x)^e \pmod{N}Enc(e,x)=(r∥x)e(modN)。在 RSA 假设下，如果 $l=O(\log N)$，这是 IND-CPA 的。

9. ElGamal 方案：私钥 $d=x$，公钥 e = ( G , q , g , h = gx)e=(G,q,g,h=g^x)e=(G,q,g,h=gx)， E n c ( e , x ) = ( gr, hr⋅ m )Enc(e,x)=(g^r,h^r \cdot m)Enc(e,x)=(gr,hr⋅m)， D e c ( d , c ) = c2/ c1x Dec(d,c)=c_2/c_1^xDec(d,c)=c2​/c1x​。在 DDH 假设下，这是 IND-CPA 的。归约过程中，将 ( g , gx, gy, gz)(g,g^x,g^y,g^z)(g,gx,gy,gz) 转化为 c = ( gy, gz⋅ mb)c=(g^y,g^z \cdot m_b)c=(gy,gz⋅mb​)，我们认为 gz≠ g x y g^z \neq g^{xy}gz​=gxy 时 $c$ 就是真随机数。

10. Gramer-shoup 方案：循环群 $G$ 随机元 g1, g2 g_1,g_2g1​,g2​，令 d = g1 x 1g2 x 2,  f = g1 y 1gs y 2,  h = g1z d=g_1^{x_1}g_2^{x_2},\, f=g_1^{y_1}g_s^{y_2},\, h=g_1^zd=g1x1​​g2x2​​,f=g1y1​​gsy2​​,h=g1z​，设置私钥 ( x1, x2, y1, y2, z )(x_1,x_2,y_1,y_2,z)(x1​,x2​,y1​,y2​,z)，公钥 ( g1, g2, d , f , h )(g_1,g_2,d,f,h)(g1​,g2​,d,f,h)，加密时先生成随机数 $r$，然后计算
    u 1= g 1 r,  u 2= g 2 r,   e= h r⋅m α=H( u 1, u 2,e),   v= d r f rα u_1=g_1^r,\, u_2=g_2^r,\, e=h^r \cdot m\\ \alpha=H(u_1,u_2,e),\, v=d^rf^{r\alpha} u1​=g1r​,u2​=g2r​,e=hr⋅mα=H(u1​,u2​,e),v=drfrα
    输出 E n c p k( m ) = ( u1, u2, e , v )Enc_{pk}(m)=(u_1,u_2,e,v)Encpk​(m)=(u1​,u2​,e,v)，解密时先验证 v = u1 x1+ y1αu2 x2+ y2α v=u_1^{x_1+y_1\alpha}u_2^{x_2+y_2\alpha}v=u1x1​+y1​α​u2x2​+y2​α​，然后才解密 m = e / u1z m=e/u_1^zm=e/u1z​
    这是 ElGamal + NIZKP 的形式，确保敌手知道随机带 $r$ 的知识。设 $H$ 是 Hash 函数（ZKP 的无偏挑战发生器），在 DDH 假设下，它是 IND-CCA2 的。归约时， A′ A’A′ 将 ( g1, g2, u1, u2)(g_1,g_2,u_1,u_2)(g1​,g2​,u1​,u2​) 转化为 p k = ( g1, g2, d , f , h′= g1 z 1g2 z 2)pk=(g_1,g_2,d,f,h’=g_1^{z_1}g_2^{z_2})pk=(g1​,g2​,d,f,h′=g1z1​​g2z2​​) 交给 $A$，如果 log ⁡ g 1u1=log ⁡ g 2u2 \log_{g_1}u_1 = \log_{g_2}u_2logg1​​u1​=logg2​​u2​ 那么 h′≡ hh’ \equiv hh′≡h 同分布，如果 log ⁡ g 1u1≠log ⁡ g 2u2 \log_{g_1}u_1 \neq \log_{g_2}u_2logg1​​u1​​=logg2​​u2​ 那么对于任意的 $m$ 总存在 ( z1, z2)(z_1,z_2)(z1​,z2​) 使得 e = ( h′)r⋅ me=(h’)^r \cdot me=(h′)r⋅m（完美保密的，$A$ 区分优势为 $0$）。

11. ROM 下基于 CDH 和 Priv-IND 的 IND-CPA 公钥加密方案： p k = ( g , gx) , s k = xpk=(g,g^x),sk=xpk=(g,gx),sk=x，加密为 E n c p k( m ) = ( gr, E n c′( H ( hr) , m ) )Enc_{pk}(m)=(g^r,Enc'(H(h^r),m))Encpk​(m)=(gr,Enc′(H(hr),m))

Signature

1. 分块签名：设 Π′ \Pi’Π′ 是长度为 $l$ 的签名方案，构造一般签名方案 $\Pi$ 如下：

   • 将 $m$ 分成 $t$ 块 m 1∥⋯∥ m tm_1\|\cdots\|m_t m1​∥⋯∥mt​，其中 ∣ m i∣=l/4|m_i|=l/4 ∣mi​∣=l/4，可能需要 Padding 1 0 ∗10^* 10∗
   • 随机选择 r← U l/4 r \leftarrow U_{l/4} r←Ul/4​，计算 σ i=Sig n sk′(r,t,i, m i)\sigma_i = Sign’_{sk}(r,t,i,m_i) σi​=Signsk′​(r,t,i,mi​)，输出 Sig n sk (m)=(r,t, σ 1,⋯   , σ t)Sign_{sk}(m)=(r,t,\sigma_1,\cdots,\sigma_t) Signsk​(m)=(r,t,σ1​,⋯,σt​)

   归约很简单，一旦给出 $\Pi$ 的伪造，那么就有一个 σi \sigma_iσi​ 是对 Π′ \Pi’Π′ 的伪造。

2. 基于 CRHF 将长度受限签名方案，扩展到一般签名方案。设 { Hs}\{H_s\}{Hs​} 是 CRHF， Π′ \Pi’Π′ 是长度受限的签名方案，那么令 s k = ( s , s k′) ,  v k = ( s , v k′)sk=(s,sk’),\, vk=(s,vk’)sk=(s,sk′),vk=(s,vk′)，签名算法为
   Sig n sk (m)=Sig n s k ′′( H s(m))Sign_{sk}(m) = Sign’_{sk’}(H_s(m)) Signsk​(m)=Signsk′′​(Hs​(m))

   归约时， A′ A’A′ 成功，仅当 $A$ 成功且 Hs H_sHs​ 没发生碰撞。于是 P r [ E x p tA= 1 ] ≤ P r [ E x p t A ′= 1 ] + P r [ C o l l ]Pr[Expt_A=1]\le Pr[Expt_{A’}=1]+Pr[Coll]Pr[ExptA​=1]≤Pr[ExptA′​=1]+Pr[Coll]，若 $\Pi$ 不安全，则 Π′, Hs \Pi’,H_sΠ′,Hs​ 至少有一个被攻破。

3. 基于抗第二原像 Hash 函数（SPRHF）将长度受限签名方案，扩展到一般签名方案。将 Hs H_sHs​ 在签名时才随机选择，可降低要求。签名算法为
   Sig n sk (m)=(Sig n s k ′′( H s(m)),   s),   s←I( 1 λ)Sign_{sk}(m) = (Sign’_{sk’}(H_s(m)),\, s),\, s \leftarrow I(1^\lambda) Signsk​(m)=(Signsk′′​(Hs​(m)),s),s←I(1λ)

   类似的， A′ A’A′ 成功，仅当 $A$ 成功且 Hs H_sHs​ 没被找到第二原像。

4. 若 OWF / CRHF 存在，那么安全的 one-time 签名方案存在。设 $f$ 是 OWF，随机选择 s k ∈ Ud 2 × l sk \in U_d^{2 \times l}sk∈Ud2×l​，计算 v k = [ f ( s k i j) ] i j vk=[f(sk_{ij})]_{ij}vk=[f(skij​)]ij​，签名算法为
   Sigm(sk,m)=(s km 1,1 ,   s km 2,2 ,   ⋯   ,s km l,l )Sigm(sk,m) = (sk_{m_1,1},\, sk_{m_2,2},\, \cdots, sk_{m_l,l}) Sigm(sk,m)=(skm1​,1​,skm2​,2​,⋯,skml​,l​)

5. 更高效的 one-time 签名方案：使用 PRG 缩短签名密钥，使用 Hash 函数缩短消息长度。

6. 若安全的 one-time 签名方案存在，那么 EUF-CMA 的签名方案存在。

   • 链式记忆依赖签名：令 Π′ \Pi’Π′ 是一次签名方案，签署 $j$ 个消息后，简记 ηj= S i g n s kj ′( mj, v k j + 1)\eta_j=Sign’_{sk_j}(m_j,vk_{j+1})ηj​=Signskj​′​(mj​,vkj+1​)，状态为
     state=(s k 2,( m 1,v k 2, η 1))∥⋯∥(s k j+1 ,( m j,v k j+1 , η j))state = (sk_2,(m_1,vk_2,\eta_1)) \|\cdots\| (sk_{j+1},(m_j,vk_{j+1},\eta_j)) state=(sk2​,(m1​,vk2​,η1​))∥⋯∥(skj+1​,(mj​,vkj+1​,ηj​))

     签署第 $j+1$ 个消息时，先 ( s k j + 2, v k j + 2) ← G e n ( 1λ)(sk_{j+2},vk_{j+2}) \leftarrow Gen(1^\lambda)(skj+2​,vkj+2​)←Gen(1λ)，然后计算 η j + 1 \eta_{j+1}ηj+1​，并在签名中加上 $O(j)$ 的 history，
     σ=( m 1,v k 2, η 1)∥⋯∥( m j,v k j+1 , η j)∥( m j+1 ,v k j+2 , η j+1 )\sigma = (m_1,vk_2,\eta_1)\|\cdots\|(m_j,vk_{j+1},\eta_j)\|(m_{j+1},vk_{j+2},\eta_{j+1}) σ=(m1​,vk2​,η1​)∥⋯∥(mj​,vkj+1​,ηj​)∥(mj+1​,vkj+2​,ηj+1​)

     设置 s t a t e = s t a t e ∥ ( s k j + 2, ( m j + 1, v k j + 2, η j + 1) )state = state\|(sk_{j+2},(m_{j+1},vk_{j+2},\eta_{j+1}))state=state∥(skj+2​,(mj+1​,vkj+2​,ηj+1​))

   • 二叉树记忆依赖签名：

     • 把链式结构变为二叉树：每个节点 node 上记录自己的公私钥 s k n o d e, v k n o d e sk_{node},vk_{node}sknode​,vknode​ 和 S i g n ( s k n o d e, m n o d e, v k n o d e . L, v k n o d e . R)Sign(sk_{node},m_{node},vk_{node.L},vk_{node.R})Sign(sknode​,mnode​,vknode.L​,vknode.R​)，签名中含有 $O(\log j)$ 的 history。随着签名数量增加，状态树越来越深。

     • 分离消息签名和密钥认证：预设二叉树深度 $L$，每个中间节点 node 上记录自己的公私钥 s k n o d e, v k n o d e sk_{node},vk_{node}sknode​,vknode​ 和 S i g n ( s k n o d e, v k n o d e . L, v k n o d e . R)Sign(sk_{node},vk_{node.L},vk_{node.R})Sign(sknode​,vknode.L​,vknode.R​)，每个叶子节点上的公私钥 s k n o d e, v k n o d e sk_{node},vk_{node}sknode​,vknode​ 用于签名验签。签名中不含签名历史，含有 $O(L)$ 个认证。可以动态生成叶子。

   • 一般的二叉树签名：为了不维护状态，需要使用 PRF 来重构确定的随机状态。生成 s k = ( s k′, s ) , v k = v k′ sk=(sk’,s),vk=vk’sk=(sk′,s),vk=vk′，对于每个中间节点 node 计算随机带 r = fs( n o d e ) , r0= fs( n o d e . L ) , r1= fs( n o d e . R )r=f_s(node),r_0=f_s(node.L),r_1=f_s(node.R)r=fs​(node),r0​=fs​(node.L),r1​=fs​(node.R)（这里的 $r$ 是有必要固定下来的，因为 Π′ \Pi’Π′ 是 one-time 的，同样的消息和不同的随机带，可视作不同的消息），然后
     (s k node.L ,   v k node.L )←Ge n ′( 1 λ; r 0) (s k node.R ,   v k node.R )←Ge n ′( 1 λ; r 1)η node =Sig n ′(s k node ,   (v k node.L ,v k node.R );r) aut h node =(v k node.L ,v k node.R , η node )(sk_{node.L},\, vk_{node.L}) \leftarrow Gen'(1^\lambda;r_0)\\ (sk_{node.R},\, vk_{node.R}) \leftarrow Gen'(1^\lambda;r_1)\\ \eta_{node} = Sign'(sk_{node},\, (vk_{node.L},vk_{node.R});r)\\ auth_{node} = (vk_{node.L},vk_{node.R},\eta_{node}) (sknode.L​,vknode.L​)←Gen′(1λ;r0​)(sknode.R​,vknode.R​)←Gen′(1λ;r1​)ηnode​=Sign′(sknode​,(vknode.L​,vknode.R​);r)authnode​=(vknode.L​,vknode.R​,ηnode​)

     最后到达一个未使用过的叶子 leaf，输出 S i g n s k( m ) = ( l e a f , a u t h r o o t, ⋯  , a u t h l e a f . p a r e n t, S i g n′( s k l e a f, m ) )Sign_{sk}(m) = (leaf,auth_{root}, \cdots,auth_{leaf.parent}, Sign'(sk_{leaf},m))Signsk​(m)=(leaf,authroot​,⋯,authleaf.parent​,Sign′(skleaf​,m))

7. 若 EUF-CMA 的非确定性签名方案存在，那么 EUF-CMA 的确定性签名方案存在。设 Π′ \Pi’Π′ 是 S i g n ( s k , m ; Un)Sign(sk,m;U_n)Sign(sk,m;Un​) 的非确定性签名，令 { Fn}n \{F_n\}_n{Fn​}n​ 是 PRF，构造 $\Pi$ 中的确定性签名为 S i g n ( s k , m , Fk( m ) )Sign(sk,m,F_k(m))Sign(sk,m,Fk​(m))。归约时，先构造 Π ′ ′ \Pi”Π′′ 为 $Sign(sk,m;f(m))$，先证明 Π≡cΠ ′ ′ \Pi \overset{c}{\equiv} \Pi”Π≡cΠ′′（因为 Fn ≡cR Fn F_n \overset{c}{\equiv} RF_nFn​≡cRFn​ ），再将 Π′ \Pi’Π′ 归约到 Π ′ ′ \Pi”Π′′ 上（类似 RO，使用一个字典 QS Q_SQS​ 记录第一次对 mi m_imi​ 的签名结果 QS[ mi] = S i g n ( s k , mi; r )Q_S[m_i] = Sign(sk,m_i;r)QS​[mi​]=Sign(sk,mi​;r)，后续的 mj= mi m_j=m_imj​=mi​ 的询问使用 QS[ mj]Q_S[m_j]QS​[mj​] 来回应）

8. 安全的签名方案存在 $⟺$ OWF 存在。设 $\Pi$ 是安全签名方案，那么 f ( s k , m , S i g n s k( m ; r ) , r ) = ( m , S i g n s k( m ; r ) )f(sk,m,Sign_{sk}(m;r),r)=(m,Sign_{sk}(m;r))f(sk,m,Signsk​(m;r),r)=(m,Signsk​(m;r)) 就是 OWF。

9. ROM 下，基于 trapdoor OWP 的签名方案：设 { Fs, Fs − 1}\{F_s,F_s^{-1}\}{Fs​,Fs−1​} 是单向陷门置换， H : { 0 , 1 }∗→ { 0 , 1 }l H:\{0,1\}^* \to \{0,1\}^lH:{0,1}∗→{0,1}l 是随机预言机，那么签名算法为
   Sig n sk (m)= F −1 (sk,H(m))Sign_{sk}(m) = F^{-1}(sk,H(m)) Signsk​(m)=F−1(sk,H(m))

   归约思路：单向性 $<$ 交互单向性 $<$ ROM 下不可伪造性。

10. RSA 方案：很简单，签名就是 S i g n ( d , m ) = md( modN )Sign(d,m)=m^d \pmod{N}Sign(d,m)=md(modN)，验签 m=?σe( modN )m\overset{?}{=}\sigma^e\pmod{N}m=?σe(modN)

11. Hashed RSA 方案：令 $H$ 是 RO，$vk=(e,s),sk=(d,s)$，签名变为 S i g n s k( m ) = hs( m )d( modN )Sign_{sk}(m)=h_s(m)^d\pmod NSignsk​(m)=hs​(m)d(modN)

12. Probabilistic RSA 方案：签名时先随机选取 $r$，然后计算 S i g n s k( m ) = hs( r ∥ m )d( modN )Sign_{sk}(m)=h_s(r\|m)^d\pmod NSignsk​(m)=hs​(r∥m)d(modN)

13. ElGamal 方案：设 $H$ 是 CRHF，设置 s k = x , v k = ( p , g , y = gx)sk=x,vk=(p,g,y=g^x)sk=x,vk=(p,g,y=gx)，签名
    Sig n sk (m)= ( r = gk( modp ) , s = ( H ( m ) − x r ) k − 1( modp − 1 ) )Sign_{sk}(m)=\left(r=g^k\pmod{p}, s=(H(m)-xr)k^{-1}\pmod{p-1}\right) Signsk​(m)=(r=gk(modp),s=(H(m)−xr)k−1(modp−1))

    验签 V e r v k( m , ( r , s ) ) = 1   ⟺   yrrs= g H ( m )( modp )Ver_{vk}(m,(r,s))=1 \iff y^rr^s=g^{H(m)}\pmod{p}Vervk​(m,(r,s))=1⟺yrrs=gH(m)(modp)