Shamir 秘密共享方案

1979年，Shamir提出的一个基于拉格朗日插值的(k,n)门限方案

• 目的：可以将秘密s分给n个成员，规定至少有k（k <= n）个成员的信息，就可以恢复出秘密s。k叫做恢复秘密的门限

• 实现方法：

• 初始化阶段：在有限域Z_q（q为大素数）上，D选择一个（k-1）次多项式f(x) ，s作为秘密存储在第一个系数a₀ 中
  （我们知道要解出f(x)我们需要k个式子，得到k个k元一次方程，才能解出所有系数a）
  

• 秘密分发阶段：
  秘密拥有者根据组成员的公开身份信息P_i，计算s_i=f(P_i) (mod q)作为组成员的秘密份额，并把si通过秘密信道分发给组成员U_i，1=< i <= n.
  (得到一个k元一次方程)

• 秘密重构阶段：
  当组成员想要恢复秘密s，他们只需要k个组成员的秘密份额，便可以重构出多项式f(x) =
  

• 注意：素数q需要大于秘密s和组成员总数n，并且公开，随机多项式的系数a_i,1<=i<=n是秘密信息，在生成n个秘密份额后销毁。

零知识证明

Schnorr 零知识证明（Zero Knowledge proof）是德国数学家与密码学家 Schnorr在1991 年提出的基于离散对数难题的一种证明体制。
“零知识”表现在当证明者 Prover想要向验证者 Verifier 证明自己知道某个秘密 x 的值时，通过 Schnorr 零知识证明，能在不泄露 x 的任何信息的情况下完成，即整个过程 Verifier 对 x 获得的知识为零。

EIGamal密码体制

EIGamal密码体制的安全性依赖于有限域离散对数困难问题。1985年EIGamal¹提出一个有限域(Z_q^*)上的离散对数问题的公钥密码体制。具体表述如下：

• Alice 选择循环群G,阶数q,G的生成元g,Alice选择x属于Z_q^*，作为私钥，计算h=g^x,公开{h,G,q,g}，保密x。
• Bob要发送密文m给Alice,使用Alice公钥进行加密:
  选择随机数k属于Z_q^*，计算y1=g^k mod q,y2=m·h^k mod q,发送密文{y1,y2}给Bob
• Alice接受到密文，使用私钥进行解密：
  Bob计算m’ = y2·（y1^a）^-1
• 证明：
• y2·（y1^a）^-1 = m·h^k ·（g^ak）^-1 =m·g^ak·（g^ak）^-1=m

---

1. Gamal T E . A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Transactions on Information Theory, 1985, 31:469-472. ↩︎