十二讲秘密分享与游戏
1
整体 概述
一 请在这里输入您的主要叙述内容
二
请在这里输入您的主要 叙述内容
三 请在这里输入您的主要叙述内容
2
秘密分享方案是与密钥建立相关的多方 协议。秘密分享的原始动机是：为了保 证密码密钥不丢失，希望产生密钥备份， 但是越多的密钥备份，密钥泄露的可能 就越大；越少的密钥备份，密钥丢失的 可能就越大。秘密分享方案就是用来提 高密钥可靠性而不增加泄露风险的方法。
12
秘密分割
使用模加的二重控制
如果一个秘密数字 S，0 S m 1，这里， m是某 个整数，必须输入到设 备(例如，一个种子密钥 )， 但是由于操作的原因， 不希望任何单独个人 (除 可信第三方以外 )知道这个数字，则可以 使用如 下方案。一个可信第三方产生一 个随机数 1 S1 m 1，并将数值 S1和S S1(mod m)分别交给实体 A和 B。A 和B分别将他们的数值输入 设备，它们 之和模 m即可恢复出 S。
3
现代密码学的一个主要成就在于高级安 全协议的发展。这些协议可以让用户在 网上解决现实世界中许多问题，进行各 种游戏，也能执行各种有趣而复杂的分 布任务。电话投币和扑克协议将在这一 讲中做简要介绍。
4
本讲提要
秘密分享的应用 秘密分割 门限方案 电话投币协议 电话扑克协议
5
秘密分享的应用
17
评述. (1) 二重控制方案可以看作 一个 (2，2)门限方案的实例， 而一致同意控制方案是 一个 (t，t)门限方案的实例。 (2) 如果需要一个门限方案 反复使用而不降低安全 性， 就需要一个阻止参与者 推出其他用户分享的控 制机制。 一种方法是阻止组内成 员直接访问他们恢复的 秘密， 而是使用一个可信的设 备来计算秘密。这非常 适合于 系统目标是分享控制， 对于每个参与者而言只 需要 看到特定行为被触发， 而不访问秘密的本身。
二重控制方案很容易以加推广，将秘S密分割给t
个用户，只有全部用参户与才能恢复 S。方法如
下：可信第三T方产生t 1个相互独立的随机S数 i， 0 Si m1，1i t 1。S1 到St1分别交给实体P1
到Pt1，每人一个。实P体t得到St S
t1S (modm)。
i1 i
秘密可以通过 S t S (modm)恢复。 i1 i
13
使用模加的二重控制(续)
评述. (1)如果可以相信A 和B不存在串谋，则没有人知 道任何S的信息，这是由于两人拥有的只是在0到 m 1之间的一个随机数。 (2) 这是知识分割方案的例子，其将对秘密S的知 识在两个人之间做分割。任何对秘密S的操作可 以看作二重控制需要两人共同触发。
14
使用模加的一致同意控制
7
但是，这仍然存在问题：如果任意一个 碎片丢失，则消息无法恢复。如果一个 雇员有烹饪方法的一个碎片而他去为竞 争对手工作并将其碎片带走，那么其他 雇员就没有那么幸运了。离职雇员虽然 不能产生烹饪方法，但他可以不在参与 恢复烹饪方法。他的碎片与其它碎片一 样对恢复消息至关重要。
8
关于门限方案 你在为核导弹安装发射程序。你想确信一个 疯子是不能启动发射，也不希望两个疯子就 能启动发射。在你允许发射前，五个军官至 少有三个是疯子。这是一个容易解决的问题。 做一个机械发射控制器，给五个军官每个人 一把钥匙，并且只有在至少三个军官的钥匙 插入适合的槽中才允许他们起爆。
16
门限方案
定义1一个(t，n)门限方案(t n) 是一种方法：一个 可信方从原始的秘密S计算秘密分享Si，1 i n，并将 Si安全的分配给用户Pi，而分享Si满足下面条件：任何 t或更多用户提交他们的分享就可以恢复出S，但任何 仅知道t 1或更少分享的用户组不能恢复出S。一个完 备的门限方案是任何对t 1或更少分享的掌握都不能 提供比任何对分享一无所知的攻击者更多的推导出秘 密S (信息论意义下)的优势。
秘密分割 假定你发明了一种烹饪食物方法。这一方法 比目前已知的方法都好。对方法保密在市场 竞争激烈的环境下十分重要。你可能仅会告 诉最为信任的雇员具体方法，但雇员如果为 竞争对手收买该怎么办？可能人人都可以按 照这一方法烹饪食物。
6
秘密分割(续) 这就需要秘密分割。方法是将一个消息分 割成碎片，每一个碎片没有任何意义，但 是合在一起就可以重现消息。有了秘密分 割技术烹饪方法可以作为消息，而每个雇 员只能拿到一个碎片，仅当他们联合才能 恢复出烹饪方法。如果任何雇员离职，他 带走的仅是自己的一个碎片，这一信息本 身并无用处。
15
使用模加的一致同意控制(续)
评述. (1)本方案和二重控制方的案模m操作都可以由异或操替作 代，其中使用的数S值和Si都是固定log2m比特长度。 (2) 在一个分割控制方案，中个人的秘密应该是全完长度的。 与分割一个r比特秘密为t份每份r/t比特相比，这将提供好更 的安全强度。例如r ，56和t 2，如果两个实体各得秘到密 的28比特，每个实体穷举索搜都只需要做228次测试，然而， 如果每个实体得到一5个6比特的数据，则需要2做56次测试。
18
的门限方案
机制1Shamir的(t，n)门限方案
9
我们甚至可以把问题变得更为复杂。也许将 军和两个上校被授权发射一个发射控制器，该发射控制器需 要把钥匙。给将军把，给每位上校把。将军 和任意两名上校，或者五名上校一起都可以 发射导弹，然而，将军和一名上校，或四名 上校就不能。
10
一个称为门限方案( )的更复杂的秘密分 享方案，可以在数学上做到这些甚至更 多。起码，可以取任意消息(秘密配方， 发射代码，洗衣价目表)并把它分成部分， 每个部分叫它的影子或分享，它们中的 任何部分能够用来重构消息。
11
我们可以将烹饪方法分给，，，和，这样 把他们中的任意三个影子放在一起就能重 构消息。如果正在渡假，那么，，和可以 考虑做这件事情；如果被汽车撞了，那 么，，和可以考虑做这件事情。然而，如 果被汽车撞了并且正在渡假，和 就不可能 重构消息。