Is there an encryption algorithm or MAC algorithm for which NO zero-knowledge-proof exists, provably? I want people who want to prove that a ciphertext decrypts into some plaintext to have to spoil the key for decryption, or if they want to prove that message's MAC is some given MAC then they have to spoil the key for MAC.


2 Answers 2


Every NP statement has a zero-knowledge proof, so there will always be a proof of decryption or MAC that doesn't reveal anything new.

But notice that doesn't prevent the statement itself from leaking the key!

Case in point: For the one-time pad, a single plaintext-ciphertext pair reveals the secret key. In a very similar way, a set of two message-tag pairs can leak the secret key in some one-time MACs. Perhaps these are the primitives you are looking for?

For just slightly less primitive ciphers and MACs, preventing zero-knowledge proofs is impossible: IND-CPA security implies that even many plaintext-ciphertext pairs must not leak the encryption key. Similarly, UF-CMA security implies that many message-tag pairs must not leak the MAC key.

  • $\begingroup$ Thank you for answering! Thankfully, no, I am not looking for anything that is one-time. So, that weakness would not affect my particular application (this time!), but thank you for pointing it out! $\endgroup$
    – donaastor
    Jun 14, 2022 at 5:07
  • 1
    $\begingroup$ If a single message-tag pair leaks the key, it's not a secure one-time MAC. Two message-tag pair can (and generally do) leak the key. $\endgroup$
    – Maeher
    Jun 14, 2022 at 7:33
  • $\begingroup$ @Maeher Indeed, that didn't make any sense at all. Thanks for pointing it out. $\endgroup$
    – yyyyyyy
    Jun 14, 2022 at 12:07

Wel.. NO. I just learned that any PSPACE problem has a ZKP.


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.