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

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

The AES Circuits repository on GitHub is more comprehensive and updated more frequently.

AES S-Box circuits added in 2026

The following are selected examples of AES circuits over the basis {AND, XOR, XNOR}. Metrics of interest: A (#AND), AD (AND depth), G (#Gates), GD (Gate depth). In one table, "Tuple Metric" (1st column) indicates a sequence of metrics for which the referenced circuit is a good representative (within the scope of the table's range). Note that any Sbox/Ax/ADy can be converted into invsbox/Ax/ADy (and vice-versa) via affine transformation, whose added depth and #gates can often be improved thereafter.

The circuits posted since 2026 were obtained via computational search assisted by reasoning models.  Most referenced circuits can be superseded by further compute focus.  However, instead of "easy" small increments, we'd prefer external contributions on the following (over AND, XOR, XNOR): 

  • S-Box and Inverse S-Box: A<=27;  G<=100;  G<=120/GD<=12.
  • MixColumns: G<=86;  G<=93/GD3.
  • Inverse MixColumns: G<=105/GD<=5.

#AND ≤ 34

Tuple
Metric		 Link #AND
(A)		 AND depth
(AD)		 #Gates
(G)		 Gate depth
(GD)		 #XOR +
#XNOR
A/AD/G circ 28 4 131 32 103
A/AD/GD circ 28 4 177 14 149
A/G circ 28 5 124 27 96
G/A circ 32 5 110 22 78
G/AD circ 33 4 110 20 77

The circuits with #AND=28 are contributions or derivations from contributions by Milad Nasr (@ Antropic, 2026-Sep-24)

#AND ≥ 35 (various depths)

Link #AND
(A)		 AND depth
(AD)		 #Gates
(G)		 Gate depth
(GD)		 #XOR +
#XNOR

circ

35

3

157

15

122

circ

36

4

137

14

102

circ

38

4

148

13

110

circ

45

4

151

12

106

circ

51

4

157

11

106

The circuit A35/AD3 was contributed by by Milad Nasr (@ Antropic, 2026-Sep-24)

AES S-Box circuits added prior to 2020

AES S-Boxes Links #ANDs

AND depth

 #Gates Depth #XOR + #XNOR
S-Box 1 SLP, Graph 32 6 115 28 83
S-Box 2 SLP 32 6 113 27 81
S-Box 3 SLP, Graph 34 4 128 16 94
S-Box inverse 1 SLP 34 4 121 21 87
S-Box inverse 2 SLP, Graph 34 4 127 16 93
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).

AES MixColumns (and inverse) added in 2026

MixColumns

Link Depth #XOR
circ 3 97
circ 4 90
circ 5 88

Inverse MixColumns

Link Depth #XOR
circ 5 121
circ 6 107
circ 7 102
circ 8 96
circ 9 95
circ 15 91

 

 

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

A linear map can be represented as a binary matrix, where each entry is a 0 or 1. Each row of the matrix represents an output bit of the linear map; each column corresponds to an input element. If the element M_{i,j} (i.e., in the i-th row and the j-th column) is a 1, then than means that the i-th output of the linear map includes a contribution from the j-th input.

The following tables contain references to circuits of diverse linear maps, including those used in some known ciphers, and various other MDS matrices.

Note: This is part of ongoing research about circuit optimization. The inclusion of a circuit below does not imply that it is the best currently known for the linear map. The referenced results will be sporadically updated with better circuits and possible update of references. Please send any comments to [email protected].

Legend:

  • Name: when it is the name of a cipher, it means that it is a linear system used within the cipher; otherwise it is based on an acronym of the authors of a corresponding paper.
  • MDS: maximum distance separable
  • [ref] in front of name: reference to the specification of the linear map
  • d-XOR: number of XOR’s required by a trivial implementation that computes each output independently. This is equal to the number of 1’s in the matrix, minus the number of row that contain at least one 1.
  • [ref] for an external circuit: reference to some work that achieves a circuit with the mentioned characteristics #XOR
  • #XORs: number of XORs in the circuit stored in this repository.
  • Depth: depth of the circuit stored in the repository
  • Circ* (under "External result"): although the circuits spec was externally obtained, the file was recompiled by us with additional metadata

Ciphers-16x16

