又來講安全歸約了，這個(gè)topic是因?yàn)槲疫@幾天審稿發(fā)現(xiàn)的論文存在的一個(gè)錯(cuò)誤知識(shí)點(diǎn)。有感而發(fā)貼出來。這個(gè)帖子的內(nèi)容是屬于小白入門的知識(shí)點(diǎn)。

背景知識(shí)：

安全模型：有敵人和挑戰(zhàn)者。這里的挑戰(zhàn)者我一直覺得取名得很奇葩，它不是為了挑戰(zhàn)方案的安全性或者困難問題的困難性，而是一位敢和敵人PK，對(duì)敵人挑戰(zhàn)的挑戰(zhàn)者。

困難問題： 我們?cè)诙x困難問題時(shí)，是這么說的： 不存在PPT敵人可以通過可忽略的優(yōu)勢(shì)（概率）解決問題并輸出正確的答案。

安全證明：有模擬者和敵人，模擬者模擬出一個(gè)方案，求著敵人懟它。為毛大家都喜歡喊成模擬器和敵手啊。

問題來了：安全證明里，模擬者把自己扮演成挑戰(zhàn)者和敵人PK。 模擬者用一個(gè)困難問題的instance模擬出方案。 那么：

• 這個(gè)困難問題的instance是哪來的？

• 誰(shuí)來尋找這個(gè)問題困難的解？

這里很亂：

• 安全證明里，敵人是攻破方案?？墒?，敵人不應(yīng)該是解決困難問題的嗎？困難問題就是定義敵人解決問題的呀？

• 既然安全證明里有敵人，且模擬者和敵人交互，那這個(gè)困難問題的instance應(yīng)該是模擬者產(chǎn)生發(fā)給敵人的了。

  
  

實(shí)際上：

• 安全證明里，模擬者才是真正要解決困難問題的“敵人”

• 安全證明里，困難問題instance可以看成“問題instance生成器產(chǎn)生的”。模擬者運(yùn)行這個(gè)生成器得到的instance。很重要的一句話是， 模擬者不知道該instance對(duì)應(yīng)的secret。 比如說, instance是【g, g^x】，那么模擬者是不知道x的。

混亂的根源： 困難問題定義里的敵人與 安全模型，安全證明里的敵人是沒有血緣關(guān)系的！ 所以，為了搞清楚關(guān)系，在理解困難問題時(shí)，不要想象成一個(gè)敵人準(zhǔn)備解決該問題，而是想象成是否存在一個(gè)算法可以解決該問題。安全證明就是為了構(gòu)造一個(gè)模擬者，作為一個(gè)算法解決該問題。所以，模擬者就是解決困難問題的敵人。