Paper 2021/1286

Post-quantum Efficient Proof for Graph 3-Coloring Problem

Ehsan Ebrahimi


In this paper, we construct an efficient interactive proof system for the graph 3-coloring problem and shows that it is computationally zero-knowledge against a quantum malicious verifier. Our protocol is inline with the sketch of an efficient protocol by Brassard and Crepéau (FOCS 1986) that later has been elaborated by Kilian (STOC 1992). Their protocol is not post-quantum secure since its soundness property holds based on the intractability of the factoring problem. Putting aside the post-quantum security, we argue that Kilian's interactive protocol for the graph 3-coloring problem does not fulfill the soundness property even in the classical setting. In this paper, we propose an XOR-homomorphic commitment scheme based on the Learning Parity with Noise (LPN) problem and use it to construct an efficient quantum computationally zero-knowledge interactive proof system for the graph 3-coloring problem.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Efficient Interactive Proof SystemPost-quantum SecurityComputational Zero-knowledge
Contact author(s)
ehsan ebrahimi @ uni lu
2022-04-14: last of 2 revisions
2021-09-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ehsan Ebrahimi},
      title = {Post-quantum Efficient Proof for Graph 3-Coloring Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1286},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.