同態(tài)加密分享第一期
大家好，我是肉餅粥。是一名人工智能專業(yè)的在讀研究生，目前在做一些和同態(tài)加密相關(guān)的工作。
我決定寫這個專欄主要有以下4個原因
在去年的視頻里我說過，我希望能夠把我做視頻的興趣愛好和我的專業(yè)結(jié)合在一起，我想可以先從寫一些專欄開始，有了專欄作為文字稿件，做視頻就是水到渠成的事情。
我想通過講解知識的方式讓我自己對知識有更多的思考，也許能夠發(fā)現(xiàn)過去沒有發(fā)現(xiàn)的問題。
我認為隱私保護是很重要的，同態(tài)加密具有非常強的隱私保護的能力，但在機器學(xué)習(xí)和人工智能的頂會中，研究同態(tài)加密的工作很少。我希望能有更多的人關(guān)注隱私保護技術(shù)。
作為一名密碼學(xué)的門外漢，我在學(xué)習(xí)同態(tài)加密技術(shù)時看了很多博客、知乎，可能是的基礎(chǔ)太薄弱，在看一遍時感覺很難懂。所以我希望能夠用盡可能簡單的語言去講同態(tài)加密，當(dāng)然，我并不覺得目前我有這個能力做到這件事，畢竟有的時候可能就是要深入才能淺出。我的想法就是先立個flag在這兒，然后逼自己去學(xué)習(xí)和思考。
第一期我主要想講一下：什么是一個好的加密方案？
????如果大家在小學(xué)傳過小紙條的話，可能會用一些加密的信息來傳，這樣即便小紙條被老師發(fā)現(xiàn)了，老師也不知道你們想交流的是什么。我小學(xué)也干過這個事情，我想到的加密方法比較簡單，我的內(nèi)容是英文的，然后把每個字母向后偏移幾位。例如偏移兩位的話a就變成了c，b就變成了d，z就變成了b。那么，
i like you
的密文就應(yīng)該是
k nkmg aqw
????后來我知道，這個加密方法叫凱撒加密，凱撒大帝早在兩千多年前就用過了。同時我也了解到，這種加密方法并不安全，因為在英語中，不同字母出現(xiàn)的頻率是不一樣的，據(jù)統(tǒng)計，像e，s出現(xiàn)的頻率就很高，因此，如果老師截獲了很多小紙條，他可以推測紙條中出現(xiàn)次數(shù)最多的那個字母就是e的密文，從而知道我的偏移位數(shù)，進而破解我的所有密文。
????那么，如何來評價一個加密方法是好是壞呢，顯然，我們無法保證老師一定猜錯，因為即便隨機選一個字母作為字母e的密文，老師也有的概率猜對。其實就是我們希望老師在看到這個密文之后，他猜對的概率依然是
。也就是說，小紙條上寫的內(nèi)容沒有給老師提供任何可以用來破解這個內(nèi)容的信息，我們知道一串隨機的字母是不會提供任何信息的，那么如果在老師看來，小紙條上面的內(nèi)容和一串隨機的字母沒有任何差別，那么我們的加密方法是非常好的。
????我們把這個概念形式化一下就得到了Perfect Secrecy(完美保密性)，在《Introduction to Modern Cryptography》這本書中，這個概念的定義是這樣的：
????用人話說就是，不管知不知道密文，對明文概率分布的估計總是一樣的。
????我們這里列舉一個具有Perfect Secrecy的加密方法，為了簡便，我們的加密方法只能加密01串，例如1010010001，稱為明文。我們的小紙條上也只能寫01串，同時我們要限制我們的小紙條上寫的01串的長度，例如10。并且要和同學(xué)提前準(zhǔn)備好一個01串，例如1010101010，稱為密鑰。我們傳小紙條之前就把明文和密鑰做個異或（兩個輸入一樣則輸出為0，反之為1）。
就得到了我們在小紙條上要寫的內(nèi)容（稱為密文）0000111011。
????很容易證明，如果密鑰是隨機生成的，那么密文也是隨機的。這個方法也被一次性密碼本（One-Time Pad，OTP）。從名字就可以看出來，他只能使用一次，并且他要求密鑰長度和明文是一樣的。這個要求很難達到，因為在我們安全地傳輸信息之前，我們首先要安全地傳輸一個至少是相同長度的密鑰。
????那么我們?yōu)槭裁葱枰粋€很長的密鑰呢？下面的定理給出了一定的解釋，這個定理也來自于《Introduction to Modern Cryptography》，它告訴我們，想要得到一個具有Perfect Secrecy的加密方法，我們的密鑰空間必須足夠大才行。
????在實際應(yīng)用中，我們一般不要求加密方法具有Perfect Secrecy，Perfect Secrecy必須要保證知道密文和不知道密文，明文的概率分布是完全一樣的，而現(xiàn)實中，我們允許這個概率分布有微小的差別。具體這個差別要有多小，由于要進入額外的概念，這里我就不講了，大概就是說，隨著明文長度n的增加，這個差別要不斷趨于0，并且趨于0的速度要快于收斂的速度。
????那么這就是這期的分享了，下期我打算開始講什么是同態(tài)加密，以及分享一下《Efficient Fully Homomorphic Encryption from (Standard) LWE》這篇文章。如果大家有問題，或者哪里覺得講得不清楚，請一定要告訴我。
