# NIZK proof for Order-preserving encryption

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!

• 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)". – Ruben De Smet Jun 26 '19 at 7:46
• 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. – 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.

• 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. – Geoffroy Couteau Jun 25 '19 at 15:42