安全歸約困惑之?dāng)橙说臒o限計(jì)算能力
感謝way-key的困惑，得以有此篇文章的出現(xiàn)。我最近又要開始閑得蛋疼了，挺好的，終于可以下山左瞧瞧右看看，然后再?zèng)Q定回山上閉關(guān)修煉什么技能。最近學(xué)習(xí)安全歸約的道友們又增加了好多，真是莫名其妙。整個(gè)人界到處可見一些魔氣，戾氣。
安全歸約是密碼學(xué)可證明安全的一種技術(shù)。 安全歸約就是把敵人對方案的攻擊，轉(zhuǎn)換為對困難問題的解，從而說明敵人的攻擊不存在。說起來很簡單，細(xì)節(jié)實(shí)在是太多了。
安全證明過程中，我們不用真實(shí)方案和敵人交互，而是模擬方案，否則拿不到有效的東西解決困難問題，因?yàn)檎鎸?shí)方案所有的秘密我們都知道（key是我們選的），而模擬方案里的部分秘密我們是不知道的（比如key）
安全歸約分三大塊， simulation, solution, 和analysis. 最后一部分的分析最難。因?yàn)槲覀円C明敵人的攻擊是可以通過不可忽略的概率（不要跟我杠是advantage）轉(zhuǎn)換為困難問題的解的。
在安全歸約導(dǎo)論那本書里，我們作者說明了直接分析行不通，要通過放縮法。首先把敵人放大到惡意敵人。然后，又為了簡單分析，把惡意敵人放大到計(jì)算能力無限的敵人。
問題來了：?
如果沒有在這個(gè)坑里摸爬滾打過，這個(gè)坑真的不好跳出來。
如果敵人可以攻破方案使得問題可以解，而問題是困難的，從而說明敵人不存在。 這句話還真沒錯(cuò)，但要說仔細(xì)些： 如果現(xiàn)實(shí)世界的敵人可以這樣干，那會(huì)和現(xiàn)實(shí)世界的困難問題矛盾，從而說明現(xiàn)實(shí)世界的敵人不存在。 這里加“現(xiàn)實(shí)世界”主要是為了和“無限計(jì)算能力敵人”區(qū)分，因?yàn)樗粚儆诂F(xiàn)實(shí)世界。
當(dāng)我們把敵人放到包括計(jì)算能力無限敵人時(shí)，即使可以攻破方案，即使我們可以解決困難問題，這也不能說明矛盾，從而說明 敵人不存在。 計(jì)算能力無限的敵人是一定可以攻破方案的。我們用不存在的敵人去解決困難問題，當(dāng)然可以有解。
安全歸約中，我們不關(guān)心敵人能不能攻破方案（因?yàn)槲覀兌技僭O(shè)敵人能攻破方案了），我們關(guān)心： 敵人攻破方案那一日，我們是否也能拿到問題的解？
再強(qiáng)調(diào)一遍，安全歸約中，敵人是一定存在的。我們只關(guān)心問題的解能不能拿到。
現(xiàn)在，我們考慮惡意敵人，想方設(shè)法輸出一個(gè) 讓我們得不到解的攻擊。
再進(jìn)一步放縮，讓這個(gè)敵人的計(jì)算能力達(dá)到無限。
如果這樣的敵人都不能搞死我們，讓我們的reduction 失敗，我們就一定能得到困難問題的解。（我們=證明者）
最后，我是通過以下通俗例子和key老師完成交互的。
?
假設(shè)對方案的攻擊，來自能力有限的敵人，攻擊方式只能來自越國（凡人修仙傳）
我們現(xiàn)在把敵人的能力放大無限，出招更多，那么攻擊方式可以cover 整個(gè)地球
現(xiàn)在，我們從地球上選出最有威脅的攻擊，證明即使是這個(gè)攻擊，歸約仍然成功
那么來自越國的攻擊也是可以進(jìn)行歸約，解決困難問題的。
而困難問題是困難的，所以，來自越國的攻擊不存在
那來自其它國家的攻擊可能存在嗎？?
可能！
但我們不管，因?yàn)橛?jì)算能力有限的敵人一定來自越國！
而我們只關(guān)心計(jì)算能力有限的敵人。
