# Zero knowledge verification of an encryption protocol

This seems like a straightforward application of zero knowledge techniques, but an answer eludes me.

Alice and Bob claim to have devised an encryption scheme: specifically, they claim to possess functions $E()$ and $D()$ to encrypt and decrypt arbitrary $n$-bit messages.

Charlie wishes to verify this claim, but Alice and Bob don't want Charlie to learn anything about the method.

Can Charlie verify that Alice and Bob can indeed encrypt and decrypt in a zero knowledge fashion ?

• How about this: $\:$ What would "Alice and Bob can't actually encrypt and decrypt" mean? $\hspace{.97 in}$
– user6973
Aug 25, 2013 at 7:35
• It would mean that there should be some message x such that $D(E(x)) != x$, yes ? Aug 25, 2013 at 7:38
• where $E$ and $D$ are ... \begn{my guess at your answer} The alleged encryption and decryption functions.\ennd{my guess at your answer} \begn{what my subsequent questions would be} How are those specified? What is to stop Alice and Bob from "proving" their claim by conducting the protocol as if $E$ and $D$ were both the identity function? \ennd{what my subsequent questions would be}
– user6973
Aug 25, 2013 at 7:43
• In ZK proofs, the prover $P$ and the verifier $V$ have access to a common input $x$. Depending on the flavor of the ZK proof, various things are proven about $x$: (1) In a language-membership proof, $P$ proves that $x \in L$ for some language $L$. (2) In a proof of knowledge, $P$ proves the knowledge of some $w$ such that $(x,w) \in R$, where $R$ is typically an NP relation. (3) In a proof of ability, $P$ proves that for any $y$ chosen by $V$, he can find some $w$ such that some predicate $\pi(x,y,w)$ holds (this is my simplification). Aug 25, 2013 at 17:24
• What does "learn anything about the method" cover? Can C see ciphertext? Can the verifier ask A and/or B to encrypt a chosen plaintext? Those options would clearly be useful in a ZKP, but would open up some attacks (particularly the latter).
– user17396
Aug 25, 2013 at 20:14

For symmetric-key encryption:

If Alice and Bob know a proof that $D_K(E_K(x))=x$ for all $x,K$, then they should be able to prove this fact in zero knowledge. In particular, they can produce boolean circuits for $D_\cdot(\cdot)$ and $E_\cdot(\cdot)$, publish a commitment to each boolean circuit, and then turn their proof into a zero-knowledge proof. In particular, verifying that $D_K(E_K(x))=x$ for all $x,K$ is in co-NP, and thus in IP, and there are zero-knowledge proofs for all of IP (and all of PSPACE).

Now if Alice wants to encrypt a message, she can give a zero-knowledge proof that she has encrypted some message correctly by doing the following: publish commitments $C(x),C(K)$ to her message $x$ and her key $K$; publish a commitment $C(y)$ to her ciphertext $y=E_K(x)$; and now give a zero-knowledge proof that all the commitments are consistent (the ciphertext corresponding to $C(y)$ is a correct encryption, under the boolean circuit for encryption that was committed to earlier, under the key corresponding to $C(K)$ of the message corresponding to $C(x)$). Whether this is a useful thing to prove is another matter entirely -- it's not clear exactly what you are looking for or how you would use a solution to your problem, but hopefully this will give you some ideas.

For public-key encryption:

See Sadeq Dousti's comment. The exposition above can be readily adjusted to fit the public-key encryption setting, along the lines Sadeq Dousti suggests.

My first two claims hold for both symmetric and public key encryption.

In the concrete security context, if there exists any secure encryption scheme, then "Can C efficiently decrypt?" is $\mathsf{coNP}$-hard.

Proof:
For a secure encryption scheme ($\hspace{.03 in}gen$ and) $E$ and $D$, given a boolean circuit $\mathcal{C}$ such that we want to decide whether or not $\mathcal{C}$ is always true, (use the same $gen$ and have) the algorithm $F\hspace{.03 in}?D$ discard the leading bit and then apply $D$, and have $F\hspace{.03 in}?E$ output $\:\:"\hspace{-0.06 in}1\hspace{-0.06 in}" || \hspace{.06 in} E(\hspace{.04 in}pk\hspace{.02 in},m) \:\:$ except when
[$\operatorname{len}(m)$ is the number of inputs to $\mathcal{C}$ and $\mathcal{C}(m)$ is false], in which case have it output $\:\: "\hspace{-0.06 in}0\hspace{-0.06 in}" || \hspace{.06 in} m \;\;$.
(Additionally, test some arbitrary input to the circuit $\mathcal{C}$, in case $\mathcal{C}$ is always false.)

