Structural lower bounds on black-box constructions of pseudorandom functions

DOI10.1007/978-3-031-68388-6_16MaRDI QIDQ6652977zbMATH OpenFDO

Authors Amos Beimel, Tal Malkin, Noam Mazor

Publication date 13 December 2024

Full work available at URL https://doi.org/10.1007/978-3-031-68388-6_16

zbMATH Keywords

black-box complexityoracle separation methodology

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Cryptography (94A60)

Recommendations

• On the complexity of constructing pseudorandom functions (especially when they don't exist)
• Hardness preserving constructions of pseudorandom functions
• Performance improvement for the GGM-construction of pseudorandom functions
• Balancing output length and query bound in hardness preserving constructions of pseudorandom functions
• The complexity of constructing pseudorandom generators from hard functions

Cites work

• A theory of the learnable
• Bounds on the Efficiency of Generic Cryptographic Constructions
• Constant depth circuits, Fourier transform, and learnability
• Fast pseudorandom functions based on expander graphs
• Hardness vs randomness
• Natural proofs
• Number-theoretic constructions of efficient pseudo-random functions
• On the complexity of constructing pseudorandom functions (especially when they don't exist)
• On the Complexity of Non-adaptively Increasing the Stretch of Pseudorandom Generators
• One way functions and pseudorandom generators
• Pseudo-random functions and factoring (extended abstract)
• Pseudorandom functions and lattices
• Synthesizers and their application to the parallel construction of pseudo-random functions
• Theory of Cryptography

Cited in

(1)

• Efficient quantum pseudorandomness from Hamiltonian phase states

This page was built for publication: Structural lower bounds on black-box constructions of pseudorandom functions

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