This page contains notes I’ve made while teaching myself certain papers and topics in computer science and cryptography in particular. The main purpose of these notes is to have some reference material that I can refer back to when I eventually forget this material in a couple of weeks. I cannot guarantee all claims here are correct, though I try to be diligent. Some of the notes maybe incomplete.
These notes are usually based on a collection of research papers and textbooks, (or sometimes a blog version of my own research papers). Click to expand.
Differential Privacy (DP) offers the (informally stated) promise that users will not be adversely affected by allowing their data to be used as input to some computation. However, when one first encounters the DP definition, a reasonable question to ask, is “Why would you define it that way?”. In this post, we show that, no matter which way you define it, if you want to formalise the above promise, then all definitions end up being equivalent to the current definition. Writeup
I used Salil Vadhan’s PhD Thesis to teach myself Zero Knowledge. These notes contain a re-derivation of the three seminal papers that together prove in the claim All statements that have statistical zero knowledge proofs reduce to the statistical distance promise problem. Three Part Writeup
DP protects an individuals privacy even against a computationally unbounded adversary. In the mid 2000’s, Salil Vadhan and Mark Bun asked - “Is there a computational task solvable by a single curator with computational differential privacy but is impossible to achieve with information-theoretic differential privacy?”. In other words, is there any benefit to reducing the power of adversary to being polynomial time. In cryptography there are enormous benefits to assuming one-way functions exist. We get commitment schemes, digitial signatures which are fundamental to how we use crypto in society. However, [GKY11] showed that for all the typical tasks for which we use DP, like publishing aggregate statistics, there is no benefit to assuming weaker adversaries. This problem has remained open for a while, till two groups independently proposed two different solutions.
In recent work, we were able to identify a separation. Concurrently, a group at Google identified a separation using completely different techniques.