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

Minimizing the Boolean circuit implementation of a given cryptographic function is an important issue. A number of papers [1], [2], [3], [4] only consider cancellation-free straight-line programs for producing small circuits over GF(2). Cancellation is allowed by the Boyar-Peralta ( ) heuristic [5, 6].