NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.
Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.
An official website of the United States government
Here’s how you know
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
Improved upper bounds for the expected circuit complexity of dense systems of linear equations over GF(2)
Published
Author(s)
Andrea Visconti, Chiara V. Schiavo, Rene Peralta
Abstract
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.
Visconti, A.
, Schiavo, C.
and Peralta, R.
(2018),
Improved upper bounds for the expected circuit complexity of dense systems of linear equations over GF(2), Information Processing Letters, [online], https://doi.org/10.1016/j.ipl.2018.04.010, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=925478
(Accessed October 9, 2025)