Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I am trying to make a taxonomy of the different purposes of some cryptographic protocols. Generally speaking, the purpose of PIR, oblivious transfer and differential privacy--it sounds as if they were invented for the same purpose: "Give me the information I want without learning anything about this information".
Can we make the aforementioned generalization?
The other answers are good but I thought I would systemize the differences with a single example. Say Bob has a database with 10 entries of the form {name, salary} and Alice would like to query it.
With PIR, Alice can retrieve any entry or entries of her choosing (say the 8th entry) without Bob learning which one. The trivial PIR is Alice just retrieves the entire database. In this case, Bob doesn't know which entry she was interested in. PIR protocols aim to reduce the amount of information Alice has to retrieve from 10 entries in this trivial case to something like the size of 4 entries.
With OT, Alice can retrieve a single entry of her choosing (again say the 8th) without Bob learning which one. Bob is additionally guaranteed she can only see the single entry she chose and gets no information about the others.
With differential privacy, Alice is not retrieving entries themselves but is instead getting an aggregate statistic for all the entries. For example, say she wants to learn the average salary. With differential privacy, the true average salary is not returned. Instead enough noise is added to the average such that it masks the contribution of each individual entry. Put another way, the number returned would still be plausible if you dropped any single entry from the database.
OT and PIR are similar: cryptographic protection against information disclosure. Differential privacy is more of a statistical approach.
In differential privacy the concern is to protect the privacy of a single row of the database. Informally, the DP concept says that everything that can be learned from the database could be learned without access to that row. In a more technical sense, a mechanism respects this property if the distribution of the answers is almost identical (in a very strict way!) for two databases that are different only in a single row.
The DP concept is orthogonal with respect to typical semantic security. In fact, it doesn't say that you could not learn anything from the database — you could at least learn some global property of the database, but you cannot distinguish if that special row is present or not.
There is a slight distinction between PIR and OT. From Wikipedia:
PIR is a weaker version of 1-out-of-n oblivious transfer, where it is also required that the user should not get information about other database items.
In other words, OT is stronger in that the receiver only gets what is requested.
Differential privacy is new to me, so I'll read up on it before commenting.
