Cryptology ePrint Archive: Report 2017/995
A signature scheme from Learning with Truncation
Jeffrey Hoffstein and Jill Pipher and William Whyte and Zhenfei Zhang
Abstract: In this paper we revisit the modular lattice signature scheme
and its efficient instantiation known as pqNTRUSign. First, we show that
a modular lattice signature scheme can be based on a standard lattice
problem. As the fundamental problem that needs to be solved by the
signer or a potential forger is recovering a lattice vector with a restricted
norm, given the least significant bits, we refer to this general class of
problems as the “learning with truncation” problem.
We show that by replacing the uniform sampling in pqNTRUSign with a
bimodal Gaussian sampling, we can further reduce the size of a signature.
As an example, we show that the size of the signature can be as low as
4608 bits for a security level of 128 bits.
The most significant new contribution, enabled by this Gaussian sam-
pling version of pqNTRUSign, is that we can now perform batch verifi-
cation, which allows the verifier to check approximately 2000 signatures
in a single verification process.
Category / Keywords: lattice-based signatures, learning with truncation/rounding, NTRU, rejection sampling
Date: received 9 Oct 2017, last revised 30 Oct 2017
Contact author: zzhang at onboardsecurity com
Available format(s): PDF | BibTeX Citation
Note: Adding sections for transcript simulation. Also minor typos.
Version: 20171030:131505 (All versions of this report)
Short URL: ia.cr/2017/995
[ Cryptology ePrint archive ]