Texas Crypto Day

The first Texas Crypto Day was held at Texas A&M University on December 2, 2022.

Program

10:00-10:30	Coffee
10:30-11:30	Sanjam Garg (UC Berkeley and NTT Research) Invited Talk: Threshold Signatures in the Multiverse
11:30-11:55	Tianyi Liu (Texas A&M) Zero-Knowledge Proof with Fully Distributed Proof Generation
11:55-1:00	Lunch
1:00-1:25	George Lu (UT Austin) Registered Attribute-Based Encryption
1:25-1:50	Rachit Garg (UT Austin) Fully Succinct and Updatable Batch Arguments for NP from Indistinguishability Obfuscation
1:50-2:15	Xiao Liang (Rice University) A New Approach to Post-Quantum Non-Malleability
2:15-2:45	Coffee Break
2:45-3:10	Rutvik Patel (Texas A&M) Universally Composable Almost-Everywhere Secure Computation
3:10-3:35	Kirill Morozov (UNT) Multi-Tier Reputation for Data Cooperatives
3:35-4:00	Yvo Desmedt (UT Dallas) The Impact of Outdated Crypto Books on Research: Anonymity Revisited

Abstracts

Threshold Signatures in the Multiverse

Sanjam Garg (UC Berkeley and NTT Research)

In this talk, I will introduce a new notion of multiverse threshold signatures (MTS). In an MTS scheme, multiple universes – each defined by a set of (possibly overlapping) signers and a specific security threshold – can co-exist. A universe can be (adaptively) created via a non-interactive asynchronous setup. Each party in the multiverse holds constant-sized keys and releases compact signatures with size and computation time both independent of the number of universes. Given sufficient partial signatures over a message from the members of a specific universe, an aggregator can produce a short aggregate signature relative to that universe. I will present a new construction of MTS, our implementation efforts and envisioned applications to decentralized oracle networks.

This is joint work with Leemon Baird, Abhishek Jain, Pratyay Mukherjee, Rohit Sinha, Mingyuan Wang, and Yinuo Zhang.

Zero-Knowledge Proof with Fully Distributed Proof Generation

Tianyi Liu (Texas A&M)

A zero-knowledge proof (ZKP) is a cryptographic tool that allows a prover to prove the correctness of an NP statement to a verifier without disclosing the witness. With the recent developement of succinct zero-knowledge proof schemes, there are many efficient ZKP systems with applications in various areas. One of the applications is to improve the scalability of blockchains and crypto-currencies via the techniques of ZK-Rollup and zkEVM. In blockchains, users post all transactions on the chain for others to verify their validity, and thus the throughput of transactions is very low in practice. With succinct ZKPs, a layer-2 node can generate a proof for the correctness of thousands of transactions and post the short proof on-chain. In this way, both the on-chain storage and the time to verify the transactions are reduced significantly, improving the scalability of blockchains. This approach has been used by many blockchains in practice.

However, the main challenge in this solution is the overhead of the prover time and space. Currently, on a single powerful machine, the proof can only batch around 2000 transactions and it takes minutes to generate one proof. To address this issue, in this talk, we will present our ongoing work to speed up the prover time and improve the scalability via a distributed generation of ZKPs. Building on a recent ZKP scheme named Plonk, we are able to develop a distributed protocol for data parallel circuits with minimum communication and synchronization among the machines. Each machine only sends O(1) messages in 2 rounds and the final proof size remains O(1) as in the original Plonk. With such a distributed ZKP scheme, users can help with the proof generation in zk-Rollup and zk-EVM and both the efficiency and the scalability can be improved by a factor of M using M machines.

This is joint work with Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang and Dawn Song.

Registered Attribute-Based Encryption

George Lu (UT Austin)

Attribute-based encryption (ABE) generalizes public-key encryption and enables fine-grained control to encrypted data. However, ABE upends the traditional trust model of public-key encryption by requiring a single trusted authority to issue decryption keys. A compromised central authority has the ability to decrypt every ciphertext in the system.

This work introduces registered ABE, a primitive that allows users to generate secret keys on their own and then register the associated public key with a “key curator” along with their attributes. The key curator aggregates the public keys from the different users into a single compact master public key. To decrypt, users occasionally need to obtain helper decryption keys from the key curator which they combine with their own secret keys. We require that the size of the aggregated public key, the helper decryption keys, the ciphertexts, as well as the encryption/decryption times to be polylogarithmic in the number of registered users. Moreover, the key curator is entirely transparent and maintains no secrets. Registered ABE generalizes the notion of registration-based encryption (RBE) introduced by Garg et al. (TCC 2018), who focused on the simpler setting of identity-based encryption.

We construct a registered ABE scheme that supports an a priori bounded number of users and policies that can be described by a linear secret sharing scheme (e.g., monotone Boolean formulas) from assumptions on composite-order pairing groups (the same pairing-based assumptions previously used to construct vanilla ABE). Notably, our approach deviates sharply from previous techniques for constructing RBE and only makes black-box use of cryptography. All existing RBE constructions (a weaker notion than registered ABE) rely on heavy non-black-box techniques. In fact, the encryption and decryption costs of our construction are comparable to those of vanilla pairing-based ABE. Finally, as a feasibility result, we show how to construct a registered ABE scheme that supports general policies and an arbitrary number of users from indistinguishability obfuscation and somewhere statistically binding hash functions.

This is joint work with Susan Hohenberger, Brent Waters, and David Wu.

