Improved zero-knowledge identification with lattices

Abstract

Zero-knowledge identification schemes solve the problem of authenticating
one party to another via an insecure channel without disclosing any
additional information that might be used by an impersonator. In this paper
we propose a scheme whose security relies on the existence of a commitment
scheme and on the hardness of worst-case lattice problems. We adapt a codebased
identification scheme devised by Cayrel, V´eron and El Yousfi, which constitutes
an improvement of Stern’s construction. Our solution sports analogous
improvements over the lattice adaption of Stern’s scheme which Kawachi et al.
presented at ASIACRYPT 2008. Specifically, due to a smaller cheating probability
close to 1/2 and a similar communication cost, any desired level of security
will be achieved in fewer rounds. Compared to Lyubashevsky’s scheme presented
at ASIACRYPT 2009, our proposal, like Kawachi’s, offers a much milder security
assumption: namely, the hardness of SIS for trinary solutions. The same assumption
was used for the SWIFFT hash function, which is secure for much smaller
parameters than those proposed by Lyubashevsky