Are zero-knowledge proofs quantum-resistant?

  • 1
    $\begingroup$ Which proof system are you talking about? $\endgroup$ – Maeher Nov 16 '18 at 7:04
  • 2
    $\begingroup$ It depends. For instance, SNARKs are not and STARKs are. $\endgroup$ – Youssef El Housni Nov 16 '18 at 7:13
  • $\begingroup$ SNARKs and STARKs are not, by default, zero-knowledge proof systems @YoussefElHousni $\endgroup$ – iwriteonbananas Nov 16 '18 at 16:59
  • $\begingroup$ @iwriteonbananas why STARKs are not quantum resistant ? $\endgroup$ – Youssef El Housni Nov 16 '18 at 17:31
  • 1
    $\begingroup$ Ok I was talking about ZK-STARKs. Precision matters. @iwriteonbananas $\endgroup$ – Youssef El Housni Nov 16 '18 at 18:35

There is no generic answer to this question. Zero-knowledge proof (ZKP) systems can be post quantum secure, but they need not be. It all depends on the cryptography on which the security of the ZKP rests.

There exist ZKPs that only use collision-resistant hash functions and hence are plausibly post quantum secure. Popular examples include Hyrax, Aurora, or zkSTARK.

Other notable ZKPs like Bulletproofs or libsnark rely on cryptographic assumptions which are known to be vulnerable to quantum attacks (e.g. hardness of discrete log in certain elliptic curve groups).

  • $\begingroup$ I think Hyrax is based on DL, so not quantum secure. $\endgroup$ – Shan Chen Nov 16 '18 at 22:45

Informally, post-quantum cryptosystems strive to remain secure even in the scenario that the attacker has a large quantum computer. Precisely, the basic hard assumptions such as DLP, BDH and so on are not secure in this scenario.

Regarding the Zero-Knowledge proof systems, it depends on the setup phase and model of working in each ZK proof scheme. For instance, ZK-SNARKs are based on a trusted setup which is executed by a third trusted party. At this point, we suppose these schemes are secure because there is no adversary to find a solution for some hard problems in the polynomial time. So a quantum attacker is able to compromise the security by attempting to find a solution for the claimed hard problem. Each user who has the master key is able to do some malicious activities. I should emphasize that if the setup phase in this schemes is based on some quantum-resistant hard assumptions so this scheme will resist against this kind of attack.

Conversely, in the ZK-STARKs, there is no third trusted party to produce secure parameters and the prover and verifier just use some plain parameters which are based on pure mathematics instead of a master key. So in this model, there is no secure parameter with some assumptions based on hard problems. You can take a look at this post. LINK

  • 1
    $\begingroup$ There are zkSNARKs with trusted setup that are PQ secure. $\endgroup$ – iwriteonbananas Nov 16 '18 at 16:58
  • 1
    $\begingroup$ And vice versa there are zkSNARKs without trusted setup that are not PQ secure. $\endgroup$ – iwriteonbananas Nov 16 '18 at 16:58
  • $\begingroup$ You are right. As I mention it is based on the hard assumption in the setup phase and there are some quantum resistant zk-SNARKs such as recently proposed scheme "Lattice-Based zk-SNARKs from Square Span Programs" by Genarro et. al. Would you please send me a link for a ZK-SNARK without trusted setup? I know Updatable zk-SNARKs exist but it is also based on a trusted user. $\endgroup$ – Mahdi Nov 16 '18 at 19:32
  • $\begingroup$ zkSTARK is a zkSNARK without trusted setup :D Aurora and Hyrax are other examples. $\endgroup$ – iwriteonbananas Nov 16 '18 at 19:36
  • $\begingroup$ :D we put them in another side, but actually it is my question whether a SNARK without trusted setup exists?! $\endgroup$ – Mahdi Nov 16 '18 at 19:39

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.