• 安全性归约（游戏）

    文章目录

    基于游戏的安全性定义

    在这里插入图片描述在这里插入图片描述在这里插入图片描述
    在将攻击 Γ \Gamma Γ 的算法 A ′ A' A′ 归约到攻击 Π \Pi Π 的算法 A A A 时，

    1. 让 A ′ A' A′ 根据 C h Γ Ch_\Gamma ChΓ​ 提供的信息，为 A A A 模拟出同分布的 C h Π Ch_\Pi ChΠ​，
    2. 然后 A ′ A' A′ 根据 A A A 针对 C h Π Ch_\Pi ChΠ​ 的输出，计算出针对 C h Γ Ch_\Gamma ChΓ​ 的输出。

    归约中的概率关系

    某事件发生

    归约过程中， A ′ A' A′ 归约到 A A A，两算法 A , A ′ A,A' A,A′ 的成功概率关系式为：
    P r [ A ′ = 1 ] = P r [ A = 1 ∧ E ] Pr[A'=1] = Pr[A=1 \wedge E] Pr[A′=1]=Pr[A=1∧E]
    其中 E E E 是 guess 事件，与事件 A = 1 A=1 A=1 相互独立。

    对于事件 A , B A,B A,B，由于相互独立，因此
    P r [ A , B ] = P r [ A , B ] = P r [ A ] ⋅ P r [ B ] \begin{aligned} Pr[A, B] &= Pr[A,B]=Pr[A] \cdot Pr[B]\\ \end{aligned} Pr[A,B]​=Pr[A,B]=Pr[A]⋅Pr[B]​
    类似的，
    P r [ A ∧ B 1 ∧ ⋯ ∧ B t ] = P r [ A ] ⋅ P r [ B 1 ∧ ⋯ ∧ B t ] \begin{aligned} Pr[A \wedge B_1 \wedge \cdots \wedge B_t] &= Pr[A] \cdot Pr[B_1 \wedge \cdots \wedge B_t]\\ \end{aligned} Pr[A∧B1​∧⋯∧Bt​]​=Pr[A]⋅Pr[B1​∧⋯∧Bt​]​

    假设

    1. 算法 A A A 的成功率 P r [ A = 1 ] ≥ 1 / p 1 ( n ) Pr[A=1] \ge 1/p_1(n) Pr[A=1]≥1/p1​(n) 不可忽略，
    2. 同时 P r [ E ] = 1 / p 2 ( x ) Pr[E] = 1/p_2(x) Pr[E]=1/p2​(x) 是多项式的，

    那么算法 A ′ A' A′ 的成功率也不可忽略，
    P r [ A ′ = 1 ] ≥ 1 p 1 ( n ) p 2 ( n ) Pr[A'=1] \ge \frac{1}{p_1(n)p_2(n)} Pr[A′=1]≥p1​(n)p2​(n)1​

    某事件不发生

    归约过程中， A ′ A' A′ 归约到 A A A，两算法 A , A ′ A,A' A,A′ 的成功概率关系式为：
    P r [ A ′ = 1 ] = P r [ A = 1 ∧ E ‾ ] Pr[A'=1] = Pr[A=1 \wedge \overline E] Pr[A′=1]=Pr[A=1∧E]

    其中 E E E 是 abort / stop 事件。

    对于事件 A , B A,B A,B，由于 1 = P r [ A , B ] + P r [ A , B ‾ ] + P r [ A ‾ , B ] + P r [ A ‾ , B ‾ ] 1 = Pr[A,B] + Pr[A,\overline B] + Pr[\overline A,B] + Pr[\overline A,\overline B] 1=Pr[A,B]+Pr[A,B]+Pr[A,B]+Pr[A,B]，因此
    P r [ A , B ‾ ] = P r [ A ] − P r [ B ] + P r [ A ‾ , B ] ≥ P r [ A ] − P r [ B ] \begin{aligned} Pr[A,\overline B] &= Pr[A] - Pr[B] + Pr[\overline A,B] \\ &\ge Pr[A] - Pr[B] \end{aligned} Pr[A,B]​=Pr[A]−Pr[B]+Pr[A,B]≥Pr[A]−Pr[B]​

    类似的，
    P r [ A ∧ B ‾ 1 ∧ ⋯ ∧ B ‾ t ] = P r [ A ] − P r [ B ‾ 1 ∧ ⋯ ∧ B ‾ t ‾ ] + P r [ A ‾ ∧ B ‾ 1 ∧ ⋯ ∧ B ‾ t ‾ ] ≥ P r [ A ] − P r [ B ‾ 1 ∧ ⋯ ∧ B ‾ t ‾ ] = P r [ A ] − P r [ B 1 ∨ ⋯ ∨ B t ] ≥ P r [ A ] − ∑ i = 1 t P r [ B i ] \begin{aligned} Pr[A \wedge \overline B_1 \wedge \cdots \wedge \overline B_t] &= Pr[A] - Pr[\overline{\overline B_1 \wedge \cdots \wedge \overline B_t}] + Pr[\overline A \wedge \overline{\overline B_1 \wedge \cdots \wedge \overline B_t}] \\ &\ge Pr[A] - Pr[\overline{\overline B_1 \wedge \cdots \wedge \overline B_t}]\\ &= Pr[A] - Pr[B_1 \vee \cdots \vee B_t]\\ &\ge Pr[A] - \sum_{i=1}^t Pr[B_i] \end{aligned} Pr[A∧B1​∧⋯∧Bt​]​=Pr[A]−Pr[B1​∧⋯∧Bt​​]+Pr[A∧B1​∧⋯∧Bt​​]≥Pr[A]−Pr[B1​∧⋯∧Bt​​]=Pr[A]−Pr[B1​∨⋯∨Bt​]≥Pr[A]−i=1∑t​Pr[Bi​]​

    假设

    1. 算法 A A A 的成功率 P r [ A = 1 ] ≥ 1 / p 1 ( n ) Pr[A=1] \ge 1/p_1(n) Pr[A=1]≥1/p1​(n) 不可忽略，
    2. 同时 E E E 发生的概率足够小，即 1 / p 1 ( n ) − P r [ E ] ≥ 1 / p 2 ( x ) 1/p_1(n) - Pr[E] \ge 1/p_2(x) 1/p1​(n)−Pr[E]≥1/p2​(x)，一般地 P r [ E ] = n e g l ( n ) Pr[E]=negl(n) Pr[E]=negl(n)

    那么算法 A ′ A' A′ 的成功率也不可忽略，
    P r [ A ′ = 1 ] ≥ P r [ A ] − P r [ E ] ≥ 1 / p 1 ( n ) − n e g l ( n ) Pr[A'=1] \ge Pr[A] - Pr[E] \ge 1/p_1(n) - negl(n) Pr[A′=1]≥Pr[A]−Pr[E]≥1/p1​(n)−negl(n)

    互斥事件

    归约过程中， A 1 ′ A_1' A1′​ 归约到 A A A，且 A 2 ′ A_2' A2′​ 归约到 A A A

    算法 A , A 1 ′ A,A'_1 A,A1′​ 的成功概率关系式为：
    P r [ A 1 ′ = 1 ] = P r [ A = 1 ∧ E ‾ ] Pr[A'_1=1] = Pr[A=1 \wedge \overline E] Pr[A1′​=1]=Pr[A=1∧E]
    算法 A , A 2 ′ A,A'_2 A,A2′​ 的成功概率关系式为：
    P r [ A 2 ′ = 1 ] = P r [ E ] Pr[A'_2=1] = Pr[E] Pr[A2′​=1]=Pr[E]
    其中 E E E 是 if-else 事件，它使得 A 1 ′ = 1 , A 2 ′ = 1 A_1'=1,A_2'=1 A1′​=1,A2′​=1 不会同时发生。

    由于
    P r [ A = 1 ] = P r [ A = 1 ∧ E ‾ ] + P r [ A = 1 ∧ E ] = P r [ A 1 ′ = 1 ] + P r [ A = 1 ∧ E ] ≤ P r [ A 1 ′ = 1 ] + P r [ E ] = P r [ A 1 ′ = 1 ] + P r [ A 2 ′ = 1 ] \begin{aligned} Pr[A=1] &= Pr[A=1 \wedge \overline E] + Pr[A=1 \wedge E]\\ &= Pr[A_1'=1] + Pr[A=1 \wedge E]\\ &\le Pr[A_1'=1] + Pr[E]\\ & = Pr[A_1'=1] + Pr[A_2'=1]\\ \end{aligned} Pr[A=1]​=Pr[A=1∧E]+Pr[A=1∧E]=Pr[A1′​=1]+Pr[A=1∧E]≤Pr[A1′​=1]+Pr[E]=Pr[A1′​=1]+Pr[A2′​=1]​
    于是，
    P r [ A 1 ′ = 1 ] ≥ P r [ A = 1 ] − P r [ A 2 ′ = 1 ] Pr[A_1'=1] \ge Pr[A=1] - Pr[A_2'=1] Pr[A1′​=1]≥Pr[A=1]−Pr[A2′​=1]
    如果算法 A A A 的成功率 P r [ A = 1 ] ≥ 1 / p o l y ( n ) Pr[A=1] \ge 1/poly(n) Pr[A=1]≥1/poly(n) 不可忽略，

    • 要么 P r [ A 2 ′ = 1 ] ≥ 1 / p o l y ( n ) Pr[A_2'=1] \ge 1/poly(n) Pr[A2′​=1]≥1/poly(n)， A 2 ′ A_2' A2′​ 的成功率不可忽略
    • 要么 P r [ A 2 ′ = 1 ] ≤ n e g l ( n ) Pr[A_2'=1] \le negl(n) Pr[A2′​=1]≤negl(n)，此时有 P r [ A 1 ′ = 1 ] ≥ P r [ A = 1 ] − n e g l ( n ) Pr[A_1'=1] \ge Pr[A=1] - negl(n) Pr[A1′​=1]≥Pr[A=1]−negl(n)， A 1 ′ A'_1 A1′​ 的成功率不可忽略
  • 相关阅读:
    LeetCode反转链表
    知识图谱从入门到应用——知识图谱的存储与查询：基于关系数据库的知识图谱存储
    puppeteer
    前后端分离：停车管理系统（Java后端，vue前端）
    QGIS编译（跨平台编译）之五十：MacOS环境下安装Python、pyqt5、pyqt5-tools等
    我，大厂测试员，降薪50%去国企，后悔了...
    VUE开发记录
    mstsc无法保存RDP凭据, 100%生效
    阿里云Serverless 极速搭建Hexo博客
    使用代理对象执行实现类目标方法异常
  • 原文地址：https://blog.csdn.net/weixin_44885334/article/details/127882020