You are looking at a specific version 20201125:101249 of this paper.
See the latest version.
Paper 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.
Metadata
- 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
- 2020-10-14: received
- See all versions
- Short URL
- https://ia.cr/2020/1255
- License
-
CC BY