安全归约困惑之困难问题哪里来
又来讲安全归约了，这个topic是因为我这几天审稿发现的论文存在的一个错误知识点。有感而发贴出来。这个帖子的内容是属于小白入门的知识点。
背景知识：
安全模型：有敌人和挑战者。这里的挑战者我一直觉得取名得很奇葩，它不是为了挑战方案的安全性或者困难问题的困难性，而是一位敢和敌人PK，对敌人挑战的挑战者。
困难问题： 我们在定义困难问题时，是这么说的： 不存在PPT敌人可以通过可忽略的优势（概率）解决问题并输出正确的答案。
安全证明：有模拟者和敌人，模拟者模拟出一个方案，求着敌人怼它。为毛大家都喜欢喊成模拟器和敌手啊。
问题来了：安全证明里，模拟者把自己扮演成挑战者和敌人PK。 模拟者用一个困难问题的instance模拟出方案。 那么：
这个困难问题的instance是哪来的？
谁来寻找这个问题困难的解？
这里很乱：
安全证明里，敌人是攻破方案。可是，敌人不应该是解决困难问题的吗？困难问题就是定义敌人解决问题的呀？
既然安全证明里有敌人，且模拟者和敌人交互，那这个困难问题的instance应该是模拟者产生发给敌人的了。
实际上：
安全证明里，模拟者才是真正要解决困难问题的“敌人”
安全证明里，困难问题instance可以看成“问题instance生成器产生的”。模拟者运行这个生成器得到的instance。很重要的一句话是， 模拟者不知道该instance对应的secret。 比如说, instance是【g, g^x】，那么模拟者是不知道x的。
混乱的根源： 困难问题定义里的敌人与 安全模型，安全证明里的敌人是没有血缘关系的！ 所以，为了搞清楚关系，在理解困难问题时，不要想象成一个敌人准备解决该问题，而是想象成是否存在一个算法可以解决该问题。安全证明就是为了构造一个模拟者，作为一个算法解决该问题。所以，模拟者就是解决困难问题的敌人。
