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 :)

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

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 circuit_complexity@nist.gov.

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    

Additional Pages

List of circuits References

Contacts

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

René Peralta

Meltem Sönmez Turan

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

Morris Dworkin

Topics

Security and Privacy: cryptography

Technologies: circuits, complexity

Created December 29, 2016, Updated September 15, 2022