Linear system External result Our result
Name Spec File D-XOR Paper Repo #XOR Depth Circ* #XOR Depth Circ
Fides+Midori+Mantis Paper *.mat.txt 32 Paper Ref 24     24 3 *.circ.txt
Joltik Paper *.mat.txt 72 Paper Ref 44 7 *.circ.txt 47    
PrideL0 Paper *.mat.txt 32 Paper Ref 24     24 4 *.circ.txt
PrinceM0 Paper *.mat.txt 32 Paper Ref 24     24 4 *.circ.txt
Qarma128 Paper *.mat.txt 64 Paper Ref 48     48 6 *.circ.txt
Qarma64 Paper *.mat.txt 32 Paper Ref 24     24 8 *.circ.txt
Skinny Paper *.mat.txt 16 Paper Ref 12     12 2 *.circ.txt
SmallScaleAES Paper *.mat.txt 72 Paper Ref 43 5 *.circ.txt 46    

Ciphers-32x32

Linear system External result Our result
Name Spec File D-XOR Paper Repo #XOR Depth Circ* #XOR Depth Circ
Anubis+ClefiaM0 Paper *.mat.txt 184 Paper Ref 98 9 *.circ.txt 103    
ClefiaM1 Paper *.mat.txt 208 Paper Ref 103 10 *.circ.txt 108    
FoxMu4 Paper *.mat.txt 219 Paper   131     130 13 *.circ.txt
Square+AES+Mugi Paper *.mat.txt 152 Paper   92 6 *.circ.txt 94    
Twofish Paper *.mat.txt 327 Paper Ref 111 8 *.circ.txt 121    
WhirlwindM0 Paper *.mat.txt 488 Paper Ref 183 14 *.circ.txt 185    
WhirlwindM1 Paper *.mat.txt 536 Paper Ref 190     187 16 *.circ.txt

Ciphers-64x64

Linear system External result Our result
Name Spec File D-XOR Paper Repo #XOR Depth Circ* #XOR Depth Circ
FoxMu8 Paper *.mat.txt 1257 Paper   592     540 14 *.circ.txt
Grostl Paper *.mat.txt 1112 Paper   460     410 12 *.circ.txt
Khazad Paper *.mat.txt 1232 Paper Ref 366 18 *.circ.txt 475    
Whirlpool+Maelstrom Paper *.mat.txt 840 Paper   464     425 11 *.circ.txt

Ciphers-128x128

Linear system External result Our result
Name Spec File D-XOR Paper Repo #XOR Depth Circ* #XOR Depth Circ
Aria Paper *.mat.txt 768 Paper   392     387 7 *.circ.txt

mds-4x4-GF16

Linear system External result Our result
Name Spec File D-XOR Paper Repo #XOR Depth Circ* #XOR Depth Circ
BKL16-4x4-GF16 Paper *.mat.txt 64 Paper Ref 41     41 5 *.circ.txt
JPST17-4x4-GF16 Paper *.mat.txt 61 Paper Ref 41     40 6 *.circ.txt
KLSW17-M-4x4-GF16 Paper *.mat.txt 92 Paper Ref 36     36 8 *.circ.txt
LS16-4x4-GF16 Paper *.mat.txt 60 Paper Ref 44     44 4 *.circ.txt
LW16-4x4-GF16 Paper *.mat.txt 60 Paper Ref 44     44 4 *.circ.txt
SKOP15-4x4-GF16 Paper *.mat.txt 68 Paper Ref 44 7 *.circ.txt 46    
SS16-4x4-GF16 Paper *.mat.txt 58 Paper Ref 41     41 5 *.circ.txt
JPST17-4x4-GF16-inv Paper *.mat.txt 68 Paper Ref 41 6 *.circ.txt 43    
LW16-4x4-GF16-inv Paper *.mat.txt 72 Paper Ref 44 6 *.circ.txt 45    
SKOP15-4x4-GF16-inv Paper *.mat.txt 72 Paper Ref 44 8 *.circ.txt 46    
SS16-4x4-GF16-inv Paper *.mat.txt 64 Paper Ref 38     38 6 *.circ.txt

mds-8x8-GF16

Linear system External result Our result
Name Spec File D-XOR Paper Repo #XOR Depth Circ* #XOR Depth Circ
KLSW17-M-8x8-GF16-0x13 Paper *.mat.txt 456 Paper Ref 196     175 12 *.circ.txt
SKOP15-8x8-GF16 Paper *.mat.txt 432 Paper Ref 170 19 *.circ.txt 173    
SS17-8x8-GF16 Paper *.mat.txt 394 Paper Ref 182     178 10 *.circ.txt
KLSW17-M-8X8-GF16-0x13-inv Paper *.mat.txt 540 Paper Ref 212     176 12 *.circ.txt
SKOP15-8x8-GF16-inv Paper *.mat.txt 512 Paper Ref 185     180 12 *.circ.txt

