## Cryptology ePrint Archive: Report 2008/363

An argument for Hamiltonicity

Abstract: A constant-round interactive argument is introduced to show existence of a Hamiltonian cycle in a directed graph. Graph is represented with a characteristic polynomial, top coefficient of a verification polynomial is tested to fit the cycle, soundness follows from Schwartz-Zippel lemma.

Category / Keywords: cryptographic protocols / Hamiltonian cycle, argument protocol, Schwartz-Zipel lemma, zero knowledge

Publication Info: unpublished