Black-Box Concurrent Zero-Knowledge Requires (Almost) Logarithmically Many Rounds

DOI10.1137/S0097539701392949MaRDI QIDQ4785630zbMATH OpenOpenAlexFDO

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

Publication date 5 January 2003

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539701392949

zbMATH Keywords

lower boundsround complexityzero-knowledgeblack-box simulationinteractive protocols

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Black-box concurrent zero-knowledge requires \(\tilde{\omega}(\log n)\) rounds
• A black-box approach to post-quantum zero-knowledge in constant rounds
• scientific article; zbMATH DE number 1759795
• The Round-Complexity of Black-Box Zero-Knowledge: A Combinatorial Characterization
• Concurrent and resettable zero-knowledge in poly-logarithmic rounds
• Concurrently Non-malleable Black-Box Zero Knowledge in the Bare Public-Key Model
• On Constant-Round Concurrent Zero-Knowledge
• On constant-round concurrent zero-knowledge from a knowledge assumption
• Concurrent zero knowledge, revisited
• Automata, Languages and Programming

Cited in

(20)

• Parallel and Concurrent Security of the HB and HB +  Protocols
• The Round-Complexity of Black-Box Zero-Knowledge: A Combinatorial Characterization
• Concurrent knowledge extraction in public-key models
• A black-box approach to post-quantum zero-knowledge in constant rounds
• Parallel and concurrent security of the HB and \(HB^{+}\) protocols
• scientific article; zbMATH DE number 1759795 (Why is no real title available?)
• The knowledge tightness of parallel zero-knowledge
• Private coins versus public coins in zero-knowledge proof systems
• Concurrent zero knowledge in the bounded player model
• Finding collisions in interactive protocols -- tight lower bounds on the round and communication complexities of statistically hiding commitments
• Lower bounds for non-black-box zero knowledge
• The ERA Theorem for Safe Memory Reclamation
• Weak Zero-Knowledge beyond the Black-Box Barrier
• Black-box concurrent zero-knowledge requires \(\tilde{\omega}(\log n)\) rounds
• Statistical concurrent non-malleable zero-knowledge from one-way functions
• Statistical concurrent non-malleable zero-knowledge from one-way functions
• Black-box impossibilities of obtaining 2-round weak ZK and strong WI from polynomial hardness
• General composition and universal composability in secure multiparty computation
• Non-black-box simulation in the fully concurrent setting, revisited
• Automata, Languages and Programming

This page was built for publication: Black-Box Concurrent Zero-Knowledge Requires (Almost) Logarithmically Many Rounds

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