Take the 2-minute tour ×
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.

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 at 16:09
cleaned up some comments as they were incorporated into the question –  mikeazo Mar 28 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 at 17:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.