文章目录

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

Encryption

私钥

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

2. 准一次一密：设 GGG 是 PRG，Enc(s,m)=G(s)⊕mEnc(s,m)=G(s) \oplus mEnc(s,m)=G(s)⊕m，密钥不可重用。

3. 若 PRF 存在，那么多消息 IND 的私钥加密方案存在。设 {Fs}\{F_s\}{Fs​} 是 PRF。加密时随机选取 rrr，令
   Enc(s,m)=(r,Fs(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 与 RFn(r)⊕mRF_n(r) \oplus mRFn​(r)⊕m 计算不可区分，RFn(r)⊕mRF_n(r) \oplus mRFn​(r)⊕m 与 Un⊕mU_{n} \oplus mUn​⊕m 计算不可区分， Un⊕mU_n \oplus mUn​⊕m 与 UnU_nUn​ 统计不可区分，于是 ExptA,ΠIND(1n,U1)Expt_{A,\Pi}^{IND}(1^n,U_1)ExptA,ΠIND​(1n,U1​) 的优势 AdvAdvAdv 可忽略。

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

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

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

6. 若 PRF 存在，那么 IND-CPA 的私钥加密方案存在。第 3 条的 Enc(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。归约证明时，用 RFnRF_nRFn​ 替换 FnF_nFn​，得到的方案是 IND-CPA 的。如果使用 FnF_nFn​ 时它不是 IND-CPA 的，那么就可以区分 Fn,RFnF_n,RF_nFn​,RFn​

7. 若 PRF 存在，任意 IND 的私钥加密方案都可以提升到 IND-CPA。第 4 条的 Enc(k,x)=(r,Enc′(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 条的 Enc(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′⊕σ′)，从而以概率 111 区分 bbb

9. 若 PRF 存在，那么 IND-CCA2 安全的私钥加密方案存在。设 {Fn},{Fn′}\{F_n\},\{F_n'\}{Fn​},{Fn′​} 是 PRF，抽样 Fk,Fk′′F_k,F'_{k'}Fk​,Fk′′​（前者为 one time pad，后者为 MAC）。加密时随机选择 rrr，计算
   Encsk(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)⊕x)(r,\, f(k,r) \oplus x)(r,f(k,r)⊕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)B(x)B(x) 是其硬核。加密时随机选取 x←Simple(e)x \leftarrow Simple(e)x←Simple(e)，令
   Enc(e,σ)=(f(e,x),B(x)⊕σ)Enc(e,\sigma) = (f(e,x),\, B(x) \oplus \sigma) Enc(e,σ)=(f(e,x),B(x)⊕σ)

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

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

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

3. 若 trapdoor OWP 存在，那么 IND-CPA 的公钥加密存在。第 1 条的 Enc(e,σ)=(f(e,x),B(x)⊕σ)Enc(e,\sigma) = (f(e,x),\, B(x) \oplus \sigma)Enc(e,σ)=(f(e,x),B(x)⊕σ) 的构造，就是 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)(y,c)，以 (y,c⊕1)(y,c\oplus 1)(y,c⊕1) 询问解密预言机得到 σ′\sigma'σ′，比较 σ′⊕1=σb\sigma'\oplus 1=\sigma_bσ′⊕1=σb​ 从而区分出 bbb。它不一定是 IND-CCA1 的，除非 {Fn,Fn−1}\{F_n,F_n^{-1}\}{Fn​,Fn−1​} 是 strong OWF。

4. 若 NIZKP 存在，那么 IND 的公钥加密方案可以提升到 IND-CCA1、IND-CCA2。这里的 NIZKP 用于约束敌手确实知道某密文的明文知识，从而解密预言机对敌手无帮助。定义双加密的关系（确保敌手知道随机带 s0,s1s_0,s_1s0​,s1​ 的知识）
   R={((e0,e1,c0,c1),(x,s0,s1)):c0=Ence0(x;s0),c1=Ence1(x;s1)}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​)}

   令 是 NIZKP 的双方，rrr 是 CRS。调用 IND 的 Π′\Pi'Π′ 的 Gen′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,s1s_0,s_1s0​,s1​，计算
   c0=Ence0(x;s0)c1=Ence1(x;s1)π←P((e0,e1,c0,c1),(x,s0,s1),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)​

   输出 Encpk(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=Decd0′(c0)=Decd1′(c1)x=Dec'_{d_0}(c_0)=Dec'_{d_1}(c_1)x=Decd0​′​(c0​)=Decd1​′​(c1​)

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

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

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

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

8. Padded RSA 方案：对于 ∣x∣=l|x|=l∣x∣=l，随机选择 r∈{0,1}∣N∣−l−1r \in \{0,1\}^{|N|-l-1}r∈{0,1}∣N∣−l−1，设置 Enc(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)l=O(\log N)l=O(logN)，这是 IND-CPA 的。

9. ElGamal 方案：私钥 d=xd=xd=x，公钥 e=(G,q,g,h=gx)e=(G,q,g,h=g^x)e=(G,q,g,h=gx)，Enc(e,x)=(gr,hr⋅m)Enc(e,x)=(g^r,h^r \cdot m)Enc(e,x)=(gr,hr⋅m)，Dec(d,c)=c2/c1xDec(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≠gxyg^z \neq g^{xy}gz​=gxy 时 ccc 就是真随机数。

10. Gramer-shoup 方案：循环群 GGG 随机元 g1,g2g_1,g_2g1​,g2​，令 d=g1x1g2x2,f=g1y1gsy2,h=g1zd=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)，加密时先生成随机数 rrr，然后计算
    u1=g1r,u2=g2r,e=hr⋅mα=H(u1,u2,e),v=drfrα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α
    输出 Encpk(m)=(u1,u2,e,v)Enc_{pk}(m)=(u_1,u_2,e,v)Encpk​(m)=(u1​,u2​,e,v)，解密时先验证 v=u1x1+y1αu2x2+y2αv=u_1^{x_1+y_1\alpha}u_2^{x_2+y_2\alpha}v=u1x1​+y1​α​u2x2​+y2​α​，然后才解密 m=e/u1zm=e/u_1^zm=e/u1z​
    这是 ElGamal + NIZKP 的形式，确保敌手知道随机带 rrr 的知识。设 HHH 是 Hash 函数（ZKP 的无偏挑战发生器），在 DDH 假设下，它是 IND-CCA2 的。归约时，A′A'A′ 将 (g1,g2,u1,u2)(g_1,g_2,u_1,u_2)(g1​,g2​,u1​,u2​) 转化为 pk=(g1,g2,d,f,h′=g1z1g2z2)pk=(g_1,g_2,d,f,h'=g_1^{z_1}g_2^{z_2})pk=(g1​,g2​,d,f,h′=g1z1​​g2z2​​) 交给 AAA，如果 log⁡g1u1=log⁡g2u2\log_{g_1}u_1 = \log_{g_2}u_2logg1​​u1​=logg2​​u2​ 那么 h′≡hh' \equiv hh′≡h 同分布，如果 log⁡g1u1≠log⁡g2u2\log_{g_1}u_1 \neq \log_{g_2}u_2logg1​​u1​​=logg2​​u2​ 那么对于任意的 mmm 总存在 (z1,z2)(z_1,z_2)(z1​,z2​) 使得 e=(h′)r⋅me=(h')^r \cdot me=(h′)r⋅m（完美保密的，AAA 区分优势为 000）。

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

Signature

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

   • 将 mmm 分成 ttt 块 m1∥⋯∥mtm_1\|\cdots\|m_tm1​∥⋯∥mt​，其中 ∣mi∣=l/4|m_i|=l/4∣mi​∣=l/4，可能需要 Padding 10∗10^*10∗
   • 随机选择 r←Ul/4r \leftarrow U_{l/4}r←Ul/4​，计算 σi=Signsk′(r,t,i,mi)\sigma_i = Sign'_{sk}(r,t,i,m_i)σi​=Signsk′​(r,t,i,mi​)，输出 Signsk(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'Π′ 是长度受限的签名方案，那么令 sk=(s,sk′),vk=(s,vk′)sk=(s,sk'),\, vk=(s,vk')sk=(s,sk′),vk=(s,vk′)，签名算法为
   Signsk(m)=Signsk′′(Hs(m))Sign_{sk}(m) = Sign'_{sk'}(H_s(m)) Signsk​(m)=Signsk′′​(Hs​(m))

   归约时，A′A'A′ 成功，仅当 AAA 成功且 HsH_sHs​ 没发生碰撞。于是 Pr[ExptA=1]≤Pr[ExptA′=1]+Pr[Coll]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）将长度受限签名方案，扩展到一般签名方案。将 HsH_sHs​ 在签名时才随机选择，可降低要求。签名算法为
   Signsk(m)=(Signsk′′(Hs(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′ 成功，仅当 AAA 成功且 HsH_sHs​ 没被找到第二原像。

4. 若 OWF / CRHF 存在，那么安全的 one-time 签名方案存在。设 fff 是 OWF，随机选择 sk∈Ud2×lsk \in U_d^{2 \times l}sk∈Ud2×l​，计算 vk=[f(skij)]ijvk=[f(sk_{ij})]_{ij}vk=[f(skij​)]ij​，签名算法为
   Sigm(sk,m)=(skm1,1,skm2,2,⋯,skml,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'Π′ 是一次签名方案，签署 jjj 个消息后，简记 ηj=Signskj′(mj,vkj+1)\eta_j=Sign'_{sk_j}(m_j,vk_{j+1})ηj​=Signskj​′​(mj​,vkj+1​)，状态为
     state=(sk2,(m1,vk2,η1))∥⋯∥(skj+1,(mj,vkj+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+1j+1j+1 个消息时，先 (skj+2,vkj+2)←Gen(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)O(j)O(j) 的 history，
     σ=(m1,vk2,η1)∥⋯∥(mj,vkj+1,ηj)∥(mj+1,vkj+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​)

     设置 state=state∥(skj+2,(mj+1,vkj+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 上记录自己的公私钥 sknode,vknodesk_{node},vk_{node}sknode​,vknode​ 和 Sign(sknode,mnode,vknode.L,vknode.R)Sign(sk_{node},m_{node},vk_{node.L},vk_{node.R})Sign(sknode​,mnode​,vknode.L​,vknode.R​)，签名中含有 O(log⁡j)O(\log j)O(logj) 的 history。随着签名数量增加，状态树越来越深。

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

   • 一般的二叉树签名：为了不维护状态，需要使用 PRF 来重构确定的随机状态。生成 sk=(sk′,s),vk=vk′sk=(sk',s),vk=vk'sk=(sk′,s),vk=vk′，对于每个中间节点 node 计算随机带 r=fs(node),r0=fs(node.L),r1=fs(node.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)（这里的 rrr 是有必要固定下来的，因为 Π′\Pi'Π′ 是 one-time 的，同样的消息和不同的随机带，可视作不同的消息），然后
     (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)(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，输出 Signsk(m)=(leaf,authroot,⋯,authleaf.parent,Sign′(skleaf,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. 安全的签名方案存在 ⟺\iff⟺ OWF 存在。设 Π\PiΠ 是安全签名方案，那么 f(sk,m,Signsk(m;r),r)=(m,Signsk(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。

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

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

9. RSA 方案：很简单，签名就是 Sign(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)

10. Hashed RSA 方案：令 HHH 是 RO，vk=(e,s),sk=(d,s)vk=(e,s),sk=(d,s)vk=(e,s),sk=(d,s)，签名变为 Signsk(m)=hs(m)d(modN)Sign_{sk}(m)=h_s(m)^d\pmod NSignsk​(m)=hs​(m)d(modN)

11. Probabilistic RSA 方案：签名时先随机选取 rrr，然后计算 Signsk(m)=hs(r∥m)d(modN)Sign_{sk}(m)=h_s(r\|m)^d\pmod NSignsk​(m)=hs​(r∥m)d(modN)

12. ElGamal 方案：设 HHH 是 CRHF，设置 sk=x,vk=(p,g,y=gx)sk=x,vk=(p,g,y=g^x)sk=x,vk=(p,g,y=gx)，签名
    Signsk(m)=(r=gk(modp),s=(H(m)−xr)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))

    验签 Vervk(m,(r,s))=1⟺yrrs=gH(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)

MAC

1. 若 PRF 存在，那么 EUF-CMA 的长度受限的 MAC 存在。令 {Fk:{0,1}l→{0,1}t}\{F_k:\{0,1\}^l \to \{0,1\}^t\}{Fk​:{0,1}l→{0,1}t} 是PRF，那么 Mac(k,m)=Fk(m)Mac(k,m)=F_k(m)Mac(k,m)=Fk​(m)。安全归约时，伪造 (m,tag)(m,tag)(m,tag) 就是对 Fk(m)F_k(m)Fk​(m) 的预测。

2. 若长度受限的 MAC 存在，那么任意长度的一般 MAC 存在。类似签名的扩展方案，分块、CRHF、SPRHF。

3. Enc-and-MAC 是 INT-PTXT 的，不是 IND-CPA 的，不是 INT-CTXT 的。由于 MAC 是确定性函数，因此 CPA 下两个不同消息的密文很容易区分，只需调用一次加密 Oracle 即可。MAC 没作用在密文上，IND-CPA 的加密方案不满足 INT-CTXT。安全的 MAC 本身就是 INT-PTXT 的。

4. MAC-then-Enc 是 IND-CPA 的，是 INT-PTXT 的，但不是 INT-CTXT 的。内层是安全的 MAC，因此明显是 INT-PTXT 的。最外层是 IND-CPA 的加密方案，因此明显是 IND-CPA 的。然而，假设密文形如 (r,c,d)(r,c,d)(r,c,d)，其中 ddd 是冗余项不参与解密运算，那么构造 (r,c,d′≠d)(r,c,d'\neq d)(r,c,d′​=d) 就得到了一个伪造的密文。

5. Enc-then-MAC 是 IND-CCA2 的，且是 INT-PTXT / INT-CTXT 的。由于密文上 MAC 的不可伪造性，使得敌手无法从解密预言机中获取知识，因此 CPA 等价于 CCA2。