渐近准最优密码学与通用可组合抗颠覆密码学解析

### 渐近准最优密码学与通用可组合抗颠覆密码学解析 #### 1. 通用可组合抗颠覆密码学基础 在通用可组合（UC）框架的拓展中，每个参与方由核心（具有秘密输入并负责生成协议消息）和反向防火墙（无秘密信息，对核心的进出通信进行净化）组成。核心和防火墙都可能受到不同类型的破坏，模拟了部分玩家恶意破坏，而其余诚实方遭受颠覆攻击的强对抗环境。 核心Ci的功能定义为： \[R := \{((\mu_i, s^*_i, \tau), (x_i, s_i, r_i)) : \mu_i = \Pi(x_i, \tau, s^*_i \oplus(s_i \oplus r_i))\}\] 这意味着核心Ci证明消息\(\mu_i\)是当输入序列为\(x_i\)、随机带为\(\hat{r}_i = s^*_i \oplus(s_i \oplus r_i)\)且当前转录为\(\tau\)时，由\(\Pi\)生成的正确下一条消息，然后将\(\mu_i\)附加到当前转录\(\tau\)上。 #### 2. 协议流程 - **防火墙验证**：当防火墙\(F_i\)从\(\hat{F}_{C\&P}\)接收到\((Sanitize, sid_i, C_i, (\mu_i, s^*_i, \tau))\)时，会验证\(s^*_i\)是否是通过\(F_{TOSS}\)获得的相同字符串，以及\(\tau\)是否包含到此时所有激活中广播的所有消息。若条件不满足，\(F_i\)会忽略该消息；否则，它会向\(\hat{F}_{C\&P}\)发送\((Continue, sid_i, C_i, (\mu_i, s^*_i, \tau))\)，并将\(\mu_i\)附加到当前转录\(\tau\)上。 - **消息追加**：当核心\(C_i\)和防火墙\(F_i\)从\(\hat{F}_{C\&P}\)接收到\((Proved, sid_j, C_j, (\mu_j, s^*_i, \tau))\)时，它们都会将\(\mu_j\)追加到转录\(\tau\)上，并重复上述步骤。 #### 3. 相关假设与安全性定理 - **假设**：假设底层协议\(\Pi\)是反应式的，通过一系列激活工作，每次激活只有一方有输入，为简化起见，每一方的随机带为\(\lambda\)位字符串。每一方需要调用独立的\(\hat{F}_{C\&P}\)副本，可表示为\(sid_i = sid||i\)。利用硬币抛掷功能\(F_{TOSS}\)简化随机性生成阶段，每个核心\(C_i\)通过\(\hat{F}_{C\&P}\)承诺一个随机字符串\(s_i\)，对应的防火墙\(F_i\)用随机字符串\(r_i\)对\(s_i\)进行盲化，各方通过\(F_{TOSS}\)获得公共随机字符串\(s^*_i\)，得到净化后的随机带\(\hat{r}_i = s^*_i \oplus(s_i \oplus r_i)\)。 - **安全性定理**：设\(F\)是\(n\)方的任何功能。假设\(\Pi\)在最多\(t \leq n - 1\)个半诚实破坏的情况下UC实现\(F\)，那么编译后的协议\(\hat{\Pi}_{GMW}\)在\((F_{SAT}, \hat{F}_{C\&P}, F_{TOSS})\)混合模型中，在最多\(t\)个恶意破坏的情况下wsrUC实现\(F\)。 #### 4. 渐近准最优密码学概述 Ishai、Kushilevitz、Ostrovsky和Sahai的工作提出了最小化密码学计算开销的目标，即安全实现给定大小为\(n\)的密码学任务所需的工作量（如布尔电路大小）与无安全要求实现相同任务所需工作量的渐近比率。在合理假设下，大多数密码学原语可以实现恒定计算开销，但这忽略了可能与具体计算安全参数\(\lambda\)多项式相关的附加项。 渐近准最优（AQO）密码学的目标是在所有\(n\)和