2
$\begingroup$

I have keypair (u,r), and two pieces of data, X and Y.

I reveal X publicly but keep Y secret. Y has high entropy.

I then concatenate X and Y, into Z.

I encrypt Z, into "encrypt(Z,u) = Q". r is needed to decrypt Q back into Z.

Later, (when it doesn't matter), r will be revealed and everyone will decrypt Q into Z. At that point, everyone will know that, all along, Q "contained" X. Can I prove that Q contains X before r is revealed (including interactive zero-knowledge proofs)?

$\endgroup$
11
  • $\begingroup$ Thanks! For some reason I thought this was crypto.stack (oops). I am actually hoping that it will be impossible to prove that Q contains X (but I wanted to ask neutrally), are you saying that the only way to do this is to change the setup to force-include additional commitment constraints? $\endgroup$
    – Terrace
    Aug 28, 2015 at 14:55
  • 2
    $\begingroup$ It is not clear what you are asking. What does it mean for the function $c$ to combine $X$ and $Y$ into $Z$? Do you just mean concatenate? What does it mean that $Q$ contains $X$? Do you mean that $Q$ encrypts a message which has information on $X$? $\endgroup$
    – Guut Boy
    Aug 28, 2015 at 15:04
  • $\begingroup$ Will you still have the randomness that was used for the encryption? $\:$ Can the verifier assume that the keypair was generated honestly? $\;\;\;\;$ $\endgroup$
    – user991
    Aug 28, 2015 at 15:12
  • $\begingroup$ Well, with the encryption-randomness kept and the keypair assumed to have been generated honestly, most PKE schemes will allow such proofs. $\;$ $\endgroup$
    – user991
    Aug 28, 2015 at 15:31
  • $\begingroup$ I experienced some kind of glitch when this question was moved here ( crypto.stackexchange.com/questions/27789/… ) , and lost control of it. $\endgroup$
    – Terrace
    Aug 28, 2015 at 15:34

1 Answer 1

1
$\begingroup$

A fundamental theorem of cryptography (Goldreich, Micali and Wigderson 1986) states that any NP statement can be proven in zero knowledge. So, the answer is yes. For any polynomial-time combination of $X$ and $Y$ into $Z$, it is possible to prove that $Q$ contains $X$ in zero knowledge.

Note that the general zero knowledge will not be practically efficient since it requires a Karp reduction. However, depending on the combination and the public-key scheme, it may be possible to do this very efficiently. El Gamal specifically is very amenable to efficient zero knowledge, but it depends on the combination you mean.

$\endgroup$
11
  • $\begingroup$ Why does it follow that the answer is yes?$\:$ (Unless somewhat bideniable PKE is known to be impossible, it's not clear to me that there must be an NP algorithm with a non-negligible probability of accepting encryptions of Z and a negligible probability of accepting encryptions of strings other than Z.) $\hspace{1.61 in}$ $\endgroup$
    – user991
    Aug 30, 2015 at 13:21
  • $\begingroup$ The ciphertext is a deterministic polynomial-time function of the plaintext (which contains X and other things) and the randomness. Thus, the NP statement is the public key and the ciphertext, and the witness is simply the plaintext and the randomness. (It's also possible to use the private key as the witness.) It appears that you are concerned with SOUNDNESS; what's stopping the prover from claiming it's a different plaintext, as you can do with non-committing types of encryption. It wasn't clear to me that this is a requirement. If it is, then you just need to use a committing encryption. $\endgroup$ Aug 30, 2015 at 13:22
  • $\begingroup$ The OP would "actually prefer it to be impossible to prove". $\;$ $\endgroup$
    – user991
    Aug 30, 2015 at 13:24
  • $\begingroup$ In that case, the question isn't well enough defined. Do you want to make it impossible to prove but also impossible to open to something else later on? This is certainly not possible. I need a better definition of the soundness requirements. $\endgroup$ Aug 30, 2015 at 14:15
  • $\begingroup$ Ideally it would be impossible to prove, during "Phase 1". During this phase, Y and r are both kept secret (and feel free to use r as a symmetric key if that matters). During "Phase 2" (approximately 10-30 minutes later) everything is revealed: X, Y, and r. I'd be happy to explain more, but am worried it would distract. The setting is a kind of voting, I want the votes ("X") to be secret while they're being cast because I'd like people to be able to lie about how they intend to vote (after the vote, it doesn't matter). $\endgroup$
    – Terrace
    Aug 31, 2015 at 2:33

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.