Let $𝑓$ be an encryption function, then we have $c = f(m)$ for some bit string $π‘š$. Here, we also have pattern matching function $𝑔(π‘š,π‘šβ€²)$ which returns true whether $π‘š$ matches roughly with $π‘šβ€²$ in terms of some criteria. Given $𝑐$ and $π‘šβ€²$ (some public string), we want to clarify whether $𝑐$ encrypts $π‘š$ such that $𝑔(π‘š,π‘šβ€²)=π‘‘π‘Ÿπ‘’π‘’$ without decrypting it.

How can we do that? I'm not looking for solutions based only on homomorphic encryption since the result will never be revealed without decryption.

Does ZKP help this?

  • 1
    $\begingroup$ Yes, ZKP can show any arbitary algorithmic statement about a ciphertext's contents are true without revealing the remaining ciphertext contents. By the way, there does exists some homomorphic encryption schemes with support for efficient ZKP's. $\endgroup$ – Natanael May 24 '19 at 22:02
  • $\begingroup$ @Natanael Thank you for the answer! Can you elaborate on such homomorphic schemes?? Do you have any source of information such as eprint paper or something. $\endgroup$ – mallea May 25 '19 at 8:05
  • $\begingroup$ Does the statement/context require that $f$ be (a) a true function, implying the same $m$ will always give the same $c$, that is deterministic encryption? and/or (b) public including it's encryption key, meaning $f$ does public-key encryption? This answer has read (b) in the question, I'm not sure about either (a) or (b). We know few encryption/decryption functions with (a) and (b) [one example is textbook RSA], but it would very much restrict $g$, Is it required an arbitrary $g$, independent of the key for $f$, like: $|m\oplus m'|<6$? $\endgroup$ – fgrieu Oct 19 '20 at 5:28

In short: ZKP does not help mostly if you keep your scheme like that. But your scheme can be fixed if you don't need to rely on public encryption.

ZKP do help if a problem can be efficiency calculated if a witness is known and otherwise it is hard to compute. And that's the problem here since anyone can generate such proofs in some cases.

If we talk about encryption schemes, there will be three kind of schemes:

(1) One-Time based: An adversary chooses any m which g(m, m') returns true and compute $k = m \oplus c$. Now anyone can create the desired proof.

(2) Symmetric-key based: An adversary randomly chooses a key k and computes $m = f_k^{-1}(c)$ and outputs k, m, if g(m, m') returns true and otherwise repeats with a different k (algorithms used in practice might have simpler attacks too). Especially if the pattern function has a wide range the likelyhood to find a true returning pattern will break the ZKP since anyone can could generate such a prove then.

(3) Public-crypto: I'm not sure myself here, but I would not rule out attacks like in (2).

The attacks I described here works because the key can be chosen by an adversary. If you rely on the random oracle model, you can use a hash function as commitment (e.g. SHA256) to commit your key using $com \leftarrow H(k|decom)$. Now an adversary must generate a prove so that he knows a key k, a message m and a decommitment decom so that $H(k|decom) = com \land f_k(m) = c \land g(m, m') = 1$ which is hard to compute if you don't know the key and the message.

I would recommend you to use a generic zero-knowledge protocols which proves the computation of a boolean circuit like presented here and here. The authors first paper even published a reference implementation of SHA256 on github. Hopefully your encryption scheme does not rely on public encryption, since otherwise the proof becomes impractical.


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.