IACR News item: 24 September 2021
Ehsan Ebrahimi
ePrint Report
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.
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.
Additional news items may be found on the IACR news page.