For that matter, "Does this encryption scheme decrypt correctly?" is also coNP-hard.
(Under no assumptions.)

Proof:
Given a boolean circuit $\mathcal{C}$, (let $gen$ uniformly sample an $n$ bit key,) let $\: E(k,m) = m \:$ for all $m\hspace{.02 in}$,
let $\: D(k,m) = m \:$ except when [$\operatorname{len}(m)$ is the number of inputs to $\mathcal{C}$ and $\mathcal{C}(m)$ is false],
in which case let $D(k,m)$ be anything other than $m$.

Assume AS0 and AS1 are publicly known axiomatic systems
that allow efficient testing of alleged proofs in them.

% will be shorthand for "an encryption scheme and a proof in AS0
that decryption works correctly and a proof of security in AS1".

AS1 would presumably take a cryptographic assumption as an axiom,
since otherwise Alice/Bob knowing % would be quite a feat.

One could use a standard zero-knowledge protocol to verify that Alice/Bob knows %,
although that would reveal an upper bound on the lengths
of the algorithm descriptions and the lengths of the proofs.
(This option can give a proof, while the next two options can only give arguments.)

If Alice/Bob knows %, then one could verify that they know an encryption scheme
for which they "quasi-know" (and in particular, there exists) the rest of %,
although that would reveal an upper bound on the lengths of the algorithms.

If Alice/Bob knows %, then one could verify that they "quasi-know" %,
without revealing anything else.

You can adapt the work of Okamoto-Chaum-Ohta to this case. Let $P$ be the prover, $V$ the verifier, $E$ the public encryption key + algorithm (common input to $P$ and $V$), and $D$ the secret decryption key + algorithm (private input to $P$). We assume that $E$ can be probabilistic (to satisfy semantic security, it has to be), and therefore it uses some randomness to encrypt a message: $c = E(x ; r)$

Further, assume that $Com$ is a commitment scheme.

The protocol is as follows (in the first step, $P$ commits to a random string $u$ using randomness $\rho$):

1. $P \to V : Com(u ; \rho)$
2. $V \to P : c = E(x ; r)$
3. $P \to V : Dec(c) \oplus u$
4. $V \to P : x, r$
5. $P \to V : \rho$

The idea is that $P$ shows to $V$ that he can decrypt by committing to the decryption. However, he does not reveal the decryption until $V$ shows that he actually knows the plaintext.

Contrary to its simplicity, this protocol has lots of caveats. For instance, one can show that if $Com$ and $E$ are related in a bizarre way, the protocol is not zero-knowledge. Another caveat is that if $E$ is in fact probabilistic, showing that the protocol is a proof of ability is very hard (if not impossible). However, if it is deterministic (say, merely a trapdoor one-way permutation), then the proof is rather easy. In any case, one can show that the protocol can be used for identification (in the smart-card model of Feige, Fiat, and Shamir).

• One probably also needs "For all $x$ and $r$, the probability over the choice of $r_d$ $\hspace{1.47 in}$ that $Dec(E(x;r);r_d) \neq x\:$ is negligible." for the protocol to be zero knowledge. $\hspace{1.44 in}$ Why does it help for there to be an initial commitment, as opposed to the prover just $\hspace{.58 in}$ committing to $\:Dec(c;r_d)\:$ in between the verifier's messages? $\;$
– user6973
Aug 27, 2013 at 5:05
• @RickyDemer: I assume that $D$ always succeeds in decryption, but assuming that it only fails with negligible probability will also do the job. The initial commitment has nothing to do with the ZK property; it is used to show that the protocol is actually a proof: The knowledge extractor (or, more precisely, the "ability extractor") uses this initial commitment to later extract $x$ from a prover $P^*$. Aug 27, 2013 at 12:43
• The property I was describing was "For all possible pairs $\:\langle x\hspace{.01 in},\hspace{-0.02 in}r\rangle\:$, $\;$ $D$ only fails with negligible probability.", which may be stronger than "$D$ only fails with negligible probability", $\hspace{.32 in}$ depending on how one interprets the latter phrase. $\;\;\;$
– user6973
Aug 27, 2013 at 16:46
• @RickyDemer: Yes, there are three interpretations for "for all $x$, D only fails with negligible probability," depending on what the probability is taken over: (1) only the randomness used by $D$, (2) the randomness used by $E$ and $D$, (3) the randomness used by $E$, $D$ and the key generation algorithm. Aug 27, 2013 at 20:11
• My interpretation was actually "for the particular public key built into the definition of $E\hspace{.03 in}$". $\hspace{.45 in}$ Of course, this interpretation makes sense for that protocol but not for PKE in general. $\hspace{.69 in}$
– user6973
Aug 27, 2013 at 20:22