mds-4x4-GF256

Linear system External result Our result
Name Spec File D-XOR Paper Repo #XOR Depth Circ* #XOR Depth Circ
BKL16-4x4-GF256 Paper *.mat.txt 136 Paper   108     107 6 *.circ.txt
JPST17-4x4-GF256 Paper *.mat.txt 122 Paper Ref 82 7 *.circ.txt 83    
KLSW17-M-4x4-GF256 Paper *.mat.txt 184 Paper Ref 72     72 7 *.circ.txt
LS16-4x4-GF256 Paper *.mat.txt 128 Paper   110     109 5 *.circ.txt
LW16-4x4-GF256 Paper *.mat.txt 106 Paper Ref 102     100 6 *.circ.txt
SKOP15-4x4-GF256 Paper *.mat.txt 136 Paper Ref 90 6 *.circ.txt 95    
SS16-4x4-GF256 Paper *.mat.txt 123 Paper   104   *.circ.txt 100 6  
JPST17-4x4-GF256-inv Paper *.mat.txt 136 Paper Ref 83 6 *.circ.txt 90    
KLSW17-M-4x4-GF256-inv Paper *.mat.txt 128 Paper Ref 84     78 5 *.circ.txt
LW16-4x4-GF256-inv-circ Paper *.mat.txt 132 Paper   97     89 7 *.circ.txt
LW16-4x4-GF256-inv-had Paper *.mat.txt 136 Paper Ref 87     87 5 *.circ.txt
SKOP15-4x4-GF256-inv Paper *.mat.txt 144 Paper Ref 91 6 *.circ.txt 95    
SS16-4x4-GF256-inv Paper *.mat.txt 160 Paper Ref 93 8   100   *.circ.txt

mds-8x8-GF256

Linear system External result Our result
Name Spec File D-XOR Paper Repo #XOR Depth Circ* #XOR Depth Circ
BKL16-8x8-GF256 Paper *.mat.txt 784 Paper   497     465 10 *.circ.txt
KLSW17-M-8x8-GF256 Paper *.mat.txt 912 Paper Ref 392     364 11 *.circ.txt
LS16-8x8-GF256 Paper *.mat.txt 688 Paper   443     427 9 *.circ.txt
SKOP15-8x8-GF256 Paper *.mat.txt 768 Paper   460     445 8 *.circ.txt
SS17-8x8-GF256 Paper *.mat.txt 680 Paper   436     418 9 *.circ.txt
JPST17-8x8-GF256-inv Paper *.mat.txt 1152 Paper   591     528 11 *.circ.txt
KLSW17-M-8x8-GF256-inv Paper *.mat.txt 1080 Paper Ref 424     368 12 *.circ.txt
SKOP15-8x8-GF256-inv Paper *.mat.txt 816 Paper Ref 348 13 *.circ.txt 397    

There are additional files showcasing the algebraic normal form (ANF) of some polynomials over GF(2):

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

Boolean ANF for polynomials over GF(2), modulo 1+x+x3+x4:

Abbreviation Link # inputs # outputs Description
inversion ANF-GF2^4-inv.txt 4 4 Inversion of an element over GF2^4
mod ANF-GF2^4-mod-of-GF2^8.txt 8 4 Reducing modulo GF2^4 an element from GF2^8
mult2 ANF-GF2^4-mult2.txt 8 4 Multiplying two polynomials over GF(2^4)
mult3 ANF-GF2^4-mult3.txt 12 4 Multiplying three polynomials over GF(2^4)
mult4 ANF-GF2^4-mult4.txt 16 4 Multiplying four polynomials over GF(2^4)

Boolean ANF for polynomials over GF(2), modulo 1+x+x3+x4+x8:

Abbreviation Link # inputs # outputs Description
inv ANF-GF2^8-inv.txt 8 8 Inversion of an element over GF2^8
mult2 ANF-GF2^8-mult2.txt 16 8 Multiplying two polynomials over GF(2^8)
mult2 ANF-GF2^8-mult3.txt 24 8 Multiplying three polynomials over GF(2^8)

Additional Pages

List of circuits References

Contacts

Reach the Circuit Complexity team at:
[email protected]

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 October 15, 2026