Cryptology ePrint Archive: Report 2021/1286

Post-quantum Efficient Proof for Graph 3-Coloring Problem

Ehsan Ebrahimi

Abstract: 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.

Category / Keywords: cryptographic protocols / Efficient Interactive Proof System, Post-quantum Security, Computational Zero-knowledge

Date: received 24 Sep 2021

Contact author: ehsan ebrahimi at uni lu

Available format(s): PDF | BibTeX Citation

Version: 20210924:175536 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]