Correlation Intractability and SNARGs from Sub-exponential DDH

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


Duration: 44:06
202 views
2

Zhengzhong Jin (MIT)
Correlation Intractability and SNARGs from Sub-exponential DDH
Minimal Complexity Assumptions for Cryptography

We provide the first constructions of SNARGs for Batch-NP and P based solely on the sub-exponential Decisional Diffie Hellman (DDH) assumption. Our schemes achieve poly-logarithmic proof sizes.

Central to our results and of independent interest is a new construction of correlation-intractable hash functions for “small input” product relations verifiable in TC^0, based on sub-exponential DDH.

Joint work with Arka Rai Choudhuri, Sanjam Garg, Abhishek Jain, and Jiaheng Zhang



Other Videos By Simons Institute for the Theory of Computing


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
2023-04-29Omnipredictors for Constrained Optimization
2023-04-28Who is Fairer: Humans vs. Machines?
2023-04-28Algorithmic Collective Action in Machine Learning
2023-04-28Sample Complexity Bounds for Realizable Multicalibration
2023-04-28Indistinguishable Generative Models of Huge Objects


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