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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
public-key cryptographydigital signaturescode-based cryptographypost-quantum cryptography
Contact author(s)
m baldi @ univpm it
History
2021-03-18: revised
2021-03-07: received
See all versions
Short URL
https://ia.cr/2021/294
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/294,
      author = {Marco Baldi and Franco Chiaraluce and Paolo Santini},
      title = {Code-based signatures without trapdoors through restricted vectors},
      howpublished = {Cryptology ePrint Archive, Paper 2021/294},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/294}},
      url = {https://eprint.iacr.org/2021/294}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.