3
$\begingroup$

Can anyone suggest a cryptosystem for the following problem? We are working on a university research project.

Problem

Alice has multiple messages $M_i$, $i = 1,\ldots ,n$. Bob should obtain any, but exactly one $M_i$, without obtaining other $M_j$, $j \neq i$. Alice, on the other hand, shouldn't get the exact $i$, which has been selected by Bob.

Analogous physical world scenario

Alice writes each $M_i$ onto a distinct piece of paper, and puts these pieces into a hat. Then, Bob shuffles the pieces by hand without seeing them, draws one piece and, finally, burns the others. Obviously, Bob doesn't have a chance to peek into the hat. Also, Alice cannot see which piece Bob has selected (she is not able to leave secret marks in the pieces).

| improve this question | |
$\endgroup$
  • 4
    $\begingroup$ Sounds like what you are looking for is Oblivious Transfer. $\endgroup$ – mikeazo Jan 6 '17 at 15:08
  • $\begingroup$ You can find a very simple, actively secure Diffie-Hellman based protocol for 1-out-of-N OT in this paper: eprint.iacr.org/2015/267 $\endgroup$ – pscholl Jan 7 '17 at 21:12
  • $\begingroup$ @mikeazo pscholl OT is exactly what we've needed. Thank you! $\endgroup$ – Emil Melnikov Jan 28 '17 at 22:45
2
$\begingroup$

Disclaimer: I'm not by any means an expert on this, and my answer is based on things I've read, which may only be the surface of the iceberg. Comments are welcome.

You can create oblivious transfer from any public key encryption scheme for which there is an algorithm that can output strings indistinguishable from real public keys or the same with ciphertexts instead.

Basically, Bob sends $(p_1, \ldots, p_n)$ to Alice where $p_j$ is his real public key and the others are "fake" public keys. Alice sends back encryption of each $M_i$ under the key $p_i$, and Bob is only able to decrypt $M_j$. Moreover, by the properties of the "fake" keys, Alice does not learn which message Bob picked. Of course, this is only secure against passive adversaries that follow the protocol.

| improve this answer | |
$\endgroup$
  • $\begingroup$ this does not prevent Bob from getting all messages by providing valid public keys for each $i$ $\endgroup$ – max taldykin Jan 7 '17 at 11:47
  • $\begingroup$ @maxtaldykin You're right, and that why I've said this is only secure against passive adversaries. $\endgroup$ – Daniel Jan 7 '17 at 13:15

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.