Strict Polynomial-Time in Simulation and Extraction

DOI10.1137/S0097539703427975zbMath1060.94014OpenAlexW2096626008MaRDI QIDQ4651493

Yehuda Lindell, Boaz Barak

Publication date: 21 February 2005

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

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

zbMATH Keywords

proofs of knowledgezero-knowledge proof systemsblack-box vs. nonblack-box algorithmsexpected vs. strict polynomial-time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Concurrent knowledge extraction in public-key models ⋮ Round-optimal zero-knowledge proofs of knowledge for NP ⋮ Which languages have 4-round zero-knowledge proofs? ⋮ Post-quantum resettably-sound zero knowledge ⋮ On expected polynomial runtime in cryptography ⋮ The Round-Complexity of Black-Box Zero-Knowledge: A Combinatorial Characterization ⋮ Efficient Fully-Simulatable Oblivious Transfer ⋮ Strong Proofs of Knowledge ⋮ Handling expected polynomial-time strategies in simulation-based security proofs ⋮ An efficient protocol for secure two-party computation in the presence of malicious adversaries ⋮ How to Simulate It – A Tutorial on the Simulation Proof Technique

This page was built for publication: Strict Polynomial-Time in Simulation and Extraction