Invisibook

第一章 问题背景与核心挑战

1.1 什么是秘密加法

在安全多方计算（MPC）中，两个参与方（Alice 和 Bob）各自持有一个二进制数的秘密份额，想要计算两个数的和，但不能泄露任何一个操作数的明文。这里的"秘密份额"指的是布尔秘密共享：一个比特 x 被拆成两个份额 x₁ 和 x₂，满足 x = x₁ ⊕ x₂，其中 ⊕ 是异或运算。Alice 持有 x₁，Bob 持有 x₂，任何一方单独看自己的份额都是一个均匀随机的比特，无法推断出 x 的真实值。

安全多方计算（MPC）允许多个参与方在不暴露各自私有数据的前提下，共同计算一个函数的值。SPDZ 是一种被广泛使用的 MPC 协议，它不仅保护隐私，还能抵抗恶意行为者，即使某些参与方试图作弊或篡改数据，协议也能检测出来并保证结果正确性。其关键技术之一就是信息论安全的消息认证码（MAC）机制。

Alice 和 Bob，他们手里分别持有一个无符号整数，Alice持有x， Bob持有y。
此时他们想互相比较出x和y的大小关系， 但同时又不想泄漏自己手里具体的数，此时我们该如何解决呢？