2
$\begingroup$

Alice has two 1GB files, and Bob wants one without Alice knowing which. Can this be done with less than 2GB (1GB for each file) of bandwidth between Alice and Bob?

$\endgroup$
  • $\begingroup$ Is there any similarity between the files? Are the files compressible? If not, then I don't see how you could possibly do that. Otherwise, any file transfer could be made more efficient just by splitting the file into two and using the scheme you are looking for. $\endgroup$ – forest Apr 19 '18 at 12:14
  • $\begingroup$ No similarity between the files, and no compression possible. I don't see how your file transfer argument works. Bob is interested in only one file, not both. $\endgroup$ – Randomblue Apr 19 '18 at 16:21
1
$\begingroup$

I wonder if it's possible to do it with indistinguishability obfuscation. Let's say that the two files have hashes H1 and H2, and that Bob knows those hashes. He can give Alice an obfuscated program that checks the two files against H1 and H2, aborts if the check fails, and if not returns one of the two files (say the one corresponding to H2) encrypted against his public key.

Alice can make sure that both files are not transferred by capping the response to 1 GB. Alternatively Alice can provide a zero-knowledge proof that the response of the obfuscated program is exactly one of the files.

$\endgroup$
  • $\begingroup$ This answer seems technically correct, but How big/slow is the program which works on 2GB? $\endgroup$ – Meir Maor Apr 28 '18 at 18:36
  • $\begingroup$ Actually, capping the response to 1 GB doesn't work; the iO could transmit 1/2 Gig of each secret, which is not supposed to be allowable under OT $\endgroup$ – poncho Apr 28 '18 at 22:41
  • $\begingroup$ @poncho: Private information retrieval capped to 1GB is acceptable in my situation. en.wikipedia.org/wiki/Private_information_retrieval $\endgroup$ – Randomblue Apr 29 '18 at 2:08
0
$\begingroup$

With a protocol that is UC secure in the standard model, the total communication from the sender has to be at least $|m_0| + |m_1|$.

In UC security, there must be a simulator that interacts with a corrupt sender and eventually extracts the two OT payloads $m_0, m_1$ (to send to the ideal functionality). The only information that the simulator receives are the protocol messages of the sender. So the total communication must be large enough to encode an arbitrary $m_0, m_1$.

I doubt a random oracle would help, and I doubt semi-honest security would help. I still feel like a similar incompressibility argument could go through. But I have not worked out such an argument.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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