## CryptoDB

### Julian Loss

#### Publications

**Year**

**Venue**

**Title**

2022

ASIACRYPT

The Abe-Okamoto Partially Blind Signature Scheme Revisited
📺
Abstract

Partially blind signatures, an extension of ordinary blind signatures, are a primitive with wide applications in e-cash and electronic voting. One of the most efficient schemes to date is the one by Abe and Okamoto (CRYPTO 2000), whose underlying idea - the OR-proof technique - has served as the basis for several works.
We point out several subtle flaws in the original proof of security, and provide a new detailed and rigorous proof, achieving similar bounds as the original work. We believe our insights on the proof strategy will find useful in the security analyses of other OR-proof-based schemes.

2022

PKC

On Pairing-Free Blind Signature Schemes in the Algebraic Group Model
📺
Abstract

Studying the security and efficiency of blind signatures is an
important goal for privacy sensitive applications. In particular, for large-
scale settings (e.g., cryptocurrency tumblers), it is important for schemes
to scale well with the number of users in the system. Unfortunately, all
practical schemes either 1) rely on (very strong) number theoretic hard-
ness assumptions and/or computationally expensive pairing operations
over bilinear groups, or 2) support only a polylogarithmic number of
concurrent (i.e., arbitrarily interleaved) signing sessions per public key.
In this work, we revisit the security of two pairing-free blind signature
schemes in the Algebraic Group Model (AGM) + Random Oracle Model
(ROM). Concretely,
1. We consider the security of Abe’s scheme (EUROCRYPT ‘01), which
is known to have a flawed proof in the plain ROM. We adapt the
scheme to allow a partially blind variant and give a proof of the new
scheme under the discrete logarithm assumption in the AGM+ROM,
even for (polynomially many) concurrent signing sessions.
2. We then prove that the popular blind Schnorr scheme is secure un-
der the one-more discrete logarithm assumption if the signatures
are issued sequentially. While the work of Fuchsbauer et al. (EURO-
CRYPT ‘20) proves the security of the blind Schnorr scheme for con-
current signing sessions in the AGM+ROM, its underlying assump-
tion, ROS, is proven false by Benhamouda et al. (EUROCRYPT
‘21) when more than polylogarithmically many signatures are issued.
Given the recent progress, we present the first security analysis of the
blind Schnorr scheme in the slightly weaker sequential setting. We
also show that our security proof reduces from the weakest possible
assumption, with respect to known reduction techniques.

2022

CRYPTO

(Nondeterministic) Hardness vs. Non-Malleability
📺
Abstract

