Schedule (see abstracts below the schedule):

Abstracts:

Yuval Ishai, Technion

Title: Dot-Product Proofs

Abstract: A dot-product proof is a simple probabilistic proof system in which the verifier decides whether to accept an input vector based on a single linear combination of the entries of the input and a proof vector. I will present constructions of linear-size dot-product proofs for circuit satisfiability and discuss two kinds of applications: exponential-time hardness of approximation of MAX-LIN from ETH, and minimizing verification complexity of succinct arguments.

Joint work with Nir Bitansky, Prahladh Harsha, Ron Rothblum, and David Wu

Huijia Lin, UW

Title: Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Function Evaluation, and More

Abstract: Although we have known about fully homomorphic encryption (FHE) from circular security assumptions for over a decade [Gentry, STOC ’09; Brakerski–Vaikuntanathan, FOCS ’11], there is still a significant gap in understanding related homomorphic primitives supporting all unrestricted polynomial-size computations. One prominent example is attribute-based encryption (ABE). The state-of-the-art constructions, relying on the hardness of learning with errors (LWE) [Gorbunov–Vaikuntanathan–Wee, STOC ’13; Boneh et al., Eurocrypt ’14], only accommodate circuits up to a predetermined depth, akin to leveled homomorphic encryption. In addition, their components (master public key, secret keys, and ciphertexts) have sizes polynomial in the maximum circuit depth. Even in the simpler setting where a single key is published (or a single circuit is involved), the depth dependency persists, showing up in constructions of 1-key ABE and related primitives, including laconic function evaluation (LFE), 1-key functional encryption (FE), and reusable garbling schemes. So far, the only approach of eliminating depth dependency relies on indistinguishability obfuscation. 

In this talk, we introduce new lattice-based techniques to overcome the depth-dependency limitations:

• Relying on a circular security assumption, we construct LFE, 1-key FE, 1-key ABE, and reusable garbling schemes capable of evaluating circuits of unbounded depth and size.

• Based on the evasive circular LWE assumption, a stronger variant of the recently proposed evasive LWE assumption [Wee, Eurocrypt ’22; Tsabary, Crypto ’22], we construct a full- fledged ABE scheme for circuits of unbounded depth and size.

Our LFE, 1-key FE, and reusable garbling schemes achieve optimal succinctness (up to polynomial factors in the security parameter). In fact, we obtain the first constant-size garbled circuits without relying on indistinguishability obfuscation.

Ryan O'Donnell, CMU

Title:  Pseudorandom Permutations

Abstract:  An extremely simple way to construct a pseudorandom permutation on {0,1}^n is to make a uniformly random n-bit, size-m circuit with reversible gates (of fan-in/out 3, say).  Previous work has shown that for some m = poly(n,k), this construction is statistically "almost k-wise independent".  In this talk, we will explain how these results can be made more practical, showing that depth O~(k) circuits suffice.  We also discuss the question: are constructions like this plausibly computationally secure pseudorandom permutations?

Vinod Vaikuntanathan, MIT

Title: Quantum Algorithms for Factoring, Revisited

Abstract: We will describe an algorithm of O. Regev who constructed an $O(n^{3/2})$-gate quantum circuit for factoring, improving on Shor's $O(n^2)$, as well as our improvements to it. We will describe a collection of results: how to reduce the number of qubits in Regev's algorithm from $O(n^{3/2})$ to $O(n)$, achieving the best of Shor and Regev; how to build a factoring circuit whose gates err with probability 1/n^{3/2} (without using expensive quantum fault-tolerance techniques), improving on both Shor and Regev; and more.

Daniel Wichs, Northeastern University

Title: Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation

Abstract:  Can we design a private variant of "Google search" that would enable users to search the Internet privately without revealing their queries to Google? Fully homomorphic encryption gives a potential solution to this problem, but would require Google to run a huge computation that is linear in the size of the entire internet to answer each encrypted search query, making it realistically infeasible! Is there a way for Google to preprocess the internet content into a special data structure that would then allow it to answer each encrypted search query very efficiently by only accessing a small number of locations in the data structure? We give an approach toward solving this problem as a special case of our work.  

Concretely, we construct the first schemes for "doubly efficient private information retrieval (DEPIR)" and "fully homomorphic encryption in the RAM model (RAM-FHE)" under standard cryptographic hardness assumptions (Ring Learning with Errors). Previously we only had heuristic candidate constructions that only satisfied relaxed variants of these primitives. Our new solutions combine tools from cryptography together with data structures for fast polynomial evaluation (Kedlaya and Umans '08).

Based on a joint work with Wei-Kai Lin and Ethan Mook at STOC 2023 (recipient of "best paper award")

https://eprint.iacr.org/2022/1703

David Wu, UT Austin

Title: Distributed Broadcast Encryption from Lattices

A broadcast encryption scheme allows a user to encrypt a message to N recipients with a ciphertext whose size scales sublinearly with N. While broadcast encryption enables succinct encrypted broadcasts, it also introduces a strong trust assumption and a single point of failure; namely, there is a central authority who generates the decryption keys for all users in the system. Distributed broadcast encryption offers an appealing alternative where there is a one-time (trusted) setup process that generates a set of public parameters. Thereafter, users can independently generate their own public keys and post them to a public-key directory. Moreover, anyone can broadcast an encrypted message to any subset of user public keys with a ciphertext whose size scales sublinearly with the size of the broadcast set. Unlike traditional broadcast encryption, there are no long-term secrets in distributed broadcast encryption and users can join the system at any time (by posting their public key to the public-key directory).

Previously, distributed broadcast encryption schemes were known from standard pairing-based assumptions or from powerful tools like indistinguishability obfuscation or witness encryption. In this talk, I will show how to construct distributed broadcast encryption scheme from the (falsifiable) \ell-succinct LWE assumption introduced by Wee (CRYPTO 2024). Previously, the only lattice-based candidate for distributed broadcast encryption goes through general-purpose witness encryption, which in turn is only known from the private-coin evasive LWE assumption, a strong and non-falsifiable lattice assumption. Along the way,  I'll also describe a more direct construction of broadcast encryption from \ell-succinct LWE that does not need any homomorphic evaluation machinery.

Joint work with Jeffrey Champion

Jeff Xu, CMU

Title: Average-Case Sum-of-Squares Lower Bounds for Crytographers.

Abstract: The Sum-of-Squares (SoS) hierarchy of semidefinite programs is a powerful algorithmic paradigm which captures state-of-the-art algorithmic guarantee, and in the average case setting, SoS lower bounds provide strong evidence of algorithmic hardness or information-computation gaps. I will discuss the techniques for proving lower Bounds for statistical problems, and if time permitted, sketch upon some major challenges addressed in recent works. Despite the progress in this field, it has not attracted much attention from the crypto community. Towards this end, I will try to mention few challenges residing in the intersection of these two areas.