Welcome to the resource topic for 2024/495
Title:
Reducing Signature Size of Matrix-code-based Signature Schemes
Authors: Tung Chou, Ruben Niederhagen, Lars Ran, Simona Samardjiska
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 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.
ePrint: https://eprint.iacr.org/2024/495
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .