8 密码学基础话题

现代密码学概论7/29/202610:57AM1江苏大学计算机科学与通信工程学院主讲人：潘森杉第8讲密码学话题定义：(t,w)门限方案是一个使得w个参与者共享一个密钥K的方法：任何t个参与者都能计算出K，但任何t-1个参与者都不能计算出K。（其中t,w为正整数，t≤w）K的值由被称为“庄家”(dealer，记为D)的特定参与者选取。参与者集合P，D不在P中。当D想在P中的参与者共享密钥K时，给每个参与者一些秘密分发的部分信息（称为共享，share）引言：Shamir门限方案记参与者集合P=｛Pi：0≤i≤w｝，密钥集合K，共享集合S密码体制

Shamir(t,w)门限方案

初始化阶段1.D在Zp中选w个不同的非零元素xi,1≤i≤w，

D把xi发给Pi。xi公开。

共享分配2.假定D想共享密钥K∈Zp。D秘密选取t-1个元素aj，1≤j≤t-1

3.对每个1≤i≤w，D计算xi=a(xi)，其中4.对每个1≤i≤w，D把yi发送给Pi作为共享。参与者集合P=｛Pi：1≤i≤w｝，参与者得到(xi,yi)密钥集合K=Zp

，共享集合S=Zpp≥w+1

例

p=17，t=3，w=5；公开的xi=i,1≤i≤5，

假定子集B={P1,P3,P5}

，共享分别为8,10,11。记a(x)=a0+a1x+a2x2分别计算a(1),a(3),a(5)得a0+a1+a2=8a0+3a1+9a2=10a0+5a1+8a2=11

求解得唯一解a0=13，a1=10，a2=2

K=a0=13

。记上例中：参与者可以先计算b1=4,b2=3,b3=11,利用他们的共享即可求出K=13.简化的(t,t)门限方案密码体制

简化的(t,t)门限方案

1.D秘密的选择Zm中t-1个元素yi,1≤i≤t-1，2.D计算

3.对于1≤i≤t，D把共享yi发给Pi。

访问结构和一般的秘密共享是由P的一些子集构成的集合，对于中的子集，参与者可以共同计算出密钥K，称为一个访问结构秘密共享方案或访问结构，中的每个子集称为授权的子集秘密共享方案或授权子集定义：在w个参与者集合P中共享密钥K的方法称为实现访问结构的一个完善的秘密共享方案，如果满足：对于一个授权的参与者子集B，如果把他们的共享集中可以确定K对于一个未授权的参与者子集B，收集他们所有的共享，不能确定关于K的任何信息B∈,BCP，易见C可以确定K，说明访问结构应满足单调性：若B∈,BCP，则C∈

(t,w)门限方案实现的访问结构{B:|B|≥t}，称门限访问结构称B是访问结构

的一个最小授权子集，如果对B的任何真子集A都不属于

。的最小授权子集的集合记为

0

，称为

的基。

={CP:BC,B∈

0

}单调电路构造假设有一个布尔电路C，有w个布尔输入x1,…,xw(对应w个参与者)，一个布尔输出y。电路由“或”门和“与”门组成，不允许“非”门出现。这样的电路称为单调布尔电路。对于一个单调电路C，指定其w个输入的布尔值，定义

B(x1,…,xw)=(Pi:xi=1)即的那些对应于输出为真的输入子集。定义

(C)={B(x1,…,xw):C(x1,…,xw)=1}

其中C(x1,…,xw)是C在输入x1,…,xw时的输出。由于C是单调的，

(C)是P的子集的一个单调集合另一方面，是P的子集组成的一个单调集合，可以建立一个单调电路C使得

(C)=：令0

是

的基，建立析取范式的布尔公式：例如前例中，0={{P1,P2,P3},{P1,P3,P4},{P2,P3}}

布尔公式(P1∧P2∧P3)∨(P1∧P3∧P4)∨(P2∧P3)单调电路构造算法

单调电路构造(C)

f(Wout)←K当存在线W使得f(W)未定义时，循环以下操作：找到C的一个门G使得f(WG)已经定义，其中WG是G的输出线，但是对于G的任何输入线来说，f(W)都没有定义过。(a)如果G是一个“或”门，那么对于G的每个输入线W，f(W)←f(WG)

(b)否则，令G的输入线是W1,…,Wt，独立随机选择Zm中的t-1个元素，记为yG,1,…,yG,t-1yG,t←f(WG)

–(yG,1,+…+yG,t-1)modmfori←1totdof(Wi)

←

yG,i例1：抛硬币的游戏游戏1：Alice和Bob聚在一起，为决定去看电影还是看足球而选择一个公平游戏。游戏2：Alice和Bob为决定去看电影还是看足球而选择一个公平游戏，可惜的是两个人都不在一起，要通过电话进行游戏。协议：一个适当定义的、在多个实体之间执行的规程。注意：如果一个规程仅有一个实体执行，那么不是协议，而是算法127/29/202610:57AM定义

