Cryptology ePrint Archive: Report 2020/1255
Boolean Ring Cryptographic Equation Solving
Sean Murphy and Maura Paterson and Christine Swart
Abstract: This paper considers multivariate polynomial equation systems over GF(2) that have a small number of solutions. This paper gives a new method EGHAM2 for solving such systems of equations that uses the properties of the Boolean quotient ring to potentially reduce memory and time complexity relative to existing XL-type or Groebner basis algorithms applied in this setting. This paper also establishes a direct connection between solving such a multivariate polynomial equation system over GF(2), an MQ problem, and an instance of the LPN problem.
Category / Keywords: MQ problem, XL algorithm, Groebner basis, Boolean ring, LPN problem.
Original Publication (in the same form): to appear in SAC2020
Date: received 9 Oct 2020, last revised 25 Nov 2020
Contact author: s murphy at rhul ac uk
Available format(s): PDF | BibTeX Citation
Version: 20201125:101249 (All versions of this report)
Short URL: ia.cr/2020/1255
[ Cryptology ePrint archive ]