Bounds on the Efficiency of Generic Cryptographic Constructions
From MaRDI portal
Publication:5700578
DOI10.1137/S0097539704443276zbMath1087.94019MaRDI QIDQ5700578
Yael Gertner, Rosario Gennaro, Luca Trevisan, Jonathan N. Katz
Publication date: 28 October 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Limits on the usefulness of random oracles ⋮ Limits on the Power of Indistinguishability Obfuscation and Functional Encryption ⋮ (Almost) Optimal Constructions of UOWHFs from 1-to-1, Regular One-Way Functions and Beyond ⋮ Random oracles and non-uniformity ⋮ The function-inversion problem: barriers and opportunities ⋮ On the complexity of collision resistant hash functions: new and old black-box separations ⋮ Merkle's key agreement protocol is optimal: an \(O(n^2)\) attack on any key agreement from random oracles ⋮ On constructing one-way permutations from indistinguishability obfuscation ⋮ Asymptotically efficient lattice-based digital signatures ⋮ Non-adaptive universal one-way hash functions from arbitrary one-way functions ⋮ Multi-input Functional Encryption with Unbounded-Message Security ⋮ Impossibility of indifferentiable iterated blockciphers from 3 or less primitive calls ⋮ Lower bounds for (batch) PIR with private preprocessing ⋮ Lower bound on SNARGs in the random oracle model ⋮ Simple constructions from (almost) regular one-way functions ⋮ The cost of adaptivity in security games on graphs ⋮ On the impossibility of purely algebraic signatures ⋮ Adaptive zero-knowledge proofs and adaptively secure oblivious transfer ⋮ Structure Versus Hardness Through the Obfuscation Lens ⋮ Bounds on the efficiency of black-box commitment schemes ⋮ Asymptotically Efficient Lattice-Based Digital Signatures ⋮ A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval ⋮ On Constructing One-Way Permutations from Indistinguishability Obfuscation ⋮ On the complexity of constructing pseudorandom functions (especially when they don't exist) ⋮ On the Security Loss in Cryptographic Reductions ⋮ Unnamed Item ⋮ Efficiency Bounds for Adversary Constructions in Black-Box Reductions ⋮ On the impossibility of highly-efficient blockcipher-based hash functions ⋮ Two Is a Crowd? A Black-Box Separation of One-Wayness and Security under Correlated Inputs ⋮ Finding Collisions in Interactive Protocols---Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments ⋮ Time-space tradeoffs and short collisions in Merkle-Damgård hash functions ⋮ Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited ⋮ On subset-resilient hash function families
