Revisiting time-space tradeoffs for function inversion

DOI10.1007/978-3-031-38545-2_15OpenAlexW4385654690MaRDI QIDQ6145922

Spencer Peters, Siyao Guo, Noah Stephens-Davidowitz, Alexander Golovnev

Publication date: 2 February 2024

Published in: Advances in Cryptology – CRYPTO 2023 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-38545-2_15

zbMATH Keywords

non-adaptive algorithmblack-box function inversion problem

Mathematics Subject Classification ID

Cryptography (94A60)

Cites Work

• NP is as easy as detecting unique solutions
• Matching is as easy as matrix inversion
• Private vs. common random bits in communication complexity
• Random oracles and non-uniformity
• Non-uniform bounds in the random-permutation, ideal-cipher, and generic-group models
• Lower bounds on the time/memory tradeoff of function inversion
• The function-inversion problem: barriers and opportunities
• On obfuscating point functions
• Time Space Tradeoffs for Attacks against One-Way Functions and PRGs
• Random Oracles and Auxiliary Input
• A cryptanalytic time-memory trade-off
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Rigorous Time/Space Trade-offs for Inverting Functions
• Data structures meet cryptography: 3SUM with preprocessing
• Communication Complexity
• Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited
• Class of constructive asymptotically good algebraic codes
• Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs
• Data Structures Lower Bounds and Popular Conjectures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Revisiting time-space tradeoffs for function inversion