单向函数f137/29/202610:57AM单向函数是否存在？仿生学的角度看，覆水难收、打破瓶子等协议1电话置币假定：Alice和Bob已经同意：某函数f是单向函数f(x)中偶数x表示正面，奇数x表示背面协议：Alice选择一个大的随机数x，并计算f(x);然后通过电话告诉Bobf(x)的值Bob告诉Alice自己对x奇偶性的猜测Alice告诉Bobx的值Bob验证f(x)，并观察他所做的猜测是否正确147/29/202610:57AM协议1的安全性分析157/29/202610:57AMBob知道了f(x)的值，是否更有利？Alice知道了Bob的猜测值，能否作弊？Bob能否相信最后输赢的公平性？协议1的问题与思考协议1与真实世界里的抛硬币完全一样吗？

在Bob猜测之前，Alice已经知道是正面还是背面，若她可以选择硬币的正反面，是否会不公平？Alice选择的随机数是否足够好?

Bob有没有可能有关于x的经验值来推断？通信信道是否能保证Alice和Bob“被迫”不改变他们对x的值以及对奇偶性的选择。(抵赖？录音？基于声音的身份识别？如何修改这个协议)167/29/202610:57AM零知识证明零知识证明由Goldwasser等人于20世纪80年代初提出，起源于最小泄露证明。在交互证明系统中，设Alice知道某一秘密，并向Bob证明自己掌握这一秘密，但又不向Bob泄露这一秘密，这就是最小泄露证明。进一步，如果Bob除了知道Alice能证明某一事实外，不能得到其他任何信息，则称Alice实现了零知识证明，相应的协议称为零知识证明协议。计算机科学系17Goldwasser零知识证明计算机科学系18零知识洞穴洞穴里有一个秘门，知道咒语的人能打开C和D之间的秘门。而对于其他不知道咒语的人来说，两条通道都是死胡同。Peggy知道这个洞穴的咒语。她想向Victor证明这一点，

但她不想泄露咒语让Victor知道。如何做到？零知识证明计算机科学系19零知识洞穴洞穴里有一个秘门，知道咒语的人能打开C和D之间的秘门。而对于其他不知道咒语的人来说，两条通道都是死胡同。Peggy和Victor进行如下协议：(1) Victor站在A点；Peggy站在B点。(2) Peggy一直走进洞穴，到达C点或D点。(3) 当Peggy进洞之后，Victor走到B点。(4) Victor向Peggy喊叫：让Peggy(a)从左边出来，或者(b)从右边出来。(5) Peggy按照要求实现(如果有必要她就用咒语打开密门)。(6) Peggy和Victor重复执行(1)~(5)步n次。姚氏百万富翁问题两个百万富翁Alice和Bob想知道他们两个谁更富有，但他们都不想让对方知道自己财富的任何信息。计算机科学系20姚期智(AndrewChi-ChihYao)，世界著名计算机学家，2000年图灵奖得主，美国科学院院士，美国科学与艺术学院院士，中国科学院外籍院士，清华大学高等研究中心教授，香港中文大学博文讲座教授。现任清华大学交叉信息研究院院长、教授。在以下三大方面具有突出贡献：（1）创建理论计算机科学的重要次领域：通讯复杂性和伪随机数生成计算理论；（2）奠定现代密码学基础，在基于复杂性的密码学和安全形式化方法方面有根本性贡献；（3）解决线路复杂性、计算几何、数据结构及量子计算等领域的开放性问题并建立全新典范。姚期智2026/7/291、假设Alice希望向Bob购买一些商品，但她愿意支付的最高金额为x元；Bob希望的最低卖出价为y元。Alice和Bob都非常希望知道x与y哪个大。如果x>y，他们都可以开始讨价还价；如果x<y，他们就不用浪费口舌。但他们都不想告诉对方自己的出价，以免自己在讨价还价中处于不利地位。A2、两个金融组织计划为了共同的利益决定互相合作一个项目，每个组织都想自己的需求获得满足。他们的需求都是他们自己专有的数据，没人愿意透露给其它方，甚至是“信任”的第三方。那么他们如何在保护数据私密性的前提下合作项目呢？B百万富翁问题的实际应用2026/7/293、经过一次花费昂贵的市场调查后，A公司决定扩展在某些地区的市场份额来获取丰厚的回报。同时，A公司也注意到B公司也在扩展一些地区的市场份额。在策略上，两个公司都不想在相同地区互相竞争，所以他们都想在不泄露市场地区位置信息的情况下知道他们的市场地区是否有重叠。(信息的泄露可能会导致公司很大的损失。比如另一家对手公司知道A和B公司的扩展地区，提前行动占领市场；又比如房地产公司知道A和B公司的扩展计划，提前提高当地的房租等等)所以他们需要一种方法在保证私密的前提下解决这个问题。C4、Alice认为她的了某种遗传疾病，想验证自己的想法。正好她知道Bob有一个关于疾病的DNA模型的数据库。如果她把自己的DNA样品寄给Bob，那么Bob可以给出她的DNA的诊断结果。但是Alice又不想别人知道，这是她的隐私。所以，她请求Bob帮忙诊断自己DNA的方式是不可行的。因为这样Bob就知道了她的DNA及相关私人信息。D百万富翁问题的实际应用2026/7/29以上四个例子的共有特点是：<1>.两或更多方参与基于他们各自私密输入的计算。<2>.而且他们都不想其他方知道自己的输入信息。

问题变成了在保护输入数据私密性的前提下如何实现这种计算?我们称之为“安全多方计算(SecureMulti-partyComputation)”问题。计算机科学系24安全多方计