Texas Crypto Day

The 2nd Texas Crypto Day was held at UT Austin on April 14, 2023.

Program

9:45-10:15	Coffee
10:15-11:15	Daniel Wichs (Northeastern and NTT Research) Invited Talk: Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
11:15-11:45	Coffee
11:45-12:10	Yingchen Wang (UT Austin) Hertzbleed: Turning Power Side-Channel Attacks Into Remote Timing Attacks on x86
12:10-1:45	Lunch (on your own)
1:45-2:10	Pouyan Forghani (Texas A&M) Optimal Asynchronous and Multi-valued Oblivious Common Coin — A Detective Story
2:10-2:35	Yu Shen (University of Edinburgh) Permissionless Clock Synchronization with Public Setup
2:35-3:00	Coffee
3:00-3:25	Zhiyong Fang (Texas A&M) Zero-knowledge proofs based on linear codes
3:25-3:50	Jiaxin Guan (Princeton University) A Lower Bound on the Length of Signatures based on Group Actions and Generic Isogenies
3:50-4:15	Yvo Desmedt (UT Dallas) Forencics Aspects of Secret Sharing

Abstracts

Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE

Daniel Wichs (Northeastern and NTT Research)

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 a solution to 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).

Joint work with Wei-Kai Lin and Ethan Mook. To appear at STOC 2023. Recipient of “Best Paper Award.”

Hertzbleed: Turning Power Side-Channel Attacks Into Remote Timing Attacks on x86

Yingchen Wang (UT Austin)

Hertzbleed is a new family of side-channel attacks: frequency side channels. In the worst case, these attacks can allow an attacker to extract cryptographic keys from remote servers that were previously believed to be secure.

Hertzbleed takes advantage of our experiments showing that, under certain circumstances, the dynamic frequency scaling of modern x86 processors depends on the data being processed. This means that, on modern processors, the same program can run at a different CPU frequency (and therefore take a different wall time) when computing, for example, 2022 + 23823 compared to 2022 + 24436.

Hertzbleed is a real, and practical, threat to the security of cryptographic software. We have demonstrated how a clever attacker can use a novel chosen-ciphertext attack against SIKE (Now retired) to perform full key extraction via remote timing, despite SIKE being implemented as “constant time.”

Optimal Asynchronous and Multi-valued Oblivious Common Coin — A Detective Story

Pouyan Forghani (Texas A&M)

An oblivious common coin (OCC) allows n parties, up to t of which might be malicious, to agree on a random common value from a (not necessarily binary) domain. The coin is “oblivious” because parties may not be aware that agreement on a common value has been achieved. OCC is a fundamental tool in the area of multiparty cryptographic protocols. In fact, as shown by Rabin [FOCS ’83], important distributed tasks such as Byzantine agreement (BA) reduce to an OCC, and moreover OCCs enable the circumvention of lower bounds and impossibility results for deterministic protocols. This line of research culminated in the seminal work of Feldman and Micali [STOC ’88] for synchronous networks, and later Canetti and Rabin [STOC ’93] for asynchronous networks, who showed how to construct a binary OCC in the information-theoretic setting, thereby obtaining expected constant-round protocols for synchronous (resp., asynchronous) BA “from scratch.”

Unfortunately, running multiple expected constant-round protocols in parallel, as it would be required by a higher-level protocol where all/multiple parties broadcast a message in the same round, does not guarantee that all of them will terminate in expected constant rounds. In light of this, Ben-Or and El-Yaniv [Distributed Computing ’03] showed how to solve arbitrarily many BA instances concurrently, while preserving the expected round complexity. They gave protocols for both synchronous and asynchronous networks, each relying on the existence of oblivious leader election (which immediately follows from a multi-valued OCC). However, while in the synchronous setting this can be obtained by extending the OCC construction of Feldman and Micali, the asynchronous version cannot be derived from Canetti and Rabin's binary coin without giving up on optimal resiliency (i.e., t < n/3 corruptions). In fact, as we discuss in the talk, an optimal asynchronous and multi-valued OCC does not seem to exist, nor is it straightforward to achieve, rendering an important body of follow-up work unsound.

We address this gap by presenting the first multi-valued OCC protocol that is simultaneously optimally-resilient and asynchronous, without relying on computational assumptions. Our result is built atop existing binary OCC constructions and uses novel combinatorial techniques. Furthermore, we use our OCC to simplify the standard approach for obtaining concurrent asynchronous BA in expected constant rounds, and prove the resulting protocols secure in Canetti's UC framework, a task that, as shown by Cohen et al. [CRYPTO ’16], is particularly challenging for probabilistic-termination protocols.

This is joint work with Ran Cohen, Juan Garay, Rutvik Patel and Vassilis Zikas.

Permissionless Clock Synchronization with Public Setup

Yu Shen (University of Edinburgh)

The permissionless clock synchronization problem asks how it is possible for a population of parties to maintain a system-wide synchronized clock, while their participation rate fluctuates—possibly very widely—over time. The underlying assumption is that parties experience the passage of time with roughly the same speed, but however they may disengage and engage with the protocol following arbitrary (and even chosen adversarially) participation patterns. This (classical) problem has received renewed attention due to the advent of blockchain protocols, and recently it has been solved in the setting of proof of stake, i.e., when parties are assumed to have access to a trusted PKI setup [Badertscher et al., Eurocrypt ’21]. In this work, we present the first proof-of-work (PoW)-based permissionless clock synchronization protocol.

Our construction assumes a public setup (e.g., a CRS) and relies on an honest majority of computational power that, for the first time, is described in a fine-grain timing model that does not utilize a global clock that exports the current time to all parties. As a secondary result of independent interest, our protocol gives rise to the first PoW-based ledger consensus protocol that does not rely on an external clock for the time-stamping of transactions and adjustment of the PoW difficulty.

Joint work with Juan Garay and Aggelos Kiayias.

Zero-knowledge proofs based on linear codes

Zhiyong Fang (Texas A&M)

Zero-knowledge proof (ZKP) allows one party, referred to as the prover, to convince another party, referred to as the verifier, that a statement about the prover’s secret witness is true. Zero-knowledge proof has been widely used in blockchains and crypto-currencies to achieve privacy and improve scalability. However, existing schemes with succinct proof size suffer from a high overhead on the proof generation time, limiting their efficiency and scalability in practice.

In this talk, we will present our recent work on building succinct ZKPs based on linear error-correcting code. The security relies on the good distance of the code and the collision resistant hash functions. The prover time is dominated by the encoding time of the linear code. The scheme is plausibly post-quantum secure and has a transparent setup.

A Lower Bound on the Length of Signatures based on Group Actions and Generic Isogenies

Jiaxin Guan (Princeton University)

We give the first black box lower bound for signature protocols that can be described as group actions, which include many based on isogenies. We show that, for a large class of signature schemes making black box use of a (potentially non-abelian) group action, the signature length must be Ω(λ^2/log λ). Our class of signatures generalizes all known signatures that derive security exclusively from the group action, and our lower bound matches the state of the art, showing that the signature length cannot be improved without deviating from the group action framework.

Forencics Aspects of Secret Sharing

Yvo Desmedt (UT Dallas)

We consider the digital forensics aspects of secret sharing. We investigate the problem of framing which occurs when a coalition is able to calculate the share of a participant who does not belong to it. In the extreme case one authorized coalition can calculate shares of another authorized coalition and use the secret in some way blaming another authorized coalition for their action.

(Paper appeared in IEEE Trans. Inf. Forensics Secur., 2021.)