Skip to Main content Skip to Navigation
Conference papers

Lattice-based Zero-knowledge Identification with Low Communication Cost

Abstract : In this paper we propose a new 5-pass zero-knowledge identification scheme with soundness error close to 1/2. We use the hardness of the Inhomogeneous Small Integer Solution problem as security basis. Our protocol achieves lower communication costs compared with previous lattice-based zeroknowledge identification schemes. Besides, our construction allows smaller public and secret keys by applying the use of ideal lattices. We allow the prover to possess several pairs of secret and public keys, and choose randomly which pair is to be used in a given round of execution. We also dealt with nonces in zero-knowledge schemes in a new way, lowering the number of values exchanged between the prover and the verifier. Hence, our scheme has the good features of having a zero-knowledge security proof based on a well known hard problem of lattice theory, with worst to average-case reduction, and small size of secret and public keys.
Document type :
Conference papers
Complete list of metadatas
Contributor : Pierre-Louis Cayrel <>
Submitted on : Tuesday, January 31, 2012 - 4:50:53 PM
Last modification on : Monday, January 13, 2020 - 5:46:03 PM


  • HAL Id : ujm-00664924, version 1



Rosemberg Silva, Pierre-Louis Cayrel, Richard Lindner. Lattice-based Zero-knowledge Identification with Low Communication Cost. XI Simposio Brasileiro de Seguranca da Informacao e de Sistemas Computacionais - SBSEG 2011, 2011, Brazil. pp.95-107. ⟨ujm-00664924⟩



Record views