MQ-Sign-LR cryptanalysis
62 views
Skip to first unread message
Lars Ran
Nov 26, 2024, 9:33:41 AM11/26/24
to KpqC-bulletin
Dear all,
We would like to share with you our analysis of the MQ-Sign-LR variant that is for consideration in the second round of the KpqC competition. In this analysis we found a way to practically sign messages for a fraction of the message space without knowing the secret key. Furthermore we found this to be a sliding scale where more computing power leads to a bigger fraction of messages that can be signed.
For example, we found that, for security Level I, one in 2^224 messages could be signed in just 32 hours and one in 2^80 messages in (at most) 2^112 operations. In fact, by trying multiple salts this technique can be extended to sign any message in 2^112 operations.
Altogether, these findings lead to a universal forgery attack on the MQ-Sign-LR variant. For more details check out our paper:
https://eprint.iacr.org/2024/1891
Kind regards,
Monika Trimoska and Lars Ran
We would like to share with you our analysis of the MQ-Sign-LR variant that is for consideration in the second round of the KpqC competition. In this analysis we found a way to practically sign messages for a fraction of the message space without knowing the secret key. Furthermore we found this to be a sliding scale where more computing power leads to a bigger fraction of messages that can be signed.
For example, we found that, for security Level I, one in 2^224 messages could be signed in just 32 hours and one in 2^80 messages in (at most) 2^112 operations. In fact, by trying multiple salts this technique can be extended to sign any message in 2^112 operations.
Altogether, these findings lead to a universal forgery attack on the MQ-Sign-LR variant. For more details check out our paper:
https://eprint.iacr.org/2024/1891
Kind regards,
Monika Trimoska and Lars Ran
Reply all
Reply to author
Forward
0 new messages