qudoku

一个嵌套阈值系统，可以补充Shamir的Secret Sharing (SSS)组，以任意数量的额外秘密，而不增加股东方面的存储负担。

[!警告]

此库是一个高度实验性的加密软件，专为特定用途设计。

不要在生产环境中使用此代码。

使用

有关使用文档，请参阅docs.rs。

背景

考虑一个阈值 $t$ 和 $n$ 个份额的某个共享秘密 $k$ 的Shamir的Secret Sharing (SSS)组。

经销商希望生成一个额外的秘密 $c$，只有当组中某些股东给出明确的同意时才能恢复。给予此类同意不会损害股东在主要组秘密 $k$ 中的份额。股东不需要存储除他们原始份额以外的任何其他数据。

示例：一个阈值恢复系统在服务器上存储加密的数据块，而解密密钥则在Shamir的Secret Sharing (SSS)组的成员之间分发。所有股东的联系方式在服务器上加密，使用密钥 $c$，这样如果某个股东启动恢复过程，所有股东都可以收到通知。然而，如果组中没有人为启动恢复，联系方式将保持秘密。

这有点像将一个秘密共享方案嵌套在另一个方案中，可能具有不同的（更小的）阈值。

简单解决方案

如果股东存储和同步不是问题，最简单的解决方案是创建第二个Shamir的Secret Sharing (SSS)组，除了原始SSS秘密 $k$ 之外，还分发秘密 $c$。股东将存储两个份额：一个在 $k$ 中，一个在 $c$ 中。

但是，在某些情况下，存储额外的份额是不切实际的。

• 如果我们需要为每一种100,000,000种不同的独立情况进行不同的且无关的秘密，那么这种方法将需要存储100,000,000 + 1个份额。
• 如果份额存储介质需要极其密集的编码，比如BIP39呢？

微妙的解决方案

我们不会将额外的秘密与每个股东一起存储，而是定义一些固定的常数参数，股东可以将这些参数与他们的股份结合使用，以重建秘密 $c$。$c$ 的重建可以由第三方执行，而第三方不会了解关于主组秘密 $k$ 的任何新信息。这种方法可以应用于现有的 SSS 组，而无需股东存储任何新信息。

先决条件

首先，让我们回顾一下我们的 SSS 组及其参数。

秘密共享多项式 $f(x)$ 是一个 $t-1$ 次多项式，它将秘密 $k$ 编码在某个固定的输出。例如，$k = f(0)$。这意味着恢复 $f(x)$ 意味着恢复 $k$。

由于 $f(x)$ 的次数是 $t-1$，没有知道 $t$ 或更多不同的 $f(x)$ 评估，就不能恢复 $f(x)$。这些评估中的每一个，$(i, f(i))$，都是 SSS 分享。

椭圆曲线

SSS 可以通过 椭圆曲线密码学 扩展，以支持更复杂的使用情况，例如 可验证秘密共享 (VSS)。我们将利用椭圆曲线群的同态性质，允许单个 SSS 组导出多个不同的秘密。

对于这个库，我们将使用 secp256k1 曲线。曲线的显著参数

椭圆曲线点可以相加和相减，但不能相互乘除。这意味着标量点乘法是一个单向操作，无法逆转（除非有量子计算机）。

算法

SSS 协议设计者必须首先固定一个选择的常数点 $Q$（这是 qudoku 命名的原因）。

选择 $Q$

该点必须具有一个重要的属性：它必须相对于曲线基点 $G$ 具有未知的离散对数。这意味着如果 $xG = Q$，那么 $x$ 必须存在，但不应该为任何人所知，包括交易者或协议设计者。知道 $x$ 的人将能够破坏 qudoku 的安全属性。

证明这样的点具有这种属性的最佳方法是使用“袖中藏物”方法，这种方法表明该点是按照一种方式选择的，即没有人能够在知道其离散对数的情况下故意选择它。

一个这样的例子是通过散列一些看起来诚实的数据来生成一个点，然后将该散列解释为椭圆曲线点的X坐标。安全散列函数的伪随机和不可预测性确保了X坐标是有效的随机数。这阻止了生成器选择一个具有已知离散对数的特定点。观察者可以提供输入数据，并重复散列操作以验证点确实是随机且诚实地选择的。

然而，并非所有散列输出都是secp256k1曲线上的有效X坐标，因此您可能需要将输出增加几次以找到有效的曲线点。

一旦找到有效的X坐标，可以选择与之相伴的奇数或偶数Y坐标 - 两者都是同样诚实且可用的。

计算$c$

$c$是我们给想要使共享的独立秘密的Shamir的秘密共享（SSS）组的符号。

让$j$是计算主秘密$k$的索引；即$f(j) = k$。在大多数SSS情况下，$j = 0$，因此秘密作为$f(x)$的常数项方便可用。

设$Z(x) := f(x) \cdot Q$

