Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)

DOI10.1007/978-3-030-84259-8_17zbMath1489.94089OpenAlexW3189736153MaRDI QIDQ2139645

Peter Scholl, Lisa Kohl, Niv Gilboa, Elette Boyle, Yuval Ishai, Geoffroy Couteau

Publication date: 18 May 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-84259-8_17

zbMATH Keywords

weak pseudorandom functionWPRF by sparse polynomials

Mathematics Subject Classification ID

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

Related Items

On the algebraic immunity of direct sum constructions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• More on average case vs approximation complexity
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• Exploring crypto dark matter: new simple PRF candidates and their applications
• \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
• The rise of Paillier: homomorphic secret sharing and public-key silent OT
• Breaking the circuit size barrier for secure computation under quasi-polynomial LPN
• On PAC learning algorithms for rich Boolean function classes
• Natural Proofs versus Derandomization
• Towards Stream Ciphers for Efficient FHE with Low-Noise Ciphertexts
• Cryptography with Auxiliary Input and Trapdoor from Constant-Noise LPN
• Pseudorandom Functions and Lattices
• Ciphers for MPC and FHE
• Candidate weak pseudorandom functions in AC ⁰ ○ MOD ₂
• New Algorithms for Learning in Presence of Errors
• Candidate One-Way Functions Based on Expander Graphs
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Constant depth circuits, Fourier transform, and learnability
• Number-theoretic constructions of efficient pseudo-random functions
• Fast Pseudorandom Functions Based on Expander Graphs
• Pseudo-random functions and factoring (extended abstract)
• Parity, circuits, and the polynomial-time hierarchy
• On Agnostic Learning of Parities, Monomials, and Halfspaces
• Polylogarithmic independence fools AC ⁰ circuits
• A theory of the learnable
• On the inherent intractability of certain coding problems (Corresp.)
• Cryptographic limitations on learning Boolean formulae and finite automata
• The intractability of computing the minimum distance of a code
• Algebraic Attacks against Random Local Functions and Their Countermeasures
• Stream Ciphers: A Practical Solution for Efficient Homomorphic-Ciphertext Compression
• Hardness of approximating the minimum distance of a linear code
• Pseudorandom Functions: Three Decades Later
• Analysis of Boolean Functions
• Cryptographic hardness of distribution-specific learning
• Learning algorithms from natural proofs
• Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
• Advances in Cryptology - CRYPTO 2003
• Secure Computation of Constant-Depth Circuits with Applications to Database Search Problems
• On ε‐biased generators in NC⁰
• Pseudorandom Functions in Almost Constant Depth from Low-Noise LPN
• The communication complexity of addition
• Natural proofs
• Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs