Suppose a cipher c=Enc(K,m), where Enc() is the order-preserving encryption scheme. Can NIZK be used to prove that c does indeed encrypt m? The Schnorr NIZK is based on discrete logarithms equality. I don't know if it can be used for order-preserving encryption.

Thank you!

  • 1
    $\begingroup$ Are there any other conditions why a "simple" arithmetic circuit based proof system would not work for you? K (and any randomization in the scheme) would be the witness, and you should be able to construct a circuit for "I know a K st. c=Enc(K,m)". $\endgroup$ Jun 26 '19 at 7:46
  • $\begingroup$ Thank you firstly. Order-preserving encryption is based on random order-preserving injective function, but I see a lot of NIZK proof is to transform the problem into discrete logarithms equality, like Schnorr NIZK. $\endgroup$
    – user70063
    Jun 27 '19 at 3:39

You cannot prove that a ciphertext (produced by an order-preserving encryption scheme) encrypts a particularly plaintext in zero-knowledge, because verification of such a proof would necessarily leak the plaintext.

Perhaps you want to instead prove that the ciphertext is well-formed (i.e., produced by the scheme)? This is possible in the context of site's definition of [OPE][1], namely, a method of encrypting data so that it's possible to make efficient inequality comparisons on the encrypted items without decrypting them, since El Gamal conforms to this definition (see [plaintext equality tests][2]), and NIZK proof systems can be used to prove various properties about El Gamal ciphertexts.

EDIT. The comments note that:

  • I assumed (possibly incorrectly) that the message was not to be revealed, and

  • The site's definition of OPE is incomplete.

I've proposed an edit to the site's definition of OPE. This answer only applies to the original definition.

  • 2
    $\begingroup$ I disagree. One could perfectly prove that an OPE ciphertext encrypts a given plaintext $m$. Sure, this assumes the plaintext is revealed, but it still makes perfect sense to use a NIZK proof here, since it will reveal nothing more than the plaintext and the fact that the ciphertext encrypts it (e.g. it conceals everything about the secret key $K$, or the randomness used to encrypt). I further disagree that ElGamal satisfies the requirements of an OPE. An OPE requires comparisons to be efficiently checkable in a public way, without interacting with the owner of $K$ or of the random coins. $\endgroup$ Jun 25 '19 at 15:42
  • $\begingroup$ @GeoffroyCouteau I agree with your first point: I assumed (possibly incorrectly) that the message was not to be revealed. (If it can be, then revealing the coins used for encryption suffices to prove that a ciphertext contains a particular plaintext.) I disagree with your second: My answer uses this site's definition of OPE and my answer is clear about that. (That definition could be revised to include without using the private/secret key.) $\endgroup$
    – learning
    Jun 25 '19 at 16:13
  • $\begingroup$ I do not think that it makes sense to assume that this informal sentence provided to give a rough intuition of the concept was ever supposed to be interpreted as a formal definition. OPE has a clear formal definition, which the site does not give nor pretends to give. So, I get what you meant, but I still think it is misleading and inappropriate as an answer. At best, your answer points out that the site definition of OPE is not sufficiently clear and could be understood in a wrong way, which is true but does not answer OP's question. $\endgroup$ Jun 25 '19 at 16:18
  • $\begingroup$ @GeoffroyCouteau I completely appreciate that. Unfortunately, numerous (sometimes contradictory) definitions exist for most concepts, as is true for OPE. I'd never heard of it, but reading the site's definition, it is straightforward to understand. Perhaps that definition can be changed? $\endgroup$
    – learning
    Jun 25 '19 at 16:25
  • $\begingroup$ It seems I can propose a change to the definition, which I've done, but that change has to be approved, so it will take a while to appear. $\endgroup$
    – learning
    Jun 25 '19 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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