6
$\begingroup$

I have a set of plaintexts e.g., ["how", "are", "you"] and a sender who encrypts each element with a unique symmetrical key (or not) and outputs the set of ciphers.

Receiver needs assurance that all the ciphers he just received have a one-to-one mapping with the ["how", "are", "you"] and not some other values. I'm not using asymmetric encryption because it'd reveal which cipher represents which item.

I have read all other questions and a few papers on set membership, pederson commits, etc but still can't understand how it'd work. It'd be very helpful if you could give a detailed answer.

$\endgroup$
1
  • 2
    $\begingroup$ Regarding your assumption that "asymmetric encryption [would] reveal which cipher represents which item": This is not true if you do asymmetric encryption properly, i.e., with randomized padding such as OAEP. That still doesn't solve your problem, though. $\endgroup$
    – yyyyyyy
    Commented Aug 12, 2017 at 10:15

2 Answers 2

2
+25
$\begingroup$

If you are allowing for probabilistic proofs, simply have the one doing the encryption encrypt the set multiple times. All of these encrypted sets are sent to you.

You then ask the one doing the encryption to reveal the keys for all but one of the sets. You do the decryption to verify that all of those sets decrypt to the proper plaintexts. This is a cut-and-choose protocol (see Cut-and-Choose Protocol by Crépeau).

If the adversary is going to cheat, they will only be able to encrypt one set incorrectly and you have to randomly not choose that set for verification. You can set the probability of this to be arbitrarily low (at the cost of communication and computation) by setting the number of copies of the set the one doing the encryption must encrypt to be high enough.

$\endgroup$
2
  • $\begingroup$ Cut and Choose would reveal the mapping, which seems to be the challenge in the question. The secure shuffle from Mental Poker by Shamir Rivest and Adleman (1979) could help with. $\endgroup$
    – tylo
    Commented Aug 15, 2017 at 9:17
  • $\begingroup$ @tylo I'm assuming a random mapping for each separate set encryption. So, revealing the mapping of $n-1$ set encryptions, should not reveal the mapping of the $n$th encrypted set. Since OP says that each plaintext is encrypted with a unique key, you should get this property automatically. $\endgroup$
    – mikeazo
    Commented Aug 15, 2017 at 11:57
1
$\begingroup$

This is a fairly common problem in some applied crypto settings, like anonymous credentials and cryptocurrency. What you need is a zero-knowledge proof of knowledge (ZKPoK) that the sender knows three distinct encryption keys and a hidden random permutation of three elements so that the ciphertexts given to the receiver are actually encryptions of the three plaintexts.

More formally, let the three ciphertexts be $c_1, c_2, c_3$. The ciphertext $c_i,i\in [1, 2, 3]$ is the encryption with a key $k_i$ of plaintext $p_{\sigma(i)}$. The plaintext $p_{\sigma(i)}$ is the $\sigma(i)^{\text{th}}$ element of the original list of plaintexts ["how", "are", "you"] where $\sigma$ is a uniformly random sample from the set of permutations of three elements.

In the language of proof systems, the string $(c_1,c_2,c_3,\text{"how"},\text{"are"},\text{"you"})$ is a member of the "language" the ZKPoK is proving membership in. The keys and hidden permutation are a "witness" that proves the string of ciphertexts and plaintexts is a member of this language. A ZKPoK of the statement below is what the sender needs to send the receiver to convince it that the ciphertexts are well-formed encryptions of the appropriate plaintexts, but not reveal any other information about the keys or the hidden permutation.

The statement is, roughly: "I know keys $k_1, k_2, k_3$ and a permutation $\sigma$ so that $c_i = E_{k_i}(p_\sigma(i))$ for $i\in [1, 2, 3]$".

Rather than using a standard encryption scheme, it's probably best to use a commitment, which is kind of like an encryption scheme that prevents the sender from proving multiple different statements about the ciphertexts.

$\endgroup$

Your Answer

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

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