## CryptoDB

### Julian Loss

#### Publications

**Year**

**Venue**

**Title**

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.

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)
- Manuel Barbosa (1)
- Balthazar Bauer (1)
- Fabrice Benhamouda (1)
- Erica Blum (4)
- Georg Fuchsbauer (2)
- Eduard Hauck (2)
- Julia Kastner (1)
- Jonathan Katz (6)
- Eike Kiltz (4)
- Tancrède Lepoint (1)
- Chen-Da Liu-Zhang (3)
- Ueli Maurer (1)
- Tal Moran (1)
- Ngoc Khanh Nguyen (1)
- Michele Orrù (1)
- Jiaxin Pan (1)
- Mariana Raykova (1)
- Michael Rosenberg (1)
- Daniel Tschudi (1)
- Jiayu Xu (3)