Upper bounds on the multiplicative complexity of symmetric Boolean functions

DOI10.1007/S12095-019-00377-3MaRDI QIDQ2179499zbMATH OpenOpenAlexWikidataFDO

Authors Luís T. A. N. Brandão, Çağdaş Çalık, Meltem Sönmez Turan, René Peralta

Publication date 12 May 2020

Published in Cryptography and Communications (Search for Journal in Brave)

Full work available at URL http://europepmc.org/articles/pmc7047778

zbMATH Keywords

logic minimizationmultiplicative complexitysymmetric Boolean functionsupper bounds

Mathematics Subject Classification ID

Boolean functions (06E30) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Boolean functions (94D10)

Recommendations

• Lower bounds to the complexity of symmetric Boolean functions
• New upper bounds on the Boolean circuit complexity of symmetric functions
• Tight bounds for the multiplicative complexity of symmetric functions
• Upper bounds for the complexity of sequences generated by symmetric Boolean functions
• Upper bounds for the formula size of symmetric Boolean functions
• On the multiplicative complexity of Boolean functions
• scientific article; zbMATH DE number 4035741
• On the multiplicative complexity of some Boolean functions
• On the combinational complexity of certain symmetric Boolean functions
• scientific article; zbMATH DE number 4108153

Cites work

• (Leveled) fully homomorphic encryption without bootstrapping
• Bounds to Complexities of Networks for Sorting and for Switching
• Higher-order masking schemes for S-boxes
• scientific article; zbMATH DE number 4035741 (Why is no real title available?)
• scientific article; zbMATH DE number 4108153 (Why is no real title available?)
• scientific article; zbMATH DE number 1294428 (Why is no real title available?)
• Improved Garbled Circuit: Free XOR Gates and Applications
• On the Complexity of Computing Two Nonlinearity Measures
• On the multiplicative complexity of Boolean functions over the basis (\(\land,\oplus,1)\).
• Optimal 4-bit reversible mixed-polarity Toffoli circuits
• Short non-interactive cryptographic proofs
• Symmetric Boolean Functions
• The multiplicative complexity of 6-variable Boolean functions
• The multiplicative complexity of Boolean functions on four and five variables
• The number of Boolean functions with multiplicative complexity 2
• Tight bounds for the multiplicative complexity of symmetric functions

Cited in

(12)

• On the multiplicative complexity of Boolean functions and bitsliced higher-order masking
• On the multiplicative complexity of Boolean functions over the basis (\(\land,\oplus,1)\).
• Boolean functions with multiplicative complexity 3 and 4
• Upper bounds on the depth of symmetric Boolean functions
• Upper Bounds on Boolean-Width with Applications to Exact Algorithms
• Complexity and depth of formulas for symmetric Boolean functions
• On the combinational complexity of certain symmetric Boolean functions
• scientific article; zbMATH DE number 1285633 (Why is no real title available?)
• Concrete Multiplicative Complexity of Symmetric Functions
• De Bruijn sequences and complexity of symmetric functions
• Tight bounds for the multiplicative complexity of symmetric functions
• New upper bounds on the Boolean circuit complexity of symmetric functions

Describes a project that uses

Uses Software

• Circuits
• GitHub

This page was built for publication: Upper bounds on the multiplicative complexity of symmetric Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2179499)