从OWF到密码学方案

从OWF到密码学方案

OWF

求逆实验 I n v e r t A , f ( n ) Invert_{A,f}(n) InvertA,f​(n)，

1. 选择均匀的 x ∈ { 0 , 1 } n x in {0,1}^n x∈{0,1}n，并计算 y : = f ( x ) y:=f(x) y:=f(x)
2. 敌手 A A A以 1 n 1^n 1n和 y y y为输入，并输出 x ′ x' x′
3. 实验的输出为 1 1 1当仅当 f ( x ′ ) = y f(x')=y f(x′)=y（注意，我们不要求 x ’ = x x’=x x’=x）

一个函数 f : { 0 , 1 } ∗ → { 0 , 1 } ∗ f:{0,1}^* rightarrow {0,1}^* f:{0,1}∗→{0,1}∗（任意长度）是单向函数（One-way Function），如果它满足两个条件：

1. 容易计算：存在多项式时间算法 M f M_f Mf​，使得 M f ( x ) = f ( x ) , ∀ x M_f(x)=f(x),forall x Mf​(x)=f(x),∀x
2. 难以求逆：任意的概率多项式时间（PPT）算法 A A A，使得 P r [ I n v e r t A , f ( n ) = 1 ] ≤ n e g l ( n ) Pr[Invert_{A,f}(n)=1]le negl(n) Pr[InvertA,f​(n)=1]≤negl(n)，其中 n e g l ( ⋅ ) negl(cdot) negl(⋅)是可忽略函数

注意，难以求逆说的是，任意多项式时间敌手 A A A，对于均匀随机的 x x x的像 f ( x ) f(x) f(x)，难以计算出它的原像
P r x ← { 0 , 1 } ∗ [ A ( 1 n , f ( x ) ) ∈ f − 1 ( f ( x ) ) ] ≤ n e g l ( n ) underset{x leftarrow {0,1}^*}{Pr}[A(1^n, f(x)) in f^{-1}(f(x))] le negl(n) x←{0,1}∗Pr​[A(1n,f(x))∈f−1(f(x))]≤negl(n)
OWF并非对所有点 x x x都难以求逆，甚至可以存在可数无限个求逆容易的点。不是OWF的函数，也可以存在某些难以求逆的点。

目前没有证明OWF存在，也没有证明OWF不存在。如果OWF存在，那么 P ≠ N P P neq NP P​=NP（因为 O W F ∉ P OWF notin P OWF∈/​P）。反之，因此即使 P ≠ N P P neq NP P​=NP，也无法证明OWF存在，因为一个函数 f ∉ P f notin P f∈/​P，仅仅是存在至少一个点 x x x， f ( x ) f(x) f(x)难以求逆，并不意味着 f f f一定是OWF。

OWP

如果一个OWF是并且length-preserving（ ∣ f ( x ) ∣ = ∣ x ∣ , ∀ x |f(x)|=|x|,forall x ∣f(x)∣=∣x∣,∀x）并且是双射，那么它是单向置换（One-way Permutation）

如果 1 n 1^n 1n足够大，那么 O W P ≡ c O W F OWP overset{c}{equiv} OWF OWP≡cOWF，它们计算上不可区分。

Hard-Core Predicates

OWF难以求逆，但计算部分输入信息可以是容易的。令 g g g是OWF，那么 f ( x 1 , x 2 ) = ( x 1 , g ( x 2 ) ) f(x_1,x_2)=(x_1,g(x_2)) f(x1​,x2​)=(x1​,g(x2​))也是OWF。

一个函数 h c : { 0 , 1 } ∗ → { 0 , 1 } hc:{0,1}^* rightarrow {0,1} hc:{0,1}∗→{0,1}是关于函数 f f f的硬核谓词，如果它满足

1. 容易计算：存在多项式时间算法 M M M，使得 M ( x ) = h c ( x ) , ∀ x M(x)=hc(x),forall x M(x)=hc(x),∀x
2. 难以推断：任意的概率多项式时间算法 A A A，使得 P r x ← { 0 , 1 } ∗ [ A ( 1 n , f ( x ) ) = h c ( x ) ] ≤ 0.5 + n e g l ( n ) underset{x leftarrow {0,1}^*}{Pr}[A(1^n, f(x)) = hc(x)] le 0.5 + negl(n) x←{0,1}∗Pr​[A(1n,f(x))=hc(x)]≤0.5+negl(n)

一个双射函数 f f f有硬核 h c hc hc，仅当 f f f是OWF（如果不是OWF，因为双射，可以求 f ( x ) f(x) f(x)原像 x x x，进而 h c ( x ) hc(x) hc(x)容易计算）

有硬核的函数未必是OWF，比如 f ( x 1 ⋯ x n ) = x 1 ⋯ x n − 1 f(x_1cdots x_n)=x_1cdots x_{n-1} f(x1​⋯xn​)=x1​⋯xn−1​和它的硬核 h c ( x 1 ⋯ x n ) = x n hc(x_1cdots x_n)=x_n hc(x1​⋯xn​)=xn​

Goldreich-Levin Theorem：假设存在一个单向函数（单向置换） f f f，那么就存在拥有硬核 h c hc hc的单向函数（单向置换） g g g，构造如下
g ( x , r ) : = ( f ( x ) , r ) h c ( x , r ) : = ⊕ i = 1 n x i ⋅ r i g(x,r) := (f(x), r)\ hc(x,r) := oplus_{i=1}^n x_i cdot r_i g(x,r):=(f(x),r)hc(x,r):=⊕i=1n​xi​⋅ri​
其中 ∣ x ∣ = ∣ r ∣ = n |x|=|r|=n ∣x∣=∣r∣=n。即：用 r r r挑选比特串 x x x的随机子集， f ( x ) f(x) f(x)可以隐藏这个随机子集的异或值。

PRG

一个确定性多项式时间算法 G : { 0 , 1 } n → { 0 , 1 } l ( n ) G:{0,1}^n rightarrow {0,1}^{l(n)} G:{0,1}n→{0,1}l(n)是伪随机生成器（Pseudorandom Generator），如果它满足两个条件：

1. 扩展性（Expansion）：多项式 l ( ⋅ ) l(cdot) l(⋅)，且 l ( n ) > n l(n)>n l(n)>n，它叫做扩张因子（expansion factor）
2. 伪随机性（Pseudorandomness）：任意的PPT区分器 D D D，使得 ∣ P r [ D ( G ( s ) ) = 1 ] − P r [ D ( r ) = 1 ] ∣ ≤ n e g l ( n ) |Pr[D(G(s))=1] - Pr[D(r)=1]| le negl(n) ∣Pr[D(G(s))=1]−Pr[D(r)=1]∣≤negl(n)，其中 r ∈ { 0 , 1 } l ( n ) r in {0,1}^{l(n)} r∈{0,1}l(n)是均匀选取的（即 r r r是真随机数）

构造PRG：令 f f f是一个拥有硬核 h c hc hc的OWP，那么扩张因子为 l ( n ) = n + 1 l(n)=n+1 l(n)=n+1的伪随机生成器可以构造如下
G ( s ) : = f ( s ) ∣ ∣ h c ( s ) G(s) := f(s) || hc(s) G(s):=f(s)∣∣hc(s)

注意，OWF是不够的。例如， g g g是OWF，令 f = 2 g f=2g f=2g也是OWF，但从随机分布中区分出 f ( s ) ∣ ∣ h c ( s ) f(s) || hc(s) f(s)∣∣hc(s)是容易的，倒数第二个比特是偶数。

扩展PRG：如果存在扩张因子 l ( n ) = n + 1 l(n)=n+1 l(n)=n+1的伪随机生成器 G G G，那么就存在 l ( n ) = p o l y ( n ) l(n)=poly(n) l(n)=poly(n)的伪随机生成器 G ′ G' G′，构造如下
G 1 ( s ) : = G ( s ) = ( s 1 ∈ { 0 , 1 } n , σ 1 ∈ { 0 , 1 } ) G k ( s ) : = ( G ( s k − 1 ) , σ k − 1 , ⋯ , σ 1 ) = ( s k ∈ { 0 , 1 } n , σ k , ⋯ , σ 1 ) G ′ ( s ) : = G p ( n ) ( s ) G_1(s) := G(s) = (s_1 in {0,1}^{n},sigma_1 in {0,1})\ G_k(s) := (G(s_{k-1}), sigma_{k-1},cdots,sigma_1) = (s_{k} in {0,1}^{n}, sigma_{k},cdots,sigma_1)\ G'(s) := G_{p(n)}(s) G1​(s):=G(s)=(s1​∈{0,1}n,σ1​∈{0,1})Gk​(s):=(G(sk−1​),σk−1​,⋯,σ1​)=(sk​∈{0,1}n,σk​,⋯,σ1​)G′(s):=Gp(n)​(s)
简单来说，就是每次迭代都只将前 n n n位输入 G G G，并将最后 1 1 1位保留在末尾。

PRF

令 F : { 0 , 1 } ∗ × { 0 , 1 } ∗ → { 0 , 1 } ∗ F:{0,1}^* times {0,1}^* rightarrow {0,1}^* F:{0,1}∗×{0,1}∗→{0,1}∗是可以有效计算的带密钥函数（Efficient Keyed Function），它是伪随机函数（Pseudorandom Function），如果任意的PPT区分器 D D D，满足如下条件
∣ P r [ D F k ( 1 n ) = 1 ] − P r [ D f ( 1 n ) = 1 ] ∣ ≤ n e g l ( n ) |Pr[D^{F_k}(1^n)=1] - Pr[D^{f}(1^n)=1]| le negl(n) ∣Pr[DFk​(1n)=1]−Pr[Df(1n)=1]∣≤negl(n)
其中 k ∈ { 0 , 1 } n kin{0,1}^n k∈{0,1}n是均匀随机的，均匀选取 f ∈ F u n c n f in Func_n f∈Funcn​，这里 F u n c n Func_n Funcn​是所有 n n n比特输入输出函数的集合，大小为 ( 2 n ) 2 n (2^n)^{2^n} (2n)2n

构造PRF：如果存在扩张因子 l ( n ) = 2 n l(n)=2n l(n)=2n的伪随机生成器 G ( x ) = ( G 0 ( x ) , G 1 ( x ) ) G(x)=(G_0(x),G_1(x)) G(x)=(G0​(x),G1​(x))，那么就存在伪随机函数 F k : { 0 , 1 } n → { 0 , 1 } n F_k: {0,1}^n rightarrow {0,1}^n Fk​:{0,1}n→{0,1}n，构造如下
F k ( x 1 ⋯ x n ) : = G x n ( ⋯ ( G x 2 ( G x 1 ( k ) ) ) ) F_k(x_1cdots x_n) := G_{x_n}(cdots(G_{x_2}(G_{x_1}(k)))) Fk​(x1​⋯xn​):=Gxn​​(⋯(Gx2​​(Gx1​​(k))))
其实，上述过程就是在以 k k k为根、以 G 0 , G 1 G_0,G_1 G0​,G1​为左右子树的二叉树上，用 x = x 1 ⋯ x n x=x_1cdots x_n x=x1​⋯xn​作为路径检索叶子。

另外，反过来从PRF构建PRG也是容易的，如 G ( s ) : = F s ( 1 ) ∣ ∣ ⋯ ∣ ∣ F s ( l ) G(s):= F_s(1)||cdots||F_s(l) G(s):=Fs​(1)∣∣⋯∣∣Fs​(l)

OWF的输出均匀，但是输出均匀的函数不一定是OWF。例如， F k ( x ) = k ⊕ x F_k(x)=koplus x Fk​(x)=k⊕x，对于均匀随机的 k k k，它的输出是均匀的，但可以被差分分析。

PRP

令 F : { 0 , 1 } ∗ × { 0 , 1 } ∗ → { 0 , 1 } ∗ F:{0,1}^* times {0,1}^* rightarrow {0,1}^* F:{0,1}∗×{0,1}∗→{0,1}∗是可以有效计算的带密钥置换（Efficient Keyed Permutation），它是强伪随机置换（Strong Pseudorandom Permutation），如果任意的PPT区分器 D D D，满足如下条件
∣ P r [ D F k , F k − 1 ( 1 n ) = 1 ] − P r [ D f , f − 1 ( 1 n ) = 1 ] ∣ ≤ n e g l ( n ) |Pr[D^{F_k, F^{-1}_k}(1^n)=1] - Pr[D^{f,f^{-1}}(1^n)=1]| le negl(n) ∣Pr[DFk​,Fk−1​(1n)=1]−Pr[Df,f−1(1n)=1]∣≤negl(n)
其中 k ∈ { 0 , 1 } n kin{0,1}^n k∈{0,1}n是均匀随机的，均匀选取 f ∈ P e r m n f in Perm_n f∈Permn​，这里 P e r m n Perm_n Permn​是所有 n n n比特置换的集合，大小为 ( 2 n ) ! (2^n)! (2n)!

注意，Strong说的是，即使额外给定求逆预言机，依然难以区分。

构造PRP：如果存在伪随机函数 f f f，那么就存在强伪随机置换 F k ( 4 ) ( x ) F_k^{(4)}(x) Fk(4)​(x)，其中 k = { k 1 , k 2 , k 3 , k 4 } k={k_1,k_2,k_3,k_4} k={k1​,k2​,k3​,k4​}， ∣ k i ∣ = n |k_i|=n ∣ki​∣=n， x = ( L 0 , R 0 ) ∈ { 0 , 1 } 2 n x=(L_0,R_0) in {0,1}^{2n} x=(L0​,R0​)∈{0,1}2n，构造如下
L i : = R i − 1 R i : = L i − 1 ⊕ F k i ( R i − 1 ) L_i := R_{i-1}\ R_i := L_{i-1} oplus F_{k_i}(R_{i-1}) Li​:=Ri−1​Ri​:=Li−1​⊕Fki​​(Ri−1​)
最后将 ( L 4 , R 4 ) (L_4,R_4) (L4​,R4​)作为输出。这其实就是 4 4 4轮的Feistel network；如果是 3 3 3轮的，那么只是PRP，并不Strong

转换

1. 可以从PRG构造OWF，事实上 l ( n ) = 2 n l(n)=2n l(n)=2n的 G ( ⋅ ) G(cdot) G(⋅)它本身就是单向的，值域比定义域大 2 n 2^n 2n倍。

2. 使用线性反馈移位寄存器（Linear-Feedback Shift Registers，LFSRs）构造的流密码，它是PRG的候选。

3. 使用PRG可以构造窃听安全（Eavesdropper）的对称加密，

   • G e n Gen Gen：令 G G G是扩展因子为 l ( n ) l(n) l(n)的PRG，输入 1 n 1^n 1n，输出 k ∈ { 0 , 1 } n k in {0,1}^n k∈{0,1}n作为密钥
   • E n c Enc Enc：输入消息 m ∈ { 0 , 1 } l ( n ) m in {0,1}^{l(n)} m∈{0,1}l(n)，输出密文 c : = G ( k ) ⊕ m c:=G(k)oplus m c:=G(k)⊕m
   • D e c Dec Dec：输入密文 c ∈ { 0 , 1 } l ( n ) c in {0,1}^{l(n)} c∈{0,1}l(n)，输出明文 m : = G ( k ) ⊕ c m:=G(k)oplus c m:=G(k)⊕c

4. 可以从 E A V EAV EAV安全的对称加密构造OWF，构造为 f ( k , m , r ) : = E n c k ( m ; r ) ∣ ∣ m f(k,m,r):=Enc_k(m;r)||m f(k,m,r):=Enck​(m;r)∣∣m，其中 ∣ k ∣ = n , ∣ m ∣ = 2 n , ∣ r ∣ = l ( n ) |k|=n,|m|=2n,|r|=l(n) ∣k∣=n,∣m∣=2n,∣r∣=l(n)

5. 如果PRP存在，那么就存在 C C A CCA CCA安全的对称密码。

6. 利用PRF，可以构造固定长度（fixed-length）的MAC， Π = ( G e n , M a c , V r f y ) Pi=(Gen,Mac,Vrfy) Π=(Gen,Mac,Vrfy)

   • M a c Mac Mac：令 F F F是PRF，输入密钥 k ∈ { 0 , 1 } n k in {0,1}^n k∈{0,1}n和消息 m ∈ { 0 , 1 } n m in {0,1}^n m∈{0,1}n，输出 t : = F k ( m ) t:=F_k(m) t:=Fk​(m)

   • V r f y Vrfy Vrfy：输入 k , m , t ∈ { 0 , 1 } n k,m,t in {0,1}^n k,m,t∈{0,1}n，判断 t = F k ( m ) t = F_k(m) t=Fk​(m)是否满足

   • 它是在自适应选择消息攻击（Adaptive Chosen-message Attack）下的存在性不可伪造（Existentially Unforgeable）的，
     P r [ M a c − f o r g e A , Π ( n ) = 1 ] ≤ n e g l ( n ) Pr[Mac-forge_{A,Pi}(n)=1] le negl(n) Pr[Mac−forgeA,Π​(n)=1]≤negl(n)

7. 从固定长度的MAC，可以构造任意长度（variable-length）的MAC

   • M a c Mac Mac：令 Π ′ = ( M a c ′ , V r f y ′ ) Pi' = (Mac',Vrfy') Π′=(Mac′,Vrfy′)是固定长度的MAC，输入密钥 k ∈ { 0 , 1 } n k in {0,1}^n k∈{0,1}n和长度为 l < 2 n / 4 l < 2^{n/4} l<2n/4的消息 m ∈ { 0 , 1 } ∗ m in {0,1}^* m∈{0,1}∗，将 m m m做padding并分成若干块 m 1 , ⋯ , m d ∈ { 0 , 1 } n / 4 m_1,cdots,m_d in {0,1}^{n/4} m1​,⋯,md​∈{0,1}n/4，选择随机数 r ∈ { 0 , 1 } n / 4 r in {0,1}^{n/4} r∈{0,1}n/4，计算 t i = M a c k ′ ( r ∣ ∣ l ∣ ∣ i ∣ ∣ m i ) t_i = Mac_k'(r||l||i||m_i) ti​=Mack′​(r∣∣l∣∣i∣∣mi​)，输出 t : = ( r , t 1 , ⋯ , t d ) t:=(r,t_1,cdots,t_d) t:=(r,t1​,⋯,td​)（这里 ∣ t ∣ ∝ ∣ m ∣ |t| propto |m| ∣t∣∝∣m∣）
   • V r f y Vrfy Vrfy：输入 k , m , t k,m,t k,m,t，将 m m m分成 d ′ d' d′块，判断 d = d ′ d=d' d=d′和 ∀ 1 ≤ i ≤ d , V r f y k ′ ( r ∣ ∣ l ∣ ∣ i ∣ ∣ m i , t i ) = 1 forall 1le ile d, Vrfy_k'(r||l||i||m_i,t_i)=1 ∀1≤i≤d,Vrfyk′​(r∣∣l∣∣i∣∣mi​,ti​)=1是否都满足
   • 它也是 E U F − C M A EUF-CMA EUF−CMA的MAC

8. 利用PRF，可以构造任意长度的CBC-MAC

   • M a c Mac Mac其一：令 F F F是PRF，输入密钥 k ∈ { 0 , 1 } n k in {0,1}^n k∈{0,1}n和长度为 l < 2 n l < 2^n l<2n的消息 m ∈ { 0 , 1 } ∗ m in {0,1}^* m∈{0,1}∗，将 m m m做padding并分成若干块 m 1 , ⋯ , m d ∈ { 0 , 1 } n m_1,cdots,m_d in {0,1}^n m1​,⋯,md​∈{0,1}n，先计算 t 0 = F k ( l ) t_0 = F_k(l) t0​=Fk​(l)（长度必须前置），再迭代计算 t i = F k ( t i − 1 ⊕ m i ) t_i = F_k(t_{i-1} oplus m_i) ti​=Fk​(ti−1​⊕mi​)，输出 t : = t d t:=t_d t:=td​
   • M a c Mac Mac其二：令 F F F是PRF，输入密钥 k 1 , k 2 ∈ { 0 , 1 } n k_1,k_2 in {0,1}^n k1​,k2​∈{0,1}n和长度为 l < 2 n l < 2^n l<2n的消息 m ∈ { 0 , 1 } ∗ m in {0,1}^* m∈{0,1}∗，将 m m m做padding并分成若干块 m 1 , ⋯ , m d ∈ { 0 , 1 } n m_1,cdots,m_d in {0,1}^n m1​,⋯,md​∈{0,1}n，先设置 t 0 = I V t_0 = IV t0​=IV（必须是固定值），再迭代计算 t i = F k 1 ( t i − 1 ⊕ m i ) t_i = F_{k_1}(t_{i-1} oplus m_i) ti​=Fk1​​(ti−1​⊕mi​)，输出 t : = F k 2 ( t d ) t:=F_{k_2}(t_d) t:=Fk2​​(td​)

9. 一个 E U F − C M A EUF-CMA EUF−CMA的MAC，根据安全性定义，它就是OWF

10. 抗碰撞Hash函数 H : { 0 , 1 } 2 n → { 0 , 1 } n H:{0,1}^{2n} rightarrow {0,1}^n H:{0,1}2n→{0,1}n可以作为OWF，因为 P r [ I n v e r t A , f ( n ) ] = P r [ H a s h − c o l l A , Π ( n ) ) = 1 ] Pr[Invert_{A,f}(n)]=Pr[Hash-coll_{A,Pi}(n))=1] Pr[InvertA,f​(n)]=Pr[Hash−collA,Π​(n))=1]

