Capturing One-Way Functions via NP-Hardness of Meta-Complexity

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


Duration: 46:45
239 views
2

Shuichi Hirahara (National Institute of Informatics, Tokyo)
https://simons.berkeley.edu/talks/shuichi-hirahara-national-institute-informatics-tokyo-2023-05-02
Minimal Complexity Assumptions for Cryptography

We present the first characterization of a one-way function by worst-case hardness assumptions: A one-way function exists iff NP is hard in the worst case and "distributional Kolmogorov complexity" is NP-hard under randomized reductions. Here, the t-time bounded distributional Kolmogorov complexity of a string x given a distribution D is defined to be the length of a shortest t-time program that outputs x given as input y drawn from the distribution D with high probability. The characterization suggests that the recent approaches of using meta-complexity to exclude Heuristica and Pessiland from Impagliazzo's five worlds are both sufficient and necessary.



Other Videos By Simons Institute for the Theory of Computing


2023-05-05Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography
2023-05-04Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
2023-05-04Assumptions in cryptography and complexity theory
2023-05-04Mutual Empowerment Between Circuit Obfuscation and Circuit Minimization
2023-05-04Tales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential Privacy
2023-05-04Tutorial on obfuscation
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


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