Semi-Regularity of Pairs of Boolean Polynomials

Timothy J.  Hodges; Hari R.  Iyer

Paper 2020/1585

Semi-Regularity of Pairs of Boolean Polynomials

Timothy J. Hodges and Hari R. Iyer

Abstract

Semi-regular sequences over $F_{2}$ are sequences of homogeneous elements of the algebra $B^{(n)} = F_{2} [X_{1}, . . ., X_{n}] / (X_{1}^{2}, . . ., X_{n}^{2})$ , which have a given Hilbert series and can be thought of as having as few relations between them as possible. It is believed that most such systems are semi-regular and this property has important consequences for understanding the complexity of Grobner basis algorithms such as F4 and F5 for solving such systems. We investigate the case where the sequence has length two and give an almost complete description of the number of semi-regular sequences for each $n$ .

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Keywords: Semi-regular sequence
Contact author(s): timothy hodges @ uc edu
History: 2022-01-10: last of 3 revisions; 2020-12-21: received; See all versions
Short URL: https://ia.cr/2020/1585
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1585,
      author = {Timothy J.  Hodges and Hari R.  Iyer},
      title = {Semi-Regularity of Pairs of Boolean Polynomials},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1585},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1585}
}