Reducing Signature Size of Matrix-code-based Signature Schemes

Tung Chou; Ruben Niederhagen; Lars Ran; Simona Samardjiska

Paper 2024/495

Reducing Signature Size of Matrix-code-based Signature Schemes

Tung Chou, Academia Sinica, Taipei, Taiwan

Ruben Niederhagen, Academia Sinica, Taipei, Taiwan, University of Southern Denmark, Odense, Denmark

Lars Ran, Radboud University, Nijmegen, Netherlands

Simona Samardjiska, Radboud University, Nijmegen, Netherlands

Abstract

This paper shows novel techniques to reduce the signature size of the code-based signature schemes MEDS and ALTEQ, by a large factor. For both schemes, the signature size is dominated by the responses for rounds with nonzero challenges, and we reduce the signature size by reducing the size of these responses. For MEDS, each of the responses consists of field elements,while in our new protocol each response consists of only ( is usually chosen to be close to and ) field elements. For ALTEQ, each of the responses consists of field elements, while in our new protocol each response consists of about field elements. In both underlying -protocols of the schemes, the prover generates a random isometry and sends the corresponding isometry to the verifier as the response. Instead of doing this, in our new protocols, the prover derives an isometry from some random code words and their presumed (full or partial) images. The prover sends the corresponding code words and images to the verifier as the response, so that the verifier can derive an isometry in the same way. Interestingly, it turns out that each response takes much fewer field elements to represent in this way.

Note: The final publication is available at Springer via https://doi.org/10.1007/978-3-031-62743-9_4

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Minor revision. PQCrypto 2024
DOI: 10.1007/978-3-031-62743-9_4
Keywords: code-based cryptography digital signature schemes post-quantum cryptography
Contact author(s): blueprint @ crypto tw
ruben @ polycephaly org
lran @ cs ru nl
simonas @ cs ru nl
History: 2024-07-03: revised; 2024-03-28: received; See all versions
Short URL: https://ia.cr/2024/495
License: CC BY

BibTeX

@misc{cryptoeprint:2024/495,
      author = {Tung Chou and Ruben Niederhagen and Lars Ran and Simona Samardjiska},
      title = {Reducing Signature Size of Matrix-code-based Signature Schemes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/495},
      year = {2024},
      doi = {10.1007/978-3-031-62743-9_4},
      url = {https://eprint.iacr.org/2024/495}
}