安全性归约（一些反例）

听课和做题时遇到的一些反例，这里随意记录下。

OWF

1. 有硬核谓词的函数不一定是单向的。令函数 $f(x^{\prime }\Vert x^{\prime \prime })=x^{\prime \prime }$，易知 $b(x^{\prime }\Vert x^{\prime \prime })=x^{\prime }$ 是其硬核谓词，但是 $f$ 不是单向函数。但如果 $f$ 是 1-1 的，那么 $f$ 是弱单向的。

2. $f(x)$ 是 OWF，则它的迭代 $f(f(x))$ 不一定是 OWF。

   例如 $f(x^{\prime }\Vert x^{\prime \prime })=g(x^{\prime \prime })\Vert 0^n$，其中 $g(x^{\prime \prime })$ 是保长 OWF。此时，
   $$f(f(x^{\prime }\Vert x^{\prime \prime }))=f(g(x^{\prime \prime })\Vert 0^n)=g(0^n)\Vert 0^n$$
   于是任意的 $x$ 都是 $g(0^n)\Vert 0^n$ 的原像。

3. 若 $f$ 是保长单向函数，定义函数 $g(x)=f(x)\oplus x$，则 $g$ 不一定是单向函数。

   如果强行归约，会发现概率损失因子是指数级。

   令 $h:$ 是保长单向函数，构造
   $$f(x)=f(x^{\prime }\Vert x^{\prime \prime })=h(x^{\prime \prime })\Vert 0^n$$
   其中 x ′ , x ′ ′ ∈ { 0 , 1 } n x',x'' \in \{0,1\}^n x′,x′′∈{0,1}n，可以证明 $f$ 是保长单向函数（归约）。

   此时，
   $$g(x)=f(x^{\prime }\Vert x^{\prime \prime })\oplus x^{\prime }\Vert x^{\prime \prime }=h(x^{\prime \prime })\oplus x^{\prime }\Vert x^{\prime \prime }$$
   容易看出存在 PPT 求逆算法：

   1. 输入 $y=y^{\prime }\Vert y^{\prime \prime }$
   2. 先提取 $x^{\prime \prime }=y^{\prime \prime }$，计算 $h(x^{\prime \prime })$
   3. 再提取 $x’=y^{\prime }\oplus h(x^{\prime \prime })$
   4. 输出 $x=x^{\prime }\Vert x^{\prime \prime }$

   成功概率为 $\underset{x\leftarrow U_{2n}}{\mathrm{Pr}}[A(g(x),1^n)\in g^{-1}(g(x))]=1$

