Paper 2017/194

Improved upper bounds for the expected circuit complexity of dense systems of linear equations over GF(2)

Andrea Visconti, Chiara Valentina Schiavo, and René Peralta


Minimizing the Boolean circuit implementation of a given cryptographic function is an important issue. A number of papers [12,13,11,5] only consider cancellation-free straight-line programs for producing short circuits over GF(2) while [4] does not. Boyar-Peralta (BP) heuristic [4] yields a valuable tool for practical applications such as building fast software and low-power circuits for cryptographic applications, e.g. AES [4], PRESENT [7], and GOST [7]. However, BP heuristic does not take into account the matrix density. In a dense linear system the rows can be computed by adding or removing a few elements from a "common path" that is "close" to almost all rows. The new heuristic described in this paper will merge the idea of "cancellation" and "common path". An extensive testing activity has been performed. Experimental results of new and BP heuristic were compared. They show that the Boyar-Peralta bounds are not tight on dense systems.

Available format(s)
Publication info
Published elsewhere. Minor revision.Information Processing Letters, vol.137, pages1-5, 2018
Gate complexitylinear systemsdense matricescircuit depthgate countXOR gates
Contact author(s)
andrea visconti @ unimi it
2022-03-02: last of 2 revisions
2017-02-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andrea Visconti and Chiara Valentina Schiavo and René Peralta},
      title = {Improved upper bounds for the expected circuit complexity of dense systems of linear equations over GF(2)},
      howpublished = {Cryptology ePrint Archive, Paper 2017/194},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.