无设置模型下广播最优四轮多方安全计算

### 无设置模型下广播最优四轮多方安全计算 #### 1. 引言 在多方安全计算（MPC）领域，如何在不同的通信模式和安全要求下优化协议是一个重要的研究方向。本文聚焦于无设置（Plain Model）的不诚实多数场景下的四轮MPC协议，探讨广播的优化使用，以实现不同的安全目标，如选择性中止（SA）、一致中止（UA）和可识别中止（SIA）。 #### 2. 相关概念和符号 在深入探讨具体协议之前，先了解一些必要的概念和符号： - **多方安全计算（MPC）**：允许多个参与方在不泄露各自输入的情况下共同计算一个函数。 - **算法表示**： - `frst-msgi(xi; ri) → (msg1i→1, ..., msg1i→n)`：计算参与方Pi的第一轮消息。 - `nxt-msgki (xi, {msglj→i}j∈[n],l∈{1,2,...,k}; ri) → (msgk+1i→1, ..., msgk+1i→n)`：计算Pi的第(k + 1)轮消息。 - `outputi(xi, msg11→i, ..., msg1n→i, ..., msgj1→i, ..., msgjn→i; ri) → yi`：计算Pi的输出。 - **通信模式**： - **BC**：表示广播可用的轮次。 - **P2P**：表示仅使用点对点通信的轮次。 - **P2Px (BCx)**：表示x轮的点对点（广播）通信。 #### 3. 技术细节与关键路径分析 ##### 3.1 输入提取原理 在某些场景下，攻击者（ASA）可以通过内部运行模拟器（SSA1,out）来提取诚实方P′1的输入。具体过程如下： 1. 攻击者知道并能决定诚实方的输入。 2. 当第i个会话到来时，通过对代表P′2接收的消息进行伪随机函数（PRF）评估生成输入x1。 3. 启动不可区分性游戏，挑战者以x1为输入。 4. 模拟器SSA1,out在第i个会话查询理想功能时返回˜x1，当挑战者使用诚实过程计算消息时，˜x1 = x1；否则，概率较小。 这个过程可以用以下流程图表示： ```mermaid graph TD; A[攻击者决定诚实方输入] --> B[第i个会话生成输入x1]; B --> C[启动不可区分性游戏]; C --> D[模拟器返回˜x1]; D --> E{˜x1 = x1?}; E -- 是 --> F[挑战者使用诚实过程]; E -- 否 --> G[挑战者生成模拟消息]; ``` ##### 3.2 第一轮回退 当SSA1,out对抗上述定义的快速攻击者（P ⋆′1根据对P′2第一轮消息应用PRF的输出改变其输入）时，ASA可以本地模拟P ⋆′1在回退期间获得的第一轮和第二轮消息，因为他控制P ⋆′2和P ⋆′out。 #### 4. 相关工作对比 | 工作 | 轮数 | 安全设置 | 通信模式 | 特点 | | ---- | ---- | ---- | ---- | ---- | | [13] | 2 | 不诚实多数，有设置 | 研究多种广播模式 | 开启广播最优MPC研究 | | [14,15] | 2 | 诚实多数，有设置 | 研究多种广播模式 | - | | [20] | 2 | 无设置 | 不同通信模型 | 不考虑广播限于一轮的模式 | | [4] | 3 | 诚实多数，有CRS | 广播最优 | 前两轮需广播 | | 本文 | 4 | 不诚实多数，无设置 | 多种P2P和BC组合 | 优化广播使用 | #### 5. 正向结果 ##### 5.1 P2P 4, SA, Plain Model, n > t 我们可以构造一个四轮协议ΠSAp2p4，实现选择性中止（SA）安全，仅依赖点对点通信。具体步骤如下： 1. **第一轮（P2P）**： - 计算Pi在Πbc中的第一轮消息`msg1i ← frst-msgi(xi)`。 - 生成加密电路`(GCi, Ki) ← garble(1λ, C1i,xi)`。 - 对加密标签进行加法秘密共享。 - 向每个参与方Pj发送消息`(msg1i, GCi, {Kbi→j,α}α∈[L],b∈{0,1})`。 2. **第二轮（P2P）**： - 检查是否收到消息，若未收到则中止。 - 拼接收到的第一轮消息。 - 发送加密电路和对应标签份额。 3. **第三轮（P2P）**： - 检查消息和加密电路的一致性，不一致则中止。 - 重构加密标签。 - 评估加密电路得到`msg2j`。 - 计算Pi在Πbc中的第三轮消息`msg3i ← nxt-msg2i (xi, {msg1j→i}j∈[n], {msg2j}j∈[n])`。 - 生成新的加密电路和标签份额并发送。 4. **第四轮（P2P）**： - 检查消息，未收到则中止。 - 拼接收到的第三轮消息。 - 发送加密电路和对应标签份额。 5. **输出计算**： - 检查消息，未收到则中止。 - 重构加密标签。 - 评估加密电路得到`msg4j`。 - 计算并输出`y ← outputi(xi, {msg1j→i}j∈[n], {msg2j}j∈[n], {msg3j→i}j∈[n], {msg4j}j∈[n])`。 ```python # 伪代码示例 # 第一轮 msg1_i = frst_msgi(xi) GCi, Ki = garble(1λ, C1i,xi) # 标签份额生成 # 发送消息 # 第二轮 # 接收消息检查 # 拼接消息 # 发送加密电路和份额 # 第三轮 # 接收消息检查 # 电路一致性检查 # 重构标签 # 评估电路 msg3_i = nxt-msg2i (xi, msg1_j_i_list, msg2_j_list) # 生成新电路和份额 # 发送消息 # 第四轮 # 接收消息检查 # 拼接消息 # 发送加密电路和份额 # 输出计算 # 接收消息检查 # 重构标签 # 评估电路 y = outputi(xi, msg1_j_i_list, msg2_j_list, msg3_j_i_list, msg4_j_list) ``` 该协议的安全性基于Πbc的安全性，通过加法秘密共享确保诚实方对消息的一致视图。 ##### 5.2 P2P 3 - BC, UA, Plain Model, n > t 当最后一轮使用广播通道时，上述协议可以实现一致中止（UA）安全。直观上，诚实方依赖最后一轮广播来一致恢复输出。如果在最后一轮之前检测到任何不一致，诚实方会发出中止信号。最后一轮广播加密电路的加法份额，防止攻击者仅让部分诚实方成功评估电路并获得输出。 ##### 5.3 BC3 - P2P, SIA, Plain Model, n > t 考虑一个四轮的可识别中止（IA）MPC协议Πbc，假设存在一个能在前三轮提取攻击者输入的模拟器。通过将最后一轮改为点对点通信，可以构造一个选择性可识别中止（SIA）协议Π。由于模拟器在前三轮提取攻击者输入，最后一轮攻击者只能决定诚实方是否获得输出或识别作弊者，两个诚实方不会获得不同的非⊥输出，满足SIA安全要求。 #### 6. 总结 本文在不诚实多数且无设置的场景下，针对四轮MPC协议提出了多种优化广播使用的方案，实现了选择性中止、一致中止和可识别中止等不同的安全目标。通过详细的技术分析和协议构造，展示了在不同通信模式下如何保障协议的安全性。这些研究成果为MPC在实际应用中的优化提供了有价值的参考。 #### 7. 展望 未来的研究可以进一步探索在更多轮次和不同安全场景下广播的优化使用，以及如何降低协议的复杂度和通信开销，提高协议的效率和实用性。同时，可以考虑结合其他密码学技术，进一步增强协议的安全性。 ### 无设置模型下广播最优四轮多方安全计算 #### 8. 技术点深入分析 ##### 8.1 加密电路与秘密共享的协同作用 在协议ΠSAp2p4中，加密电路和加法秘密共享起到了关键作用。加密电路用于计算后续轮次的消息，而秘密共享则保证了诚实方对消息的一致视图。具体来说，在第一轮和第三轮，各方生成加密电路并将其标签进行加法秘密共享。在后续轮次中，各方根据接收到的消息和份额重构标签，然后评估加密电路。 例如，在第一轮，Pi生成加密电路`(GCi, Ki)`，并将标签份额`{Kbi→j,α}`发送给其他各方。在第二轮，各方根据接收到的第一轮消息和份额，拼接消息并发送加密电路和对应标签份额。这样，只有当各方发送的第一轮消息一致时，才能成功重构标签并评估加密电路。 这种协同作用可以用以下步骤表示： 1. 生成加密电路和标签。 2. 对标签进行加法秘密共享。 3. 发送消息和份额。 4. 接收消息和份额，拼接消息。 5. 重构标签。 6. 评估加密电路。 ```mermaid graph TD; A[生成加密电路和标签] --> B[加法秘密共享]; B --> C[发送消息和份额]; C --> D[接收消息和份额，拼接消息]; D --> E[重构标签]; E --> F[评估加密电路]; ``` ##### 8.2 不同安全目标下的协议调整 不同的安全目标（SA、UA、SIA）需要对协议进行相应的调整。 - **选择性中止（SA）**：协议ΠSAp2p4通过加密电路和秘密共享确保诚实方对消息的一致视图，防止攻击者通过发送不一致的消息获取优势。 - **一致中止（UA）**：在P2P 3 - BC协议中，最后一轮使用广播通道，诚实方依赖最后一轮广播来一致恢复输出。如果在最后一轮之前检测到任何不一致，诚实方会发出中止信号。 - **选择性可识别中止（SIA）**：在BC3 - P2P协议中，假设存在一个能在前三轮提取攻击者输入的模拟器。最后一轮改为点对点通信，攻击者只能决定诚实方是否获得输出或识别作弊者，两个诚实方不会获得不同的非⊥输出。 | 安全目标 | 协议调整 | | ---- | ---- | | SA | 仅使用P2P通信，通过加密电路和秘密共享确保消息一致性 | | UA | 最后一轮使用广播通道，依赖广播恢复输出 | | SIA | 前三轮使用广播，最后一轮使用P2P，依赖模拟器提取攻击者输入 | #### 9. 实际应用考虑 ##### 9.1 通信开销 在实际应用中，通信开销是一个重要的考虑因素。不同的通信模式（P2P和BC）会对通信开销产生影响。例如，广播通道可以减少消息的发送次数，但可能会增加带宽需求。而点对点通信则需要更多的消息发送，但可以更灵活地控制消息的传递。 在协议设计中，需要根据具体的应用场景和需求，权衡不同通信模式的优缺点，选择合适的通信模式。例如，在网络带宽有限的情况下，可以优先选择P2P通信；而在需要快速传播消息的场景下，可以考虑使用广播通道。 ##### 9.2 计算复杂度 协议的计算复杂度也是一个关键因素。加密电路的生成和评估、秘密共享的操作等都会增加计算开销。在实际应用中，需要优化算法和数据结构，降低计算复杂度。例如，可以使用更高效的加密算法和秘密共享方案，减少计算时间和资源消耗。 #### 10. 潜在挑战与解决方案 ##### 10.1 攻击者策略的多样性 攻击者可能会采用各种策略来破坏协议的安全性。例如，攻击者可能会发送不一致的消息、篡改加密电路或标签份额等。为了应对这些挑战，需要设计更健壮的协议和安全机制。 解决方案包括： - 增加消息验证机制，确保消息的完整性和一致性。 - 对加密电路和标签份额进行签名，防止篡改。 - 引入随机化机制，增加攻击者的攻击难度。 ##### 10.2 网络延迟和故障 网络延迟和故障可能会影响协议的正常执行。例如，消息的延迟到达可能会导致诚实方在错误的时间进行操作，从而影响协议的安全性。 解决方案包括： - 引入超时机制，当消息在规定时间内未到达时，采取相应的措施。 - 设计容错机制，确保协议在网络故障的情况下仍能正常运行。 #### 11. 总结与回顾 本文围绕不诚实多数且无设置的场景下的四轮MPC协议，详细探讨了广播的优化使用。通过构造不同的协议，实现了选择性中止、一致中止和可识别中止等不同的安全目标。具体内容包括： - 介绍了相关概念和符号，为后续的协议设计和分析奠定基础。 - 分析了输入提取原理和第一轮回退机制，展示了攻击者如何通过内部运行模拟器提取诚实方的输入。 - 对比了相关工作，突出了本文在优化广播使用方面的创新点。 - 详细描述了三个正向结果协议（P2P 4, SA；P2P 3 - BC, UA；BC3 - P2P, SIA）的构造和安全性分析。 - 深入分析了加密电路与秘密共享的协同作用，以及不同安全目标下的协议调整。 - 考虑了实际应用中的通信开销和计算复杂度，提出了相应的优化建议。 - 讨论了潜在挑战和解决方案，为协议的实际应用提供了保障。 #### 12. 未来研究方向展望 未来的研究可以从以下几个方面展开： - **更多轮次和不同安全场景**：进一步探索在更多轮次和不同安全场景下广播的优化使用，设计更高效、更安全的协议。 - **降低复杂度和开销**：研究如何降低协议的复杂度和通信开销，提高协议的效率和实用性。例如，探索更高效的加密算法和秘密共享方案。 - **结合其他密码学技术**：考虑结合其他密码学技术，如零知识证明、同态加密等，进一步增强协议的安全性。 - **实际应用验证**：将研究成果应用到实际场景中，进行验证和优化，确保协议在实际环境中的可行性和有效性。 通过不断的研究和创新，有望推动MPC技术在更多领域的应用，为信息安全和隐私保护提供更强大的支持。