OWF

设 III 是多项式可列举的指标集，若 fff 是 III 上的非全域（弱）单向函数，令
g(x):=f(x′),g′(x):=f(x′)∥x′′g(x):=f(x'),\, g'(x):= f(x')\|x'' g(x):=f(x′),g′(x):=f(x′)∥x′′

其中 x=x′∥x′′∈{0,1}∗x=x'\|x'' \in \{0,1\}^*x=x′∥x′′∈{0,1}∗，且 ∣x′∣=max⁡{n∈I:n≤∣x∣}|x'|=\max\{n \in I:n \le |x|\}∣x′∣=max{n∈I:n≤∣x∣}

那么 g,g′g,g'g,g′ 都是全域（弱）单向函数。默认（弱）单向函数是全域的。
设 fff 是（弱）单向函数，某多项式 p(⋅)p(\cdot)p(⋅) 满足 ∣f(x)∣≤p(∣x∣)|f(x)| \le p(|x|)∣f(x)∣≤p(∣x∣)，令
f′(x):=f(x)∥1∥0p(∣x∣)−∣f(x)∣∈{0,1}p(∣x∣)+1f′′(x):=f′(x′),x=x′∥x′′,∣x∣=p(∣x′∣)+1\begin{aligned} f'(x) &:= f(x) \| 1 \| 0^{p(|x|)-|f(x)|} \in \{0,1\}^{p(|x|)+1} \\ f''(x) &:= f'(x'),\, x=x'\|x'',\,|x| = p(|x'|)+1 \end{aligned} f′(x)f′′(x):=f(x)∥1∥0p(∣x∣)−∣f(x)∣∈{0,1}p(∣x∣)+1:=f′(x′),x=x′∥x′′,∣x∣=p(∣x′∣)+1

那么 f′f'f′ 是长度正则的（弱）单向函数，f′′f''f′′ 是保长的（弱）单向函数。默认（弱）单向函数是保长的。
存在不是单向函数的弱单向函数。设 fff 是单向函数，令
g(x)={x′∥f(x′′),x′=0log⁡2nx′∥x′′,x′≠0log⁡2ng(x) = \left\{ \begin{aligned} x'&\|f(x''), && x' = 0^{\log_2 n}\\ x'&\|x'', && x' \neq 0^{\log_2 n}\\ \end{aligned} \right. g(x)={x′x′∥f(x′′),∥x′′,x′=0log2nx′=0log2n

其中 x=x′∥x′′x=x'\|x''x=x′∥x′′，x∈{0,1}nx \in \{0,1\}^nx∈{0,1}n，x′∈{0,1}log⁡2nx'\in \{0,1\}^{\log_2 n}x′∈{0,1}log2n，那么最多只有占比 1/n1/n1/n 的实例是难以求逆的。

那么 ggg 不是单向函数，可以证明它是弱单向函数。
单向函数存在 ⟺\iff⟺ 弱单向函数存在。设 f:{0,1}n→{0,1}nf:\{0,1\}^n \to \{0,1\}^nf:{0,1}n→{0,1}n 是弱单向函数，存在多项式 t(⋅)t(\cdot)t(⋅)，使得
g(x1,⋯,xt(n))=(f(x1),⋯,f(xt(n)))g(x_1,\cdots,x_{t(n)}) = (f(x_1),\cdots,f(x_{t(n)})) g(x1,⋯,xt(n))=(f(x1),⋯,f(xt(n)))

是单向函数。基本思路就是 lim⁡n→∞(1−1/p(n))t(n)→negl(n)\underset{n \to \infty}{\lim} (1-1/p(n))^{t(n)} \to negl(n)n→∞lim(1−1/p(n))t(n)→negl(n)，但归约时更复杂些；因为敌手的策略不一定会对各分量独立选取的输入的像做回应。
单向函数存在，那么存在 O(n2)O(n^2)O(n2) 时间内可计算的单向函数。任意常数 c>2c > 2c>2，设 ggg 是可在 O(nc)O(n^c)O(nc) 时间内求解的 OWF，令
f(x′∥x′′)=x′∥g(x′′)f(x'\|x'') = x'\|g(x'') f(x′∥x′′)=x′∥g(x′′)

其中 ∣x′∣=nc−n|x'| = n^c-n∣x′∣=nc−n，∣x′′∣=n|x''|=n∣x′′∣=n，那么 ∣x∣=nc|x|=n^c∣x∣=nc，g(x)g(x)g(x) 可在 O(∣x′′∣c)=O(∣x∣2)O(|x''|^c) = O(|x|^2)O(∣x′′∣c)=O(∣x∣2) 内求解。
如果单向函数存在，那么 NP≠PNP \neq PNP=P。令 fff 是单向函数，且 ∣x∣≤p(∣f(x)∣)|x| \le p(|f(x)|)∣x∣≤p(∣f(x)∣)，定义语言
Lf:={(y,x′):∃x′′,∣x′∥x′′∣≤p(y),f(x′∥x′′)=y}L_f := \{(y,x'): \exist x'', |x'\|x''| \le p(y), f(x'\|x'')=y\} Lf:={(y,x′):∃x′′,∣x′∥x′′∣≤p(y),f(x′∥x′′)=y}

那么 Lf∈NPL_f \in NPLf∈NP，可以证明 Lf∉PL_f \not\in PLf∈P。
如果 NP≠PNP \neq PNP=P，那么存在在某些实例上难以求逆的函数。存在 L∈NP−PL \in NP-PL∈NP−P，令
f(x,w):={1∥x,(x,w)∈R(L)0∥x,(x,w)∉R(L)f(x,w) := \left\{ \begin{aligned} 1&\|x, && (x,w) \in R(L)\\ 0&\|x, && (x,w) \notin R(L)\\ \end{aligned} \right. f(x,w):={10∥x,∥x,(x,w)∈R(L)(x,w)∈/R(L)

那么 fff 是可有效计算的函数，且存在至少一点 (x,w)(x,w)(x,w) 难以求逆（最坏意义下的困难性，不一定是 OWF）。

单向函数需要平均意义下的困难性，此时 f(x,w)f(x,w)f(x,w) 就是弱单向函数了。
存在原像的任意一比特都不是硬核谓词的单向函数。设 f:{0,1}n→{0,1}nf:\{0,1\}^n \to \{0,1\}^nf:{0,1}n→{0,1}n 是单向函数，令
g(x)=f(x−j′)∥xj′∥x′′g(x) = f(x'_{-j})\|x'_j\|x'' g(x)=f(x−j′)∥xj′∥x′′

其中 ∣x′∣=n+1|x'|=n+1∣x′∣=n+1，∣x′′∣=log⁡2(n+1)|x''|=\log_2(n+1)∣x′′∣=log2(n+1)，而 xj′x_j'xj′ 表示第 jjj 比特，x−j′x'_{-j}x−j′ 表示去掉第 jjj 比特，这里 j=int(x′′)j=int(x'')j=int(x′′)

那么，ggg 的定义域被划分为 n+1n+1n+1 块，第 jjj 块的函数值泄露 x′x'x′ 的第 jjj 比特。任意确定性函数 b(x)b(x)b(x) 都不可能成为通用硬核谓词，但给定的一个单向函数可以有确定性硬核。
Goldreich-Levin 定理：存在有硬核的单向函数。设 fff 是单向函数，构造另一个单向函数
g(x,r)=f(x)∥rg(x,r) = f(x)\|r g(x,r)=f(x)∥r

其中 ∣x∣=∣r∣|x|=|r|∣x∣=∣r∣，那么 b(x,r)=(mod2)b(x,r) = \pmod 2b(x,r)=(mod2) 是 ggg 的硬核谓词。这里的 b(x,r)b(x,r)b(x,r) 是通用硬核。

归约证明时，将求逆 f(x)f(x)f(x) 的算法 BBB 归约到求解 b(x,r)b(x,r)b(x,r) 的算法 AAA 上，
- 当 Pr[A=1]=1Pr[A=1]=1Pr[A=1]=1 时，BBB 可直接调用用 nnn 次 AAA 计算 b(x,ei)b(x,e_i)b(x,ei)，从而恢复出各个分量 xix_ixi
- 当 Pr[A=1]≥1−negl(n)Pr[A=1] \ge 1-negl(n)Pr[A=1]≥1−negl(n) 时，BBB 可直接用 nnn 次随机化的 b(x,r)⊕b(x,ei⊕r)b(x,r) \oplus b(x,e_i \oplus r)b(x,r)⊕b(x,ei⊕r) 恢复出各个分量 xix_ixi
- 当 Pr[A=1]≥3/4+1/p(n)Pr[A=1] \ge 3/4+1/p(n)Pr[A=1]≥3/4+1/p(n) 时，BBB 可统计 ttt 次随机化的 b(x,r)⊕b(x,ei⊕r)b(x,r) \oplus b(x,e_i \oplus r)b(x,r)⊕b(x,ei⊕r)，用 major 恢复出各个分量 xix_ixi
- 当 Pr[A=1]≥1/2+c,c<1/4Pr[A=1] \ge 1/2+c,\, c<1/4Pr[A=1]≥1/2+c,c<1/4 时，BBB 可先猜测 ttt 个 σ=b(x,r)\sigma=b(x,r)σ=b(x,r)，统计 ttt 次随机化的 σ⊕b(x,ei⊕r)\sigma \oplus b(x,e_i \oplus r)σ⊕b(x,ei⊕r)，用 major 恢复出各个分量 xix_ixi
- 当 Pr[A=1]≥1/2+1/p(n)Pr[A=1] \ge 1/2+1/p(n)Pr[A=1]≥1/2+1/p(n) 时，BBB 可先随机选取 lll 个 sss，猜测它们的 σ=b(x,s)\sigma=b(x,s)σ=b(x,s)，然后构造出两两独立的 ttt 个 (r,τ=b(x,r))(r,\tau = b(x,r))(r,τ=b(x,r))，统计 ttt 次随机化的 τ⊕b(x,ei⊕r)\tau \oplus b(x,e_i \oplus r)τ⊕b(x,ei⊕r)，用 major 恢复出各个分量 xix_ixi
素因子分解假设下，{fmult(x,y)=xy}\{f_{mult}(x,y)=xy\}{fmult(x,y)=xy} 是弱单向函数簇，其中难以求逆的实例占比至少为 1/4n21/4n^21/4n2
离散对数假设下，{fi(x)=gx}\{f_i(x)=g^x\}{fi(x)=gx} 是单向函数簇。
RSA 假设下，{fN,e(x)=xe(modN)}\{f_{N,e}(x)=x^e \pmod N\}{fN,e(x)=xe(modN)} 是单向函数簇。

PRG

如果 l(n)=n+1l(n)=n+1l(n)=n+1 的 PRG 存在，那么任意多项式 l(n)=p(n)l(n)=p(n)l(n)=p(n) 的 PRG 也存在。设 G0G_0G0 是 l(n)=n+1l(n)=n+1l(n)=n+1 的 PRG，构造
σi∥si=G0(si−1),∣si∣=∣si−1∣=n\sigma_i \| s_i = G_0(s_{i-1}),\, |s_i|=|s_{i-1}|=n σi∥si=G0(si−1),∣si∣=∣si−1∣=n

那么 Gp(s0)=σ1⋯σp(n)G_p(s_0) = \sigma_1 \cdots \sigma_{p(n)}Gp(s0)=σ1⋯σp(n) 也是 PRG。归约过程中使用混合技术。
如果 OWP 存在，那么 PRG 存在。令 fff 是 OWP，bbb 是硬核，那么
G1(s)=b(s)∥f(s)G_1(s) = b(s)\|f(s) G1(s)=b(s)∥f(s)

是扩张因子 l(n)=n+1l(n)=n+1l(n)=n+1 的 PRG。归约过程很简单。

然后构造
σi=b(si−1),si=f(si−1)\sigma_i = b(s_{i-1}),\, s_i = f(s_{i-1}) σi=b(si−1),si=f(si−1)

那么 Gp(s0)=σ1⋯σp(n)G_p(s_0) = \sigma_1 \cdots \sigma_{p(n)}Gp(s0)=σ1⋯σp(n) 就是 l(n)=p(n)l(n)=p(n)l(n)=p(n) 的 PRG。归约过程中采用逆序，D′D'D′ 为了计算 y=f(x)y=f(x)y=f(x) 的原像的硬核 b(x)b(x)b(x)，猜测 DDD 的预测位置 iii，设置 si−1=ys_{i-1}=ysi−1=y，然后 si−j=f(si−j+1)=fj−1(y)=fj(x)s_{i-j}=f(s_{i-j+1})=f^{j-1}(y)=f^j(x)si−j=f(si−j+1)=fj−1(y)=fj(x)，直到 s0=fi(x)s_0=f^i(x)s0=fi(x)；设置 si,si+1,⋯←Uns_i,s_{i+1},\cdots \leftarrow U_nsi,si+1,⋯←Un，以为 DDD 提供相同分布。
PRG 存在 ⟺\iff⟺ OWF 存在。设 G:{0,1}n→{0,1}2nG:\{0,1\}^n \to \{0,1\}^{2n}G:{0,1}n→{0,1}2n 是伪随机生成器，令
f(x0,x1)=G(x0)f(x_0,x_1) = G(x_0) f(x0,x1)=G(x0)

那么 fff 是单向函数。而从 OWF 构造出 PRG 很困难，需要先构造出 false-entropy-generator，然后构造出 pseudoentropy-generator，最后才构造出 PRG。
Rabin 函数：二次剩余假设下，{fN(x)=x2modp,x∈ZN∗}\{f_N(x)=x^2 \mod p,x \in \mathbb Z_N^*\}{fN(x)=x2modp,x∈ZN∗} 是 QRNQR_NQRN 上单向置换，且 lsb(x)lsb(x)lsb(x) 是硬核。

PRF

PRG 存在，那么 PRF 存在。设 G:{0,1}d→{0,1}2dG: \{0,1\}^d \to \{0,1\}^{2d}G:{0,1}d→{0,1}2d 是 PRG，记做 G(s)=G0(s)∥G1(s)G(s)=G_0(s)\|G_1(s)G(s)=G0(s)∥G1(s)，那么由 sss 指定的函数 fs:{0,1}→{0,1}df_s:\{0,1\} \to \{0,1\}^dfs:{0,1}→{0,1}d
fs(x)=Gx(s)f_s(x) = G_x(s) fs(x)=Gx(s)

是最简单的 PRF，可编码为长度为 2d2d2d 的序列。
GGM 方法：设 G:{0,1}d→{0,1}2dG: \{0,1\}^d \to \{0,1\}^{2d}G:{0,1}d→{0,1}2d 是 PRG，记做 G(s)=G0(s)∥G1(s)G(s)=G_0(s)\|G_1(s)G(s)=G0(s)∥G1(s)，那么由 sss 指定的函数 fs:{0,1}l→{0,1}df_s:\{0,1\}^l \to \{0,1\}^dfs:{0,1}l→{0,1}d 构造如下
sx1=Gx1(s),sx1⋯xi=Gxi(sx1⋯xi−1)s_{x_1} = G_{x_1}(s),\, s_{x_1 \cdots x_{i}} = G_{x_i}(s_{x_1 \cdots x_{i-1}}) sx1=Gx1(s),sx1⋯xi=Gxi(sx1⋯xi−1)

那么 fs(x)=sx1⋯xl=sxf_s(x) = s_{x_1 \cdots x_l} = s_xfs(x)=sx1⋯xl=sx 是 PRF，可编码为长度为 d⋅2ld \cdot 2^ld⋅2l 的序列。归约过程使用混合技术。
复合定理：如果 G′G'G′ 是 PRG，FnF_nFn 是 GGM 构造的 PRF，那么 G′(Fn(⋅))G'(F_n(\cdot))G′(Fn(⋅)) 是 PRF。归约时，先后证明 G′∘Fn≡cG′∘RFnG' \circ F_n \overset{c}{\equiv} G' \circ RF_nG′∘Fn≡cG′∘RFn 和 RFn≡cG′∘RFnRF_n \overset{c}{\equiv} G' \circ RF_nRFn≡cG′∘RFn，采用通用编码，使用混合技术。
PRF 存在，那么 OWF 存在。设 fkf_kfk 是 PRF，那么 f(k,x)=x∥fk(x)f(k,x)=x\|f_k(x)f(k,x)=x∥fk(x) 就是 OWF。

因此，PRF 存在 ⟺\iff⟺ OWF 存在 ⟺\iff⟺ PRG 存在。
Naor-Reingold 的 PRF 构造：DDH 假设下，{Ga(b)=(gb,gab)}\{G_a(b)=(g^b,g^{ab})\}{Ga(b)=(gb,gab)} 具有 PRG 的性质（但 aaa 是保密的）。设置私钥 a=(a0,a1,⋯,al)a=(a_0,a_1,\cdots,a_l)a=(a0,a1,⋯,al)，基于 GGM 方法和 {Ga}\{G_a\}{Ga}，得到
Fa(x)=ga0∏i=1laixiF_a(x) = g^{a_0 \prod_{i=1}^l a_i^{x_i}} Fa(x)=ga0∏i=1laixi

那么 {Fa}\{F_a\}{Fa} 是 PRF。
NR 方法：设 S:{0,1}2n→{0,1}nS:\{0,1\}^{2n} \to \{0,1\}^{n}S:{0,1}2n→{0,1}n 是伪随机合成器，fs1:{0,1}→{0,1}n⟺s0∥s1←RU2nf_s^1:\{0,1\} \to \{0,1\}^n \iff s_0\|s_1 \leftarrow_R U_{2n}fs1:{0,1}→{0,1}n⟺s0∥s1←RU2n 是最简单的随机函数。令 k=2lk=2^lk=2l，那么由 s=s0∥s1←Un⋅2ls=s_0\|s_1 \leftarrow U_{n \cdot 2^l}s=s0∥s1←Un⋅2l 指定的函数 fsk:{0,1}k→{0,1}nf_s^k: \{0,1\}^k \to \{0,1\}^nfsk:{0,1}k→{0,1}n 构造如下
fsk(x)={S(fs0k/2(x0),fs1k/2(x1)),k>1sx,k=1f_{s}^k(x) = \left\{ \begin{aligned} S(f_{s_0}^{k/2}(x_0),\, f_{s_1}^{k/2}(x_1)),&& k>1\\ s_x,&& k=1 \end{aligned} \right. fsk(x)={S(fs0k/2(x0),fs1k/2(x1)),sx,k>1k=1

那么 fsk(x)f_s^k(x)fsk(x) 是 PRF，可编码为长度为 n⋅2kn \cdot 2^kn⋅2k 的序列。归约过程使用混合技术。
若 trapdoor OWP 存在，那么 weak PRF 存在。设 {gt}t∈I\{g_t\}_{t \in I}{gt}t∈I 是单向陷门置换，DnD_nDn 是值域上的抽样算法，b(⋅)b(\cdot)b(⋅) 是其硬核，令
ft(x)=b(gt−1(Dn(x)))f_t(x) = b(g_t^{-1}(D_n(x))) ft(x)=b(gt−1(Dn(x)))

其中 Dn(x)D_n(x)Dn(x) 意为使用 xxx 作为输入随机带，那么 ft{0,1}n→{0,1}f_t \{0,1\}^n \to \{0,1\}ft{0,1}n→{0,1} 是弱 PRF。
若 weak PRF 存在，那么伪随机合成器存在。设 {fn}n∈N\{f_n\}_{n \in \mathbb N}{fn}n∈N 是弱 PRF，III 是抽样算法，令 Sn:{0,1}∗×{0,1}∗→{0,1}∗S_n:\{0,1\}^* \times \{0,1\}^* \to \{0,1\}^*Sn:{0,1}∗×{0,1}∗→{0,1}∗ 为
Sn(x,y)=fI(y)(x)S_n(x,y) = f_{I(y)}(x) Sn(x,y)=fI(y)(x)

其中 I(y)I(y)I(y) 意为使用 yyy 作为输入随机带，那么 SnS_nSn 是伪随机合成器。归约过程中采取混合技术，将方阵 {Sn(xi,yj)}i,j=1k\{S_n(x_i,y_j)\}_{i,j=1}^k{Sn(xi,yj)}i,j=1k 和 Unk2U_{nk^2}Unk2 按列混合，前 iii 列取自前者，后 k−ik-ik−i 列取自后者。
CDH 假设下，函数簇 {Sp,g,r(x,y)=}\{S_{p,g,r}(x,y)=\}{Sp,g,r(x,y)=} 上的均匀分布 SDH={Sn}S_{DH}=\{S_n\}SDH={Sn}，是伪随机合成器。
令 fff 是 PRF，Feistel 置换定义为
Df(L,R)=(R,L⊕f(R))D_f(L,R) = (R,\, L \oplus f(R)) Df(L,R)=(R,L⊕f(R))

那么两轮 Feistel Fn=Dfs2∘Dfs1F_n = D_{f_{s_2}} \circ D_{f_{s_1}}Fn=Dfs2∘Dfs1 是 weak PRP
Luby-Rackoff 的 PRP 构造：
- 设 fs1,fs2,fs3f_{s_1},f_{s_2},f_{s_3}fs1,fs2,fs3 是 PRF，三轮 Feistel Fn=Dfs3∘Dfs2∘Dfs1F_n = D_{f_{s_3}} \circ D_{f_{s_2}} \circ D_{f_{s_1}}Fn=Dfs3∘Dfs2∘Dfs1 是 PRP
- 设 fs1,fs2,fs3,fs4f_{s_1},f_{s_2},f_{s_3},f_{s_4}fs1,fs2,fs3,fs4 是 PRF，四轮 Feistel Fn=Dfs4∘Dfs3∘Dfs2∘Dfs1F_n = D_{f_{s_4}} \circ D_{f_{s_3}} \circ D_{f_{s_2}} \circ D_{f_{s_1}}Fn=Dfs4∘Dfs3∘Dfs2∘Dfs1 是 strong PRP
Naor-Reingold 的 PRP 构造：
- pairwise independent 置换簇：置换簇 {Hk:Dk→Dk}k\{H_k:D_k \to D_k\}_k{Hk:Dk→Dk}k，对于任意 x≠y,z∈Dx \neq y,z \in Dx=y,z∈D，都有
  Prk←RK[Hk(x)⊕Hk(y)=z]≤negl(n)\underset{k \leftarrow_R K}{Pr}[H_k(x)\oplus H_k(y)=z] \le negl(n) k←RKPr[Hk(x)⊕Hk(y)=z]≤negl(n)
- 令 {Ht}\{H_t\}{Ht} 是两两独立置换簇，设 f,gf,gf,g 是 PRF，那么 Fn=Dg∘Df∘HtF_n = D_g \circ D_f \circ H_tFn=Dg∘Df∘Ht 是 PRP
- 令 {Ht}\{H_t\}{Ht} 是两两独立置换簇，设 f,gf,gf,g 是 PRF，那么 Fn=Ht2∘Dg∘Df∘Ht1F_n = H_{t_2} \circ D_g \circ D_f \circ H_{t_1}Fn=Ht2∘Dg∘Df∘Ht1 是 strong PRP
Puncturable PRF（可穿孔伪随机函数）：函数簇 {fk}\{f_k\}{fk}，随机密钥 kkk，给定穿孔密钥 kx∗k_{x^*}kx∗，在某点 x∗x^*x∗ 上的函数值不可计算（与均匀分布计算不可区分），其他点 x≠x∗x \neq x^*x=x∗ 的函数值可有效计算。使用 GGM 可以构造 Puncturable PRF。
Constrained PRF（受限的伪随机函数）：函数簇 {fk}\{f_k\}{fk}，随机密钥 kkk，给定电路 CCC 的相关密钥 kCk_CkC，在满足 C(x)=1C(x)=1C(x)=1 的点上的函数值可有效计算，其他点不可计算（与均匀分布计算不可区分）。使用 GGM 和 NR 可以构造某些简单电路的 Constrained PRF。

Hash

Damgard 迭代结构：设 F={fs:{0,1}t→{0,1}l}sF=\{f_s:\{0,1\}^t \to \{0,1\}^l\}_sF={fs:{0,1}t→{0,1}l}s 是固定长度的 CRHF，构造任意长度的 CRHF hs:{0,1}∗→{0,1}l(∣s∣)h_s:\{0,1\}^* \to \{0,1\}^{l(|s|)}hs:{0,1}∗→{0,1}l(∣s∣)，
- 将 mmm 划分为长度为 t−l−1t-l-1t−l−1 的若干块 m1∥⋯∥mkm_1\|\cdots\|m_km1∥⋯∥mk，最后一块 padding 000
- 设置 d=∣m∣(modt−l−1)d=|m| \pmod{t-l-1}d=∣m∣(modt−l−1)（就是 padding 之前的 ∣mk∣|m_k|∣mk∣），编码为二进制写入 mk+1m_{k+1}mk+1
- 计算 h1=fs(0l∥0∥m1)h_1 = f_s(0^l\|0\|m_1)h1=fs(0l∥0∥m1)，然后迭代计算 hj=fs(hj−1∥1∥mj)h_j = f_s(h_{j-1}\|1\|m_j)hj=fs(hj−1∥1∥mj)，输出 hs(m)=hk+1h_s(m) = h_{k+1}hs(m)=hk+1
Merkle-Damgard 迭代结构：设 f:{0,1}c+b→{0,1}cf:\{0,1\}^{c+b} \to \{0,1\}^cf:{0,1}c+b→{0,1}c，g:{0,1}c→{0,1}ng:\{0,1\}^c \to \{0,1\}^ng:{0,1}c→{0,1}n，构造 h:{0,1}∗→{0,1}nh:\{0,1\}^* \to \{0,1\}^nh:{0,1}∗→{0,1}n，
- 将 mmm 划分为长度为 bbb 的若干块 m1∥⋯∥mtm_1\|\cdots\|m_tm1∥⋯∥mt，最后一块 padding 000
- 设置 h0=IV∈{0,1}ch_0 = IV \in \{0,1\}^ch0=IV∈{0,1}c，迭代计算 hi=f(hi−1,mi)h_{i}=f(h_{i-1},m_i)hi=f(hi−1,mi)，输出 h(m)=g(ht)h(m)=g(h_t)h(m)=g(ht)
若 fff 是 CRHF，那么 hhh 也是 CRHF。归约时，依次比较两个链条的中间状态，直到找到第一个相同的位置，从而给出 fff 的碰撞。
基于 Claw-free 置换的 CRHF：设 {fi0,fi1}i∈I\{f_i^0,f_i^1\}_{i \in I}{fi0,fi1}i∈I 是 {0,1}l(∣i∣)\{0,1\}^{l(|i|)}{0,1}l(∣i∣) 上的 Claw-free 的置换对，任意的 s∈Is \in Is∈I 和 u∈{0,1}lu \in \{0,1\}^lu∈{0,1}l，构造 hs,u(m)h_{s,u}(m)hs,u(m) 如下，
hs,u(m)=fsm1∘⋯∘fsmk(u),∣m∣=kh_{s,u}(m) = f_s^{m_1} \circ \cdots \circ f_s^{m_k}(u),\, |m|=k hs,u(m)=fsm1∘⋯∘fsmk(u),∣m∣=k

归约证明时，注意设置 u=fsb(u′)u=f_s^b(u')u=fsb(u′)，其中 b←U1b \leftarrow U_1b←U1，u′←Ulu' \leftarrow U_lu′←Ul，为了抓住在一对碰撞 m0,m1m_0,m_1m0,m1 中 m0m_0m0 是 m1m_1m1 前缀的情况。
Merkle Tree：设 h:{0,1}2l→{0,1}lh: \{0,1\}^{2l} \to \{0,1\}^{l}h:{0,1}2l→{0,1}l 是 CRHF，定义 CRHF H:{0,1}∗→{0,1}lH:\{0,1\}^* \to \{0,1\}^lH:{0,1}∗→{0,1}l 为一颗二叉树，叶子是 mmm 的各个分块的摘要 h(mi)h(m_i)h(mi)，中间节点是两个孩子的摘要 h(hL,hR)h(h_L,h_R)h(hL,hR)，迭代到根节点 H(m)H(m)H(m)。归约证明时，两棵不同的树 H(m0)=H(m1)H(m_0)=H(m_1)H(m0)=H(m1)，深度优先搜索一个两棵树的摘要不同的节点，那么其父节点上就出现 hhh 的碰撞。
若 OWF 存在，那么 UOWHF 存在。从 OWF 到 Regular OWF 到 OWP 到 UOWHF 到 Claw-free Trapdoor Permutation 到 Signature，构造方案很麻烦。
Composition lemma：设 H1,⋯,HlH_1,\cdots,H_lH1,⋯,Hl 是 UOWHF，那么它们的复合 H=H1∘⋯∘HlH = H_1 \circ \cdots \circ H_lH=H1∘⋯∘Hl 也是 UOWHF。
若抗第二原像的 Hash 函数存在，那么 UOWHF 存在。设 FFF 是抗第二原像的，那么 {Hk(x)=F(k⊕x)}k\{H_k(x) = F(k \oplus x)\}_k{Hk(x)=F(k⊕x)}k 是 UOWHF。
UOWHF(rrr) 经过 r+1r+1r+1 轮 MD 迭代后是 UOWHF。设 HHH 是 UOWHF(rrr)，得到 MDr+1(H)(⋅)MD_{r+1}(H)(\cdot)MDr+1(H)(⋅) 是 UOWHF。归约时，对于一对碰撞 m≠m′m \neq m'm=m′，依次比较两者 MD 的链接变量，找到第一个相同的位置。

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：托运价格（c++基础）

下一篇：实施OKR过程中需要注意的7个事项，尤其是第2个！

安全性归约（构造 1）

文章目录

OWF

PRG

PRF

Hash

相关内容

热门资讯