We present the first truly explicit constructions of \emph{non-malleable codes} against tampering by bounded polynomial size circuits. These objects imply unproven circuit lower bounds and our construction is secure provided $\Eclass$ requires exponential size nondeterministic circuits, an assumption from the derandomization literature.
Prior works on NMC for polysize circuits, either required an untamperable CRS [Cheraghchi, Guruswami ITCS'14; Faust, Mukherjee, Venturi, Wichs EUROCRYPT'14] or very strong cryptographic assumptions [Ball, Dachman-Soled, Kulkarni, Lin, Malkin EUROCRYPT'18; Dachman-Soled, Komargodski, Pass CRYPTO'21]. Both of works in the latter category only achieve non-malleability with respect to efficient distinguishers and, more importantly, utilize cryptographic objects for which no provably secure instantiations are known outside the random oracle model. In this sense, none of the prior yields fully explicit codes from non-heuristic assumptions. Our assumption is not known to imply the existence of one-way functions, which suggests that cryptography is unnecessary for non-malleability against this class.
Technically, security is shown by \emph{non-deterministically} reducing polynomial size tampering to split-state tampering. The technique is general enough that it allows us to to construct the first \emph{seedless non-malleable extractors} [Cheraghchi, Guruswami TCC'14] for sources sampled by polynomial size circuits [Trevisan, Vadhan FOCS'00] (resp.~recognized by polynomial size circuits [Shaltiel CC'11]) and tampered by polynomial size circuits. Our construction is secure assuming $\Eclass$ requires exponential size $\Sigma_4$-circuits (resp. $\Sigma_3$-circuits), this assumption is the state-of-the-art for extracting randomness from such sources (without non-malleability).
Several additional results are included in the full version of this paper [Eprint 2022/070].
First, we observe that non-malleable codes and non-malleable secret sharing [Goyal, Kumar STOC'18] are essentially equivalent with respect to polynomial size tampering. In more detail, assuming $\Eclass$ is hard for exponential size nondeterministic circuits, any efficient secret sharing scheme can be made non-malleable against polynomial size circuit tampering.
Second, we observe that the fact that our constructions only achieve inverse polynomial (statistical) security is inherent. Extending a result from [Applebaum, Artemenko, Shaltiel, Yang CC'16] we show it is impossible to do better using black-box reductions. However, we extend the notion of relative error from [Applebaum, Artemenko, Shaltiel, Yang CC'16] to non-malleable extractors and show that they can be constructed from similar assumptions.
Third, we observe that relative-error non-malleable extractors can be utilized to render a broad class of cryptographic primitives tamper and leakage resilient, while preserving negligible security guarantees.

2022

CRYPTO

PI-Cut-Choo and Friends: Compact Blind Signatures via Parallel Instance Cut-and-Choose and More
📺
Abstract

Blind signature schemes are one of the best-studied tools for privacy-preserving authentication. Unfortunately, known constructions of provably secure blind signatures either rely on non-standard hardness assumptions, or require parameters that grow linearly with the number of concurrently issued signatures, or involve prohibitively inefficient general techniques such as general secure two-party computation.
Recently, Katz, Loss and Rosenberg (ASIACRYPT'21) gave a technique that, for the security parameter n, transforms blind signature schemes secure for O(log n) concurrent executions of the blind signing protocol into ones that are secure for any poly(n) concurrent executions.
This transform has two drawbacks that we eliminate in this paper: 1) the communication complexity of the resulting blind signing protocol grows linearly with the number of signing interactions; 2) the resulting schemes inherit a very loose security bound from the underlying scheme and, as a result, require impractical parameter sizes.
In this work, we give an improved transform for obtaining a secure blind signing protocol tolerating any poly(n) concurrent executions from one that is secure for O(log n) concurrent executions.
While preserving the advantages of the original transform, the communication complexity of our new transform only grows logarithmically with the number of interactions.
Under the CDH and RSA assumptions, we improve on this generic transform in terms of concrete efficiency and give (1) a BLS-based blind signature scheme over a standard-sized group where signatures are of size roughly 3 KB and communication per signature is roughly 120 KB; and (2) an Okamoto-Guillou-Quisquater-based blind signature scheme with signatures and communication of roughly 9 KB and 8 KB, respectively.

2022

CRYPTO

Gossiping for Communication-Efficient Broadcast
📺
Abstract

Byzantine Broadcast is crucial for many cryptographic protocols such as secret sharing, multiparty computation and blockchain consensus. In this paper we apply \emph{gossiping} (propagating a message by sending to a few random parties who in turn do the same, until the message is delivered) and propose new communication-efficient protocols, under dishonest majority, for Single-Sender Broadcast (BC) and Parallel Broadcast (PBC), improving the state-of-the-art in several ways.
As our first warm-up result, we give a randomized protocol for BC which achieves $O(n^2\kappa^2)$ communication complexity from plain public key setup assumptions. This is the first protocol with subcubic communication in this setting, but does so only against static adversaries.
Using some ideas from our BC protocol, we then move to our central contribution and present two protocols for PBC that are secure against adaptive adversaries. To the best of our knowledge we are the first to study PBC \emph{specifically}: All previous approaches for parallel BC (PBC) naively run $n$ instances of single-sender Broadcast, increasing the communication complexity by an undesirable factor of $n$. Our insight of avoiding black-box invocations of BC is particularly crucial for achieving our asymptotic improvements. In particular:
\begin{enumerate}
\item Our first PBC protocol achieves $\tilde{O}(n^3\kappa^2)$ communication complexity and relies only on plain public key setup assumptions.
\item Our second PBC protocol uses trusted setup and achieves nearly optimal communication complexity $\tilde{O}(n^2\kappa^4)$.
\end{enumerate}
Both PBC protocols yield an almost linear improvement over the best known solutions involving $n$ parallel invocations of the respective BC protocols such as those of Dolev and Strong (SIAM Journal on Computing, 1983) and Chan et al. (Public Key Cryptography, 2020). Central to our PBC protocols is a new problem that we define and solve, that we call ``{Converge}''. In {Converge}, parties must run an adaptively-secure and \emph{efficient} protocol such that by the end of the protocol, the honest parties that remain possess a superset of the union of the inputs of the initial honest parties.

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.

2022

ASIACRYPT

Efficient Adaptively-Secure Byzantine Agreement for Long Messages
📺
Abstract

We investigate the communication complexity of Byzantine agreement
protocols for long messages against an adaptive adversary. In this setting, prior $n$-party protocols either achieved a communication complexity of $O(nl\cdot\poly(\kappa))$ or $O(nl + n^2 \cdot \poly(\kappa))$ for $l$-bit long messages and security parameter $\kappa$. We improve the state of the art by presenting protocols with communication complexity $O(nl + n \cdot \poly(\kappa))$ in both the synchronous and asynchronous communication models. The synchronous protocol tolerates $t \le (1-\epsilon) \frac{n}{2}$ corruptions and assumes a VRF setup, while the asynchronous protocol tolerates $t \le (1-\epsilon) \frac{n}{3}$ corruptions under further cryptographic assumptions. Our protocols are very simple and combine subcommittee election with the recent approach of Nayak et al. (DISC'20). Surprisingly, the analysis of our protocols is 'all but simple' and involves an interesting new application of Mc Diarmid's inequality to obtain 'almost optimal' corruption thresholds.

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

EUROCRYPT

On the (in)security of ROS
Abstract

We present an algorithm solving the ROS (Random inhomogeneities in a Overdetermined Solvable system of linear equations) problem mod p in polynomial time for $l > log p$ dimensions. Our algorithm can be combined with Wagner's attack, and leads to a sub-exponential solution for any dimension $l$ with best complexity known so far.
When concurrent executions are allowed, our algorithm leads to practical attacks against unforgeability of blind signature schemes such as Schnorr and Okamoto--Schnorr blind signatures, threshold signatures such as GJKR and the original version of FROST, multisignatures such as CoSI and the two-round version of MuSig, partially blind signatures such as Abe--Okamoto, and conditional blind signatures such as ZGP17. Schemes for e-cash and anonymous credentials (such as Anonymous Credentials Light) inspired from the above are also affected.

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

Always Have a Backup Plan: Fully Secure Synchronous MPC with Asynchronous Fallback
📺
Abstract

Protocols for secure Multi-Party Computation (MPC) can be classified according to the underlying communication model. Two prominent communication models considered in the literature are the synchronous and asynchronous models, which considerably differ in terms of the achievable security guarantees. Synchronous MPC protocols can achieve the optimal corruption threshold $n/2$ and allow every party to give input, but become completely insecure when synchrony assumptions are violated. On the other hand, asynchronous MPC protocols remain secure under arbitrary network conditions, but can tolerate only $n/3$ corruptions and parties with slow connections unavoidably cannot give input.
A natural question is whether there exists a protocol for MPC that can tolerate up to $t_s < n/2$ corruptions under a synchronous network and $t_a < n/3$ corruptions even when the network is asynchronous. We answer this question by showing tight feasibility and impossibility results. More specifically, we show that such a protocol exists if and only if $t_a + 2t_s < n$ and the number of inputs taken into account under an asynchronous network is at most $n-t_s$.

2020

CRYPTO

A Classification of Computational Assumptions in the Algebraic Group Model
📺
Abstract

We give a taxonomy of computational assumptions in the algebraic group model (AGM). We first analyze the Uber assumption family for bilinear groups defined by Boyen and then extend it in multiple ways to cover assumptions such as Gap Diffie-Hellman and the LRSW assumption.
We show that in the AGM every member of these families reduces to the q-discrete logarithm (DL) problem, for some q that depends on the degrees of the polynomials defining the assumption.
Using the meta-reduction technique, we then separate (q+1)-DL from q-DL, which thus yields a classification of all members of the extended Uber-assumption families. We finally show that there are strong assumptions, such as one-more DL, that provably fall outside our classification, as we prove that they cannot be reduced to q-DL even in the AGM.

2020

CRYPTO

Lattice-Based Blind Signatures, Revisited
📺
Abstract

We observe that all previously known lattice-based blind signatures schemes contain subtle flaws in their security proofs (e.g.,~Rückert, ASIACRYPT '08) or can be attacked (e.g., BLAZE by Alkadri et al., FC~'20). Motivated by this, we revisit the problem of constructing blind signatures from standard lattice assumptions. We propose a new three-round lattice-based blind signature scheme whose security can be proved, in the random oracle model, from the standard SIS assumption. Our starting point is a modified version of the insecure three-round BLAZE scheme, which itself is based Lyubashevsky's three-round identification scheme combined with a new aborting technique to reduce the correctness error. Our proof builds upon and extends the recent modular framework for blind signatures of Hauck, Kiltz, and Loss (EUROCRYPT~'19). It also introduces several new techniques to overcome the additional challenges posed by the correctness error which is inherent to all lattice-based constructions.
While our construction is mostly of theoretical interest, we believe it to be an important stepping stone for future works in this area.

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}.

2020

ASIACRYPT

MPC with Synchronous Security and Asynchronous Responsiveness
📺
Abstract

Two paradigms for secure MPC are synchronous and asynchronous
protocols. While synchronous protocols tolerate more corruptions and allow every party to give its input, they are very slow because the speed depends on the conservatively assumed worst-case delay $\Delta$ of the network. In contrast, asynchronous protocols allow parties to obtain output as fast as the actual network allows, a property called \emph{responsiveness}, but unavoidably have lower resilience and parties with slow network connections cannot give input.
It is natural to wonder whether it is possible to leverage synchronous MPC protocols to achieve responsiveness, hence obtaining the advantages of both paradigms: full security with responsiveness up to t corruptions, and 'extended' security (full security or security with unanimous abort) with no responsiveness up to a larger threshold T of corruptions. We settle the question by providing matching feasibility and impossibility results:
-For the case of unanimous abort as extended security, there is an MPC protocol if and only if T + 2t < n.
-For the case of full security as extended security, there is an MPC protocol if and only if T < n/2 and T + 2t < n. In particular, setting t = n/4 allows to achieve a fully secure MPC for honest majority, which in addition benefits from having substantial responsiveness.

2019

EUROCRYPT

A Modular Treatment of Blind Signatures from Identification Schemes
📺
Abstract

We propose a modular security treatment of blind signatures derived from linear identification schemes in the random oracle model. To this end, we present a general framework that captures several well known schemes from the literature and allows to prove their security. Our modular security reduction introduces a new security notion for identification schemes called One-More-Man In the Middle Security which we show equivalent to the classical One-More-Unforgeability notion for blind signatures.We also propose a generalized version of the Forking Lemma due to Bellare and Neven (CCS 2006) and show how it can be used to greatly improve the understandability of the classical security proofs for blind signatures schemes by Pointcheval and Stern (Journal of Cryptology 2000).

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$$.

2018

CRYPTO

The Algebraic Group Model and its Applications
📺
Abstract

One of the most important and successful tools for assessing hardness assumptions in cryptography is the Generic Group Model (GGM). Over the past two decades, numerous assumptions and protocols have been analyzed within this model. While a proof in the GGM can certainly provide some measure of confidence in an assumption, its scope is rather limited since it does not capture group-specific algorithms that make use of the representation of the group.To overcome this limitation, we propose the Algebraic Group Model (AGM), a model that lies in between the Standard Model and the GGM. It is the first restricted model of computation covering group-specific algorithms yet allowing to derive simple and meaningful security statements. To prove its usefulness, we show that several important assumptions, among them the Computational Diffie-Hellman, the Strong Diffie-Hellman, and the interactive LRSW assumptions, are equivalent to the Discrete Logarithm (DLog) assumption in the AGM. On the more practical side, we prove tight security reductions for two important schemes in the AGM to DLog or a variant thereof: the BLS signature scheme and Groth’s zero-knowledge SNARK (EUROCRYPT 2016), which is the most efficient SNARK for which only a proof in the GGM was known. Our proofs are quite simple and therefore less prone to subtle errors than those in the GGM.Moreover, in combination with known lower bounds on the Discrete Logarithm assumption in the GGM, our results can be used to derive lower bounds for all the above-mentioned results in the GGM.

#### Program Committees

- Eurocrypt 2021

#### Coauthors

- Michel Abdalla (1)
- Andreea Alexandru (1)
- Marshall Ball (1)
- Manuel Barbosa (1)
- Balthazar Bauer (1)
- Fabrice Benhamouda (1)
- Amey Bhangale (1)
- Erica Blum (5)
- Rutchathon Chairattana-Apirom (1)
- Dana Dachman-Soled (1)
- Georg Fuchsbauer (2)
- Lucjan Hanzlik (1)
- Eduard Hauck (2)
- Julia Kastner (2)
- Jonathan Katz (7)
- Eike Kiltz (4)
- Tancrède Lepoint (1)
- Chen-Da Liu-Zhang (4)
- Anna Lysyanskaya (1)
- Ueli Maurer (1)
- Tal Moran (1)
- Kartik Nayak (1)
- Ngoc Khanh Nguyen (1)
- Michele Orrù (1)
- Jiaxin Pan (1)
- Charalampos Papamanthou (1)
- Mariana Raykova (1)
- Michael Rosenberg (1)
- Daniel Tschudi (1)
- Georgios Tsimos (1)
- Benedikt Wagner (1)
- Jiayu Xu (4)