Minimal Complexity Assumptions for Cryptography 2023
2023-05-01..2023-05-05
Berkeley, United States
as the organisers put it
This workshop will aim to capitalize on recent progress in meta-complexity to gain an improved understanding of questions such as: Can one-way functions be based on average-case hardness of NP? Is there a characterization of asymmetric-key cryptography by a standard complexity assumption? Can connections between meta-complexity and obfuscation be exploited to base obfuscation on more general assumptions? What kinds of connections exist among proof complexity, cryptography, and the theory of TFNP?
| title | author | length |
|---|---|---|
| Tutorial on Proof Systems | Abhishek Jain | 01h 08m |
Survey of recent work on making non‑interactive succinct proofs practical: shows how PCP+Kilian-style compilers and the Fiat‑Shamir heuristic are turned into… | ||
| Correlation Intractability and SNARGs from Sub-exponential DDH | Zhengzhong Jin | 44m |
Construction of SNARGs for Batch-NP and P from the sub-exponential Decisional Diffie–Hellman assumption, achieving poly-logarithmic proof sizes and a CIH for… | ||
| Rate-1 BARGs via fully-local SSB hash families | Lalita Devadas | 46m |
Defines and builds a fully-local SSB hash family whose local openings are poly(lambda) and verifiable against a succinct digest, so openings do not grow with… | ||
| Non-interactive Universal Arguments | Dana Shamir | 45m |
Constructs non-interactive universal arguments by lifting existing SNARGs for P into a universal protocol using fully homomorphic encryption plus a family of… | ||
| Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness | Amit Sahai, Alexis Korb | 49m |
Proves a concrete conditional separation: assuming UP not in RP (which follows from injective one‑way functions), with probability 1 over a random oracle O one… | ||
| New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, ... | Dana Dachman-Soled | 38m |
Transformation shows that a NIZK in the uniform random string model with provers running in time T yields a ZAP where provers run in time poly(n)·T, enabling… | ||
| Cryptography and Kolmogorov Complexity: A Quick Tutorial | Yanyi Liu | 01h 05m |
Claim: existence of one-way functions is equivalent to some polynomial time bound t for which t-time Kolmogorov complexity Kt is mildly hard-on-average over… | ||
| Incompressiblity and Next-Block Pseudoentropy | Iftach Haitner | 47m |
A k-incompressible distribution provably has (k−2) bits of next-block pseudoentropy: the contrapositive builds an efficient compressor from any estimator with… | ||
| Cryptographic Hardness of Correlated Sampling | Russell Impagliazzo | 31m |
Shows that converting perfect generalization (or stability) into replicability hinges on correlated sampling and cryptography: a white box correlated sampling… | ||
| SNARGs Beyond Non-Signaling | Yael Tauman Kalai | 39m |
Constructs a SNARG for a subclass called monotone policy batch NP under the LWE assumption, yielding the first standard-assumption SNARG for a class not known… | ||
| Derandomization: A Quick Tutorial | Lijie Chen | 01h 01m |
Shows a conditional conversion that turns any constant‑round, doubly‑efficient interactive proof into an NP-type deterministic argument with essentially the… | ||
| Capturing One-Way Functions via NP-Hardness of Meta-Complexity | Shuichi Hirahara | 47m |
Main theorem: a one-way function iff NP is worst-case hard and distributional Kolmogorov complexity is NP-hard under randomized polynomial-time reductions… | ||
| NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach | Hanlin Ren | 46m |
Proves NP-hardness of approximating Minimum Oracle Circuit Size Problem with a near‑optimal gap: Yes instances admit O‑oracle circuits of size ≤ 2^{ε n}, No… | ||
| Communication Complexity, Streaming and Computational Assumptions | Moni Naor | 01h 01m |
Assuming polynomial-time adversaries, the work shows concrete reductions: a simultaneous-message equality protocol that beats the sqrt(n) bound implies a… | ||
| On the Complexity of Two-Party Differential Privacy | Naom Mazor | 40m |
Shows that any two-party computational differential privacy protocol that computes inner product (or Hamming distance) with accuracy better than the trivial… | ||
| Fine-Grained Cryptography | Marshall Ball | 54m |
Focuses on cryptography against n^c adversaries and gives concrete constructions and limits: builds fine-grained one-way/PRG candidates from planted kSum /… | ||
| Tutorial on obfuscation | Rachel Lin | 01h 04m |
Survey claims a concrete blueprint to get iO from LPN + local PRGs + bilinear maps: randomized encodings (garbled circuits) reduce evaluation to a single… | ||
| Tales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential Privacy | Rahul Ilango | 48m |
Three concrete results use obfuscation and related primitives to resolve open problems: assuming indistinguishability obfuscation and NP ≠ coNP, there is no… | ||
| Mutual Empowerment Between Circuit Obfuscation and Circuit Minimization | Ilya Volkovich | 37m |
Shows that Indistinguishability Obfuscation (IO) and MCSP mutually empower each other by concrete implications: a perfect IO secure against non‑uniform… | ||
| Assumptions in cryptography and complexity theory | 29m | |
Panelists debate concrete examples: reductions matter more than vague claims, and Strong ETH is treated as a research muse because attempts to refute it spur… | ||
| Constant-Round Arguments from One-Way Functions | Guy N. Rothblum | 43m |
Assumes only one-way functions and constructs a constant-round doubly-efficient argument for any language with log-space-uniform, polynomial-size circuits of… | ||
| Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE | Daniel Wichs | 59m |
Constructs the first unkeyed schemes that make single-server private reads and RAM-style FHE practical under Ring LWE, turning PIR into evaluation of a… | ||
| Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography | Benny Applebaum | 38m |
Introduces a single hypothesis: prover-laconic AVP (trusted advisor gives one-time advice, verifier gets x, prover may send constant bits) requires… | ||
| Batch Proofs are Statistically Hiding | Prashant Vadusevan | 45m |
Shows that any statistically-sound batch proof for a language L (communication < t^{1−ε}) yields Statistically Witness Indistinguishable (SWI) proofs for L… | ||
| Unclonable Polymers and Their Cryptographic Applications | Tal Malkin | 48m |
Claim: a biologically grounded primitive—consumable token—encodes secrets in short peptides (≈30 amino acids, keys ≈10 amino acids ≈50 bits) with an antibody… | ||
| New Ways to Garble Arithmetic Circuits | Rachel Lin | 51m |
Presents a construction that achieves constant-rate for bounded integers using the Decisional Composite Residuosity (Paillier) assumption and an alternative… | ||
| Collision-Resistance from Multi-Collision-Resistance | Ron D. Rothblum | 49m |
Shows a non-blackbox transformation that turns a moderately shrinking 3‑MCRH (and separately 4‑MCRH) into a collision‑resistant hash family by using the… | ||
| Geometry of Secure Computation | Hemanta Maji | 48m |
Presents a geometric characterization of information‑theoretic two‑party secure computation that encodes every b‑bit protocol as a point and reduces existence… | ||
| Black-Hole Radiation Decoding as a Cryptographic Assumption | Zvika Brakerski | 47m |
Claims an existential equivalence between the hardness of decoding Hawking radiation and the existence of basic quantum cryptography, showing hardness of the… | ||
| Cryptography with Certified Deletion | Dakshita Khurana | 46m |
Constructs public key encryption and many advanced primitives that produce a classical ciphertext plus a quantum register of BB84 conjugate encodings, where… | ||
| Quantum Minimalism | Mark Zhandry | 34m |
Argues that classical one-way functions are minimal because they are trivially implied by most primitives, have a simple, robust definition, admit universal… | ||
| Commitments to Quantum States | Fermi Ma | 48m |
Introduces a precise binding definition called swap binding that requires committing erases the message from the sender’s view, gives the first succinct… | ||
| On the Computational Hardness Needed for Quantum Cryptography | Ran Canetti | 48m |
Claims that EFI pairs — efficiently samplable states that are statistically far but computationally indistinguishable — are necessary and broadly sufficient… | ||
| Quantum pseudorandomness in Algorithmica, and its implications to cryptography and complexity | Luowen Qian | 46m |
The paper constructs a classical oracle world where P = PH yet t‑forrelation states (Hadamard/phase interleavings of t Boolean functions) remain single‑copy… | ||
| Black-Box Separations in Quantum Cryptography | Mohammad Mahmoody | 48m |
States a conditional black-box separation: any key‑agreement protocol that uses classical messages, up to d quantum queries per party, and has perfect… | ||
| nothing matches | ||