# Select a single message without showing which one has been selected

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

• Sounds like what you are looking for is Oblivious Transfer. – mikeazo Jan 6 '17 at 15:08
• 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 – pscholl Jan 7 '17 at 21:12
• @mikeazo pscholl OT is exactly what we've needed. Thank you! – Emil Melnikov Jan 28 '17 at 22:45

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.
• this does not prevent Bob from getting all messages by providing valid public keys for each $i$ – max taldykin Jan 7 '17 at 11:47