1970-01-01

(2026-02) Improved preprocessing for the Crossbred algorithm and application to the MQ problem

• [[Damien Vidal]]
• [[Claire Delaplace]]
• [[Sorina Ionica]]

2026-02-22

• #cryptography
• #paper

Abstract

First, we correct certain omissions in the literature on the complexity analysis of Crossbred and give a full analysis of this algorithm. Secondly, we propose a criterion to reduce the number of polynomials generated in the preprocessing step for a set of admissible parameters $D$, $d$ and $k$, whenever this step of the algorithm produces more polynomials than necessary. We conclude by applying this criterion to the security of MQOM.