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) Unconditionally Secure Auxiliary-Input Quantum Commitment with Statistical Hiding |
| 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 | Juan Garay (Texas A&M) Rational Protocol Design: Overview and Recent Developments
|
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.
Unconditionally Secure Auxiliary-Input Quantum Commitment with Statistical Hiding
Nai-Hui Chia (Rice University)
We present the first unconditionally secure auxiliary-input quantum commitment scheme with statistical hiding. Our construction resolves an open question posed in [Qia24, MNY24] by proving security even when adversaries are equipped with additional classical advice; however, the scheme fails in the presence of quantum advice. Remarkably, this limitation not only poses a compelling open problem in cryptography but also yields an unconditional separation in quantum complexity theory. Specifically, our findings distinguish the quantum promise complexity classes \(\mathsf{p}/\mathsf{mBQP}/\mathsf{qpoly}\) and \(\mathsf{p}/\mathsf{mBQP}/\mathsf{poly}\)—quantum analogues of the classical \(\mathsf{BQP}/\mathsf{(q)poly}\) classes.
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.
Joint work with Yao-Ching Hsieh and David Wu.
Rational Protocol Design: Overview and Recent Developments
Juan Garay (Texas A&M)
Rational Protocol Design (RPD), introduced by Garay, Katz, Maurer, Tackmann and Zikas [FOCS ’13] leverages the well-established real/ideal paradigm to prove the security of cryptographic protocols against malicious attackers to incorporate participants’ incentives to misbehave. In a nutshell, RPD casts a protocol attack as a two-party game between a rational protocol designer and a rational attacker. The attacker aims at breaking certain security properties, from which he obtains his utility, by choosing an appropriate adversarial strategy corresponding to a central adversary who gets to corrupt parties in a standard cryptographic manner; symmetrically, the goal of the designer is to come up with a protocol which (when executed by the parties who adhere to the protocol) maximizes its own utility. Importantly, RPD allows for the establishment of a partial order of protocols with respect to the property under consideration (e.g., fairness). In this talk, after a brief introduction of the RPD framework, we showcase it in a variety of applications, including secure multi-party computation in the presence of a dishonest majority, fair (reactive) 2-party computation, and the Bitcoin ledger, explaining why Bitcoin continues to work even though majority coalitions are in fact possible.