Paper 2018/1205

Cryptanalysis of a code-based one-time signature

Jean-Christophe Deneuville and Philippe Gaborit

Abstract

In 2012, Lyubashevsky introduced a new framework for building lattice-based signature schemes without resorting to any trapdoor (such as GPV [6] or NTRU [8]). The idea is to sample a set of short lattice elements and construct the public key as a Short Integer Solution (SIS for short) instance. Signatures are obtained using a small subset sum of the secret key, hidden by a (large) gaussian mask. (Information leakage is dealt with using rejection sampling.) In this paper, we show that this framework cannot be adapted to coding theory. In particular, we show that any code-based signature obtained through a direct translation from the lattice setting is doomed to fail, due to an inherent difference between bounds in Hamming and Euclidean metrics. The attack consists in rewriting a signature as a noisy syndrome decoding problem, which can be handled efficiently using the extended bit flipping decoding algorithm.We illustrate our results by breaking Persichetti’s one-time signature scheme built upon this approach [13]: using a single signature, we recover the secret (signing) key in about the same amount of time as required for a couple of signature verifications.