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
2  
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
1  
cleaned up some comments as they were incorporated into the question –  mikeazo Mar 28 '14 at 16:39
2  
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

2 Answers 2

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

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,...tn.

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 at 16:44
    
That would be discovered at the end, right? –  Dmitry Grigoryev Mar 23 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 at 17:14

Your Answer

 
discard

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.