<abstract xmlns="http://www.w3.org/1999/xhtml"><p> 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 code- -based 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 ’08. Specifically, due to a smaller cheating probability close to 1<italic>/</italic>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 ’09, 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.</p></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 code- -based 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 ’08. 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 ’09, 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.

Improved Zero-Knowledge Identification with Lattices

Laboratoire Hubert Curien UMR CNRS 5516 de Saint-Etienne, Bˆatiment F 18 rue du professeur Benoˆıt Lauras, 42000 Saint-Etienne, FRANCE

Technische Universität Darmstadt, Department of Computer Science, Hochschulstraße 10, 64289 Darmstadt, GERMANY

Institute of Computing, University of Campinas, Av. Albert Einstein 1251, Cidade Universitria, 13083-852 Campinas/SP, BRAZIL

Tatra Mountains Mathematical Publications

{"article-title":"Improved Zero-Knowledge Identification with Lattices"}

Zero-knowledge identification schemes solve the problem of authenticating one party to another via an insecure channel without disclosing any additional...

Improved Zero-Knowledge Identification with Lattices

Published Online: Feb 01, 2013

Page range: 33 - 63

DOI: https://doi.org/10.2478/v10127-012-0038-4

Keywords
lattice-based cryptography, identification scheme, hash function, SIS problem, zero-knowledge

This content is open access.

Improved Zero-Knowledge Identification with Lattices

Published Online: Feb 01, 2013

Page range: 33 - 63

DOI: https://doi.org/10.2478/v10127-012-0038-4

Keywordslattice-based cryptography, identification scheme, hash function, SIS problem, zero-knowledge

This content is open access.

Keywords
lattice-based cryptography, identification scheme, hash function, SIS problem, zero-knowledge