Cryptology ePrint Archive: Report 2021/294

Code-based signatures without trapdoors through restricted vectors

Marco Baldi and 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.

Category / Keywords: public-key cryptography / public-key cryptography, digital signatures, code-based cryptography, post-quantum cryptography

Date: received 5 Mar 2021, last revised 18 Mar 2021

Contact author: m baldi at univpm it

Available format(s): PDF | BibTeX Citation

Version: 20210318:080114 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]