Constant-Round Arguments from One-Way Functions

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=ndE-7IagxfQ


Duration: 42:52
216 views
1

Guy Rothblum (Apple)
https://simons.berkeley.edu/talks/guy-rothblum-apple-2023-05-01
Minimal Complexity Assumptions for Cryptography

We show that, assuming only the existence of one-way functions, there is a constant-round doubly-efficient argument system with almost-linear verification time for languages that have log-space uniform circuits of linear depth and polynomial size.



Comparing this new result with prior work: known unconditionally sound interactive proofs for this class of computations do not rely on any cryptographic assumptions, but they require a linear number of rounds [Goldwasser, Kalai and Rothblum, STOC 2008]. Kilian's protocol [STOC 1992] works for a richer class of computations (all of P or even all of NP, assuming the prover is given a witness for the input's membership in the language), but it assumes the existence of collision-resistant hash functions.



Joint work with Noga Amit.



Other Videos By Simons Institute for the Theory of Computing


2023-05-04Fine-Grained Cryptography
2023-05-04On the Complexity of Two-Party Differential Privacy
2023-05-03Communication Complexity, Streaming and Computational Assumptions
2023-05-03NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
2023-05-03Capturing One-Way Functions via NP-Hardness of Meta-Complexity
2023-05-03Derandomization: A Quick Tutorial
2023-05-03SNARGs Beyond Non-Signaling
2023-05-03Cryptographic Hardness of Correlated Sampling
2023-05-03Incompressiblity and Next-Block Pseudoentropy
2023-05-02Cryptography and Kolmogorov Complexity: A Quick Tutorial
2023-05-02Constant-Round Arguments from One-Way Functions
2023-05-02New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, ...
2023-05-02Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness
2023-05-02Non-interactive Universal Arguments
2023-05-02Rate-1 BARGs via fully-local SSB hash families
2023-05-02Correlation Intractability and SNARGs from Sub-exponential DDH
2023-05-01Tutorial on Proof Systems
2023-04-29Connections Between Multicalibration and Doubly Robust Estimation
2023-04-29On the Causal Foundations of Fair Machine Learning
2023-04-29Social Norm Bias: Residual Harms of Fairness-Aware Algorithms
2023-04-29Measuring Our Chances: Risk Prediction in this World and its Betters


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Guy Rothblum
Minimal Complexity Assumptions for Cryptography