Paper 2020/1255

Boolean Ring Cryptographic Equation Solving

Sean Murphy, Maura Paterson, and Christine Swart


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.

Available format(s)
Publication info
Published elsewhere. to appear in SAC2020
MQ problemXL algorithmGroebner basisBoolean ringLPN problem.
Contact author(s)
s murphy @ rhul ac uk
2020-11-25: revised
2020-10-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sean Murphy and Maura Paterson and Christine Swart},
      title = {Boolean Ring Cryptographic Equation Solving},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1255},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.