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
Date: received 23 Aug 2008
Contact author: vf at unity net
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20080827:151954 (All versions of this report)
Short URL: ia.cr/2008/363
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]