Skip to main content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.


The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

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



Andrea Visconti, Chiara V. Schiavo, Rene C. Peralta


Minimizing the Boolean circuit implementation of a given cryptographic function is an important issue. A number of papers only consider cancellation-free straight-line programs for producing short circuits over GF(2). The Boyar-Peralta (BP) heuristic yields a valuable tool for practical applications such as building fast software and low-power circuits for cryptographic applications, e.g. AES, HMAC-SHA-1, PRESENT, GOST, and so on. However, the 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 ideas of "cancellation" and "common path". An extensive testing activity has been performed. Experimental results of the new and the BP heuristic were compared. They show that the Boyar-Peralta bounds are not tight on dense systems.
Information Processing Letters


Gate complexity, linear systems, dense matrices, circuit depth, XOR gates.
Created April 21, 2018, Updated November 10, 2018