Cryptology ePrint Archive: Report 2008/363

An argument for Hamiltonicity

Vadym Fedyukovych

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