Improved zero-knowledge identification with lattices

Cayrel, Pierre-Louis ; Lindner, Richard ; Rückert, Markus ; Silva, Rosemberg

Tatra Mountains Mathematical Publications, Tome 51 (2012), / Harvested from Mathematical Institute

Résumé

Zero-knowledge identification schemes solve the problem of authenticatingone party to another via an insecure channel without disclosing anyadditional information that might be used by an impersonator. In this paperwe propose a scheme whose security relies on the existence of a commitmentscheme and on the hardness of worst-case lattice problems. We adapt a codebasedidentification scheme devised by Cayrel, V´eron and El Yousfi, which constitutesan improvement of Stern’s construction. Our solution sports analogousimprovements over the lattice adaption of Stern’s scheme which Kawachi et al.presented at ASIACRYPT 2008. Specifically, due to a smaller cheating probabilityclose to 1/2 and a similar communication cost, any desired level of securitywill be achieved in fewer rounds. Compared to Lyubashevsky’s scheme presentedat ASIACRYPT 2009, our proposal, like Kawachi’s, offers a much milder securityassumption: namely, the hardness of SIS for trinary solutions. The same assumptionwas used for the SWIFFT hash function, which is secure for much smallerparameters than those proposed by Lyubashevsky

Détail

Publié le : 2012-01-01
DOI : https://doi.org/10.2478/tatra.v53i0.193