Gate Elimination for Linear Functions and New Feebly Secure Constructions

DOI10.1007/978-3-642-20712-9_12zbMath1332.94064WikidataQ57101095 ScholiaQ57101095MaRDI QIDQ3007624

Sergey I. Nikolenko, Alex Davydow

Publication date: 17 June 2011

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20712-9_12

zbMATH Keywords

circuit complexity; gate elimination; feebly one-way functions; feebly secure cryptography

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

94A60: Cryptography

Related Items

Feebly secure cryptographic primitives, Circuit complexity of linear functions: gate elimination and feeble security

Cites Work

• A Boolean function requiring 3n network size
• Another look at ``provable security
• Decomposition of graphs and monotone formula size of homogeneous functions
• Feebly secure cryptographic primitives
• A Feebly Secure Trapdoor Function
• Linear Circuits over $\operatorname{GF}(2)$
• A Complete Public-Key Cryptosystem
• Communication Theory of Secrecy Systems*
• New directions in cryptography
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• A method for obtaining digital signatures and public-key cryptosystems
• On the combinational complexity of certain symmetric Boolean functions
• Foundations of Cryptography
• On Robust Combiners for Oblivious Transfer and Other Primitives
• Lattice-Based Cryptography
• On lattices, learning with errors, random linear codes, and cryptography
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item