Paper 2013/757

Practical Signatures from the Partial Fourier Recovery Problem

Jeff Hoffstein, Jill Pipher, John Schanck, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
lattice techniquesdigital signatures
Contact author(s)
wwhyte @ securityinnovation com
History
2013-11-17: received
Short URL
https://ia.cr/2013/757
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/757,
      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{https://eprint.iacr.org/2013/757}},
      url = {https://eprint.iacr.org/2013/757}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.