U.S. flag   An official website of the United States government
Dot gov

Official websites use .gov
A .gov website belongs to an official government organization in the United States.


Secure .gov websites use HTTPS
A lock (Dot gov) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Circuit Complexity



  • 2022: M. Sönmez Turan. New Bounds on the Multiplicative Complexity of Boolean Functions. 7th International Workshop on Boolean Functions and their Applications (BFA). Also at https://ia.cr/2022/1077
  • 2021: M. Sönmez Turan, and R. Peralta, On the Multiplicative Complexity of Cubic Boolean Functions. https://ia.cr/2021/1041
  • 2020: Çalık, Ç., Turan, M.S. & Peralta, R. Boolean functions with multiplicative complexity 3 and 4. Cryptogr. Commun. 12, 935–946 (2020). DOI: 10.1007/s12095-020-00445-z. Also at ia.cr/2019/1364
  • 2019: Ç. Ç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.
  • 2019: 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
  • 2018: Ç. Ç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
  • 2018: 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.
  • 2017: 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
  • 2016: 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
  • 2014: 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
  • 2013: 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
  • 2008: 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.
  • 2000: 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 - NIST

Meltem Sönmez Turan - NIST

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


Security and Privacy: cryptography

Technologies: circuits, complexity

Created December 29, 2016, Updated February 24, 2023