Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am trying to make a taxonomy of different purposes of some cryptographic protocols. Generally speaking the purpose of PIR, oblivious transfer and differential privacy it sounds like being invented for the same purpose. "Give me information i want without learning anything about this information". Can we make the aforiomentioned generalization?

share|improve this question
add comment

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
    
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? –  curious Jun 28 '12 at 15:08
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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 –  curious Jun 18 '12 at 8:47
1  
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. –  D.W. Jun 24 '13 at 19:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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