Paper 2014/874

Accelerating Bliss: the geometry of ternary polynomials

Léo Ducas


The signature scheme Bliss proposed by Ducas, Durmus, Lepoint and Lyubashevsky at Crypto’13, is currently the most compact and efficient lattice-based signature scheme that is provably secure under lattice assumptions. It does compare favourably with the standardized schemes RSA and ECDSA on both Software and Hardware. In this work, we introduce a new technique that improves the above scheme, offering an acceleration factor up to 2.8, depending on the set of parameters. Namely, we improve the unnatural geometric bound used in Bliss to a tighter and much more natural bound by using some extra degree of freedom: the ternary representations of binary challenges. Precisely, we efficiently choose a ternary representation that makes the result deterministically shorter than the expected length for a random challenges. Our modified scheme Bliss-b is rather close to the original scheme, and both versions are compatible. The patch has been implemented on the Open-Source Software implementation of Bliss, and will be released under similar license.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Lattice Based CryptgraphySignatureBliss
Contact author(s)
lducas @ eng ucsd edu
2014-10-22: received
Short URL
Creative Commons Attribution


      author = {Léo Ducas},
      title = {Accelerating Bliss: the geometry of ternary polynomials},
      howpublished = {Cryptology ePrint Archive, Paper 2014/874},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.