陷门置换构造加密方案

通过提取基于RSA困难问题假设的加密方案中使用的RSA属性，并定义封装这些属性的抽象概念，可以获得了一个通用模板，用于基于任何满足相同属性集的原语构建安全加密方案。
而陷门置换就是一种抽象概念
在一些结构中，参数生成算法Gen输出一些附加信息和I，从而实现(f_I)的有效反演。称这些附加信息为陷门，并将单向置换的族称为陷门置换的附加属性族。
陷门的形式化定义为：
一组多项式时间算法(Gen,Samp,f,Inv)如果满足以下条件则称其为陷门：

概率性的参数生成算法Gen：输入(1^n)，输出(I,td)其中|I| (le) n，I的每一个值定义了一个置换的定义域和值域(D_I)，(f_I:D_I o D_I)
用(Gen_1)表示由Gen算法生成的结果，并且只输出I。则((Gen_1),Samp,f)是一族单向置换
用(I,td)表示Gen((1^n))的输出，则确定性的反向算法Inv，将td以及y (in D_I)作为输入，然后输出x (in D_I)，表示成x := (Inv_{td}(y))。则需要保证所有由Gen((1^n))生成的(I,td)，有一个概率均匀的选择x (in D_I)，有(Inv_{td}(f_I(x))=x)

如果没有td，则很难求(f_I)的逆；如果有了td，则能够高效率的求(f_I)的逆

陷门置换构造的公钥加密方案：设(Pi)=(Gen,f,Inv)是一族陷门置换，令hc为一个确定性的多项式时间算法，这个算法接收I以及x(in D_I)作为输入，然后输出一个比特(hc_I(x))，称hc为(Pi)的硬核谓词，如果对于所有PPT上的算法A，存在一个可忽略函数negl满足(Pr[A(I,f_I(x))=hc_I(x)] le frac{1}{2}+negl(n))

陷门置换的不对称性意味着任何一个知道与I相关的陷门td的人而可以从(f_I(x))中恢复出x，并由此从(f_I(x))计算出(hc_I(x))
但是如果只给了一个I，对于一个概率均匀选择的x，很难从(f_I(x))计算出(hc_I(x))

从任何一组陷门置换构造公钥加密方案：设(Pi’)=(Gen’,f,Inv)是一族陷门置换，其硬核谓词为hc，则可以构造一个公钥加密方案如下：

Gen：输入安全参数(1^n)，运行Gen'((1^n))获得(I,td)，输出公钥I，私钥td
Enc：输入一个公钥I以及一条明文m (in) {0,1}，概率均匀的选择一个r (in D_I)，r满足(hc_I(r)=m)，输出密文c := (f_I(r))
Dec：输入一个私钥td以及一条密文c，计算r:=(Inv_I(c))，然后输出明文m := (hc_I(r))

定理：如果(Pi’)是一族硬核谓词为hc的陷门置换，那么上面所构造的加密方案是CPA安全的
加密更长的明文：在前面的RSA-lsb中已经介绍过如何利用加密单比特明文的加密方案加密更长的明文

秘密共享以及门限加密

安全(交互)协议可能比基本的密码原语(例如，加密和签名方案)复杂得多。一方面是因为它们可能涉及多方交换几轮消息，另一方面是因为它们旨在实现更复杂的安全需求。

秘密共享

应用情景：一个发牌员持有一个秘密(比如核弹的发射密码)，希望通过给与每个用于一点份额在用户集合(P_1,…,P_N)之间共享这个秘密
任意t个用户都能通过将他们的份额组装起来从而恢复这个秘密，但是用户数量小于t则无法知道任何关于这个秘密的信息
上述的应用情景称为(t,N)门限秘密共享，而(t,N)门限秘密共享有有两种情况：t=N，以及t<N

t=N
假设s (inlbrace 0,1 brace^l)

发牌员概率均匀的选择(s_1,…,s_{N-1}inlbrace 0,1 brace^l)，然后计算(s_N:=sigoplus(igoplus^{N-1}_{i=1}s_i))，则每个用户的份额就是(s_i)
因为((igoplus^N_{i=1}s_i)=s)，所以只有每个用户都交出自己的份额才能够恢复出这个秘密
并且，当用户数量少于N的时候，无法获得任何关于秘密s的信息

t<N，与上面那种情况不同的是，在选择(s_1,…,s_N)的时候需要满足一定的约束，并且显然效率是很低的

Shamir秘密共享方案：这个方案是基于一个有限多项式域F设计的，其中F满足s (in) F并且|F| > N，其原理主要是一个t阶的多项式p(x)，而p(x)=0最多有t个根
此外还有一个重要的引理：F中任意t对((x_1,y_1),…,(x_t,y_t))，都有一个唯一的t-1阶多项式p满足(p(x_i)=y_i)
该方案的工作原理如下，设(x_1,…,x_N in F)，没有重复并且不含零元素，这组元素是公开可知的：

