Texas Crypto Day

The 4th Texas Crypto Day was held at Texas A&M University on April 26, 2024.

Program

10:30-11:00	Coffee
11:00-12:00	Hoeteck Wee (NTT Research) Invited Talk: ABE for Circuits with poly(λ)-sized Keys from LWE
12:00-1:30	Lunch (provided)
1:30-2:00	Nai-Hui Chia (Rice University) Classical Verification of Quantum Depth
2:00-2:30	Shafik Nassar (UT Austin) Strong Batching for Non-interactive Statistical Zero-Knowledge
2:30-3:00	Coffee
3:00-3:30	Pouyan Forghani (Texas A&M University) Is It Even Possible? On the Parallel Composition of Asynchronous Cryptographic Protocols
3:30-4:00	Eli Bradley (UT Austin) Batch Arguments to NIZKs from One-Way Functions
4:00-5:00	Coffee and Social Hour

Abstracts

ABE for Circuits with poly(λ)-sized Keys from LWE

Hoeteck Wee (NTT Research)

We present a key-policy attribute-based encryption (ABE) scheme for circuits based on the Learning With Errors (LWE) assumption whose key size is independent of the circuit depth. Our result constitutes the first improvement for ABE for circuits from LWE in almost a decade, given by Gorbunov, Vaikuntanathan, and Wee (STOC 2013) and Boneh, et al. (EUROCRYPT 2014) – we reduce the key size in the latter from poly(depth, λ) to poly(λ). The starting point of our construction is a recent ABE scheme of Li, Lin, and Luo (TCC 2022), which achieves poly(λ) key size but requires pairings and generic bilinear groups in addition to LWE; we introduce new lattice techniques to eliminate the additional requirements.

Joint work with Valerio Cini.

Classical Verification of Quantum Depth

Nai-Hui Chia (Rice University)

Verifying if a remote server has sufficient quantum resources to demonstrate quantum advantage is a fascinating question in complexity theory and a practical challenge. One approach is asking the server to solve some classically intractable problem, such as factoring. Another approach is the proof of quantumness protocols. These protocols enable a classical client to check whether a remote server can complete some classically intractable problem and thus can be used to distinguish quantum from classical computers. However, these two approaches mainly focus on distinguishing quantum computers from classical ones. They do not directly translate into ones that separate quantum computers with different quantum resources.

In this talk, we want to go one step further by showing protocols that can distinguish machines with different quantum depths. We call such protocols Classical Verification of Quantum Depth (CVQD). Roughly speaking, if a server has quantum circuit depth at most d, the classical client will reject it; otherwise, the classical client will accept it. Note that a malicious server, in general, can use classical computers to cheat. Thus, CVQD protocols shall be able to distinguish hybrid quantum-classical computers with different quantum depths. We will see two CVQD protocols: The first protocol can separate hybrid quantum-classical computers with quantum depth d and d+c (for c some fixed constant) assuming quantum LWE with d rounds. The second protocol is a one-round protocol assuming quantum LWE and the classical random oracle heuristics.

Strong Batching for Non-interactive Statistical Zero-Knowledge

Shafik Nassar (UT Austin)

A zero-knowledge proof enables a prover to convince a verifier that a statement is true, without revealing anything beyond this fact. By running a zero-knowledge proof k times, it is possible to prove (still in zero-knowledge) that k separate statements are all true. However, this increases the communication by a multiplicative factor of k. Can one do better? In other words, is (non-trivial) zero-knowledge batch verification possible?

Previous work of Kaslasi et al. (TCC 2020, Eurocrypt 2021) presented non-trivial batching for problems that have a non-interactive statistical zero-knowledge, but (1) at the cost of introducing interaction and (2) achieved communication that is roughly poly(n)+k, which is non-trivial but still scales linearly with k. In this talk, we show how to overcome both obstacles and achieve non-interactive batching with total communication of poly(n, log k).

Joint work with Changui Mu, Ron Rothblum, and Prashant Nalini Vasudevan.

Is It Even Possible? On the Parallel Composition of Asynchronous Cryptographic Protocols

Pouyan Forghani (Texas A&M University)

In the design and analysis of cryptographic protocols it is often assumed an idealized model where the communication is synchronous and messages are always delivered by the start of the next round. However, while substantially simplifying things, hiding environmental nuisances and allowing us to focus on the task at hand, this strong assumption incurs significant overhead in practice.

In this talk, we will show that, as opposed to the synchronous setting, well-established techniques for parallel protocol composition completely break in the asynchronous setting. Specifically, we rule out the possibility of any black-box compiler for the parallel composition of arbitrary protocols. On the positive side, we introduce a round-preserving compiler for a restricted class of protocols (which includes all existing asynchronous MPC protocols) that achieves parallel composition in asynchronous networks.

Joint work with Ran Cohen, Juan Garay, Rutvik Patel, and Vassilis Zikas.

Batch Arguments to NIZKs from One-Way Functions

Eli Bradley (UT Austin)

Succinctness and zero-knowledge are two fundamental properties in the study of cryptographic proof systems. Several recent works have formalized the connections between these two notions by showing how to realize non-interactive zero-knowledge (NIZK) arguments from succinct non-interactive arguments. Specifically, Champion and Wu (CRYPTO 2023) as well as Bitansky, Kamath, Paneth, Rothblum, and Vasudevan (STOC 2024) recently showed how to construct a NIZK argument for NP from a (somewhere-sound) non-interactive batch argument (BARG) and a dual-mode commitment scheme (and in the case of the Champion-Wu construction, a local pseudorandom generator). The main open question is whether a BARG suffices for a NIZK (just assuming one-way functions).

In this talk, I will show that an adaptively-sound BARG for NP together with an one-way function imply a computational NIZK argument for NP. Using complexity leveraging, adaptively-sound BARGs can be based on a sub-exponentially-secure somewhere sound BARG. Taken together, we obtain a NIZK argument for NP from one-way functions and a sub-exponentially-secure somewhere-sound BARG for NP. I then show that if we instead start with public-key encryption instead of one-way functions, then a polynomially-secure somewhere-sound batch argument for NP suffices for the same implication. As a corollary, this means a somewhere-sound BARG can be used to generically upgrade any semantically-secure public-key encryption scheme into one secure against chosen-ciphertext attacks. More broadly, our results demonstrate that constructing non-interactive batch arguments for NP is essentially no easier than constructing NIZK arguments for NP.

Joint work with Brent Waters and David J. Wu.