Gate elimination for linear functions and new feebly secure constructions

DOI10.1007/978-3-642-20712-9_12MaRDI QIDQ3007624zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Alex Davydow, Sergey Nikolenko

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 complexityfeebly one-way functionsfeebly secure cryptographygate elimination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Recommendations

• Circuit complexity of linear functions: gate elimination and feeble security
• On the limits of gate elimination
• On the limits of gate elimination
• Feebly secure cryptographic primitives
• A Feebly Secure Trapdoor Function

Cites work

• A 2.5n-Lower Bound on the Combinational Complexity of Boolean Functions
• A Boolean function requiring 3n network size
• A Complete Public-Key Cryptosystem
• A Feebly Secure Trapdoor Function
• A method for obtaining digital signatures and public-key cryptosystems
• Another look at ``provable security
• Communication Theory of Secrecy Systems*
• Decomposition of graphs and monotone formula size of homogeneous functions
• Feebly secure cryptographic primitives
• Foundations of Cryptography
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 3607492 (Why is no real title available?)
• scientific article; zbMATH DE number 1024027 (Why is no real title available?)
• scientific article; zbMATH DE number 1559544 (Why is no real title available?)
• scientific article; zbMATH DE number 1361466 (Why is no real title available?)
• Lattice-Based Cryptography
• Linear Circuits over $\operatorname{GF}(2)$
• New combinatorial complete one-way functions
• New directions in cryptography
• On lattices, learning with errors, random linear codes, and cryptography
• On Robust Combiners for Oblivious Transfer and Other Primitives
• On the combinational complexity of certain symmetric Boolean functions

Cited in

(3)

• Feebly secure cryptographic primitives
• Circuit complexity of linear functions: gate elimination and feeble security
• A Feebly Secure Trapdoor Function

This page was built for publication: Gate elimination for linear functions and new feebly secure constructions

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