3
$\begingroup$

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)

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ One could do that with generic multi-party computation. $\:$ I don't know of any more efficient solution. $\hspace{.33 in}$ $\endgroup$
    – user991
    Mar 28, 2014 at 16:09
  • 1
    $\begingroup$ cleaned up some comments as they were incorporated into the question $\endgroup$
    – mikeazo
    Mar 28, 2014 at 16:39
  • 3
    $\begingroup$ 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. $\endgroup$
    – Stephen Touset
    Mar 28, 2014 at 17:51

3 Answers 3

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ The enitre point of ZKP is that it is a proof to other people. This answer does not address the question at all. $\endgroup$
    – tylo
    Jun 22, 2015 at 13:35
0
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – poncho
    Mar 23, 2015 at 16:44
  • $\begingroup$ That would be discovered at the end, right? $\endgroup$
    – Dmitry Grigoryev
    Mar 23, 2015 at 17:05
  • $\begingroup$ Not unless the $n$ parties sit down and compare results afterwards -- that wasn't mentioned within the problem statement. $\endgroup$
    – poncho
    Mar 23, 2015 at 17:14
  • $\begingroup$ 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. $\endgroup$
    – tylo
    Jun 22, 2015 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.