Cryptology ePrint Archive: Report 2014/457
Transcript secure signatures based on modular lattices
Jeff Hoffstein and Jill Pipher and John M. Schanck and Joseph H. Silverman and William Whyte
Abstract: We introduce a class of lattice-based digital signature schemes
based on modular properties of the coordinates of lattice vectors. We also
suggest a method of making such schemes transcript secure via a rejection
sampling technique of Lyubashevsky (2009). A particular instantiation
of this approach is given, using NTRU lattices. Although the scheme is
not supported by a formal security reduction, we present arguments for
its security and derive concrete parameters (first version) based on the
performance of state-of-the-art lattice reduction and enumeration tech-
niques. In the revision, we re-evaluate the security of first version of the
parameter sets, under the hybrid approach of lattice reduction attack
the meet-in-the-middle attack. We present new sets of parameters that
are robust against this attack, as well as all previous known attacks.
Category / Keywords: public-key cryptography / lattice techniques, digital signatures
Original Publication (with minor differences): PQCRYPTO 2014
Date: received 13 Jun 2014, last revised 29 Apr 2016
Contact author: wwhyte at securityinnovation com
Available format(s): PDF | BibTeX Citation
Note: In this revision, we revisit the security of the proposed parameter sets of the
NTRUMLS scheme. The re-evaluation of the security is based on an analysis of
a hybrid attack on NTRU lattices.
We also propose a new set of parameters that are immune to the above
cryptanalysis. For a given security level, we increased the dimension of the NTRU
lattice, while reducing the modulus q. This gives us a very low acceptance rate
(between 2% to 8%) during the rejection sampling phase. This drawback can be
mitigated with parallel computation.
Version: 20160429:190624 (All versions of this report)
Short URL: ia.cr/2014/457
[ Cryptology ePrint archive ]