这个是我上课的时候讲differential privacy的ppt的内容，有英文和中文。内容是基于几篇论文和网上的资料。
Differential Privacy presentation materials
– A hospital has a database of patient records, eachrecord containing a binary value indicating whether or not the patient has someform of cancer.
– We want to know the total number of patients withcancers?
Easy! A summation over these binary values
– But how about if weknow anyone must on the list?
Or anyone must be the end of the list?
If Jack hascancer? S(3)-S(2)
Dierential privacy addresses thequestion of, given the total number of patients with cancer, whether or not anadversary can learn if a particular individual has cancer.
一家医院有一些关于癌症病人的统计数据，如果我们想知道总的患癌症的人数，很简单，做has cancer 列的求和就行了。问题是如果我们知道某个人一定在这个表内，或者我们知道某个人在这个表的最后一行，这是我们再做求和的操作。例如我们知道Jack在表格的最后一行，那么Jack有没有患癌症，我们可以通过S(3)-S(2)就可以知道。这时候隐私就会泄露。Differential privacy就是解决这种问题，怎么可以给出总体的，我们需要的信息，但是不泄露个体的隐私数据？
Differential Privacy
“Let us do the sum function in peace”
-What we want is a protocol that has aprobability distribution over outputs
such that if person I changed their inputfrom xi to any other allowed xi’, the relative probabilities of any output donot change by much
-So, for instance, can pretend your inputwas any other allowed value you want.
简单来说就是Differentialprivacy提供一种关于输出的概率分布的机制或者是协议，可以让我们对数据表进行一定程度的修改，例如把上表的Jack换成其他人，或者改变他患癌症列的属性，但是对总体的输出不会发生大变化。所以就可以假装你的数据表可能包含所有可能的数据，让攻击者不知道任何关于个人的信息，从而达到隐私保护的作用。
Differential privacyaims to provide means to maximize the accuracy of queries fromstatistical databases while minimizing the chances of identifying its records.
The denition was rst proposed in CynthiaDwork’s ICALP paper.
[1] C. Dwork. Dierential privacy. InICALP, pages 1–12, 2006.
[2] C. Dwork, F. McSherry, K. Nissim, andA. Smith. Calibrating noise to sensitivity in private data analysis. InProceedings of the Third conference on Theory of Cryptography, TCC’06, pages265–284, 2006.
[3] C. Dwork , Dierential privacy: Asurvey of results, Theory and Applications of Models of Computation, (2008),pp. 1–19.
Previous eorts
-be “broken”in the sense there are well known attacks
k-anonymity
-dierential privacy has rigorous denition
successful
Differential privacy 的目标是最大化查询准确率并且最小化隐私泄露的风险。它最早被提出来的文章是2006年Cynthia在ICALP的文章，然后下面是他另外一些比较经典的文章。其实之前也有关于这方面的研究，但是在某些攻击下隐私还是很容易泄露，就是k-匿名。但是因为Differential privacy 严格的定义，在很多情况下，他都取得了不错的效果。
让A是从D^N到Y的一个随机化算法。D1，D2是两个数据库，他们只有一行记录不同，我们说这两种数据库叫database neighbors。随机化算法（randomized algorithm），是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。就是将算法的某一步或某几步置于运气的控制之下，即该算法在运行的过程中的某一步或某几步涉及一个随机决策，或者说其中的一个决策依赖于某种随机事件。
定义1，epsilon大于0，定义一个随机化算法A，如果它是epsilon-differentially privacy的话，它满足下面的公式。这时候A的输出的概率分布与抛硬币的概率分布近似。
下面我们来看一个例子。假设Alice跟Bob在玩一个游戏。A 抽取不同的数，不同数目有一共有m个。Alice从中任意抽取任何一个。D下降n表示之前n-1抽取到的结果。Dn,m表示知道前n-1个结果后的第n个结果为数目m。Alice只给Bob前n-1个结果，要求Bob猜出第n个结果。BOB会根据下面公式给出他的猜测。就是计算每一种结果的概率，，然后选出其中最大的j。但是如果A满足epslion differential privacy,即下面这条公式，每种结果的概率相差很小，Bob就会很难猜测到结果，效果跟随机估算差不多。
Pure semantic privacy
Can not learn information about anindividual by the output of some algorithm.
Unfortunately, external information makessuch a privacy denition impossible .
回避现实的人，未来将更不理想。
