Black-box concurrent zero-knowledge requires \tilde {Ω} (log n ) rounds

DOI10.1145/380752.380852zbMath1317.68064MaRDI QIDQ5176015

Alon Rosen, Ran Canetti, Erez Petrank, Joe Kilian

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380852

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

94A60: Cryptography

Related Items

Cryptography and cryptographic protocols, Minimal Assumptions and Round Complexity for Concurrent Zero-Knowledge in the Bare Public-Key Model, Magic Adversaries Versus Individual Reduction: Science Wins Either Way, Round-optimal honest-majority MPC in Minicrypt and with everlasting security (extended abstract), Possibility and impossibility results for selective decommitments, Hybrid commitments and their applications to zero-knowledge proof systems, The hunting of the SNARK, Round-preserving parallel composition of probabilistic-termination cryptographic protocols, Random walks and concurrent zero-knowledge, Polynomial runtime and composability, Lower bounds and impossibility results for concurrent self composition, Concurrent zero knowledge, revisited, Novel \(\Omega\)-protocols for NP, Lower bounds for non-black-box zero knowledge, Individual simulations, Non-Black-Box Simulation from One-Way Functions and Applications to Resettable Security, Two-Message, Oblivious Evaluation of Cryptographic Functionalities, On Constant-Round Concurrent Zero-Knowledge from a Knowledge Assumption, Concurrently Non-malleable Black-Box Zero Knowledge in the Bare Public-Key Model, Eye for an Eye: Efficient Concurrent Zero-Knowledge in the Timing Model, Possibility and Impossibility Results for Encryption and Commitment Secure under Selective Opening

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)