Asmuth-Bloom 方案

Asmuth-Bloom 方案是一种基于中国剩余定理（CRT）的门限秘密共享方案

它的核心思想是：将一个秘密 S 拆分成 n 个份额，只有当凑齐至少 t 个份额时，才能恢复出 S；任意少于 t 个份额不会泄露关于 S 的任何信息

方案参数设定

需要一组整数满足以下条件：

    1. 模数选择：m1, m2, ..., mn 两两互质
    1. 大小约束：对于门限 t，要求前 t 个最小的模数之积大于 m0 乘以后 t-1 个最大的模数之积
1
m1 * m2 * ... * mt > m0 * m_{n-t+2} * ... * m_n

这个条件保证了任何 t 个份额用 CRT 恢复的 x 落在正确范围内，且模 m0 后能唯一确定秘密；而任意 t-1 个份额会导致 x 的取值范围大于模数积，信息论上无法确定秘密

    1. 秘密范围：秘密 S 必须小于 m0：
1
0 <= S < m0

份额生成

输入：秘密 S，公共参数 m0, m1, ..., mn，门限 t

    1. 随机选取一个整数 A，使得构造的 x 满足：
1
x = S + A * m0

并且 x 落在区间 [0, m1*m2*...*mt) 内，通常取随机 A 足够大以保证安全性

    1. 为每个参与者计算份额 s_i：
1
s_i = x mod m_i,  (i = 1, 2, ..., n)

每个份额就是一个余数对 (s_i, m_i)

秘密恢复（任意 t 个份额）

输入：任意 t 个份额，假设选择的是 s_{i1}, s_{i2}, ..., s_{it}，对应的模数为 m_{i1}, ..., m_{it}

    1. 用 CRT 求解同余方程组
1
2
3
4
x ≡ s_{i1} (mod m_{i1})
x ≡ s_{i2} (mod m_{i2})
   ...
x ≡ s_{it} (mod m_{it})

得到唯一解 x' 在模 M = m_{i1} * ... * m_{it} 下

    1. 恢复秘密
1
S = x' mod m0

因为 x' = x（原构造值），而 x = S + A*m0，模 m0 自然得到 S

详细案例

设定参数

设定：门限 t=2，n=3，秘密 S=42

    1. 选取公开素数 m0=7（让 S=5，m0=7，满足 0 <= S < 7）
    1. 选模数序列：找 3 个两两互质的整数且满足大小约束（取 m1=11, m2=13, m3=17）
    1. 检查条件：t=2，前 2 个乘积 11*13 = 143，后 t-1=1 个最大模数乘积乘 m0：m0 * m3 = 7 * 17 = 119；因为 143 > 119，满足条件，若小于则需重新选取
    1. 构造 x：选取随机 A。通常 A 需要足够大使得 x 在 [0, m1*m2) 内且不可预测。这里简单起见取 A=9
1
2
3
x = S + A * m0 = 5 + 9 * 7 = 5 + 63 = 68

检查：68 < 143，在允许范围内
    1. 生成份额
1
2
3
4
5
s1 = 68 mod 11 = 2
s2 = 68 mod 13 = 3
s3 = 68 mod 17 = 0

份额为：(2,11), (3,13), (0,17)
    1. 恢复秘密（假设获得前两份额）
1
2
x ≡ 2 (mod 11)
x ≡ 3 (mod 13)
    1. 求 CRT 解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
N1 = 143 / 11 = 13

N1 = 143 / 11 = 13

13 mod 11 = 2

逆元：2 * 6 = 12 ≡ 1 mod 11

基数：M1 = 13 * 6 = 78

--------------------------------

N2 = 143 / 13 = 11

11 mod 13 = 11

逆元：11 * 6 = 66 ≡ 1 mod 13

基数：M2 = 11*6 = 66

--------------------------------

x' = 2*78 + 3*66
   = 156 + 198
   = 354 ≡ 354 mod 143
   = 354 - 2*143
   = 354 - 286
   = 68
    1. 提取秘密
1
2
3
S = x' mod 7
  = 68 mod 7
  = 5