Paper 2021/294

Code-based signatures without trapdoors through restricted vectors

Marco Baldi, Franco Chiaraluce, and Paolo Santini

Abstract

The Schnorr-Lyubashevsky approach has been shown able to produce secure and efficient signature schemes without trapdoors in the lattice-based setting, exploiting small vectors in the Euclidean metric and rejection sampling in the signature generation. Translating such an approach to the code-based setting has revealed to be challenging, especially for codes in the Hamming metric. In this paper, we propose a novel adaptation of the Schnorr-Lyubashevsky framework to the code-based setting, by relying on random non-binary linear codes and vectors with restricted entries to produce signatures. We provide some preliminary arguments to assess the security of the new scheme and to compute its parameters. We show that it achieves compact and competitive key and signature sizes, even without resorting to structured random codes.