4. 若 $f$ 是保长单向函数，定义函数 $g(x,y)=f(x)\oplus f(y)$，则 $g$ 不一定是单向函数。

   如果强行归约，会发现概率损失因子是指数级。

   令 $h:$ 是保长单向函数，构造
   f ( x ) = { h ( x ′ ′ ) ∥ x ′ , x ′ ≠ 0 n h ( x ′ ′ ) ⊕ x ′ ′ ∥ 0 n , x ′ = 0 n f(x) = \left\{

   h(x″)‖x′,x′≠0nh(x″)⊕x″‖0n,x′=0n" role="presentation" style="position: relative;">h(x′′)h(x′′)⊕x′′∥x′,∥0n,x′≠0nx′=0n$$\begin{array}{rlrl}h(x^{″})& \Vert x^{\prime },& & x^{\prime }\ne 0^n\\ h(x^{″})\oplus x^{″}& \Vert 0^n,& & x^{\prime }=0^n\end{array}$$
   \right. f(x)={h(x′′)h(x′′)⊕x′′​∥x′,∥0n,​​x′=0nx′=0n​
   其中 x ′ , x ′ ′ ∈ { 0 , 1 } n x',x'' \in \{0,1\}^n x′,x′′∈{0,1}n，可以证明 $f$ 是保长单向函数：对于 $x$ 在 $x^{\prime }=0^n$ 和 $x^{\prime }\ne 0^n$ 时的像不相交，而当 $x^{\prime }\ne 0^n$ 时（占比为 $1-negl(n)$）它是保长单向的（归约）。

   此时，
   $$g(x,y)=f(x^{\prime }\Vert x^{\prime \prime })\oplus f(y^{\prime }\Vert y^{\prime \prime })$$
   存在 PPT 求逆算法：

   1. 输入 $z=z^{\prime }\Vert z^{\prime \prime }$
   2. 如果 $z^{\prime \prime }\ne 0^n$，
      1. 令 $x^{\prime }=z^{\prime \prime },x^{\prime \prime }=z^{\prime }$，于是 $x=z^{\prime \prime }\Vert z^{\prime }$，
      2. 令 $y^{\prime }=0^n,y^{\prime \prime }=x^{\prime \prime }$，于是 $y=0^n\Vert z^{\prime }$
   3. 如果 $z^{\prime \prime }=0^n$，且 $z^{\prime }=0^n$，那么任取 $x$，令 $y=x$
   4. 如果 $z^{\prime \prime }=0^n$，且 $z^{\prime }\ne 0^n$，此时必然 $x^{\prime }=y^{\prime }=0^n$（需要寻找 $h(x^{\prime \prime })\oplus x^{\prime \prime }\oplus h(y^{\prime \prime })\oplus y^{\prime \prime }=z^{\prime }$），直接 abort
   5. 输出 $(x,y)$

   成功概率为 $\underset{x,y\leftarrow U_{2n}}{\mathrm{Pr}}[A(g(x,y),1^n)\in g^{-1}(g(x,y))]=1-negl(n)$

PRG

1. 设 $f$ 是 OWF，$b$ 是其硬核，令 $G_1(x)=b(x)\Vert f(x)$，那么其迭代 $G_p(x)$ 不一定是伪随机生成器。

   令 $f$ 是保长 OWF，构造 $g(x^{\prime }\Vert x^{\prime \prime })=1^n\Vert f(x^{\prime })$，那么
   G 1 ( x ) = b ( x ) ∥ ( 1 n ∥ f ( x ′ ) ) G 2 ( x ) = b ( x ) ∥ b ( 1 n ∥ f ( x ′ ) ) ∥ ( 1 n ∥ f ( 1 n ) ) G 3 ( x ) = b ( x ) ∥ b ( 1 n ∥ f ( x ′ ) ) ∥ b ( 1 n ∥ f ( 1 n ) ) ∥ ( 1 n ∥ f ( 1 n ) ) ⋯

   G1(x)=b(x)‖(1n‖f(x′))G2(x)=b(x)‖b(1n‖f(x′))‖(1n‖f(1n))G3(x)=b(x)‖b(1n‖f(x′))‖b(1n‖f(1n))‖(1n‖f(1n))⋯" role="presentation" style="position: relative;">G1(x)G2(x)G3(x)⋯=b(x)∥(1n∥f(x′))=b(x)∥b(1n∥f(x′))∥(1n∥f(1n))=b(x)∥b(1n∥f(x′))∥b(1n∥f(1n))∥(1n∥f(1n))$$\begin{array}{rl}{G}_1(x)& =b(x)\Vert (1^n\Vert f(x^{\prime }))\\ G_2(x)& =b(x)\Vert b(1^n\Vert f(x^{\prime }))\Vert (1^n\Vert f(1^n))\\ G_3(x)& =b(x)\Vert b(1^n\Vert f(x^{\prime }))\Vert b(1^n\Vert f(1^n))\Vert (1^n\Vert f(1^n))\\ \cdots \end{array}$$
   G1​(x)G2​(x)G3​(x)⋯​=b(x)∥(1n∥f(x′))=b(x)∥b(1n∥f(x′))∥(1n∥f(1n))=b(x)∥b(1n∥f(x′))∥b(1n∥f(1n))∥(1n∥f(1n))​
   明显 $G_p(x)$ 不是 PRG，因为 $f$ 迭代退化了。

2. 设 G : { 0 , 1 } 2 n → { 0 , 1 } ∗ G:\{0,1\}^{2n} \to \{0,1\}^* G:{0,1}2n→{0,1}∗ 是 PRG，但是 $G^{\prime }(x^{\prime }\Vert x^{\prime \prime })=G(x^{\prime }\Vert 0^n)$ 不一定是 PRG。

   令 $f(x^{\prime }\Vert x^{\prime \prime })=x^{\prime }\Vert p(x^{\prime \prime })$，其中 $p(x^{\prime \prime })$ 是 OWP，且它满足 $p(0^n)\to 0^n$，易知 $f$ 是 OWP。

   此时，$f$ 仅对于形式为 $x^{\prime }\Vert 0^n$ 的输入，它迭代退化，
   $$f(f(x^{\prime }\Vert 0^n))=f(x^{\prime }\Vert 0^n)=x^{\prime }\Vert 0^n$$
   于是，使用 OWP 和 Hardcore 迭代的那种 PRG 构造下，$G(U_{2n})$ 依旧是 PRG，但 $G^{\prime }(U_n\Vert 0^n)$ 的状态 $s_i$ 总会收敛到同一值，从而后续的序列 ${\sigma }_i=b(s_i)$ 都相同。

PRF

1. 设 $f:K\times X\to Y$ 是伪随机函数，定义函数 $g(k,(x,y))=f(k,x)\oplus f(k,y)$，则 $g$ 不一定是伪随机函数。

   如果强行归约，会发现无论 $A$ 的区分优势有多大，$A^{\prime }$ 的区分优势总是为零。

   存在 PPT 区分器：

   1. 询问 $(x,y),(y,z),(x,z)$ 的函数值 $r_1,r_2,r_3$
   2. 如果 $r_1\oplus r_2=r_3$，输出 $b^{\prime }=1$
   3. 否则，输出 $b^{\prime }=0$

   区分优势为 $Ad{v}_D=\left|Pr[Exp{t}_D^{G_n,R{F}_n}(1^n,b=0)=1]-Pr[Exp{t}_D^{G_n,R{F}_n}(1^n,b=1)=1]\right|=1-negl(n)$

Hash

1. 一个 Hash 抗碰撞，但不一定是抗原像的。即：存在找一个原像容易，但找到两个原像困难的 Hash 函数。（这俩不等价吧？）

   令 $H_1$ 是 OWHF，令 H 2 : { 0 , 1 } n + 1 → { 0 , 1 } n H_2:\{0,1\}^{n+1} \to \{0,1\}^n H2​:{0,1}n+1→{0,1}n 为
   H 2 ( b ∥ x ) = { x , b = 0 H 1 ( x ) , b = 1 H_2(b\|x) = \left\{

   x,b=0H1(x),b=1" role="presentation" style="position: relative;">x,H1(x),b=0b=1$$\begin{array}{rlr}x,& & b=0\\ H_1(x),& & b=1\end{array}$$
   \right. H2​(b∥x)={x,H1​(x),​​b=0b=1​
   $H_2$ 不抗原像。任给像 $y$，找到一个原像 $0\Vert y$ 是容易的。

   但找另一个原像 $1\Vert x$，使得 $H_1(x)=y$ 是困难的，因为 OWHF。

2. 另一种更好的构造。假如 $f$ 是可逆置换，$g$ 是抗碰撞函数，它们的值域、像空间的关系为：不交、互补

   f : S 1 → S 1 ′ g : S 2 → S 2 ′ S 1 ∩ S 2 = ∅ ,    S 1 ′ ∩ S 2 ′ = ∅ S 1 ∪ S 2 = { 0 , 1 } l ( n ) ,    S 1 ′ ∪ S 2 ′ = { 0 , 1 } n 2 l ( n ) − n = O ( p o l y ( n ) ) f:S_1 \to S_1'\\ g:S_2 \to S_2'\\ S_1 \cap S_2 = \empty,\,\, S_1' \cap S_2' = \empty\\ S_1 \cup S_2 = \{0,1\}^{l(n)},\,\, S_1' \cup S_2' = \{0,1\}^n\\ 2^{l(n) - n} = O(poly(n)) f:S1​→S1′​g:S2​→S2′​S1​∩S2​=∅,S1′​∩S2′​=∅S1​∪S2​={0,1}l(n),S1′​∪S2′​={0,1}n2l(n)−n=O(poly(n))

   定义如下 Hash 函数

   h ( x ) = { f ( x ) , x ∈ S 1 g ( x ) , x ∈ S 2 h(x) = \left\{

   f(x),x∈S1g(x),x∈S2" role="presentation" style="position: relative;">f(x),g(x),x∈S1x∈S2$$\begin{array}{rlr}f(x),& & x\in S_1\\ g(x),& & x\in S_2\end{array}$$
   \right. h(x)={f(x),g(x),​​x∈S1​x∈S2​​

   当 $S_1,S_2$ 的占比都不可忽略时，$h(x)$ 是一个不抗原像的抗碰撞（抗第二原像） Hash 函数！

3. MD 迭代不保持 UOW 性。

   设 F k : { 0 , 1 } l + t → { 0 , 1 } l F_k:\{0,1\}^{l+t} \to \{0,1\}^l Fk​:{0,1}l+t→{0,1}l 是 UOWHF，定义 H s : { 0 , 1 } l + t → { 0 , 1 } l + k H_s:\{0,1\}^{l+t} \to \{0,1\}^{l+k} Hs​:{0,1}l+t→{0,1}l+k
   H s ( x 1 ∥ x 2 ∥ x 3 ) = { F s ( x 1 ∥ x 2 ∥ x 3 ) ∥ s , x 2 ≠ s 1 l ∥ 1 k , x 2 = s H_s(x_1\|x_2\|x_3) = \left\{

   Fs(x1‖x2‖x3)‖s,x2≠s1l‖1k,x2=s" role="presentation" style="position: relative;">Fs(x1∥x2∥x3)∥s,1l∥1k,x2≠sx2=s$$\begin{array}{rlr}{F}_s(x_1\Vert x_2\Vert x_3)\Vert s,& & x_2\ne s\\ 1^l\Vert 1^k,& & x_2=s\end{array}$$
   \right. Hs​(x1​∥x2​∥x3​)={Fs​(x1​∥x2​∥x3​)∥s,1l∥1k,​​x2​=sx2​=s​
   那么 $H_s$ 是 UOWHF，但是 $M{D}_2(H_s,m)=H_s(H_s(IV\Vert m_0)\Vert m_1)$ 不满足 UOW：选取挑战 $IV=I{V}_1\Vert I{V}_2,m=0^{t-k}\Vert 0^{t-k}$，收到 $s$，如果 $s\ne I{V}_2$ 则选取 $m^{\prime }=1^{t-k}\Vert 0^{t-k}$，那么 $m^{\prime }$ 就是第二原像。

4. 一个收缩的 OWF，不一定是 OWHF。即：存在抗原像，但不抗第二原像的 Hash 函数。

   令 $H_1$ 是 OWHF，令 $H_2(x^{\prime }\Vert x^{\prime \prime })=H_1(x^{\prime \prime })$，明显 $H_2$ 是抗原像的。

   给定 $x^{\prime }\Vert x^{\prime \prime }$，输出 $H_2(x^{\prime }\Vert x^{\prime \prime })$ 的第二原像是容易的：$x^{\prime \prime \prime }\Vert x^{\prime \prime }$，其中任取 $x^{\prime \prime \prime }\ne x^{\prime }$ 即可。

Encryption

Signature

MAC