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$ Nov 16 '18 at 7:13
  • $\begingroup$ SNARKs and STARKs are not, by default, zero-knowledge proof systems @YoussefElHousni $\endgroup$ Nov 16 '18 at 16:59
  • $\begingroup$ @iwriteonbananas why STARKs are not quantum resistant ? $\endgroup$ Nov 16 '18 at 17:31
  • 1
    $\begingroup$ Ok I was talking about ZK-STARKs. Precision matters. @iwriteonbananas $\endgroup$ 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

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .