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

https://hal-ujm.archives-ouvertes.fr/ujm-00664924
Contributor : Pierre-Louis Cayrel <>
Submitted on : Tuesday, January 31, 2012 - 4:50:53 PM
Last modification on : Tuesday, November 19, 2019 - 10:46:19 AM

Identifiers

  • HAL Id : ujm-00664924, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

134