语义安全
后续补充。
陷门置换
参考博客单陷门置换。
方案构造
直接采用单陷门定义构造如下：文章来源：https://www.toymoban.com/news/detail-430646.html
- 密钥生成：运行 G e n Gen Gen，得到 ( f , f − 1 ) (f,f^{-1}) (f,f−1)。令 p k = f , s k = f − 1 pk=f,sk=f^{-1} pk=f,sk=f−1。
- 加密算法： E ( ⋅ ) = f ( ⋅ ) E(\cdot)=f(\cdot) E(⋅)=f(⋅)
- 解密算法：
D
f
−
1
(
⋅
)
=
f
−
1
(
⋅
)
D_{f^-1}(\cdot)=f^{-1}(\cdot)
Df−1(⋅)=f−1(⋅)
由于 f ( ⋅ ) f(\cdot) f(⋅)是确定性的，例如RSA算法对于输入 x x x得到的 E ( x ) E(x) E(x)是确定的，因此其不能用于构造出语义安全的公钥加密方案。我们需要对其进行“随机化”，引入随机比特。
令 H = { h K : { 0 , 1 } K → { 0 , 1 } } K ≥ 1 H=\{h_{\mathcal{K}}:\{ 0,1 \}^{\mathcal{K}} \rightarrow \{ 0,1 \}\}_{\mathcal{K} \geq 1} H={hK:{0,1}K→{0,1}}K≥1， F F F是一个陷门置换。 H H H是 F F F的一个随机比特，如果对于所有的PPT敌手 A \mathcal{A} A，存在一个可忽略的函数 ε ( K ) \varepsilon(\mathcal{K}) ε(K)，使得 A \mathcal{A} A在下面的对抗中，优势 A d v A ( K ) ≤ ε ( K ) {Adv}_{\mathcal{A}}(\mathcal{K}) \leq \varepsilon(\mathcal{K}) AdvA(K)≤ε(K)：
F u n c t i o n A ( K ) : {Function}_{\mathcal{A}}(\mathcal{K}): FunctionA(K):
( f , f − 1 ) ← G e n ( K ) (f,f^{-1}) \leftarrow Gen(\mathcal{K}) (f,f−1)←Gen(K)；
x ← R { 0 , 1 } K x \leftarrow _{R}\{ 0,1 \}^{\mathcal{K}} x←R{0,1}K；
y = f ( x ) y=f(x) y=f(x)；
返回 A ( f , y ) A(f,y) A(f,y)
A \mathcal{A} A的优势定义为： A d v A ( K ) = ∣ P r [ F u n c t i o n A ( K ) = h K ( x ) ] − 1 2 ∣ {Adv}_{\mathcal{A}}(\mathcal{K})=\lvert Pr[{Function}_{\mathcal{A}}(\mathcal{K})=h_{\mathcal{K}}(x)] - \frac{1}{2} \rvert AdvA(K)=∣Pr[FunctionA(K)=hK(x)]−21∣。因为猜对随机比特的概率为 1 2 \frac{1}{2} 21，所以在这里可以减去 1 2 \frac{1}{2} 21当做 A \mathcal{A} A的优势。
下面构造随机比特：
设 h K ′ ( x ∣ r ) = x ⋅ r h_{\mathcal{K}}^{\prime}(x|r)=x \cdot r hK′(x∣r)=x⋅r， f : { 0 , 1 } K → { 0 , 1 } K f:\{ 0,1 \}^{\mathcal{K}} \rightarrow \{ 0,1 \}^{\mathcal{K}} f:{0,1}K→{0,1}K。定义一个新的置换 f ′ f^{\prime} f′, f ′ : { 0 , 1 } K → { 0 , 1 } K f^{\prime} : \{ 0,1 \}^{\mathcal{K}} \rightarrow \{ 0,1 \}^{\mathcal{K}} f′:{0,1}K→{0,1}K定义为 f ′ ( x ∣ r ) = f ( x ) ⊕ h ′ f^{\prime}(x|r)=f(x)\oplus h^{\prime} f′(x∣r)=f(x)⊕h′，其中 h ′ h^{\prime} h′为随机比特。
其中运算“ ⋅ \cdot ⋅”表示二元点乘。若 x = x 1 x 2 ⋯ x K ∈ { 0 , 1 } K , r = r 1 r 2 ⋯ r K ∈ { 0 , 1 } K x=x_1x_2 \cdots x_{\mathcal{K}} \in \{ 0,1 \}^{\mathcal{K}},r=r_1r_2 \cdots r_{\mathcal{K}} \in \{ 0,1 \}^{\mathcal{K}} x=x1x2⋯xK∈{0,1}K,r=r1r2⋯rK∈{0,1}K，则 x ⋅ r = x 1 r 1 ⊕ x 2 r 2 ⊕ ⋯ ⊕ r K x K x \cdot r=x_1r_1 \oplus x_2r_2 \oplus \cdots \oplus r_{\mathcal{K}}x_{\mathcal{K}} x⋅r=x1r1⊕x2r2⊕⋯⊕rKxK。
引入随机比特后的方案：
密钥产生过程：
G e n K e y ( K ) : GenKey(\mathcal{K}): GenKey(K):
( f , f − 1 ) ← G e n ( K ) (f,f^{-1})\leftarrow Gen(\mathcal{K}) (f,f−1)←Gen(K)
r ← R { 0 , 1 } K r \leftarrow _{R}\{ 0,1 \}^{\mathcal{K}} r←R{0,1}K
p k = ( f , r ) , s k = f − 1 pk=(f,r),sk=f^{-1} pk=(f,r),sk=f−1
加密过程（ M M M为待加密消息， M ∈ { 0 , 1 } M \in \{ 0,1 \} M∈{0,1}）：
E p k ( M ) : E_{pk}(M): Epk(M):
x ← R { 0 , 1 } K x \leftarrow _{R}\{ 0,1 \}^{\mathcal{K}} x←R{0,1}K
y = f ( x ) y=f(x) y=f(x)
h ′ = x ⋅ r h^{\prime}=x \cdot r h′=x⋅r
输出 ( y , h ′ ⊕ M ) (y,h^{\prime}\oplus M) (y,h′⊕M)
解密过程（ b b b为 h ′ ⊕ M h^{\prime}\oplus M h′⊕M）：
D s k ( y , b ) D_{sk}(y,b) Dsk(y,b)
输出 b ⊕ ( f − 1 ( y ) ⋅ r ) b \oplus (f^{-1}(y) \cdot r) b⊕(f−1(y)⋅r)
b ⊕ ( f − 1 ( y ) ⋅ r ) = ( h ′ ⊕ M ) ⊕ ( x ⋅ r ) = ( ( x ⋅ r ) ⊕ M ) ⊕ ( x ⋅ r ) = ( x ⋅ r ) ⊕ M ⊕ ( x ⋅ r ) = M b \oplus (f^{-1}(y) \cdot r)=(h^{\prime}\oplus M) \oplus (x \cdot r)=((x \cdot r)\oplus M) \oplus (x \cdot r)=(x \cdot r) \oplus M \oplus (x \cdot r)=M b⊕(f−1(y)⋅r)=(h′⊕M)⊕(x⋅r)=((x⋅r)⊕M)⊕(x⋅r)=(x⋅r)⊕M⊕(x⋅r)=M
案例
r = 011 , f ( 111 ) = 100 , f − 1 ( 100 ) = 111 , x = 111 , M = 1 r=011,f(111)=100,f^{-1}(100)=111,x=111,M=1 r=011,f(111)=100,f−1(100)=111,x=111,M=1，则有 y = f ( x ) = 100 , h ′ = ( 0 ∗ 1 ) ⊕ ( 1 ∗ 1 ) ⊕ ( 1 ∗ 1 ) = 0 , b = 0 ⊕ 1 = 1 y=f(x)=100,h^{\prime}=(0*1) \oplus (1*1) \oplus (1*1)=0,b=0 \oplus 1 = 1 y=f(x)=100,h′=(0∗1)⊕(1∗1)⊕(1∗1)=0,b=0⊕1=1。综上 M = 1 ⊕ ( 111 ⋅ 011 ) = 1 ⊕ ( 0 ⊕ 1 ⊕ 1 ) = 1 M=1 \oplus (111 \cdot 011) = 1 \oplus (0 \oplus 1 \oplus 1)=1 M=1⊕(111⋅011)=1⊕(0⊕1⊕1)=1。文章来源地址https://www.toymoban.com/news/detail-430646.html
到了这里，关于基于陷门置换的语义安全的公钥加密方案构造的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