Fully Succinct and Updatable Batch Arguments for NP from Indistinguishability Obfuscation

Rachit Garg (UT Austin)

Non-interactive batch arguments for \(\mathsf{NP}\) provide a way to amortize the cost of \(\mathsf{NP}\) verification across multiple instances. In particular, they allow a prover to convince a verifier of multiple \(\mathsf{NP}\) statements with communication that scales sublinearly in the number of instances.

In this work, we study fully succinct batch arguments for \(\mathsf{NP}\) in the common reference string (CRS) model where the length of the proof scales not only sublinearly in the number of instances \(T\), but also sublinearly with the size of the \(\mathsf{NP}\) relation. Batch arguments with these properties are special cases of succinct non-interactive arguments (SNARGs); however, existing constructions of SNARGs either rely on idealized models or strong non-falsifiable assumptions. The one exception is the Sahai-Waters SNARG based on indistinguishability obfuscation. However, when applied to the setting of batch arguments, we must impose an a priori bound on the number of instances. Moreover, the size of the common reference string scales linearly with the number of instances.

We give a direct construction of a fully succinct batch argument for \(\mathsf{NP}\) that supports an unbounded number of statements from indistinguishability obfuscation and one-way functions. Then, by additionally relying on a somewhere statistically-binding (SSB) hash function, we show how to extend our construction to obtain a fully succinct and updatable batch argument. In the updatable setting, a prover can take a proof \(\pi\) on \(T\) statements \((x_1, \ldots, x_T)\) and “update” it to obtain a proof \(\pi'\) on \((x_1, \ldots, x_T, x_{T + 1})\). Notably, the update procedure only requires knowledge of a (short) proof for \((x_1, \ldots, x_T)\) along with a single witness \(w_{T + 1}\) for the new instance \(x_{T + 1}\). Importantly, the update does not require knowledge of witnesses for \(x_1, \ldots, x_T\).

This is joint work with Kristin Sheridan, Brent Waters, and David Wu.

A New Approach to Post-Quantum Non-Malleability

Xiao Liang (Rice University)

We provide the first constant-round construction of post-quantum non-malleable commitments under the minimal assumption that post-quantum one-way functions exist. We achieve the standard notion of non-malleability with respect to commitments. Prior constructions required Ω(log*λ) rounds under the same assumption.

We achieve our results through a new technique for constant-round non-malleable commitments which is easier to use in the post-quantum setting. The technique also yields an almost elementary proof of security for constant-round non-malleable commitments in the classical setting, which may be of independent interest.

As an application, when combined with existing work, our results yield the first constant-round post-quantum secure multiparty computation under the polynomial hardness of quantum fully-homomorphic encryption and quantum learning with errors.

This is joint work with Omkant Pandey and Takashi Yamakawa.

Universally Composable Almost-Everywhere Secure Computation

Rutvik Patel (Texas A&M)

Most existing work on secure multi-party computation (MPC) ignores a key idiosyncrasy of modern communication networks, that there are a limited number of communication paths between any two nodes, many of which might even be corrupted. The problem becomes particularly acute in the information-theoretic setting, where the lack of trusted setups (and the cryptographic primitives they enable) makes communication over sparse networks more challenging. The work by Garay and Ostrovsky [EUROCRYPT’08] on almost-everywhere MPC (AE-MPC), introduced “best-possible security” properties for MPC over such incomplete networks, where necessarily some of the honest parties may be excluded from the computation.

In this work, we provide a universally composable definition of almost-everywhere security, which allows us to automatically and accurately capture the guarantees of AE-MPC (as well as AE-communication, the analogous ‘‘best-possible security’’ version of secure communication) in the Universal Composability (UC) framework of Canetti. Our results offer the first simulation-based treatment of this important but under-investigated problem, along with the first simulation-based proof of AE-MPC. To achieve that goal, we state and prove a general composition theorem, which makes precise the level or “quality” of AE-security that is obtained when a protocol's hybrids are replaced with almost-everywhere components.

This is joint work with Nishanth Chandran, Pouyan Forghani, Juan Garay, Rafail Ostrovsky and Vassilis Zikas.

Multi-Tier Reputation for Data Cooperatives

Kirill Morozov (UNT)

Data cooperatives allow their members–the data owners–to pool their digital assets together for processing and access management. In this context, reputation is an important measure of trust, which can effectively complement financial assets in the decentralized scenario, also providing incentives for users’ honest behavior. We present a decentralized data cooperative system based on the Proof-of-Reputation and Proof-of-Stake blockchains. In order to provide inclusivity for low reputation (newly joined) users, which is required in our community based scenario, we use the tier-based committee selection introduced by Kleinrock et al. at Indocrypt 2020. As the underlying Proof-of-Stake system, we use Snow White due to its convenient properties such as flexible committee selection and user participation.

This is joint work with Abiola Salau, Ram Dantu, Kritagya Upadhyay, and Syed Badruddoja.

The Impact of Outdated Crypto Books on Research: Anonymity Revisited

Yvo Desmedt (UT Dallas)

Book authors often “copy” chapters from earlier books, implying that new books might be outdated. Worse, today we have so many security venues, that we find applied crypto “everywhere”. Unfortunately, these working on applying crypto do not check updated literature as is evident from work published at, e.g., at USENIX. To give an example we focus on anonymity, in particular the paper published in 2019 (IEEE Tr. Inf. Th.).