共享：给定一个秘密s (in) F，发牌员概率均匀的选择(a_1,…,a_{t-1} in F)，然后定义一个多项式p(X)=s+(Sigma^{t-1}_{i=1}a_iX^i)，每个用户的份额为(s_i=p(x_i) in F)
恢复：t个用户(P_1,…,P_t)交出他们的份额(s_1,…,s_t)然后利用(p(x_i)=s_i)计算出多项式多项式p，则秘密为s=p(0)。而且显然，对于任何用户数量小于t的用户都无法计算出p，也就无法获取任何关于秘密s的信息

可验证秘密共享

在秘密共享方案中存在着两种恶意行为，而可验证秘密共享(Verifiable Secret Sharing,VSS)用于抵抗这两种恶意行为

腐败的发牌员：给用户发放不一致的份额，这样会导致不同的用户组会恢复出不同的秘密
在恢复阶段中一个恶意的用户可能会提交一个假的份额，从而影响恢复过程

更加形式化的定义是，可验证秘密共享方案需要满足以下两个条件：如果用户集合中有t-1个腐败的用户，并且相互串通，甚至其中可能包括发牌员，则：

在共享阶段结束的时候，需要保证任何t个份额都能够会付出秘密s
如果发牌员是诚实的，那么秘密就是发牌员的密钥

当然上面的第一个条件是假设用户集合中的大多数((le) t个)用户是不腐败的，那么N应该满足N (le) t+t-1 > 2(t-1)

可验证秘密共享方案：设H是一个由随机预言机构造的函数，假设由G((1^n))生成的可信任参数(G,q,g)是提前发表了的，其中q是一个素数，所以(Z_q)是一个域，并且所有用户都可以访问广播频道

共享阶段：

设将要分享的秘密为s，则发牌员概率均匀的选择一个(a_0 in Z_q)，然后利用Shamir秘密共享方案共享(a_0)，将(s_i=p(i)=Sigma^{t-1}_{j=0}a_ii^j)发送给用户(P_i)，此外，发牌员利用广播频道广播(A_0=g^{a_0},…,A_{t-1}=g^{a_{t-1}})，以及“被掩盖的秘密”c := H((a_0)) (igoplus) s
每个用户(P_i)在收到了自己的份额后需要验证(g^{s_i}=?prod^{t-1}_{j=0}(A_j)^{i^j})，如果不满足，则在广播频道上报错
(prod^{t-1}_{j=0}(A_j)^{i^j}=prod^{t-1}_{j=0}(g^{a_i})^{i^j}=g^{Sigma^{t-1}_{j=0}a_j·i^j}=g^{p(i)}=g^{s_i})
如果有超过t-1个用户报错，则发牌员不合格，协议终止；否则，发牌员广播(s_i)作为回应；如果广播出去的份额仍然无法通过验证，则这个发牌员是不合格的，协议终止；否则，用户(P_i)将广播的(s_i)作为自己的份额

恢复阶段：在恢复之前需要先进行验证，如果用户组中的用户(P_i)不能通过验证，那么这个用户将被丢弃，而在这剩下的t个通过验证的用户中，可以恢复出(a_0)，然后计算s:=c(igoplus)H((a_0))

门限与电子选举

El-Gamal加密方案的一种变体的同态加密方案：给定公钥pk=(G,q,g,h)，如果要加密明文m(in Z_q)，则计算M=(g^m)，概率均匀的选择一个y(in Z_q)，然后发送密文c=((g^y,h^y·M))；如果要解密，想用标准的El-Gamal加密方案计算出M，然后计算m=(log_gM)

缺点：如果明文空间比较大，那么效率将会非常低；如果明文空间比较小，那么接收方可以使用穷举搜索高效的解密
优点：对于(Z_q)中的加法同态：((g^{y_1},h^{y_1}·g^{m_1})·(g^{y_2},h^{y_2}·g^{m_2})=(g^{y_1+y_2},h^{y_1+y_2}·g^{m_1+m_2}))

使用同态加密进行电子选举的基本方法是让每个投票者对其投票(v_i)∈{0,1}进行加密，从而获得一个密文(c_i)。一旦所有人都已经投了票，则将所有的密文相乘，从而获得投票的总和的密文，称为最终密文，然后将私钥委托权威机构进行解密，从而获取投票的总和

然而存在着一个缺陷：该机构是可信的，既可以(正确地)解密最终的密文，也可以不解密任何个别选民的密文。

解决的方法是同时委托多个机构，然后利用秘密共享将私钥分享给这些机构
不过仍然存在着一个缺陷：如果权威机构为了解密某个密文而恢复这个私钥，那么所有的机构都会知道这个私钥，那么他们可以按照自己选择解密任何密文