Circuit complexity of linear functions: gate elimination and feeble security
From MaRDI portal
Publication:1946842
DOI10.1007/s10958-012-1104-9zbMath1262.94022OpenAlexW2006196719WikidataQ57100982 ScholiaQ57100982MaRDI QIDQ1946842
A. P. Davydow, Sergey I. Nikolenko
Publication date: 9 April 2013
Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10958-012-1104-9
Cites Work
- A Boolean function requiring 3n network size
- Another look at ``provable security
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Lower bounds on monotone complexity of the logical permanent
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- One way functions and pseudorandom generators
- Feebly secure cryptographic primitives
- The tale of one-way functions
- Complexity of the realization of a linear function in the class of \(\Pi\)-circuits
- Gate Elimination for Linear Functions and New Feebly Secure Constructions
- Parity, circuits, and the polynomial-time hierarchy
- A Feebly Secure Trapdoor Function
- Linear Circuits over $\operatorname{GF}(2)$
- A Complete Public-Key Cryptosystem
- Communication Theory of Secrecy Systems*
- Languages that Capture Complexity Classes
- Classifying the computational complexity of problems
- 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
- Another Look at “Provable Security”. II
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
