Paper 2013/757

Practical Signatures from the Partial Fourier Recovery Problem

Jeff Hoffstein, Jill Pipher, John Schanck, Joseph H. Silverman, and William Whyte


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. Minor revision.
lattice techniquesdigital signatures
Contact author(s)
wwhyte @ securityinnovation com
2013-11-17: received
Short URL
Creative Commons Attribution


      author = {Jeff Hoffstein and Jill Pipher and John Schanck and Joseph H.  Silverman and William Whyte},
      title = {Practical Signatures from the Partial Fourier Recovery Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2013/757},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.