Cryptology ePrint Archive: Report 2019/511

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

Gilles Barthe and Sonia Belaïd and Thomas Espitau and Pierre-Alain Fouque and 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.

Category / Keywords: implementation / Timing Attack, Phase Retrieval algorithms, Constant-time Implementation, Lattice-based Cryptography, Masking Countermeasure

Original Publication (with minor differences): ACM-CCS

Date: received 16 May 2019, last revised 19 Aug 2020

Contact author: gbarthe at mpi-sp org, sonia belaid at cryptoexperts com, thomas espitau at lip6 fr, pierre-alain fouque at univ-rennes1 fr, melissa rossi at ens fr, mehdi tibouchi br at hco ntt co jp

Available format(s): PDF | BibTeX Citation

Version: 20200819:143516 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]