Random oracles and non-uniformity

DOI10.1007/978-3-319-78381-9_9zbMath1423.94063OpenAlexW2794798416MaRDI QIDQ1648794

Siyao Guo, Sandro Coretti, Yevgeniy Dodis, John P. Steinberger

Publication date: 9 July 2018

Full work available at URL: https://doi.org/10.1007/978-3-319-78381-9_9

Mathematics Subject Classification ID

Cryptography (94A60)

Related Items (33)

Ciphertext expansion in limited-leakage order-preserving encryption: a tight computational lower bound ⋮ Random oracles and non-uniformity ⋮ Single-server private information retrieval with sublinear amortized time ⋮ On building fine-grained one-way functions from strong average-case hardness ⋮ The function-inversion problem: barriers and opportunities ⋮ On the complexity of collision resistant hash functions: new and old black-box separations ⋮ Optimal security for keyed hash functions: avoiding time-space tradeoffs for finding collisions ⋮ On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing ⋮ On differential privacy and adaptive data analysis with bounded space ⋮ A random oracle for all of us ⋮ On the worst-case inefficiency of CGKA ⋮ On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing ⋮ Non-uniformity and quantum advice in the quantum random oracle model ⋮ Lower bounds for (batch) PIR with private preprocessing ⋮ Revisiting time-space tradeoffs for function inversion ⋮ The query-complexity of preprocessing attacks ⋮ Crooked indifferentiability of enveloped XOR revisited ⋮ Lower bound on SNARGs in the random oracle model ⋮ Time-space tradeoffs for sponge hashing: attacks and limitations for short collisions ⋮ Time-space lower bounds for finding collisions in Merkle-Damgård hash functions ⋮ Time-space lower bounds for finding collisions in Merkle-Damgård Hash functions ⋮ Unifying presampling via concentration bounds ⋮ Non-malleable time-lock puzzles and applications ⋮ Quantum depth in the random oracle model ⋮ On the need for large quantum depth ⋮ On black-box verifiable outsourcing ⋮ Immunizing backdoored PRGs ⋮ On time-space lower bounds for finding short collisions in sponge hash functions ⋮ Tight characterizations for preprocessing against cryptographic salting ⋮ On building fine-grained one-way functions from strong average-case hardness ⋮ Password hashing and preprocessing ⋮ The memory-tightness of authenticated encryption ⋮ Time-space tradeoffs and short collisions in Merkle-Damgård hash functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Conditionally-perfect secrecy and a provably-secure randomized cipher
• A uniform-complexity treatment of encryption and zero-knowledge
• Definitions and properties of zero-knowledge proof systems
• Random oracles and non-uniformity
• Constructing locally computable extractors and cryptosystems in the bounded-storage model
• Pseudorandomness for network algorithms
• Key-Alternating Ciphers and Key-Length Extension: Exact Bounds and Multi-user Security
• Non-uniform Cracks in the Concrete: The Power of Free Precomputation
• Formalizing Human Ignorance
• On the power of nonuniformity in proofs of security
• Security Amplification for the Cascade of Arbitrarily Weak PRPs: Tight Bounds via the Interactive Hardcore Lemma
• The random oracle methodology, revisited
• Message Authentication Codes from Unpredictable Block Ciphers
• Tight security proofs for the bounded-storage model
• Time Space Tradeoffs for Attacks against One-Way Functions and PRGs
• Random Oracles and Auxiliary Input
• The “Coefficients H” Technique
• How To Prove Yourself: Practical Solutions to Identification and Signature Problems
• A cryptanalytic time-memory trade-off
• Simple Constructions of Almost k-wise Independent Random Variables
• Everlasting security in the bounded storage model
• On the Composition of Zero-Knowledge Proof Systems
• Rigorous Time/Space Trade-offs for Inverting Functions
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
• Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited
• Advances in Cryptology - EUROCRYPT 2004
• Key Derivation without Entropy Waste
• Advances in Cryptology - CRYPTO 2003
• Bounds on the Efficiency of Generic Cryptographic Constructions
• On the Power of Hierarchical Identity-Based Encryption
• Rectangles Are Nonnegative Juntas
• Theory of Cryptography

This page was built for publication: Random oracles and non-uniformity