1
$\begingroup$

Short version:

Given a hash of a plaintext, a public key, and a ciphertext (but not knowing the original plaintext), is there any way to verify that the ciphertext is the plaintext after being encrypted with the public key?

Long version:

I'd like to develop a broker that can pass to a recipient a message of which it knows the ciphertext and the plaintext's hash (but not the plaintext itself), but will only do so if it can be confident that the ciphertext is indeed the original message that was encrypted using the recipient's public key (which it knows).

This is somewhat similar to proxy re-encryption, except that the proxy is only verifying the public key of the re-encryption, not actually doing the re-encryption. Perhaps there's a way to do this through holomorphic encryption?

As far as I'm aware, there is currently no way to do this. But, advancements in zero-knowledge proofs and other cryptographic tricks are happening so quickly that I wanted to check and see if this could be done before giving up on it.

You may ask "why doesn't the recipient just try to decrypt it and verify it against the cipher text hash?" That is not feasible in this use case, because other actions are tied to the broker forwarding messages and they shouldn't happen unless it's actually a valid message. i.e. there are good reasons that the broker cannot forward an invalid message.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
0
$\begingroup$

Correct, the encrypter can make a zero knowledge proof of encryption. You would prove the encryption of some value was done under a specific public key, and reveal the public key and ciphertext only (example AES encryption ZK circuit here: https://github.com/Electron-Labs/aes-circom). There are a number of other implemented schemes as well, depending on your encryption algorithm.

You could also do a regex or substring match on the pre-image to ensure that the pre-image is structured correctly.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you, this looks promising. This seems like it could prove that the encryption of "some value" was done with a specific public key, but could it also prove that the value that was encrypted was the correct value? i.e. we need proof that "the plaintext that was encrypted has this hash", AND "the plaintext was encrypted using this public key." $\endgroup$
    – Jordan
    Sep 20 at 19:08
  • $\begingroup$ Yes, you could just add a public output that would be the hash of the input. The whole circuit should be a handful of lines to prototype at zkrepl.dev if you just import poseidon (it already is) and add the AES import, and apply both operations to the cyphertext. $\endgroup$
    – John Targaryen
    Sep 21 at 9:46
0
$\begingroup$

Yes, this is possible. If I understood what you try to achieve, you have a public key $pk$, a hash value $h$ and a ciphertext $c$ and you want a way to prove knowledge of $m$ such that $H(m)=h$ and $\mathsf{enc}_{pk}(m)=c$ for some key $k$ and without revealing neither $k$ nor $m$. This is an NP relation with $(pk,c,h)$ as the instance and $m$ as the witness; and we know how to construct zero-knowledge proofs of knowledge for any NP relation. An efficient way to construct this sort of proof is through the MPC in the head paradigm. It can also be made non-interactive using the Fiat-Shamir transform.

This was the theory, I'm guessing from your question that you're looking to implement such a thing. I don't know of any existing toolkit to let you prove this out of the box. But a good starting point might be to look at post-quantum signature schemes that a based on the MPC in the head paradigm, such as Picnic.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, and yes, that is the correct understanding. And yes, I do neet to design a practical implementation. I'll do some investigation, but first I'll need to spend a fair bit of time understanding ZKPs in general! $\endgroup$
    – Jordan
    Sep 21 at 16:33
0
$\begingroup$

If you can get creative with the protocol, you can simplify things as follows:

There is a plaintext which has been encrypted with a secret key $x$. The key $x$ is a uniformly random scalar, and is known by Alice. In the context of ECC, a scalar value is an integer less than the size of the group generated by the base point $G$ chosen for that curve.

The Broker is informed of $X$, which is the public key corresponding to the secret key $x$. It is calculated as $X=xG$.

Instead of encrypting the entire plaintext again for each recipient, it is only $x$ that is encrypted for each recipient.

Charlie is an intended recipient. Charlie, in advance, picks a uniformly random scalar $y$. Charlie privately communicates $y$ to Alice. Charlie also communicates the corresponding public key $Y$ to the Broker. $Y$ is calculated as $Y=yG$.

Alice, who knows $x$, calculates $z=x-y$ and sends $z$ to the Broker.

The broker can verify that $X\overset{?}{=} Y+zG$.

Since Charlie has already communicated that he knows $y$ such that $Y=yG$, the Broker is now assured that $z$ can be used by Charlie to recover $x$ as $x=y+z$.

Note: addition and subtraction of scalar values are done modulo the order of the group. The same $y$ value should never be used for more than one transaction.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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