统计安全两方计算的再探索

### 统计安全两方计算的再探索 #### 1. 技术概述 在两方计算中，实现安全且高效的协议是一个重要的研究方向。这里展示了通过一个三轮统计接收方私有基本不经意传输（elementary OT，简称 eOT）协议和一个非交互承诺方案，能够获得一个五轮（轮次最优）的两方计算（2PC）协议，该协议能抵御计算能力无界的接收方和概率多项式时间（PPT）的发送方的攻击。 ##### 1.1 单边统计两方计算协议 我们的编译器基于前人的工作进行改进，前人构建了一个五轮的 2PC 协议来抵御恶意对手。该协议涉及两个参与方：接收方计算能力无界，在第四轮结束时获得输出；发送方计算能力受限，在第五轮结束时获得输出。协议通过两个转换步骤实现：先构建一个能抵御可解释对手的协议，然后通过交互式证明将其编译为能抵御恶意对手的协议。 - **抵御可解释对手的健壮 2PC**：可解释对手生成的协议消息处于所有诚实生成的传输记录分布的支持范围内，模拟器需要从传输记录中提取对手方的输入和随机性。在这种情况下，经典的基于混淆电路的方法（接收方为评估者，发送方为混淆者）不再适用，因为接收方计算能力无界，而信息论上的私有混淆方案仅适用于 NC1 电路。 - **角色反转**：采用不同的方法，让接收方混淆电路，发送方评估电路。发送方通过统计接收方私有 OT 获得与输入对应的线标签，从而对无界的恶意接收方隐藏其输入。OT 协议需要三轮，从接收方（作为 OT 的发送方）开始，接收方在第三轮发送混淆电路。 - **针对可解释方的模拟**：模拟器需要通过提取可解释对手的输入来进行模拟。为了提取恶意发送方的输入，发送方需要使用四轮统计隐藏且计算绑定的可提取承诺方案对其输入进行承诺。同样，接收方使用三轮统计绑定且计算隐藏的可提取承诺方案对其输入和随机性进行承诺。这些承诺允许模拟器提取可解释对手方的输入和随机性。 - **最后修改**：为了避免模拟中的问题，接收方混淆一个不同的电路，使得混淆电路计算输出的加密。发送方在第三轮结束时获得混淆电路，对其进行评估以获得加密输出，然后在第四轮将其发送给接收方。接收方解密输出并在第五轮将其发送给发送方。在理想世界中，模拟器向恶意发送方发送一个模拟的混淆电路，该电路输出 0 的加密，从而在理想世界中提供正确的模拟。 前人工作得到了一个健壮的 5 轮安全两方计算协议 πexp，具有黑盒模拟，能抵御无界的可解释接收方和 PPT 可解释发送方。其底层原语如下： | 原语 | 描述 | | ---- | ---- | | 三轮不经意传输 | 接收方具有统计隐私，发送方具有计算隐私 | | 三轮统计绑定且计算隐藏的承诺方案 | 满足可提取性 | | 四轮统计隐藏且计算绑定的承诺方案 | 满足可提取性 | | NC1 电路的信息论混淆电路 | 用于验证特定的 NC1 关系 | 我们的贡献在于证明了 eOT 协议和非交互承诺方案足以实例化上述原语，从而从 eOT 和非交互承诺方案得到协议 πexp。具体如下： 1. 从 eOT 以保轮的方式构建满足不可区分性发送方安全的三轮 SRP - OT 协议（iOT）。 2. 从任何非交互承诺方案构建三轮统计绑定且计算隐藏的承诺方案。 3. 通过将非交互承诺方案替换为两轮统计隐藏承诺方案，得到四轮统计隐藏且计算绑定的可提取承诺方案。我们从 SRP iOT 构建两轮统计隐藏承诺方案。 4. 从单向函数获得混淆电路。 ##### 1.2 最终编译器 为了将 πexp 的安全性提升到能抵御恶意对手，使用零知识协议： - **应对恶意发送方**：发送方需要证明其正确生成了 πexp 的第二轮和第四轮消息。这通过一个四轮延迟输入统计零知识协议（SZK）来完成，输入语句由发送方（作为证明者）在 SZK 的最后一轮选择。SZK 与 πexp 并行运行，πexp 前两轮的健壮性确保即使恶意发送方错误构造第二轮消息，诚实接收方的输入也不会泄露。 - **应对恶意接收方**：接收方需要证明其正确生成了 πexp 的第一轮、第三轮和第五轮消息。这通过一个五轮延迟输入零知识证明（ZKP）来完成，输入语句由接收方（作为证明者）在 ZKP 的最后一轮选择。ZKP 与 πexp 并行运行，πexp 前两轮的健壮性确保即使恶意接收方错误构造第一轮消息，诚实发送方的输入也不会泄露。然而，恶意构造的 πexp 第三轮消息可能会在发送方发送第四轮消息时泄露诚实发送方的输入，ZKP 无法解决这个问题。 - **条件秘密披露**：为了解决上述问题，使用两轮条件秘密披露（CDS）协议。接收方在发送 πexp 的第三轮消息时附带 CDS 的公钥。发送方使用 CDS 公钥和输入语句对 πexp 的第四轮消息进行加密。如果接收方能够提供证明其第一轮和第三轮消息可解释的见证，则成功解密第四轮消息；否则，CDS 明文（πexp 的第四轮消息）保持统计隐藏。 mermaid 流程图如下： ```mermaid graph LR A[开始] --> B[构建 πexp] B --> C{应对恶意发送方} B --> D{应对恶意接收方} C --> E[SZK 证明] D --> F[ZKP 证明] D --> G[CDS 协议] E --> H[协议完成] F --> H G --> H ``` #### 2. 从 eOT 构建组件 接下来介绍从 eOT 构建的几个重要原语。 ##### 2.1 三轮统计接收方私有 eOT 引入了纯模型下统计接收方私有基本 OT 的概念。它是一个三轮的 OT 协议，发送方发送第一条消息作为预处理阶段，接收方根据其选择位发送第二条消息，发送方发送第三条消息。发送方获得随机输出。基本安全性确保恶意接收方无法计算出发送方的两个输出，统计接收方隐私意味着选择位对恶意发送方统计隐藏。可以通过 OT 反转技术从两轮统计发送方私有 OT 构建 eOT，从而从多种假设（如 LWE、QR、N 次剩余性、DDH、决策 CSIDH 和 LPN + Nissan Wigderson 去随机化）中获得实例。还基于 CDH 假设和互逆 CSIDH 假设构建了 eOT。 ##### 2.2 三轮统计接收方私有 iOT 提升 eOT 的安全性以构建 iOT，使其获得针对恶意接收方的不可区分性安全。如果接收方的选择位是 γ，则 m1 - γ 对恶意接收方在计算上与随机字符串不可区分。通过基于 Goldreich - Levin 哈希函数的基本 OT 到不可区分性安全 OT 的转换，以保轮的方式实现这一点，从而从与 eOT 相同的假设集合中获得 iOT。 ##### 2.3 三轮延迟输入统计发送方私有 SSPOT 引入了延迟输入统计发送方私有 SSPOT 的概念，其中只有最后一条 OT 消息依赖于接收方的选择位 γ。它是一个三轮的 OT 协议，接收方发送第一条消息作为接收方预处理阶段，发送方发送第二条消息作为发送方预处理阶段，接收方根据 γ 发送第三条消息。发送方获得随机输出字符串。通过对三轮 SRP iOT 仔