Black-box concurrent zero-knowledge requires ( n) rounds

DOI10.1145/380752.380852MaRDI QIDQ5176015zbMATH OpenOpenAlexFDO

Authors Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen

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

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Recommendations

• Black-Box Concurrent Zero-Knowledge Requires (Almost) Logarithmically Many Rounds
• Concurrent and resettable zero-knowledge in poly-logarithmic rounds
• scientific article; zbMATH DE number 1759795
• Private coins versus public coins in zero-knowledge proof systems
• The knowledge tightness of parallel zero-knowledge

Cites work

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

Cited in

(28)

• Hybrid commitments and their applications to zero-knowledge proof systems
• The hunting of the SNARK
• Round-preserving parallel composition of probabilistic-termination cryptographic protocols
• A black-box approach to post-quantum zero-knowledge in constant rounds
• 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
• Possibility and impossibility results for selective decommitments
• scientific article; zbMATH DE number 1759795 (Why is no real title available?)
• Black-Box Concurrent Zero-Knowledge Requires (Almost) Logarithmically Many Rounds
• Cryptography and cryptographic protocols
• Minimal Assumptions and Round Complexity for Concurrent Zero-Knowledge in the Bare Public-Key Model
• The Round-Complexity of Black-Box Zero-Knowledge: A Combinatorial Characterization
• Magic adversaries versus individual reduction: science wins either way
• Round-optimal honest-majority MPC in Minicrypt and with everlasting security (extended abstract)
• The power of undirected rewindings for adaptive security
• The round complexity of statistical MPC with optimal resiliency
• The black-box simulation barrier persists in a fully quantum world

This page was built for publication: Black-box concurrent zero-knowledge requires \(\tilde{\omega}(\log n)\) rounds

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