可验证的秘密共享简介

最编程 2024-04-30 07:36:05

...

一、秘密共享的实践

最近FATE开源社区分享了「基于FATE实现的可验证秘密共享算法」一文（后简称实现），介绍了光大科技在联邦学习技术实践过程中，针对跨机构数据统计这一场景，实践了可验证秘密共享（Verifiable Secret Sharing）的安全多方隐私求和方案，能够在数据不出本地的情况下，对多个机构的数据求和。

按照原文介绍可知，该场景是对Shamir秘密共享和可验证秘密共享的综合应用（整体方案参见原文）。

这里对文中涉及的可验证秘密共享做一个简单说明。

二、可验证秘密共享简介

可验证秘密共享（Verifiable Secret Share, VSS）的概念由 Benny Chor、Shafi Goldwasser、Silvio Micali 和 Baruch Awerbuch 于 1985 年首次提出：如果参与方可以使用辅助信息验证其他参与方秘密共享内容的一致性，那么该秘密共享方案就是可验证的。可验证的秘密共享确保了即使某参与方是恶意的，也必须有一个明确定义的秘密（遵循协议设定），其他参与方稍后可以恢复秘密值。

注：经典的Shamir秘密共享方案中，假参与方是诚实的。

可验证的秘密共享对于安全多方计算来说还是很重要的。我们知道，安全多方计算通常是通过对输入进行秘密共享并操作共享来计算某些函数完成的。为了应对可能“捣乱”的参与方，可以对秘密共享的安全性进行增强，额外添加验证操作，防止（或及早发现）这些参与方的偏离协议行为。

下文对Feldman的可验证秘密共享方案进行简单说明。

三、Feldman的可验证秘密共享方案

Feldman VSS是一个常见的可验证秘密共享方案，由 Paul Feldman 提出（参见其论文：「A Practical Scheme for Non-interactive Verifiable Secret Sharing」）；它在 Shamir 秘密共享之上结合了同态加密方案。

该方案中首先选取一个素数( $q$ )阶的循环群 $G$ 以及 $G$ 的生成元 $g$ ，这些会公开作为系统参数。选择适合的循环群 $G$ 以保证其上离散对数计算的困难性。通常，可以选择 $(\mathbb{Z}_p)^*$ 的 $q$ 阶子群，其中 $p，q$ 是素数，且 $q$ 整除 $p−1$ 。

然后处理方生成一个 $t$ 次随机多项式 $P$ ，其系数在 $Z_q$ 中选取，且 $P(0)=s$ （即是秘密值）。 $n$ 个参与方中的每一个都将收到一个值 $P(1), \dots, P(n) \bmod q$ 。任何 $t+1$ 个秘密分享的持有者都可以使用多项式插值模 $q$ 恢复秘密 $s$ （但任何最多 $t$ 个持有者们都不能恢复秘密值）。

以上基本是Shamir秘密共享方案。为了使这些共享可以验证，参与方需要分发 $P$ 多项式系数模 $p$ 作为承诺（commitment）。

比如， $P(x)=s+a_1x+a_2x^2+\dots+a_tx^t$ ，那么必须给出的承诺是：

$c_0=g^s \bmod p$
$c_1=g^{a1}\bmod p$
...
$c_t=g^{a_t}\bmod p$

一旦给出这些，任何一方都可以验证他们的得到的秘密分享。例如，为了验证 $v = P(i) \bmod q$ ，如：

$g^{v}=c_{0}c_{1}^{i}c_{2}^{i^{2}}\cdots c_{t}^{i^{t}}=\prod _{j=0}^{t}c_{j}^{i^{j}}=\prod _{j=0}^{t}g^{a_{j}i^{j}}=g^{\sum _{j=0}^{t}a_{j}i^{j}}=g^{P(i)}$