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).

$\endgroup$
3
  • 4
    $\begingroup$ Sounds like what you are looking for is Oblivious Transfer. $\endgroup$
    – mikeazo
    Jan 6, 2017 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, 2017 at 21:12
  • $\begingroup$ @mikeazo pscholl OT is exactly what we've needed. Thank you! $\endgroup$ Jan 28, 2017 at 22:45

1 Answer 1

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.

$\endgroup$
2
  • $\begingroup$ this does not prevent Bob from getting all messages by providing valid public keys for each $i$ $\endgroup$ Jan 7, 2017 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, 2017 at 13:15

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.