CryptoDB
An argument for Hamiltonicity
Authors: | |
---|---|
Download: | |
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. |
BibTeX
@misc{eprint-2008-18040, title={An argument for Hamiltonicity}, booktitle={IACR Eprint archive}, keywords={cryptographic protocols / Hamiltonian cycle, argument protocol, Schwartz-Zipel lemma, zero knowledge}, url={http://eprint.iacr.org/2008/363}, note={unpublished vf@unity.net 14114 received 23 Aug 2008}, author={Vadym Fedyukovych}, year=2008 }