1、 令 G为某个乘法群， a, b, 和 cG，并有正整数 x, y, 和 z。在各参数为指数规模时，请设计一个有效的算法计算 axbycz并分析其计算效率。 第十五讲 秘密分享与游戏秘密分享方案是与密钥建立相关的多方协议。秘密分享的原始动机是：为了保证密码密钥不丢失，希望产生密钥备份，但是越多的密钥备份，密钥泄露的可能就越大；越少的密钥备份，密钥丢失的可能就越大。秘密分享方案就是用来提高密钥可靠性而不增加泄露风险的方法。现代密码学的一个主要成就在于高级安全协议的发展。这些协议可以让用户在网上解决现实世界中许多问题，进行各种游戏，也能执行各种有趣而复杂的分布任务。电话投币和扑克协议将在这一讲中做
2、简要介绍。本讲提要q 秘密分享的应用 q 秘密分割q 门限方案q 电话投币协议q 电话扑克协议1 秘密分享的应用1.1 秘密分割假定你发明了一种烹饪食物方法。这一方法比目前已知的方法都好。对方法保密在市场竞争激烈的环境下十分重要。你可能仅会告诉最为信任的雇员具体方法，但雇员如果为竞争对手收买该怎么办？可能人人都可以按照这一方法烹饪食物。1.1 秘密分割 (续 )这就需要秘密分割。方法是将一个消息分割成碎片，每一个碎片没有任何意义，但是合在一起就可以重现消息。有了秘密分割技术烹饪方法可以作为消息，而每个雇员只能拿到一个碎片，仅当他们联合才能恢复出烹饪方法。如果任何雇员离职，他带走的仅是自己的一个
3、碎片，这一信息本身并无用处。但是，这仍然存在问题：如果任意一个碎片丢失，则消息无法恢复。如果一个雇员有烹饪方法的一个碎片而他去为竞争对手工作并将其碎片带走，那么其他雇员就没有那么幸运了。离职雇员虽然不能产生烹饪方法，但他可以不在参与恢复烹饪方法。他的碎片与其它碎片一样对恢复消息至关重要。1.2 关于门限方案你在为核导弹安装发射程序。你想确信一个疯子是不能启动发射，也不希望两个疯子就能启动发射。在你允许发射前，五个军官至少有三个是疯子。这是一个容易解决的问题。做一个机械发射控制器，给五个军官每个人一把钥匙，并且只有在至少三个军官的钥匙插入适合的槽中才允许他们起爆。我们甚至可以把问题变得更为复杂。也许将军和两个上校被授权发射导弹，但如果将军正在打高尔夫球，那么启动发射需要五名上校。制造一个发射控制器，该发射控制器需要 5把钥匙。给将军 3把，给每位上校 1把。将军和任意两名上校，或者五名上校一起都可以发射导弹，然而，将军和一名上校，或四名上校就不能。
