安全归约困惑之敌人的无限计算能力
感谢way-key的困惑，得以有此篇文章的出现。我最近又要开始闲得蛋疼了，挺好的，终于可以下山左瞧瞧右看看，然后再决定回山上闭关修炼什么技能。最近学习安全归约的道友们又增加了好多，真是莫名其妙。整个人界到处可见一些魔气，戾气。
安全归约是密码学可证明安全的一种技术。 安全归约就是把敌人对方案的攻击，转换为对困难问题的解，从而说明敌人的攻击不存在。说起来很简单，细节实在是太多了。
安全证明过程中，我们不用真实方案和敌人交互，而是模拟方案，否则拿不到有效的东西解决困难问题，因为真实方案所有的秘密我们都知道（key是我们选的），而模拟方案里的部分秘密我们是不知道的（比如key）
安全归约分三大块， simulation, solution, 和analysis. 最后一部分的分析最难。因为我们要证明敌人的攻击是可以通过不可忽略的概率（不要跟我杠是advantage）转换为困难问题的解的。
在安全归约导论那本书里，我们作者说明了直接分析行不通，要通过放缩法。首先把敌人放大到恶意敌人。然后，又为了简单分析，把恶意敌人放大到计算能力无限的敌人。
问题来了：
如果没有在这个坑里摸爬滚打过，这个坑真的不好跳出来。
如果敌人可以攻破方案使得问题可以解，而问题是困难的，从而说明敌人不存在。 这句话还真没错，但要说仔细些： 如果现实世界的敌人可以这样干，那会和现实世界的困难问题矛盾，从而说明现实世界的敌人不存在。 这里加“现实世界”主要是为了和“无限计算能力敌人”区分，因为它不属于现实世界。
当我们把敌人放到包括计算能力无限敌人时，即使可以攻破方案，即使我们可以解决困难问题，这也不能说明矛盾，从而说明 敌人不存在。 计算能力无限的敌人是一定可以攻破方案的。我们用不存在的敌人去解决困难问题，当然可以有解。
安全归约中，我们不关心敌人能不能攻破方案（因为我们都假设敌人能攻破方案了），我们关心： 敌人攻破方案那一日，我们是否也能拿到问题的解？
再强调一遍，安全归约中，敌人是一定存在的。我们只关心问题的解能不能拿到。
现在，我们考虑恶意敌人，想方设法输出一个 让我们得不到解的攻击。
再进一步放缩，让这个敌人的计算能力达到无限。
如果这样的敌人都不能搞死我们，让我们的reduction 失败，我们就一定能得到困难问题的解。（我们=证明者）
最后，我是通过以下通俗例子和key老师完成交互的。
假设对方案的攻击，来自能力有限的敌人，攻击方式只能来自越国（凡人修仙传）
我们现在把敌人的能力放大无限，出招更多，那么攻击方式可以cover 整个地球
现在，我们从地球上选出最有威胁的攻击，证明即使是这个攻击，归约仍然成功
那么来自越国的攻击也是可以进行归约，解决困难问题的。
而困难问题是困难的，所以，来自越国的攻击不存在
那来自其它国家的攻击可能存在吗？
可能！
但我们不管，因为计算能力有限的敌人一定来自越国！
而我们只关心计算能力有限的敌人。
