## CryptoDB

### Jonathan Katz

#### Publications

**Year**

**Venue**

**Title**

2022

ASIACRYPT

An Analysis of the Algebraic Group Model
📺
Abstract

The algebraic group model (AGM), formalized by Fuchsbauer, Kiltz, and Loss, has recently received significant attention. One of the appealing properties of the AGM is that it is viewed as being (strictly) weaker than the generic group model (GGM), in the sense that hardness results for algebraic algorithms imply hardness results for generic algorithms, and generic reductions in the AGM (namely, between the algebraic formulations of two problems) imply generic reductions in the~GGM. We highlight that as the GGM and AGM are currently formalized, this is not true: hardness in the AGM may not imply hardness in the GGM, and a generic reduction in the AGM may not imply a similar reduction in the~GGM.

2022

EUROCRYPT

Post-Quantum Security of the Even-Mansour Cipher
📺
Abstract

The Even-Mansour cipher is a simple method for constructing a (keyed) pseudorandom permutation $E$ from a public random permutation~$P:\bool^n \rightarrow \bool^n$. It is a core ingredient in a wide array of symmetric-key constructions, including several lightweight cryptosystems presently under consideration for standardization by NIST. It is secure against classical attacks, with optimal attacks requiring $q_E$ queries to $E$ and $q_P$ queries to $P$ such that $q_P \cdot q_E \approx 2^n$. If the attacker is given \emph{quantum} access to both $E$ and $P$, however, the cipher is completely insecure, with attacks using $q_P = q_E = O(n)$ queries known.
In any plausible real-world setting, however, a quantum attacker would have only \emph{classical} access to the keyed permutation $E$ implemented by honest parties, while retaining quantum access to $P$. Attacks in this setting with $q_P^2 \cdot q_E \approx 2^n$ are known, showing that security degrades as compared to the purely classical case, but leaving open the question as to whether the Even-Mansour cipher can still be proven secure in this natural ``post-quantum'' setting.
We resolve this open question, showing that any attack in this post-quantum setting requires $q^2_P \cdot q_E + q_P \cdot q_E^2 \approx 2^n$. Our results apply to both the two-key and single-key variants of Even-Mansour. Along the way, we establish several generalizations of results from prior work on quantum-query lower bounds that may be of independent interest.

2022

ASIACRYPT

State Machine Replication under Changing Network Conditions
📺
Abstract

Protocols for state machine replication (SMR) are typically designed for synchronous or asynchronous networks, with a lower corruption threshold in the latter case. Recent network-agnostic protocols are secure when run in either a synchronous or an asynchronous network. We propose two new constructions of network-agnostic SMR protocols that improve on existing protocols in terms of either the adversarial model or communication complexity:
1. an adaptively secure protocol with optimal corruption thresholds and quadratic amortized communication complexity per transaction;
2. a statically secure protocol with near-optimal corruption thresholds and linear amortized communication complexity per transaction.
We further explore SMR protocols run in a network that may change between synchronous and asynchronous arbitrarily often; parties can be uncorrupted (as in the proactive model), and the protocol should remain secure as long as the appropriate corruption thresholds are maintained. We show that purely asynchronous proactive secret sharing is impossible without some form of synchronization between the parties, ruling out a natural approach to proactively secure network-agnostic SMR protocols. Motivated by this negative result, we consider a model where the adversary is limited in the total number of parties it can corrupt over the duration of the protocol and show, in this setting, that our SMR protocols remain secure even under arbitrarily changing network conditions.

2021

ASIACRYPT

Boosting the Security of Blind Signature Schemes
📺
Abstract

