Finding Collisions in Interactive Protocols---Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments
From MaRDI portal
Publication:5252662
DOI10.1137/130938438zbMath1397.94068arXiv2105.01417OpenAlexW4300025581MaRDI QIDQ5252662
Jonathan Hoch, Gil Segev, Omer Reingold, Iftach Haitner
Publication date: 2 June 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2105.01417
one-way functionsprivate information retrievalblack-box impossibility resultsstatistically hiding commitments
Related Items (27)
Limits on the usefulness of random oracles ⋮ Enhancements are blackbox non-trivial: impossibility of enhanced trapdoor permutations from standard trapdoor permutations ⋮ Limits on the Power of Indistinguishability Obfuscation and Functional Encryption ⋮ Composable Security in the Tamper-Proof Hardware Model Under Minimal Complexity ⋮ Parallel Hashing via List Recoverability ⋮ 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 ⋮ A random oracle for all of us ⋮ On the impossibility of key agreements from quantum random oracles ⋮ Collision-resistance from multi-collision-resistance ⋮ The gap is sensitive to size of preimages: collapsing property doesn't go beyond quantum collision-resistance for preimages bounded hash functions ⋮ General properties of quantum bit commitments (extended abstract) ⋮ Quantum computationally predicate-binding commitments with application in quantum zero-knowledge arguments for NP ⋮ Structure Versus Hardness Through the Obfuscation Lens ⋮ A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval ⋮ On the relationship between statistical zero-knowledge and statistical randomized encodings ⋮ On Constructing One-Way Permutations from Indistinguishability Obfuscation ⋮ Can PPAD hardness be based on standard cryptographic assumptions? ⋮ Possibility and Impossibility Results for Encryption and Commitment Secure under Selective Opening ⋮ On the Communication Complexity of Key-Agreement Protocols. ⋮ On the Relationship Between Statistical Zero-Knowledge and Statistical Randomized Encodings ⋮ Private Coins versus Public Coins in Zero-Knowledge Proof Systems ⋮ Finding Collisions in Interactive Protocols---Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments ⋮ Unnamed Item ⋮ The Many Entropies in One-Way Functions ⋮ On subset-resilient hash function families
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bit commitment using pseudorandomness
- Lower bounds for concurrent zero knowledge
- A discrete logarithm implementation of perfect zero-knowledge blobs
- Minimum disclosure proofs of knowledge
- Perfect zero-knowledge arguments for NP using any one-way permutation
- On the existence of statistically hiding bit commitment schemes and fail-stop signatures
- Parallel coin-tossing and constant-round secure two-party computation
- How to construct constant-round zero-knowledge proof systems for NP
- A new interactive hashing theorem
- One-way functions are essential for single-server private information retrieval
- On the Instantiability of Hash-and-Sign RSA Signatures
- Lossy Functions Do Not Amplify Well
- On the Cryptographic Applications of Random Functions (Extended Abstract)
- Limits on the Power of Zero-Knowledge Proofs in Cryptographic Constructions
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Private Coins versus Public Coins in Zero-Knowledge Proof Systems
- A complete problem for statistical zero knowledge
- Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function
- Lower bounds on the efficiency of encryption and digital signature schemes
- On the Round Complexity of Zero-Knowledge Proofs Based on One-Way Permutations
- Oblivious Transfer Is Symmetric
- One-Way Permutations, Interactive Hashing and Statistically Hiding Commitments
- Compression from Collisions, or Why CRHF Combiners Have a Long Output
- On the (Im)Possibility of Key Dependent Encryption
- Chosen-Ciphertext Security via Correlated Products
- A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
- How to Construct Pseudorandom Permutations from Pseudorandom Functions
- A Pseudorandom Generator from any One-way Function
- Computing with Very Weak Random Sources
- Foundations of Cryptography
- Black-Box Concurrent Zero-Knowledge Requires (Almost) Logarithmically Many Rounds
- Foundations of Cryptography
- On the Composition of Zero-Knowledge Proof Systems
- Inaccessible entropy
- Finding Collisions in Interactive Protocols---Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments
- Information Security and Privacy
- Reducing Complexity Assumptions for Statistically-Hiding Commitment
- Chosen-Ciphertext Security via Correlated Products
- Concurrent zero-knowledge
- A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval
- Information Security
- Bounds on the Efficiency of Generic Cryptographic Constructions
- Automata, Languages and Programming
- Automata, Languages and Programming
- Theory of Cryptography
- Theory of Cryptography
- Theory of Cryptography
This page was built for publication: Finding Collisions in Interactive Protocols---Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments
