We propose a novel algorithm to solve underdetermined systems of multivariate quadratic (MQ) equations over finite fields. In modern MQ signature schemes such as MAYO, QR-UOV and SNOVA finding solutions to such systems is equivalent to signature forgery. The current benchmark for estimating the forgery bit complexity is Hashimoto’s algorithm which transforms the original underdetermined MQ system P into a more tractable system \(\tilde{P}\) . A hybrid combination of solving \(\tilde{P}\) via Gröbner basis and exhaustive search eventually solves P. We introduce a novel transformation that pushes the hybrid approach to its extreme. Specifically, we reduce the underdetermined MQ system to a sequence of quadratic equations in a single variable at the cost of a larger exhaustive search. As a consequence, signature forgery no longer relies on the hardness of MQ solving but becomes pure guessing via exhaustive search. This in turn implies that signature forgery is significantly more vulnerable against quantum attacks via Grover search. We provide accurate estimates for the classical and quantum bit complexity of forging signatures for MAYO, QR-UOV and SNOVA using our novel algorithm. We reduce the quantum security of all security levels of MAYO, QR-UOV and SNOVA.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Just Guess: Improved (Quantum) Algorithm for the Underdetermined MQ Problem

  • Alexander May,
  • Massimo Ostuzzi,
  • Henrik Ressler

摘要

We propose a novel algorithm to solve underdetermined systems of multivariate quadratic (MQ) equations over finite fields. In modern MQ signature schemes such as MAYO, QR-UOV and SNOVA finding solutions to such systems is equivalent to signature forgery. The current benchmark for estimating the forgery bit complexity is Hashimoto’s algorithm which transforms the original underdetermined MQ system P into a more tractable system \(\tilde{P}\) . A hybrid combination of solving \(\tilde{P}\) via Gröbner basis and exhaustive search eventually solves P. We introduce a novel transformation that pushes the hybrid approach to its extreme. Specifically, we reduce the underdetermined MQ system to a sequence of quadratic equations in a single variable at the cost of a larger exhaustive search. As a consequence, signature forgery no longer relies on the hardness of MQ solving but becomes pure guessing via exhaustive search. This in turn implies that signature forgery is significantly more vulnerable against quantum attacks via Grover search. We provide accurate estimates for the classical and quantum bit complexity of forging signatures for MAYO, QR-UOV and SNOVA using our novel algorithm. We reduce the quantum security of all security levels of MAYO, QR-UOV and SNOVA.