You are looking at a specific version 20191226:052433 of this paper. See the latest version.

Paper 2019/973

On the Non-Existence of Short Vectors in Random Module Lattices

Ngoc Khanh Nguyen

Abstract

Recently, Lyubashevsky & Seiler (Eurocrypt 2018) showed that small polynomials in the cyclotomic ring $Z_q[X]/(X^n+1)$, where $n$ is a power of two, are invertible under special congruence conditions on prime modulus $q$. This result has been used to prove certain security properties of lattice-based constructions against unbounded adversaries. Unfortunately, due to the special conditions, working over the corresponding cyclotomic ring does not allow for efficient use of the Number Theoretic Transform (NTT) algorithm for fast multiplication of polynomials and hence, the schemes become less practical. In this paper, we present how to overcome this limitation by analysing zeroes in the Chinese Remainder (or NTT) representation of small polynomials. Concretely, we follow the proof techniques from Stehlé and Steinfeld (Eprint 2013/004) and provide upper bounds on the probabilities related to the (non)-existence of a short vector in a random module lattice with no assumptions on the prime modulus. Then, we apply these results, along with the generic framework by Kiltz et al. (Eurocrypt 2018), to a number of lattice-based Fiat-Shamir signatures so they can both enjoy tight security in the quantum random oracle model and support fast multiplication algorithms (at the cost of slightly larger public keys and signatures), such as the Bai-Galbraith signature scheme (CT-RSA 2014), Dilithium-QROM (Kiltz et al., Eurocrypt 2018) and qTESLA (Alkim et al., PQCrypto 2017). These techniques can also be applied to prove that recent commitment schemes by Baum et al. (SCN 2018) are statistically binding with no additional assumptions on $q$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2019
Keywords
Lattice-based cryptographyFiat-Shamir signaturesmodule latticeslossy identification schemesprovable security
Contact author(s)
nkn @ zurich ibm com
History
2019-12-26: last of 2 revisions
2019-08-29: received
See all versions
Short URL
https://ia.cr/2019/973
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.