Cryptology ePrint Archive: Report 2013/757
Practical Signatures from the Partial Fourier Recovery Problem
Jeff Hoffstein and Jill Pipher and John Schanck and Joseph H. Silverman and William Whyte
Abstract: Abstract. We present PASSSign, a variant of the prior PASS and PASS-2 proposals, as a candidate for a practical post-quantum signature scheme. Its hardness is based on the problem of recovering a ring element with small norm from an incomplete description of its Chinese remainder representation. For our particular instantiation, this corresponds to the recovery of a signal with small infinity norm from a limited set of its Fourier coefficients.
The key improvement over previous versions of PASS is the introduction of a rejection sampling technique from Lyubashevsky (2009) which assures that transcript distributions are completely decoupled from the keys that generate them.
Although the scheme is not supported by a formal security reduction, we present extensive arguments for its security and derive concrete parameters based on the performance of state of the art lattice reduction and enumeration techniques.
Category / Keywords: public-key cryptography / lattice techniques, digital signatures
Date: received 15 Nov 2013
Contact author: wwhyte at securityinnovation com
Available format(s): PDF | BibTeX Citation
Version: 20131117:022256 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]