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

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 $m^2 + n^2$ field elements,while in our new protocol each response consists of only $2k$ ($k$ is usually chosen to be close to $m$ and $n$) field elements. For ALTEQ, each of the responses consists of $n^2$ field elements, while in our new protocol each response consists of about $\sqrt{2} n^{3/2}$ field elements. In both underlying $\Sigma$-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.

Available format(s)
Cryptographic protocols
Publication info
code-based cryptographydigital signature schemespost-quantum cryptography
Contact author(s)
blueprint @ crypto tw
ruben @ polycephaly org
lran @ cs ru nl
simonas @ cs ru nl
2024-04-01: approved
2024-03-28: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.