Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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 ?
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$):
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).
