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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know the question is rather unusual, but let me clarify what I'm searching for:

There is one person, lets call her $Alice$. $Alice$ has $n$ plaintexts $t_1..t_n$ and $n$ public keys $pk_1..pk_n$ of other persons.

Now $Alice$ has to encrypt one $t_i$ with a $pk_j$ for arbitrary $i,j$. Each key and plaintext should only be used exactly once. After everything has been encryptied $Alice$ should not have any means to determine which $t_i$ was used to generate one of the outputs. There are $n$ other players to which the keys $pk_1..pk_n$ belong. The other players all can see the encrypted results of $Alice$s encryption operation and nothing else. Obviously every one of them can only decrypt the plaintext encrypted with his or her private key.

Alice should be able to prove to every other player, that she does not know which plaintext got encrypted with which key.

Is that possible at all? I possibly left something out one needs to know to hint me to a proper solution, in that case please leave a comment and i try to provide the Information.

(Sorry for my mediocre english)

share|improve this question
One could do that with generic multi-party computation. $\:$ I don't know of any more efficient solution. $\hspace{.33 in}$ – Ricky Demer Mar 28 '14 at 16:09
cleaned up some comments as they were incorporated into the question – mikeazo Mar 28 '14 at 16:39
To Ricky's point, there's no way for Alice to prove this outside of involving the other parties in the computation. Fundamentally, Alice can always write down each $t_i,E(pk_j,t_i)$ pair on a sheet of paper. – Stephen Touset Mar 28 '14 at 17:51
up vote 2 down vote accepted

What you're describing sounds a lot like mental poker. That is, your Alice has a number of messages ("cards") that she wants to shuffle and deal to the other players, in such a way that she can prove to the other players that she does not know who got which cards.

Various protocols have been proposed for mental poker; see the linked Wikipedia article for some examples. Apparently, there currently exists at least one practical and secure implementation of such a protocol.

share|improve this answer

No, sorry, this is the bad case in zero knowledge proofs. Can it be done? Yes. Can it be proven to another party? No.

share|improve this answer
The enitre point of ZKP is that it is a proof to other people. This answer does not address the question at all. – tylo Jun 22 '15 at 13:35

I suppose you will need another party, Bob. Bob generates a pair of keys, encrypts all messages with the public key and discloses the encrypted messages to everyone, including Alice, sorted alphabetically, so that Alice cannot guess which one is t1,

Alice shuffles the messages at will and encrypts them with pk1...pkn. Then Bob releases his private key and everyone discovers which message they got.

As long as Bob and Alice don't collaborate, there is no way for Alice to cheat. In case there is no Bob who is trusted by everyone, each participant will have to do the same procedure as Bob, so that messages are encrypted and sorted n times before they get to Alice, and Alice will need everyone's cooperation to find out which message is which.

share|improve this answer
One of the things that both Alice and Bob need to prove is that what they generate is some permutation of the inputs; for example, Bob didn't discard $t_1$, and gave two encryptions of $t_2$. – poncho Mar 23 '15 at 16:44
That would be discovered at the end, right? – Dmitry Grigoryev Mar 23 '15 at 17:05
Not unless the $n$ parties sit down and compare results afterwards -- that wasn't mentioned within the problem statement. – poncho Mar 23 '15 at 17:14
If all the $t_i$ are known to everyone, this works, because everyone can check the output of Bob, when he revealed his key. Basically this is like a commitment scheme. However, this way Alice will also find out later who got which text, after Bob revealed his key. All you need then is a proof that Alice actually used those commitments and used each one just once. – tylo Jun 22 '15 at 13:44

Your Answer


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.