Paper 2019/511

GALACTICS: Gaussian Sampling for Lattice-Based Constant-Time Implementation of Cryptographic Signatures, Revisited

Gilles Barthe, Sonia Belaïd, Thomas Espitau, Pierre-Alain Fouque, Mélissa Rossi, and Mehdi Tibouchi

Abstract

In this paper, we propose a constant-time implementation of the BLISS lattice-based signature scheme. BLISS is possibly the most efficient lattice-based signature scheme proposed so far, with a level of performance on par with widely used pre-quantum primitives like ECDSA. It is only one of the few postquantum signatures to have seen real-world deployment, as part of the strongSwan VPN software suite. The outstanding performance of the BLISS signature scheme stems in large part from its reliance on discrete Gaussian distributions, which allow for better parameters and security reductions. However, that advantage has also proved to be its Achilles’ heel, as discrete Gaussians pose serious challenges in terms of secure implementations. Implementations of BLISS so far have included secret-dependent branches and memory accesses, both as part of the discrete Gaussian sampling and of the essential rejection sampling step in signature generation. These defects have led to multiple devastating timing attacks, and were a key reason why BLISS was not submitted to the NIST postquantum standardization effort. In fact, almost all of the actual candidates chose to stay away from Gaussians despite their efficiency advantage, due to the serious concerns surrounding implementation security. Moreover, naive countermeasures will often not cut it: we show that a reasonable-looking countermeasure suggested in previous work to protect the BLISS rejection sampling can again be defeated using novel timing attacks, in which the timing information is fed to phase retrieval machine learning algorithm in order to achieve a full key recovery. Fortunately, we also present careful implementation techniques that allow us to describe an implementation of BLISS with complete timing attack protection, achieving the same level of efficiency as the original unprotected code, without resorting on floating point arithmetic or platform-specific optimizations like AVX intrinsics. These techniques, including a new approach to the polynomial approximation of transcendental function, can also be applied to the masking of the BLISS signature scheme, and will hopefully make more efficient and secure implementations of lattice-based cryptography possible going forward.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision. ACM-CCS
DOI
10.1145/3319535.3363223
Keywords
Timing AttackPhase Retrieval algorithmsConstant-time ImplementationLattice-based CryptographyMasking Countermeasure
Contact author(s)
gbarthe @ mpi-sp org
sonia belaid @ cryptoexperts com
thomas espitau @ lip6 fr
pierre-alain fouque @ univ-rennes1 fr
melissa rossi @ ens fr
mehdi tibouchi br @ hco ntt co jp
History
2020-08-19: last of 3 revisions
2019-05-20: received
See all versions
Short URL
https://ia.cr/2019/511
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/511,
      author = {Gilles Barthe and Sonia Belaïd and Thomas Espitau and Pierre-Alain Fouque and Mélissa Rossi and Mehdi Tibouchi},
      title = {GALACTICS: Gaussian Sampling for Lattice-Based Constant-Time Implementation of Cryptographic Signatures, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2019/511},
      year = {2019},
      doi = {10.1145/3319535.3363223},
      note = {\url{https://eprint.iacr.org/2019/511}},
      url = {https://eprint.iacr.org/2019/511}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.