Paper 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
Efficient Interactive Proof SystemPost-quantum SecurityComputational Zero-knowledge
Contact author(s)
ehsan ebrahimi @ uni lu
History
2022-04-14: last of 2 revisions
2021-09-24: received
See all versions
Short URL
https://ia.cr/2021/1286
License
Creative Commons Attribution
CC BY

BibTeX

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