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.

Projects Circuit Complexity

Circuit Complexity

Publications

The following NIST-authored publications are directly related to this project.

Series & Number Title Status Released
Conference Paper New Bounds on the Multiplicative Complexity of Boolean Functions Final 09/11/2022
Other On the Multiplicative Complexity of Cubic Boolean Functions Final 08/11/2021
Journal Article Boolean Functions with Multiplicative Complexity 3 and 4 Final 07/18/2020
Journal Article Upper Bounds on the Multiplicative Complexity of Symmetric Boolean Functions Final 08/17/2019
Conference Paper Searching for Best Karatsuba Recurrences Final 06/24/2019
Journal Article Better Circuits for Binary Polynomial Multiplication Final 04/01/2019
Journal Article Improved upper bounds for the expected circuit complexity of dense systems of linear equations over GF(2) Final 09/01/2018
Journal Article The Multiplicative Complexity of 6-variable Boolean Functions Final 04/03/2018
Journal Article Small Low-Depth Circuits for Cryptographic Applications Final 03/24/2018
Conference Paper A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function Final 10/11/2016
Journal Article Separating OR, SUM, and XOR Circuits Final 08/23/2016
Journal Article On Various Nonlinearity Measures for Boolean Functions Final 05/19/2016
Other The Number of Boolean Functions with Multiplicative Complexity 2 Final 10/27/2015
Other Multiplicative Complexity of Vector Value Boolean Functions Final 09/21/2015
Conference Paper Constructive Relationships Between Algebraic Thickness and Normality Final 08/04/2015
Conference Paper The Multiplicative Complexity of Boolean Functions on Four and Five Variables Final 03/17/2015
Conference Paper Four Measures of Nonlinearity Final 06/23/2013
Journal Article Logic Minimization Techniques with Applications to Cryptology Final 04/01/2013
Journal Article On the Nonlinearity of Maximum-length NFSR Feedbacks Final 08/14/2012
Other A depth-16 circuit for the AES S-box Final 06/17/2011
Conference Paper A New Combinational Logic Minimization Technique with Applications to Cryptology Final 05/20/2010
Conference Paper On the Shortest Linear Straight-Line Program for Computing Linear Forms Final 08/29/2008
Journal Article Tight Bounds for the Multiplicative Complexity of Symmetric Functions Final 04/28/2008

Additional Pages

List of circuits References

Contacts

Reach the Circuit Complexity team at:
circuit_complexity@nist.gov

René Peralta - NIST

Meltem Sönmez Turan - NIST

Luís T. A. N. Brandão - NIST/Strativia

Topics

Security and Privacy: cryptography

Technologies: circuits, complexity

Created December 29, 2016, Updated February 01, 2024