### 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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2020/1255

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.