函数与弱单向函数"/>
单向函数与弱单向函数
单向函数与弱单向函数的区别:
密码学是建立在单向函数存在性假设之上的,那么单向函数是如何定义的呢?弱单向函数又是如何定义的呢?它们的区别是什么呢?
单向函数
一个函数 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 =不可忽略!!!)。
更多推荐
单向函数与弱单向函数
发布评论