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.


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

This is an archive
(replace .gov by .rip)

Circuit Complexity


Peer reviewed publications: 




  • Ç. Çalık, M. Dworkin, N. Dykas, and R. Peralta. Searching for Best Karatsuba Recurrences. Analysis of Experimental Algorithms (SEA 2019), LNCS vol. 11544, pp 332-342, Springer International Publishing, 2019. DOI: 10.1007/978-3-030-34029-2_22. Preprint available at NIST.

  • L.T.A.N. Brandão, Ç. Çalık, M. Sönmez Turan, and R. Peralta. Upper bounds on the multiplicative complexity of symmetric Boolean functions. Cryptography and Communications, vol. 11, pp. 1339–1362 (2019). DOI: 10.1007/s12095-019-00377-3. Also at ia.cr/2019/708


  • Ç. Çalık, M. Sönmez Turan, and R. Peralta, The multiplicative complexity of 6-variable Boolean functions. Cryptography and Communications. Special Issue on Boolean Functions and Their Applications, pp. 1–15, 2018. doi:10.1007/s12095-018-0297-2. Also at ia.cr/2018/002

  • A. Visconti, C.V. Schiavo, R. Peralta. Improved upper bounds for the expected circuit complexity of dense systems of linear equations over GF(2). Information Processing Letters. Vol. 137, Sep. 2018, Pages 1-5. doi:10.1016/j.ipl.2018.04.010. Copy available at NIH.


  • M. Gausdal Find, Daniel Smith-Tone, M. Sönmez Turan. The number of boolean functions with multiplicative complexity 2. IJICoT 4(4): 222-236 (2017). doi:10.5555/3150183.3150185. Also at ia.cr/2015/1041


  • M. Gausdal Find, A. Golovnev, E. A. Hirsch, A. S. Kulikov. A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. Foundations of Computer Science, FOCS 2016. doi:10.1109/FOCS.2016.19


  • M. Sönmez Turan and R. Peralta, The Multiplicative Complexity of Boolean Functions on Four and Five Variables. In Proc. 3rd International Workshop on Lightweight Cryptography for Security and Privacy — LightSec 2014(T. Eisenbarth and E. Öztürk, eds.), vol. 8898 of LNCS, pp. 21–33, Springer, 2015. doi:10.1007/978-3-319-16363-5_2. Also at ia.cr/2015/848


  • J. Boyar, P. Matthews, and R. Peralta. Logic Minimization Techniques with Applications to Cryptology. Journal of Cryptology, vol. 26, pp. 280–312 (2013). doi:10.1007/s00145-012-9124-7


  • J. Boyar and R. Peralta, Tight bounds for the multiplicative complexity of symmetric functions. Theoretical Computer Science, vol. 396, no. 1-3, pp. 223–246, 2008. doi:10.1016/j.tcs.2008.01.030. Copy available at NIST.


  • J. Boyar, R. Peralta, and D. Pochuev, On the multiplicative complexity of Boolean functions over the basis (∧,⊕,1). Theoretical Computer Science, vol. 235, no. 1, pp. 43 – 57, 2000. doi:10.1016/S0304-3975(99)00182-6 


Other links: 

  • Circuit complexity team at the Cryptographic Technology Group, NIST. Circuits for functions of interest to cryptography. GitHub:usnistgov/Circuits, 2019.

Additional Pages

List of circuits References


Reach the Circuit Complexity team at:

René Peralta

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

Morris Dworkin

Meltem Sönmez Turan


Security and Privacy: cryptography

Technologies: circuits, complexity

Created December 29, 2016, Updated November 08, 2021