|
|
2.1 秘密共享定义
秘密共享的核心思想是将一个秘密 S 拆分成 n 份 S_{1},S_{2},...,S_{t},...,S_{n} 并分发给不同的参与方 P_{1},P_{2},...,P_{t},...,P_{n}管理。只要多于 t 个参与方合作才能恢复秘密。一方面，单个参与方无法自己恢复秘密；另一方面，不需要所有参与方就能恢复秘密。在给出秘密共享的定义之前，我们先介绍接入结构的定义：
定义 \left\{ {p_{1},...,p_{n}} \right\} 为参与方集合， A\subseteq 2^{\left\{ {p_{1},...,p_{n}} \right\}} 为参与方集合的一个集族。如果集合 B\in A 且 B\subseteq C 可推出 C\in A ，那么集族 A 就是单调的。接入结构定义为 \left\{ {p_{1},...,p_{n}} \right\} 的非空子集的一个单调集族 A 。接入结构 A 内的集合被称为”授权集合“，接入 结构 A外的集合被称为”未授权集合”。[不太理解]
秘密域 K 内的分配方案 \Sigma = <\Pi,\mu> 由 \Pi 和 \mu 决定。 \mu 是某个被称为随机字符串集合的有限集合 R 上的概率分布， \Pi 是从 K\times R 到 n 元组 K_{1} \times K_{2} \times ...\times K_{n} 的集合的映射，其中， K_{j} 被称为秘密份额 p_{j} 的域。秘密分发者根据 \Pi 将秘密 k\in K 分享给各个参与方。首先，秘密分发者根据 \mu 采样一个随机字符串 r\in R ；接着，秘密分发者计算秘密份额向量 \Pi(k,r) = (s_{1},...,s_{n}) ;最后，秘密分发者安全地将每个秘密份额 s_{j} 发送给对应参与方 p_{j} 。下面给出秘密共享的定义：
定义 K 为秘密的有限集合， \left| K \right| \leq 2 。如果以下两个要求成立，那么秘密域 K 内的分配方案 <\Pi,\mu> 就是 实现接入结构 A 的一个秘密共享方案。
正确性：秘密 K 能被任何授权的参与方集合恢复。即，对于任何集合 B=\left\{ p_{i1} ,..., p_{i\left| B \right|}\right\} \in A ，存在一个恢复函数 RECON_{B}：K_{i1} \times ...\times K_{i\left| B \right|} \rightarrow K ，对于每个 k\in K： Pr \left[ RECON(\Pi (k,r)_{B})=k \right] =1
隐私保护：未授权的参与方集合不能从它们的秘密共享份额中恢复有关秘密的任何信息。对于任意集合 T\notin A ，任意两个秘密 a,b\in K 和任意可能的秘密份额向量 <s_{j}>_{pj\in T}: Pr \left[ \Pi(a,r)_{T}=<s_{j}>_{pj\in T} \right] = Pr \left[ \Pi(b,r)_{T}=<s_{j}>_{pj\in T} \right]
上述两个要求可以放宽：要求以正确性以较高的概率成立，或者 \Pi(a,r)_{T} 和 \Pi(b,r)_{T} 的统计距离很小。这样宽泛的要求就满足统计秘密共享方案。
2.2 经典秘密共享方案
Shamir秘密共享方案也被称作(t,n)门限秘密共享方案，简称门限方案。Shamir的方案基于拉格朗日插值的方式实现。给定二维空间内的 t 个点 (x_{1},y_{1}),...,(x_{t},y_{t}) ，其中 x_{i} 各不相同。对于每一个 x_{i} ，有且只有一个 t-1 度多项式 q(x)=a_{0}+a_{1}x+...+a_{t-1}x^{t-1} ，使得 q(x_{i})=y_{i} 。
1.秘密拆分阶段
首先确定 t 和 n 。赋值 a_{0}=S ， S 为想要分享的秘密，随机产生 a_{1},...,a_{t-1}，计算： S_{1}=q(1),...,S_{i}=q(i),...,S_{n}=q(n)
2.秘密分发阶段
将 (S_{1},1),...,(S_{n},n) 分发给秘密持有者。
3.秘密恢复阶段
获得任意 t 个 S_{i} 的值，就可以通过差值法计算得出多项式 q(x) 的系数 a_{0},...,a_{t-1} ，其中 a_{0} 为恢复得到的秘密 S 。但是少于 t 个 S_{i} 的值不能解出多项式，无法恢复出原本的秘密。
需要说明的是，为了保证计算的准确性，Shamir方案用模运算代替实数运算。首先确定一个大质数 p ，保证 p 同时大于 S 和 n ，多项式 q(x) 的系数 a_{0},...,a_{t-1} 从一个范围为 [0,p) 的均匀分布中随机取出，且 S_{1},...,S_{n} 也通过对 p 取模得到。
1.秘密拆分阶段
设秘密为 S ，确定 n 和 t 。生成 n 个互质的随机数 d_{1},...,d_{n} ，要求其中 t 个最小的随机数相乘的结果大于秘密 S ，其中 t-1 个最大的随机数相乘的结果小于 S 。分别计算 S_{i}=S mod d_{i} 。
2.秘密分发阶段
将 (S_{1},d_{1}),...,(S_{n},d_{n}) 分发给秘密持有者
3.秘密恢复阶段
根据 (S_{1},d_{1}),...,(S_{t},d_{t}) 列出方程式 Smodd_{i}=S_{i} 。根据中国剩余定理求解出 S 即可得出秘密。
Brickell秘密共享方案是Shamir秘密方案的推广，由一维方程转向思考多维向量。
设秘密为 S ，确定 n 和向量维度 d ，选择模数 p 。然后确定解密规则 \left\{ \left\{ v_{1},v_{2},v_{3} \right\} , \left\{ v_{1},v_{4}\right\} \right\} ，其中 v_{i} 表示第 i 个 d 维向量，该解密规则表示第一、二、三个人和第一、四个人分别可以合作恢复出秘密。确定所有人共享的 n 个向量 \left\{ v_{1},...,v_{n} \right\} ，要求解密规则里的任何一组向量都可以线性构成 (1,0,0) ，而不再解密规则里的组合无法构成。
生成 d-1 个小于 p 的随机数 a_{2},...,a_{d} ，同时将 S 的值赋值给 a_{1} 。分别计算 S_{i}=\alpha\cdot v_{i} ，其中 \alpha =(a_{1},...,a_{n}) 。
2. 秘密分发环节
将 (S_{i},i) 作为钥匙分发给秘密持有者。
3.秘密恢复环节
利用满足解密规则的秘密持有者的向量构造(1,0,0).例如：通过 c_{1}v_{1}+c_{2}v_{2}+c_{3}v_{3}=(1,0,0) 解出 c_{1},c_{2},c_{3} ，然后将参数带入 (c_{1}S_{1}+c_{2}S_{2}+c_{3}S_{3})modp=S ,得出秘密S的值。
Blakley秘密共享方案基于高斯消元法。
首先确定 n 、t 。假设 S=(x,y,z,...)共 t 维， S 是 t 维空间中的一点。然后，构造出经过 S 点的 n 个平面。
2. 秘密分发环节
将第 i 个平面分发给第 i 个人。
3.秘密恢复环节
集齐任何满足解密规则的钥匙，列出方程组，即包含 t 个变量的 t 个方程组，得出原来的秘密 S 。
2.3 秘密共享方案的同态特性
秘密共享的同态性表达的是：秘密份额的组合等价于组合的秘密共享份额。下面给出秘密共享同态性的定义：
假设\oplus和\otimes分别对应于秘密空间S和份额空间T中的二元函数。(t,n)门限秘密共享具有(\oplus,\otimes)同态性，如果对于任意子集I:s=F_{I}(s_{i1},...,s_{it})，s^{&#39;}=F_{I}(s_{i1}^{&#39;},...,s_{it}^{&#39;})，那么s\oplus s^{&#39;}=F_{I}(s_{i1}\otimes s_{i1}^{&#39;},..., s_{it}\otimes s_{it}^{&#39;})
水平有限，欢迎批评指正！ |
|
发 帖
发表于 2022-9-23 19:27:25