Paper 2020/1255

Boolean Ring Cryptographic Equation Solving

Sean Murphy, 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. to appear in SAC2020
Keywords
MQ problemXL algorithmGroebner basisBoolean ringLPN problem.
Contact author(s)
s murphy @ rhul ac uk
History
2020-11-25: revised
2020-10-14: received
See all versions
Short URL
https://ia.cr/2020/1255
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1255,
      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{https://eprint.iacr.org/2020/1255}},
      url = {https://eprint.iacr.org/2020/1255}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.