U.S. flag   An unofficial archive of your favorite United States government website
Dot gov

Official websites do not use .rip
We are an unofficial archive, replace .rip by .gov in the URL to access the official website. Access our document index here.

Https

We are building a provable archive!
A lock (Dot gov) or https:// don't prove our archive is authentic, only that you securely accessed it. Note that we are working to fix that :)

Computer Security Resource Center

Computer Security Resource Center

This is an archive
(replace .gov by .rip)
    Projects Circuit Complexity

Circuit Complexity

List of circuits

 The circuit files with the straight-line programs (SLPs) are stored in our GitHub page, here:

https://github.com/usnistgov/Circuits/tree/master/data/slp

AES S-Boxes Links #ANDs #XOR + #XNOR #Gates Depth AND-Depth
S-Box 1 SLP, Graph 32 83 115 28 6
S-Box 2 SLP 32 81 113 27 6
S-Box 3 SLP, Graph 34 94 128 16 4
S-Box inverse 1 SLP 34 87 121 21 4
S-Box inverse 2 SLP, Graph 34 93 127 16 4

 

AES Cipher Links #ANDs #XNOR #XOR #Gates Depth AND-Depth
AES-128(k,m) SLP 6400 844 21 356 28 600 326 60
AES-128(0,m) SLP 5120 1620 14 652 21 392 325 60

The AES circuit above is constructed using: (i) the S-Box implementation “forward 2” (doi:10.1007/s00145-012-9124-7 further improved in 2013 by 2 XORs); and (ii) the MixColumn circuit by Maximov in 2019 (ia.cr/2019/833).

SHA256 Links #AND #NOT #XNOR #XOR #Gates Depth AND-Depth
SHA256 (input 512) SLP 22 385 355 3894 89 248 115 882 5403 1604
SHA256 (iv256+input512) SLP 22 632 13 2840 92 802 118 287 5458 1607
Multiplication in field Links #ANDs #XORs #Gates Depth
GF(26) mod x6 + x3 + 1 SLP, Graph 27 30 57 5
GF(27) mod x7 + x3 + 1 SLP, Graph 40 45 85 5
GF(27) mod x7 + x4 + 1 SLP, Graph 40 44 84 5
GF(28) mod x8 + x4 + x3 + x + 1 SLP 48 69 117 6

Circuits for multiplying two n-terms (degree n-1) polynomials.

#Terms (n) Links #ANDs #XORs #Gates Depth AND-Depth
11 SLP, Graph 78 108 186 7 1
12 SLP, Graph 81 126 207 7 1
15 SLP 117 195 312 9 1
16 SLP, Graph 144 205 349 8 1
18 SLP, Graph 195 259 454 8 1
19 SLP, Graph 214 284 498 8 1
20 SLP, Graph 225 302 527 8 1

Bn is the set of all boolean functions on n-variables.

MaxMC is the maximum of the MCs of all functions in a class.

Bn Links MaxMC #Classes
B4 SLPs of All predicates 3 8
B5 (see B6) 4 48
B6 SLPs of representatives of all classes, Paper (ia.cr/2018/002) 6 150367

Additional Pages

List of circuits References

Contacts

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

René Peralta

Luís T. A. N. Brandão

Morris Dworkin

Meltem Sönmez Turan

Topics

Security and Privacy: cryptography

Technologies: circuits, complexity

Created December 29, 2016, Updated November 08, 2021