单向函数与弱单向函数

函数与弱单向函数"/>

单向函数与弱单向函数

单向函数与弱单向函数的区别：

密码学是建立在单向函数存在性假设之上的，那么单向函数是如何定义的呢？弱单向函数又是如何定义的呢？它们的区别是什么呢？ 

单向函数

一个函数 f : { 0 , 1 } ∗ → { 0 , 1 } ∗ f:\{ 0,1\}^*\rightarrow \{0,1\}^* f:{0,1}∗→{0,1}∗被称为单向函数，若满足：

• Easy to compute: 存在多项式时间算法 A \mathcal{A} A，满足对于 x ∈ { 0 , 1 } , A ( x ) = f ( x ) x\in \{0,1\},\mathcal{A}(x)=f(x) x∈{0,1},A(x)=f(x).
• Hard to invert: 对于任意PPT算法 A \mathcal{A} A和任意正多项式 p l o y ( ⋅ ) ploy(\cdot) ploy(⋅)，当 n n n充分大时，有 Pr ⁡ [ A ( f ( U n ) , 1 n ) ∈ f − 1 ( f ( U n ) ) ] < 1 p o l y ( n ) \operatorname{Pr}\left[A\left(f\left(U_n\right), 1^n\right) \in f^{-1}\left(f\left(U_n\right)\right)\right]<\frac{1}{p o l y(n)} Pr[A(f(Un​),1n)∈f−1(f(Un​))]<poly(n)1​
  其中 U n U_n Un​表示 { 0 , 1 } n \{0,1\}^n {0,1}n上的均匀分布， 1 n 1^n 1n表示安全参数为 n n n。

弱单向函数

一个函数 f : { 0 , 1 } ∗ → { 0 , 1 } ∗ f:\{ 0,1\}^*\rightarrow \{0,1\}^* f:{0,1}∗→{0,1}∗被称为单向函数，若满足：

• Easy to compute: 同单向函数。
• Hard to invert: 对于任意PPT算法 A \mathcal{A} A和存在正多项式 p l o y ( ⋅ ) ploy(\cdot) ploy(⋅)和 n n n(充分大)，有下式成立 Pr ⁡ [ A ( f ( U n ) , 1 n ) ∉ f − 1 ( f ( U n ) ) ] > 1 p o l y ( n ) \operatorname{Pr}\left[A\left(f\left(U_n\right), 1^n\right) \not\in f^{-1}\left(f\left(U_n\right)\right)\right]>\frac{1}{p o l y(n)} Pr[A(f(Un​),1n)∈f−1(f(Un​))]>poly(n)1​
  其中 U n U_n Un​表示 { 0 , 1 } n \{0,1\}^n {0,1}n上的均匀分布， 1 n 1^n 1n表示安全参数为 n n n。

（强）单向函数与弱单向函数的区别

\quad 单向函数条件更强一点，单向函数要求对于 x ∈ U n x\in U_n x∈Un​中的绝大多数满足难求逆，也就是说，可以求逆的 x ∈ U n x\in U_n x∈Un​相对于多项式时间来讲是可忽略的。
\quad 弱单向函数只需要满足难求逆的 x ∈ U n x\in U_n x∈Un​是显著的即可(注意显著 ≠ \neq =不可忽略!!!)。