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?


3 Answers 3


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.

  • $\begingroup$ Is there a restriction for the type of data? PIR operates only on plaintext? or can be applied in encrypted data as well, as with searchable encryption? $\endgroup$
    – curious
    Commented Jun 28, 2012 at 15:08

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.

  • $\begingroup$ Yes you are right. OT is a more rigorous meaning in the sense that it is described as 2-1 OT or many to 1 oblivious transfer.In PIT there is no such distinction. It is more abstract applied in the upper layers of an infrastructure. OT is like a building block $\endgroup$
    – curious
    Commented Jun 18, 2012 at 8:47
  • 2
    $\begingroup$ That quote from Wikipedia is worded poorly, since it is ambiguous whether the "where..." clause applies to PIR or to OT. With PIR, it's fine to get information about the other database items. With 1-out-of-n oblivious transfer, it's a security requirement that Alice should not be able to get any information about the other database items. $\endgroup$
    – D.W.
    Commented Jun 24, 2013 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.