那么$c$定义为$Z(j)$的散列

$$ \begin{align} c\ :=&\ H(Z(j)) \ =&\ H(f(j) \cdot Q) \ =&\ H(kQ) \ \end{align} $$

因此$c$可以通过知道$f(x)$和$k$的经销商（或$t$或更多的股东，他们可以插值$f(x)$和$k$）来推导。然而，对于我们的目的来说，有趣的是，也可以在不了解$f(x)$或$k$的情况下学习$c$。

假设你被给出了$t$或更多的$Z(x)$评估。这将允许你完全插值$Z(x)$并计算$c = H(Z(j))$。但由于椭圆曲线点标量乘法是一个单向同态操作，因此使用你关于$Z(j)$的知识来计算$f(x)$或$k$是完全不切实际的。这个特性与Feldman的可验证的秘密共享（VSS）方案的安全特性相同。

恢复$Z(x)$

每个秘密共享组成员都拥有$Z(x)$的评估。每个份额$(i, f(i))$可以通过简单地乘以常数点$Q$转换为$Z(x)$的份额，得到份额$(i, f(i) \cdot Q) = (i, Z(i))$。

股东不需要在其份额旁边存储任何额外的信息；固定点$Q$可以硬编码到股东的软件中，或者由股东在事后选择。计算$Z(i)$的能力是任何在索引$i$拥有份额的股东隐含的能力。

为了分发秘密$c$，股东只需要计算$t$或更多$Z(i)$的份额，然后将这些份额发送给预期的接收者。

降低阈值

如果组希望降低学习$c$所需的最小安全阈值，怎么办？

目前，SSS组需要向接收者发送$t$或更多的$Z(x)$份额，因为$Z(x)$与其从其中导出的因函数$f(x)$具有相同的多项式度数($t-1$)。

要将此阈值从$t$降低到任何$t' \le t$，组或经销商必须与预期的接收者预先共享$Z(x)$的$t - t'$个评估。这个预先共享的评估集允许接收者仅使用稍后由股东提供的额外的$t'$个份额来插值$Z(x)$。

这些预先共享的评估必须使用一个与股东股份不同的输入 $i$。重新使用输入索引意味着一些股东无法对受助者帮助插值 $Z(x)$ 产生有意义的 影响，因为他们的 $Z(x)$ 股份可能已经为受助者所知。

预先共享的股份索引可以通过以下方式选择，例如

• 为预先共享的股份保留特定的索引，例如 $\{q-1, q-2, ... q-t'\}$，确保现有股东不会使用这些索引。
• 从 $[1, q)$ 中随机采样索引。因为 $q$ 非常大，所以与股东发生冲突的可能性非常小。

如果 SSS 经纪商可用，他们可以直接计算预先股份，因为他们知道 $Z(x)$。

如果没有，股东可能需要 使用多方计算直接向受助者发行预先股份。

根据我们之前加密恢复服务器的示例，SSS 群组将提前固定 $Q$，并将 $Z(x) = f(x) \cdot Q$ 的 $t-1$ 股份预先共享给恢复服务器。联系信息将用 $c = H(Z(s))$ 加密。当任何具有股份 $(i, f(i))$ 的股东启动恢复程序时，他们向服务器提供 $(i, Z(i))$，服务器随后可以插值 $Z(x)$ 并计算 $c = H(Z(s))$，从而允许其解密联系信息。

扩展到多个秘密

如果股东希望预先安排大量独立秘密，他们可以预先安排一组 $m$ 个固定的常数点 $\{Q_1, Q_2, ... Q_m\}$，这些点相对于彼此都必须有 未知的离散对数，从而有效地使它们成为 互质的。

_{技术上，sec256k1 曲线上没有两个点可以互质，因为总是存在共同因子，但只要这些共同因子是不可计算的，那就足以保证安全性。}

对于每个点 $Q_i$，股东定义 $Z_i(x) := f(x) \cdot Q_i$，并独立计算秘密 $c_i := H(Z_i(s))$。可以根据需要按秘密进行预先共享。

[!警告]

为什么所有的 $Q$ 点都必须是有效的互质的？

假设有两个点 $Q_1$ 和 $Q_2$，以及一个 $p$，使得 $p Q_1 = Q_2$。那么如果我们能够插值 $Z_1(x)$，我们也可以通过计算 $Z_1(x) \cdot p$ 来插值 $Z_2(x)$。

$$ \begin{align} Z_2(x) &= f(x) \cdot Q_2 \ &= f(x) \cdot Q_1 \cdot p \ &= Z_1(x) \cdot p \ \end{align} $$

假设所有的 $Q$ 点都是互质的，那么没有人可以将任何 $Z_a(x)$ 多项式的股份与另一个多项式 $Z_b(x)$ 相乘，因此所有派生秘密 $\{c_1, c_2, ... c_m\}$ 都是完全独立的。