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

• 公共参数：

  • 一个大素数模数 p（远大于所有中间值）
  • 一个比特长度 ℓ （假设 x, y < 2^ℓ）

第 0 步：秘密分片的定义

一个秘密数 x 是这样被“持有”的：

• Alice 持有：x_A

• Bob 持有：x_B

• 满足：

  x = x_A + x_B   (mod p)
  

❗ 关键事实：

• x_A 是随机数
• x_B 也是随机数
• 任何一方单独看，都对 x 一无所知

第 1 步：x、y 已经是秘密分片状态

一开始：

• Alice 持有：x_A , y_A
• Bob 持有：x_B , y_B

满足：

x = x_A + x_B
y = y_A + y_B

没人知道 x 或 y 的值。

第 2 步：秘密计算 z = x − y

各自本地算（无交互）：

• Alice：

  z_A = x_A − y_A   (mod p)
  

• Bob：

  z_B = x_B − y_B   (mod p)
  

于是：

z = z_A + z_B = x − y

现在的状态：

• Alice 只知道 z_A
• Bob 只知道 z_B
• z 的真实值无人知道

第 3 步：把“是否 x ≥ y”转化成一个数学判断

我们要判断：

x ≥ y  ⇔  z ≥ 0

但问题是：

• z 是秘密的
• 不能打开 z

第 4 步：模域偏移

大家共同约定一个常数：

K = 2^ℓ

然后秘密地计算：

w = z + K

各自本地算：

• Alice：

  w_A = z_A + K
  

• Bob：

  w_B = z_B
  

（也可以把 K 拆开给两人，不影响原理）

于是：

w = w_A + w_B = z + 2^ℓ

第 5 步：关键数学事实

因为 x, y < 2^ℓ，所以：

z = x − y ∈ (−2^ℓ , 2^ℓ)

因此：

结论：

w 的第 ℓ 位（二进制） 正好等于：x ≥ y 的判断结果

第 6 步：目标被彻底简化了

我们现在只需要一件事：

在不打开 w 的情况下，判断 w 的第 ℓ 位是 0 还是 1

第 7 步：秘密 bit-decomposition（不打开 w）

这一步是 SPDZ 的核心协议之一，但思想很朴素：

目标是得到：

w = b_0·2^0 + b_1·2^1 + ... + b_ℓ·2^ℓ + ...

其中：

• 每个 b_i ∈ {0,1}
• 每个 b_i 仍然是秘密分片的

也就是说：

• Alice 持有：b_{i,A}

• Bob 持有：b_{i,B}

• 满足：

  b_i = b_{i,A} + b_{i,B}   (mod p)
  

❗ 注意：

• 没有人看到某一位是 0 还是 1
• 只是把“一个秘密数”变成了“很多秘密 bit”

第 8 步：取出第 ℓ 位（这是你真正要的）

• 双方各自取自己手里的第 ℓ 位 share：

  • Alice：b_{ℓ,A}
  • Bob：b_{ℓ,B}

于是：

b_ℓ = b_{ℓ,A} + b_{ℓ,B}

第 9 步：只打开这一位（允许！）

协议允许：

• 只打开最终的比较结果 bit
• 不打开 w
• 不打开 z
• 不打开 x、y

打开后得到：

b_ℓ ∈ {0,1}

第 10 步：解释结果

• b_ℓ = 1 → x ≥ y
• b_ℓ = 0 → x < y

为什么整个过程没有泄漏任何数量级信息？

我逐条回答你最关心的点：

1️⃣ z 没被随机数“污染”，但仍然是秘密的

• z 是确定等于 x−y

• 但：

  • Alice 只有 z_A
  • Bob 只有 z_B

• 没有人知道 z

2️⃣ w 没被“打开”，随机性仍然存在

• bit-decomposition 是在秘密分片上做的
• 得到的是 秘密 bit
• 没有看到任何中间值

3️⃣ 为什么加 2^ℓ 后判断是有意义的？

因为这是一个严格数学等价：

z ≥ 0  ⇔  z + 2^ℓ ≥ 2^ℓ

随机性不参与这一步的语义，只参与“谁知道什么”。

• Next Post →