Tight bounds for the multiplicative complexity of symmetric functions

DOI10.1016/j.tcs.2008.01.030zbMath1145.68015OpenAlexW2007233204WikidataQ62472218 ScholiaQ62472218MaRDI QIDQ924152

René Peralta, Joan. Boyar

Publication date: 28 May 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.01.030

zbMATH Keywords

symmetric functionscircuit complexitymultiplicative complexitymulti-party computationcryptographic proofs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Related Items (7)

On various nonlinearity measures for Boolean functions ⋮ Logic minimization techniques with applications to cryptology ⋮ Upper bounds on the multiplicative complexity of symmetric Boolean functions ⋮ Multiplicative complexity of vector valued Boolean functions ⋮ The multiplicative complexity of 6-variable Boolean functions ⋮ Multiplicative complexity of bijective \(4\times 4\) \(S\)-boxes ⋮ On the decision tree complexity of threshold functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A discrete logarithm implementation of perfect zero-knowledge blobs
• Minimum disclosure proofs of knowledge
• The multiplicative complexity of quadratic boolean forms
• On the communication complexity of zero-knowledge proofs
• Short non-interactive cryptographic proofs
• On the multiplicative complexity of Boolean functions over the basis (\(\land,\oplus,1)\).
• On the combinational complexity of certain symmetric Boolean functions
• Upper Bounds on the Communication Complexity of Optimally Resilient Cryptographic Multiparty Computation

This page was built for publication: Tight bounds for the multiplicative complexity of symmetric functions