Texas Crypto Day

The Texas Crypto Day is a recurrent one-day workshop about cryptography research held in different locations in Texas. If you are interested in receiving information about future events, please subscribe to the texas-crypto-day mailing list.

Current organizers: Yvo Desmedt, Juan Garay, Kirill Morozov, Brent Waters, David Wu

Former organizers: Yupeng Zhang

Upcoming Event

The next Texas Crypto Day will be held at T.S. Painter Hall (PAI 5.42) at UT Austin on April 25, 2025. The nearest parking garage is San Jacinto Garage. From there, it is an 8-minute walk to Painter Hall.

Please register here if you are interested in attending. Registration is free. A tentative program is provided below:

Program

10:00-10:30am	Coffee
10:30-11:30am	Elaine Shi (CMU) Invited Talk: Foundations of Decentralized Mechanism Design
11:30-11:50am	Coffee
11:50-12:15pm	Nai-Hui Chia (Rice University) New Results on Quantum Commitments
12:15-2pm	Lunch (on your own)
2:00-2:25pm	Alexandra Henzinger (MIT) Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse LPN
2:25-2:50pm	Daniel Collins (Texas A&M) Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement
2:50-3:10pm	Coffee
3:10-3:35pm	Jeff Champion (UT Austin) Registered ABE and Adaptively-Secure Broadcast Encryption from Succinct LWE
3:35-4:00pm	Yvo Desmedt (UT Dallas) TBD

Abstracts

Foundations of Decentralized Mechanism Design

Elaine Shi (CMU)

In classical auction design, we take it for granted that the auctioneer is trusted and always implements the auction's rules honestly. This assumption, however, no longer holds in modern auctions based on blockchains, or those mediated by third-party platforms such as Google. For example, in blockchain-based auctions, the consensus nodes that partly serve as the auctioneer are incentivized to deviate from honest behavior if profitable. Third-party auction platforms such as Google have also been involved in high-profile anti-trust lawsuits for manipulating their auctions.

In this talk, I will describe our recent work on decentralized mechanism design, where we aim to build a new scientific foundation for emerging auctions that are not backed by a trusted auctioneer. I will characterize the mathematical landscape of decentralized mechanism design, by showing several infeasibility and feasibility results. I will also highlight how cryptography can play an essential role for bypassing impossibility results in decentralized mechanism design, leading to a new class of auctions that not only incentivize bidders to act honestly, but also incentivize the auctioneer to play by the book.

New Results on Quantum Commitments

Nai-Hui Chia (Rice University)

Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse LPN

Alexandra Henzinger (MIT)

In this talk, I will show how to construct somewhat homomorphic encryption from the sparse learning-parities-with-noise problem, along with an assumption that implies linearly homomorphic encryption (e.g., the decisional Diffie-Hellman or decisional composite residuosity assumptions). The resulting schemes support an a-priori bounded number of homomorphic operations: \(o(\log \lambda)\) multiplications followed by \(\mathsf{poly}(\lambda)\) additions, where \(\lambda\) is a security parameter. This gives the first constructions of somewhat homomorphic encryption for the class of bounded-degree polynomials that do not rely on lattice assumptions or bilinear maps. Moreover, our schemes are conceptually simple: much as in Gentry, Sahai, and Waters’ fully homomorphic encryption scheme, ciphertexts in our scheme are matrices, homomorphic addition is matrix addition, and homomorphic multiplication is matrix multiplication.

Joint work with Henry Corrigan-Gibbs, Yael Kalai, and Vinod Vaikuntanathan (to appear at EUROCRYPT 2025).

Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement

Daniel Collins (Texas A&M)

It is well known that a trusted setup allows one to solve the Byzantine agreement problem in the presence of \(t < n/2\) corruptions, bypassing the setup-free \(t < n/3\) barrier. Alas, the overwhelming majority of protocols in the literature have the caveat that their security crucially hinges on the security of the cryptography and setup, to the point where if the cryptography is broken, even a single corrupted party can violate the security of the protocol. Thus these protocols provide higher corruption resilience (\(n/2\) instead of \(n/3\)) for the price of increased assumptions. Is this trade-off necessary?

We further the study of crypto-agnostic Byzantine agreement among parties that answers this question in the negative. Specifically, let \(t_s\) and \(t_i\) denote two parameters such that (1) \(2t_i + t_s < n\), and (2) \(t_i \le t_s < n/2\). Crypto-agnostic Byzantine agreement ensures agreement among honest parties if (1) the adversary is computationally bounded and corrupts up to \(t_s\) parties, or (2) the adversary is computationally unbounded and corrupts up to \(t_i\) parties, and is moreover given all secrets of all parties established during the setup. We propose a compiler that transforms any pair of resilience-optimal Byzantine agreement protocols in the authenticated and information-theoretic setting into one that is crypto-agnostic. Our compiler has several attractive qualities, including using only \(O(kn^2)\) bits for security parameter k over the two underlying Byzantine agreement protocols, and preserving round and communication complexity in the authenticated setting. In particular, our results improve the state-of-the-art in bit complexity by at least two factors of n and provide either early stopping (deterministic) or expected constant round complexity (randomized). We therefore provide fallback security for authenticated Byzantine agreement for free for \(t_i \le n/4\).

Joint work with Yuval Efron and Jovan Komatovic (to appear at EUROCRYPT 2025).

Registered ABE and Adaptively-Secure Broadcast Encryption from Succinct LWE

Jeff Champion (UT Austin)

Registered attribute-based encryption (ABE) is a generalization of public-key encryption that enables fine-grained access control to encrypted data (like standard ABE), but without needing a central trusted authority. In a key-policy registered ABE scheme, users choose their own public and private keys and then register their public keys together with a decryption policy with an (untrusted) key curator. The key curator aggregates all of the individual public keys into a short master public key which serves as the public key for an ABE scheme.

Currently, we can build registered ABE for restricted policies (e.g., Boolean formulas) from pairing-based assumptions and for general policies using witness encryption or indistinguishability obfuscation. In this work, we construct a key-policy registered ABE for general policies (specifically, bounded-depth Boolean circuits) from the \(\ell\)-succinct learning with errors (LWE) assumption in the random oracle model. The ciphertext size in our registered ABE scheme is \(\mathsf{poly}(\lambda, d)\), where \(\lambda\) is a security parameter and \(d\) is the depth of the circuit that computes the policy circuit \(C\). Notably, this is independent of the length of the attribute \(\mathbf{x}\) and is optimal up to the \(\mathsf{poly}(d)\) factor.

Previously, the only lattice-based instantiation of registered ABE uses witness encryption, which relies on private-coin evasive LWE, a stronger assumption than \(\ell\)-succinct LWE. Moreover, the ciphertext size in previous registered ABE schemes that support general policies (i.e., from obfuscation or witness encryption) scales with \(\mathsf{poly}(\lambda, |\mathbf{x}|, |C|)\). The ciphertext size in our scheme depends only on the depth of the circuit (and not the length of the attribute or the size of the policy). This enables new applications to identity-based distributed broadcast encryption.

Our techniques are also useful for constructing adaptively-secure (distributed) broadcast encryption, and we give the first scheme from the \(\ell\)-succinct LWE assumption in the random oracle model. Previously, the only lattice-based broadcast encryption scheme with adaptive security relied on witness encryption in the random oracle model. All other lattice-based broadcast encryption schemes only achieved selective security.