Existing blind signature schemes that are secure for polynomially many concurrent executions of the signing protocol are either inefficient or rely on non-standard assumptions (even in the random-oracle model). We show the first efficient blind signature schemes achieving this level of security based on the RSA, quadratic residuosity, and discrete logarithm assumptions (in the random-oracle model). Our core technique involves an extension and generalization of a transform due to
Pointcheval (Eurocrypt~'98) that allows us to convert certain
blind signature schemes that are secure for (concurrently) issuing logarithmically many signatures into ones secure for (concurrently) issuing polynomially many signatures.

2021

ASIACRYPT

Tardigrade: An Atomic Broadcast Protocol for Arbitrary Network Conditions
📺
Abstract

We study the problem of \emph{atomic broadcast}---the underlying problem addressed by blockchain protocols---in the presence of a malicious adversary who corrupts some fraction of the $n$ parties running the protocol.
Existing protocols are either robust for any number of corruptions in a
\emph{synchronous} network (where
messages are delivered within some known
time~$\Delta$) but fail if the synchrony assumption is violated, or tolerate fewer than $n/3$ corrupted parties in an
\emph{asynchronous} network (where messages can be delayed arbitrarily) and cannot tolerate more corruptions even if the network happens to be well behaved.
We design an atomic broadcast protocol (TARDIGRADE) that, for any $t_s \geq t_a$ with $2t_s + t_a < n$, provides security against $t_s$ corrupted parties if the network is synchronous, while remaining secure when $t_a$ parties are corrupted even in an asynchronous network.
We show that TARDIGRADE achieves optimal tradeoffs between $t_s$ and~$t_a$.
Finally, we show a second protocol (UPGRADE) with similar (but slightly weaker) guarantees that achieves per-transaction
communication complexity linear in~$n$.

2021

ASIACRYPT

Algebraic Adversaries in the Universal Composability Framework
📺
Abstract

The algebraic-group model (AGM), which lies between the generic group model and the standard model of computation, provides a means by which to analyze the security of cryptosystems against so-called algebraic adversaries. We formalize the AGM within the framework of universal composability, providing formal definitions for this setting and proving an appropriate composition theorem.
This extends the applicability of the AGM to more-complex protocols, and lays the foundations for analyzing algebraic adversaries in a composable fashion.
Our results also clarify the meaning of composing proofs in the AGM with other proofs and they highlight a natural form of independence between idealized groups that seems inherent to the AGM and has not been made formal before---these insights also apply to the composition of game-based proofs in the AGM.
We show the utility of our model by proving several important protocols universally composable for algebraic adversaries, specifically: (1) the Chou-Orlandi protocol for oblivious transfer, and (2) the SPAKE2 and CPace protocols for password-based authenticated key exchange.

2020

CRYPTO

Better Concrete Security for Half-Gates Garbling (in the Multi-Instance Setting)
📺
Abstract

We study the concrete security of high-performance implementations of half-gates garbling, which all rely on (hardware-accelerated) AES. We find that current instantiations using k-bit wire labels can be completely broken—in the sense that the circuit evaluator learns all the inputs of the circuit garbler—in time O(2k/C), where C is the total number of (non-free) gates that are garbled, possibly across multiple independent executions. The attack can be applied to existing circuit-garbling libraries using k = 80 when C ≈ $10^9$, and would require 267 machine-months and cost about $3500 to implement on the Google Cloud Platform. Since the attack can be entirely parallelized, the attack could be carried out in about a month using ≈ 250 machines.
With this as our motivation, we seek a way to instantiate the hash function in the half-gates scheme so as to achieve better concrete security. We present a construction based on AES that achieves optimal security in the single-instance setting (when only a single circuit is garbled). We also show how to modify the half-gates scheme so that its concrete security does not degrade in the multi-instance setting. Our modified scheme is as efficient as prior work in networks with up to 2 Gbps bandwidth.

2020

CRYPTO

Universally Composable Relaxed Password Authenticated Key Exchange
📺
Abstract

Protocols for password authenticated key exchange (PAKE) allow two parties who share only a weak password to agree on a cryptographic key. We revisit the notion of PAKE in the universal composability (UC) framework, and propose a relaxation of the PAKE functionality of Canetti et al. that we call lazy-extraction PAKE (lePAKE). Our relaxation allows the ideal-world adversary to postpone its password guess until after a session is complete. We argue that this relaxed notion still provides meaningful security in the password-only setting. As our main result, we show that several PAKE protocols that were previously only proven secure with respect to a ``game-based'' definition of security can be shown to UC-realize the lePAKE functionality in the random-oracle model. These include SPEKE, SPAKE2, and TBPEKE, the most efficient PAKE schemes currently known.

2020

TCC

Asynchronous Byzantine Agreement with Subquadratic Communication
📺
Abstract

Understanding the communication complexity of Byzantine agreement (BA) is a fundamental problem in distributed computing. In particular, as protocols are run with a large number of parties (as, e.g., in the context of blockchain protocols), it is important to understand the dependence of the communication on the number of parties~$n$. Although adaptively secure BA protocols with $o(n^2)$ communication are known in the synchronous and partially synchronous settings, no such protocols are known in the fully asynchronous case.
We show here an asynchronous BA protocol with subquadratic communication tolerating an adaptive adversary who can corrupt $f<(1-\epsilon)n/3$ of the parties (for any $\epsilon>0$).
One variant of our protocol assumes initial setup done by a trusted dealer, after which an unbounded number of BA executions can be run; alternately, we can achieve subquadratic \emph{amortized} communication with no prior setup. We also show that some form of setup is needed for (non-amortized) subquadratic BA tolerating $\Theta(n)$ corrupted parties.
As a contribution of independent interest, we show a secure-computation protocol in the same threat model that has $o(n^2)$ communication when computing no-input functionalities with short output (e.g., coin tossing).

2020

TCC

On the Security of Time-Lock Puzzles and Timed Commitments
📺
Abstract

Time-lock puzzles—problems whose solution requires some amount of \emph{sequential} effort—have recently received increased interest (e.g., in the context of verifiable delay functions). Most constructions rely on the sequential-squaring conjecture that computing $g^{2^T} \bmod N$ for a uniform~$g$ requires at least $T$ (sequential) steps. We study the security of time-lock primitives from two perspectives:
1. We give the first hardness result about the sequential-squaring conjecture. Namely, in a quantitative version of the algebraic group model (AGM) that we call the \emph{strong} AGM, we show that any speed up of sequential squaring is as hard as factoring $N$.
2. We then focus on \emph{timed commitments}, one of the most important primitives that can be obtained from time-lock puzzles. We extend existing security definitions to settings that may arise when using timed commitments in higher-level protocols, and give the first construction of \emph{non-malleable} timed commitments. As a building block of independent interest, we also define (and give constructions for) a related primitive called \emph{timed public-key encryption}.

2019

EUROCRYPT

Covert Security with Public Verifiability: Faster, Leaner, and Simpler
Abstract

The notion of covert security for secure two-party computation serves as a compromise between the traditional semi-honest and malicious security definitions. Roughly, covert security ensures that cheating behavior is detected by the honest party with reasonable probability (say, 1/2). It provides more realistic guarantees than semi-honest security with significantly less overhead than is required by malicious security.The rationale for covert security is that it dissuades cheating by parties that care about their reputation and do not want to risk being caught. But a much stronger disincentive is obtained if the honest party can generate a publicly verifiable certificate when cheating is detected. While the corresponding notion of publicly verifiable covert (PVC) security has been explored, existing PVC protocols are complex and less efficient than the best covert protocols, and have impractically large certificates.We propose a novel PVC protocol that significantly improves on prior work. Our protocol uses only “off-the-shelf” primitives (in particular, it avoids signed oblivious transfer) and, for deterrence factor 1/2, has only 20–40% overhead compared to state-of-the-art semi-honest protocols. Our protocol also has, for the first time, constant-size certificates of cheating (e.g., 354 bytes long at the 128-bit security level).As our protocol offers strong security guarantees with low overhead, we suggest that it is the best choice for many practical applications of secure two-party computation.

2019

JOFC

(Efficient) Universally Composable Oblivious Transfer Using a Minimal Number of Stateless Tokens
Abstract

We continue the line of work initiated by Katz (Eurocrypt 2007) on using tamper-proof hardware tokens for universally composable secure computation. As our main result, we show an oblivious-transfer (OT) protocol in which two parties each create and transfer a single, stateless token and can then run an unbounded number of OTs. We also show a more efficient protocol, based only on standard symmetric-key primitives (block ciphers and collision-resistant hash functions), that can be used if a bounded number of OTs suffice. Motivated by this result, we investigate the number of stateless tokens needed for universally composable OT. We prove that our protocol is optimal in this regard for constructions making black-box use of the tokens (in a sense we define). We also show that nonblack-box techniques can be used to obtain a construction using only a single stateless token.

2019

TCC

Synchronous Consensus with Optimal Asynchronous Fallback Guarantees
Abstract

Typically, protocols for Byzantine agreement (BA) are designed to run in either a synchronous network (where all messages are guaranteed to be delivered within some known time $$\varDelta $$ from when they are sent) or an asynchronous network (where messages may be arbitrarily delayed). Protocols designed for synchronous networks are generally insecure if the network in which they run does not ensure synchrony; protocols designed for asynchronous networks are (of course) secure in a synchronous setting as well, but in that case tolerate a lower fraction of faults than would have been possible if synchrony had been assumed from the start.Fix some number of parties n, and $$0< t_a< n/3 \le t_s < n/2$$. We ask whether it is possible (given a public-key infrastructure) to design a BA protocol that is resilient to (1) $$t_s$$ corruptions when run in a synchronous network and (2) $$t_a$$ faults even if the network happens to be asynchronous. We show matching feasibility and infeasibility results demonstrating that this is possible if and only if $$t_a + 2\cdot t_s < n$$.

2019

JOFC

Feasibility and Infeasibility of Secure Computation with Malicious PUFs
Abstract

A recent line of work has explored the use of physically unclonable functions (PUFs) for secure computation, with the goals of (1) achieving universal composability without additional setup and/or (2) obtaining unconditional security (i.e., avoiding complexity-theoretic assumptions). Initial work assumed that all PUFs, even those created by an attacker, are honestly generated. Subsequently, researchers have investigated models in which an adversary can create malicious PUFs with arbitrary behavior. Researchers have considered both malicious PUFs that might be stateful , as well as malicious PUFs that can have arbitrary behavior but are guaranteed to be stateless . We settle the main open questions regarding secure computation in the malicious-PUF model: We prove that unconditionally secure oblivious transfer is impossible, even in the stand-alone setting, if the adversary can construct (malicious) stateful PUFs. We show that if the attacker is limited to creating (malicious) stateless PUFs, then universally composable two-party computation is possible, unconditionally.

2018

CRYPTO

Optimizing Authenticated Garbling for Faster Secure Two-Party Computation
📺
Abstract

Wang et al. (CCS 2017) recently proposed a protocol for malicious secure two-party computation that represents the state-of-the-art with regard to concrete efficiency in both the single-execution and amortized settings, with or without preprocessing. We show here several optimizations of their protocol that result in a significant improvement in the overall communication and running time. Specifically:We show how to make the “authenticated garbling” at the heart of their protocol compatible with the half-gate optimization of Zahur et al. (Eurocrypt 2015). We also show how to avoid sending an information-theoretic MAC for each garbled row. These two optimizations give up to a 2.6$$\times $$× improvement in communication, and make the communication of the online phase essentially equivalent to that of state-of-the-art semi-honest secure computation.We show various optimizations to their protocol for generating AND triples that, overall, result in a 1.5$$\times $$× improvement in the communication and a 2$$\times $$× improvement in the computation for that step.

2018

CRYPTO

Provable Security of (Tweakable) Block Ciphers Based on Substitution-Permutation Networks
📺
Abstract

Substitution-Permutation Networks (SPNs) refer to a family of constructions which build a wn-bit block cipher from n-bit public permutations (often called S-boxes), which alternate keyless and “local” substitution steps utilizing such S-boxes, with keyed and “global” permutation steps which are non-cryptographic. Many widely deployed block ciphers are constructed based on the SPNs, but there are essentially no provable-security results about SPNs.In this work, we initiate a comprehensive study of the provable security of SPNs as (possibly tweakable) wn-bit block ciphers, when the underlying n-bit permutation is modeled as a public random permutation. When the permutation step is linear (which is the case for most existing designs), we show that 3 SPN rounds are necessary and sufficient for security. On the other hand, even 1-round SPNs can be secure when non-linearity is allowed. Moreover, 2-round non-linear SPNs can achieve “beyond-birthday” (up to
$$2^{2n/3}$$
22n/3 adversarial queries) security, and, as the number of non-linear rounds increases, our bounds are meaningful for the number of queries approaching
$$2^n$$
2n. Finally, our non-linear SPNs can be made tweakable by incorporating the tweak into the permutation layer, and provide good multi-user security.As an application, our construction can turn two public n-bit permutations (or fixed-key block ciphers) into a tweakable block cipher working on wn-bit inputs, 6n-bit key and an n-bit tweak (for any
$$w\ge 2$$
w≥2); the tweakable block cipher provides security up to
$$2^{2n/3}$$
22n/3 adversarial queries in the random permutation model, while only requiring w calls to each permutation, and 3w field multiplications for each wn-bit input.

2018

ASIACRYPT

Simple and Efficient Two-Server ORAM
Abstract

We show a protocol for two-server oblivious RAM (ORAM) that is simpler and more efficient than the best prior work. Our construction combines any tree-based ORAM with an extension of a two-server private information retrieval scheme by Boyle et al., and is able to avoid recursion and thus use only one round of interaction. In addition, our scheme has a very cheap initialization phase, making it well suited for RAM-based secure computation. Although our scheme requires the servers to perform a linear scan over the entire data, the cryptographic computation involved consists only of block-cipher evaluations.A practical instantiation of our protocol has excellent concrete parameters: for storing an N-element array of arbitrary size data blocks with statistical security parameter $$\lambda $$, the servers each store 4N encrypted blocks, the client stores $$\lambda +2\log N$$ blocks, and the total communication per logical access is roughly $$10 \log N$$ encrypted blocks.

2018

ASIACRYPT

More is Less: Perfectly Secure Oblivious Algorithms in the Multi-server Setting
Abstract

The problem of Oblivious RAM (ORAM) has traditionally been studied in the single-server setting, but more recently the multi-server setting has also been considered. Yet it is still unclear whether the multi-server setting has any inherent advantages, e.g., whether the multi-server setting can be used to achieve stronger security goals or provably better efficiency than is possible in the single-server case.In this work, we construct a perfectly secure 3-server ORAM scheme that outperforms the best known single-server scheme by a logarithmic factor. In the process we also show, for the first time, that there exist specific algorithms for which multiple servers can overcome known lower bounds in the single-server setting.

2014

TCC

2013

JOFC

Round-Optimal Password-Based Authenticated Key Exchange
Abstract

We show a general framework for constructing password-based authenticated key-exchange protocols with optimal round complexity—one message per party, sent simultaneously—in the standard model, assuming the existence of a common reference string. When our framework is instantiated using bilinear-map-based cryptosystems, the resulting protocol is also (reasonably) efficient. Somewhat surprisingly, our framework can be adapted to give protocols in the standard model that are universally composable while still using only one (simultaneous) round.

2009

ASIACRYPT

2008

EUROCRYPT

#### Program Committees

- Crypto 2020
- Crypto 2017 (Program chair)
- TCC 2016
- Crypto 2016 (Program chair)
- PKC 2015 (Program chair)
- Eurocrypt 2013
- Crypto 2013
- TCC 2012
- Asiacrypt 2012
- Eurocrypt 2011
- Asiacrypt 2010
- PKC 2010
- Eurocrypt 2009
- Crypto 2009
- Eurocrypt 2008
- Asiacrypt 2008
- Asiacrypt 2007
- TCC 2007
- PKC 2007
- Crypto 2006
- TCC 2006
- Eurocrypt 2006
- Crypto 2005
- Asiacrypt 2004
- Crypto 2003

#### Coauthors

- Michel Abdalla (2)
- Gorjan Alagic (1)
- Andreea Alexandru (1)
- Joël Alwen (2)
- Daniel Apon (1)
- Giuseppe Ateniese (1)
- Chen Bai (1)
- Manuel Barbosa (2)
- Adam Bender (2)
- Erica Blum (4)
- Dan Boneh (1)
- Xavier Boyen (1)
- Tatiana Bradley (1)
- Zvika Brakerski (1)
- Enrico Buonanno (1)
- Ran Canetti (5)
- T.-H. Hubert Chan (1)
- Jung Hee Cheon (1)
- Seung Geol Choi (6)
- Kai-Min Chung (1)
- Carlos Cid (1)
- Benoît Cogliati (1)
- Giovanni Di Crescenzo (1)
- Dana Dachman-Soled (4)
- Yevgeniy Dodis (8)
- David Evans (1)
- Serge Fehr (1)
- Nils Fleischhacker (2)
- David Freeman (1)
- Georg Fuchsbauer (1)
- Rosario Gennaro (1)
- Shafi Goldwasser (1)
- S. Dov Gordon (6)
- Vipul Goyal (2)
- Adam Groce (2)
- Siyao Guo (1)
- Chun Guo (1)
- Iftach Haitner (2)
- Shai Halevi (5)
- Carmit Hazay (1)
- Viet Tung Hoang (1)
- Cheng Hong (1)
- Omer Horvitz (3)
- Yan Huang (2)
- Abhishek Jain (1)
- Stanislaw Jarecki (1)
- Seny Kamara (2)
- Vladimir Kolesnikov (2)
- Chiu-Yuen Koo (5)
- Hugo Krawczyk (1)
- Ranjit Kumaresan (3)
- Jooyoung Lee (1)
- Yehuda Lindell (5)
- Feng-Hao Liu (2)
- Chen-Da Liu-Zhang (1)
- Julian Loss (7)
- Wen-jie Lu (1)
- Anna Lysyanskaya (2)
- Philip D. MacKenzie (1)
- Christian Majenz (1)
- Lior Malka (1)
- Alex J. Malozemoff (3)
- Ueli Maurer (2)
- Ruggero Morselli (4)
- Steven Myers (1)
- David Naccache (1)
- Kartik Nayak (1)
- Adam O'Neill (1)
- Rafail Ostrovsky (6)
- Giuseppe Persiano (1)
- Antigoni Polychroniadou (1)
- Tal Rabin (1)
- Samuel Ranellucci (1)
- Vanishree Rao (1)
- Leonid Reyzin (1)
- Michael Rosenberg (1)
- Mike Rosulek (1)
- Amit Sahai (2)
- Dominique Schröder (5)
- Gil Segev (1)
- Jae Hong Seo (1)
- Ronen Shaltiel (2)
- Abhi Shelat (1)
- Elaine Shi (4)
- Ji Sun Shin (2)
- Adam Smith (6)
- Fang Song (1)
- John P. Steinberger (1)
- Björn Tackmann (1)
- Aishwarya Thiruvengadam (4)
- Vinod Vaikuntanathan (5)
- Ivan Visconti (1)
- Shabsi Walfish (1)
- Xiao Wang (5)
- Brent Waters (2)
- Hoeteck Wee (1)
- Chenkai Weng (1)
- Jiayu Xu (3)
- Shouhuai Xu (2)
- Arkady Yerukhimovich (6)
- Yu Yu (1)
- Moti Yung (9)
- Mohammad Zaheri (1)
- Zhe Zhang (1)
- Cong Zhang (1)
- Hong-Sheng Zhou (10)
- Vassilis Zikas (4)