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)

Short URL: ia.cr/2013/757

Discussion forum: Show discussion | Start new discussion