同态加密分享第一期
大家好，我是肉饼粥。是一名人工智能专业的在读研究生，目前在做一些和同态加密相关的工作。
我决定写这个专栏主要有以下4个原因
在去年的视频里我说过，我希望能够把我做视频的兴趣爱好和我的专业结合在一起，我想可以先从写一些专栏开始，有了专栏作为文字稿件，做视频就是水到渠成的事情。
我想通过讲解知识的方式让我自己对知识有更多的思考，也许能够发现过去没有发现的问题。
我认为隐私保护是很重要的，同态加密具有非常强的隐私保护的能力，但在机器学习和人工智能的顶会中，研究同态加密的工作很少。我希望能有更多的人关注隐私保护技术。
作为一名密码学的门外汉，我在学习同态加密技术时看了很多博客、知乎，可能是的基础太薄弱，在看一遍时感觉很难懂。所以我希望能够用尽可能简单的语言去讲同态加密，当然，我并不觉得目前我有这个能力做到这件事，毕竟有的时候可能就是要深入才能浅出。我的想法就是先立个flag在这儿，然后逼自己去学习和思考。
第一期我主要想讲一下：什么是一个好的加密方案？
如果大家在小学传过小纸条的话，可能会用一些加密的信息来传，这样即便小纸条被老师发现了，老师也不知道你们想交流的是什么。我小学也干过这个事情，我想到的加密方法比较简单，我的内容是英文的，然后把每个字母向后偏移几位。例如偏移两位的话a就变成了c，b就变成了d，z就变成了b。那么，
i like you
的密文就应该是
k nkmg aqw
后来我知道，这个加密方法叫凯撒加密，凯撒大帝早在两千多年前就用过了。同时我也了解到，这种加密方法并不安全，因为在英语中，不同字母出现的频率是不一样的，据统计，像e，s出现的频率就很高，因此，如果老师截获了很多小纸条，他可以推测纸条中出现次数最多的那个字母就是e的密文，从而知道我的偏移位数，进而破解我的所有密文。
那么，如何来评价一个加密方法是好是坏呢，显然，我们无法保证老师一定猜错，因为即便随机选一个字母作为字母e的密文，老师也有的概率猜对。其实就是我们希望老师在看到这个密文之后，他猜对的概率依然是
。也就是说，小纸条上写的内容没有给老师提供任何可以用来破解这个内容的信息，我们知道一串随机的字母是不会提供任何信息的，那么如果在老师看来，小纸条上面的内容和一串随机的字母没有任何差别，那么我们的加密方法是非常好的。
我们把这个概念形式化一下就得到了Perfect Secrecy(完美保密性)，在《Introduction to Modern Cryptography》这本书中，这个概念的定义是这样的：
用人话说就是，不管知不知道密文，对明文概率分布的估计总是一样的。
我们这里列举一个具有Perfect Secrecy的加密方法，为了简便，我们的加密方法只能加密01串，例如1010010001，称为明文。我们的小纸条上也只能写01串，同时我们要限制我们的小纸条上写的01串的长度，例如10。并且要和同学提前准备好一个01串，例如1010101010，称为密钥。我们传小纸条之前就把明文和密钥做个异或（两个输入一样则输出为0，反之为1）。
就得到了我们在小纸条上要写的内容（称为密文）0000111011。
很容易证明，如果密钥是随机生成的，那么密文也是随机的。这个方法也被一次性密码本（One-Time Pad，OTP）。从名字就可以看出来，他只能使用一次，并且他要求密钥长度和明文是一样的。这个要求很难达到，因为在我们安全地传输信息之前，我们首先要安全地传输一个至少是相同长度的密钥。
那么我们为什么需要一个很长的密钥呢？下面的定理给出了一定的解释，这个定理也来自于《Introduction to Modern Cryptography》，它告诉我们，想要得到一个具有Perfect Secrecy的加密方法，我们的密钥空间必须足够大才行。
在实际应用中，我们一般不要求加密方法具有Perfect Secrecy，Perfect Secrecy必须要保证知道密文和不知道密文，明文的概率分布是完全一样的，而现实中，我们允许这个概率分布有微小的差别。具体这个差别要有多小，由于要进入额外的概念，这里我就不讲了，大概就是说，随着明文长度n的增加，这个差别要不断趋于0，并且趋于0的速度要快于收敛的速度。
那么这就是这期的分享了，下期我打算开始讲什么是同态加密，以及分享一下《Efficient Fully Homomorphic Encryption from (Standard) LWE》这篇文章。如果大家有问题，或者哪里觉得讲得不清楚，请一定要告诉我。