11. 使用Merkle-Damgard Transform，可以将固定长度Hash函数 h s h^s hs转化为任意长度Hash函数 H H H，
    Z 1 : = h s ( I V ∣ ∣ m 1 ) Z i : = h s ( Z i − 1 ∣ ∣ m i ) H ( m ) : = h s ( Z B ∣ ∣ L ) Z_1 := h^s(IV||m_1)\ Z_{i} := h^s(Z_{i-1}||m_i)\ H(m) := h^s(Z_{B}||L) Z1​:=hs(IV∣∣m1​)Zi​:=hs(Zi−1​∣∣mi​)H(m):=hs(ZB​∣∣L)
    注意，这里的长度 L L L是后置的， I V IV IV是任意常数。

12. 使用抗碰撞Hash函数 h h h构造HMAC，
    k i n : = h s ( I V ∣ ∣ k ⊕ i p a d ) k o u t : = h s ( I V ∣ ∣ k ⊕ o p a d ) Z 1 : = h s ( k i n ∣ ∣ m 1 ) Z i : = h s ( Z i − 1 ∣ ∣ m i ) Z B + 1 : = h s ( Z B ∣ ∣ L ) t : = h s ( k o u t ∣ ∣ Z B + 1 ) k_{in} := h^s(IV||koplus ipad)\ k_{out} := h^s(IV||koplus opad)\ Z_1 := h^s(k_{in}||m_1)\ Z_{i} := h^s(Z_{i-1}||m_i)\ Z_{B+1} := h^s(Z_{B}||L)\ t := h^s(k_{out}||Z_{B+1}) kin​:=hs(IV∣∣k⊕ipad)kout​:=hs(IV∣∣k⊕opad)Z1​:=hs(kin​∣∣m1​)Zi​:=hs(Zi−1​∣∣mi​)ZB+1​:=hs(ZB​∣∣L)t:=hs(kout​∣∣ZB+1​)

13. 可以从因子分解、RSA、DLP等问题，构造出OWF、OWP、Hash等部件。

文献

[1] J. Katz and Y. Lindell. Introduction to modern cryptography. CRC press, 2020.