Boolean Ring Cryptographic Equation Solving. / Murphy, Sean; Paterson, Maura; Swart, Christine.

Springer, 2020. p. 252-272 (LNCS).

Research output: Working paper

Published

Documents

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.
Original languageEnglish
PublisherSpringer
Pages252-272
Number of pages21
Volume12804
Publication statusPublished - 18 Sep 2020

Publication series

NameLNCS
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 38885797