Open AccessAn algorithm for solving over-determined multivariate quadratic systems over finite fields
Author(s) -
Lih-Chung Wang,
Tzer-jen Wei,
Jian-Ming Shih,
Yuh-Hua Hu,
Chih-Cheng Hsieh
Publication year - 2024
Publication title -
advances in mathematics of communications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.601
H-Index - 26
eISSN - 1930-5346
pISSN - 1930-5338
DOI - 10.3934/amc.2022001
Subject(s) - multivariate statistics , mathematics , cryptosystem , quadratic equation , finite field , algorithm , cryptography , discrete mathematics , statistics , geometry
An algorithm for solving over-determined multivariate quadratic systems over finite fields is given. It is more efficient than other known algorithms over finite fields of relatively large size in terms of both performance and memory comsumption. It is also simpler for computer programming. The complexity estimate of our algorithm can be used to estimate the security level of multivariate cryptosystems by solving the multivariate quadratic systems induced by the cryptosystems.