Rigorous Time/Space Trade-offs for Inverting Functions

DOI10.1137/S0097539795280512MaRDI QIDQ4943846zbMATH OpenFDO

Authors Moni Naor, Amos Fiat

Publication date 19 March 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539795280512

zbMATH Keywords

randomized algorithmscryptographyrandom graphscryptanalysisone-way functionshashing data encryption standard

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Cryptography (94A60)

Recommendations

• Lower bounds on the time/memory tradeoff of function inversion
• Time space tradeoffs for attacks against one-way functions and PRGs
• Quantum algorithm to solve function inversion with time-space trade-off
• Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs
• Beyond Hellman's time-memory trade-offs with applications to proofs of space

Cited in

(30)

• Bounded simultaneous messages
• Random oracles and non-uniformity
• Optimal security for keyed hash functions: avoiding time-space tradeoffs for finding collisions
• New proofs for NMAC and HMAC: security without collision resistance
• Quantum algorithm to solve function inversion with time-space trade-off
• Revisiting time-space tradeoffs for function inversion
• Lower bounds on the time/memory tradeoff of function inversion
• Complexity of inverting the Euler function
• The cost of false alarms in Hellman and rainbow tradeoffs
• Basing Weak Public-Key Cryptography on Strong One-Way Functions
• Ciphertext expansion in limited-leakage order-preserving encryption: a tight computational lower bound
• A general technique for searching in implicit sets via function inversion
• Beyond Hellman's time-memory trade-offs with applications to proofs of space
• Time-memory trade-off attack on the GSM A5/1 stream cipher using commodity GPGPU (extended abstract)
• Offline-online indifferentiability of cryptographic systems
• Time-space tradeoffs for sponge hashing: attacks and limitations for short collisions
• Fixing cracks in the concrete: random oracles with auxiliary input, revisited
• On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing
• On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing
• Improved space-efficient approximate nearest neighbor search using function inversion
• Computing Inverse ST in Linear Complexity
• The function-inversion problem: barriers and opportunities
• Time-space tradeoffs for sponge hashing: attacks and limitations for short collisions
• Time and space efficient collinearity indexing
• Fine-grained complexity in a world without cryptography
• Gapped string indexing in subquadratic space and sublinear query time
• Time space tradeoffs for attacks against one-way functions and PRGs
• The non-uniform perebor conjecture for time-bounded Kolmogorov complexity is false
• scientific article; zbMATH DE number 176209 (Why is no real title available?)
• On black-box meta complexity and function inversion

This page was built for publication: Rigorous Time/Space Trade-offs for Inverting Functions

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