1
$\begingroup$

Are zero-knowledge proofs quantum-resistant?

$\endgroup$
8
  • 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
7
$\begingroup$

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. The most well-known examples are those using the FRI protocol: Aurora, Fractal, and zk-Starks [*].

Other notable ZKPs like Bulletproofs or Groth16 rely on cryptographic assumptions (e.g. hardness of discrete log in elliptic curve groups) for which it is known they would be vulnerable to quantum attacks, if such attacks became practical.

[*] "zk-STARK" refers both to a security definition and to a particular family of FRI-based proof systems that satisfies it. The security definition does not mention post-quantum security, so it is the latter that is meant here.

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

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.