## CryptoDB

### Julia Hesse

#### Publications

**Year**

**Venue**

**Title**

2021

ASIACRYPT

Security Analysis of CPace
📺
Abstract

In response to standardization requests regarding password-authenticated key exchange (PAKE) protocols, the IRTF working group CFRG has setup a PAKE selection
process in 2019, which led to the selection of the CPace protocol in the balanced setting, in which parties share a common password. In subsequent standardization efforts, the CPace protocol further developed, yielding a protocol family whose actual security guarantees in practical settings are not well understood. In this paper, we provide a comprehensive security analysis of CPace in the universal composability framework. Our analysis is realistic in the sense that it captures adaptive corruptions and refrains from modeling CPace's MapToPoint function that maps field elements to curve points as an idealized function. In order to extend our proofs to different CPace variants optimized for specific elliptic-curve ecosystems, we employ a new approach which represents the assumptions required by the proof as libraries accessed by a simulator. By allowing for the modular replacement of assumptions used in the proof, this new approach avoids a repeated analysis of unchanged protocol parts and lets us efficiently analyze the security guarantees of all the different CPace variants. As a result of our analysis, all of the investigated practical CPace variants enjoy adaptive UC security.

2021

TCC

On the (Ir)Replaceability of Global Setups, or How (Not) to Use a Global Ledger
📺
Abstract

In universally composable (UC) security, a global setup is intended to capture the ideal behavior of a primitive which is accessible by multiple protocols, allowing them to share state. A representative example is the Bitcoin ledger. Indeed, since Bitcoin---and more generally blockchain ledgers---are known to be useful in various scenarios, it has become increasingly popular to capture such ledgers as global setup. Intuitively, one would expect UC to allow us to make security statements about protocols that use such a global setup, e.g., a global ledger, which can then be automatically translated into the setting where the setup is replaced by a protocol implementing it, such as Bitcoin.
We show that the above reasoning is flawed and such a generic security-preserving replacement can only work under very (often unrealistic) strong conditions on the global setup and the security statement. For example, the UC security of Bitcoin for realizing a ledger proved by Badertscher {\em et al.} [CRYPTO'17] is {\em not} sufficient per se to allow us to replace the ledger by Bitcoin when used as a global setup. In particular, we cannot expect that all security statements in the global ledger-hybrid world would be preserved when using Bitcoin as a ledger.
On the positive side, we provide characterizations of security statements for protocols that make use of global setups, for which the replacement is sound. Our results can be seen as a first guide on how to navigate the very tricky question of what constitutes a ``good'' global setup and how to use it in order to keep the modular protocol-design approach intact.

2021

TCC

Towards Tight Adaptive Security of Non-Interactive Key Exchange
📺
Abstract

We investigate the quality of security reductions for non-interactive key
exchange (NIKE) schemes. Unlike for many other cryptographic building blocks
(like public-key encryption, signatures, or zero-knowledge proofs), all known
NIKE security reductions to date are non-tight, i.e., lose a factor of at least
the number of users in the system. In that sense, NIKE forms a particularly
elusive target for tight security reductions.
The main technical obstacle in achieving tightly secure NIKE schemes are
adaptive corruptions. Hence, in this work, we explore security notions and
schemes that lie between selective security and fully adaptive security.
Concretely:
- We exhibit a tradeoff between key size and reduction loss.
We show that a tighter reduction can be bought by larger public and secret NIKE
keys. Concretely, we present a simple NIKE scheme with a reduction loss of
O(N^2 log(\nu)/\nu^2), and public and secret keys of O(\nu) group
elements, where N denotes the overall number of users in the system, and
\nu is a freely adjustable scheme parameter.
Our scheme achieves full adaptive security even against multiple "test
queries" (i.e., adversarial challenges), but requires keys of size O(N) to
achieve (almost) tight security under the matrix Diffie-Hellman assumption.
Still, already this simple scheme circumvents existing lower bounds.
- We show that this tradeoff is inherent.
We contrast the security of our simple scheme with a lower bound for all NIKE
schemes in which shared keys can be expressed as an ``inner product in the
exponent''. This result covers the original Diffie-Hellman NIKE scheme, as well
as a large class of its variants, and in particular our simple scheme. Our
lower bound gives a tradeoff between the ``dimension'' of any such scheme
(which directly corresponds to key sizes in existing schemes), and the
reduction quality. For \nu = O(N), this shows our simple scheme and reduction
optimal (up to a logarithmic factor).
- We exhibit a tradeoff between security and key size for tight reductions.
We show that it is possible to circumvent the inherent tradeoff above by
relaxing the desired security notion. Concretely, we consider the natural
notion of semi-adaptive security, where the adversary has to commit to a single
test query after seeing all public keys. As a feasibility result, we bring
forward the first scheme that enjoys compact public keys and tight
semi-adaptive security under the conjunction of the matrix Diffie-Hellman and
learning with errors assumptions.
We believe that our results shed a new light on the role of adaptivity in NIKE
security, and also illustrate the special role of NIKE when it comes to tight
security reductions.

2020

TCC

Universal Composition with Global Subroutines: Capturing Global Setup within plain UC
📺
Abstract

The Global and Externalized UC frameworks [Canetti-Dodis-Pass-Walfish, TCC 07] extend the plain UC framework to additionally handle protocols that use a ``global setup'', namely a mechanism that is also used by entities outside the protocol. These frameworks have broad applicability: Examples include public-key infrastructures, common reference strings, shared synchronization mechanisms, global blockchains, or even abstractions such as the random oracle. However, the need to work in a specialized framework has been a source of confusion, incompatibility, and an impediment to broader use.
We show how security in the presence of a global setup can be captured within the plain UC framework, thus significantly simplifying the treatment. This is done as follows:
- We extend UC-emulation to the case where both the emulating protocol $\pi$ and the emulated protocol $\phi$ make subroutine calls to protocol $\gamma$ that is accessible also outside $\pi$ and $\phi$. As usual, this notion considers only a single instance of $\phi$ or $\pi$ (alongside $\gamma$).
- We extend the UC theorem to hold even with respect to the new notion of UC emulation. That is, we show that if $\pi$ UC-emulates $\phi$ in the presence of $\gamma$, then $\rho^{\phi\rightarrow\pi}$ UC-emulates $\rho$ for any protocol $\rho$, even when $\rho$ uses $\gamma$ directly, and in addition calls many instances of $\phi$, all of which use the same instance of $\gamma$. We prove this extension using the existing UC theorem as a black box, thus further simplifying the treatment.
We also exemplify how our treatment can be used to streamline, within the plain UC model, proofs of security of systems that involve global set-up, thus providing greater simplicity and flexibility.

2020

ASIACRYPT

Fuzzy Asymmetric Password-Authenticated Key Exchange
📺
Abstract

Password-Authenticated Key Exchange (PAKE) lets users with passwords exchange a cryptographic key. There have been two variants of PAKE which make it more applicable to real-world scenarios:
* Asymmetric PAKE (aPAKE), which aims at protecting a client's password even if the authentication server is untrusted, and
* Fuzzy PAKE (fPAKE), which enables key agreement even if passwords of users are noisy, but "close enough".
Supporting fuzzy password matches eases the use of higher entropy passwords and enables using biometrics and environmental readings (both of which are naturally noisy).
Until now, both variants of PAKE have been considered only in separation. In this paper, we consider both of them simultaneously. We introduce the notion of Fuzzy Asymmetric PAKE (fuzzy aPAKE), which protects against untrusted servers and supports noisy passwords. We formulate our new notion in the Universal Composability framework of Canetti (FOCS'01), which is the preferred model for password-based primitives. We then show that fuzzy aPAKE can be obtained from oblivious transfer and some variant of robust secret sharing (Cramer et al, EC'15). We achieve security against malicious parties while avoiding expensive tools such as non-interactive zero-knowledge proofs.
Our construction is round-optimal, with message and password file sizes that are independent of the schemes error tolerance.

2019

EUROCRYPT

Multi-party Virtual State Channels
📺
Abstract

Smart contracts are self-executing agreements written in program code and are envisioned to be one of the main applications of blockchain technology. While they are supported by prominent cryptocurrencies such as Ethereum, their further adoption is hindered by fundamental scalability challenges. For instance, in Ethereum contract execution suffers from a latency of more than 15 s, and the total number of contracts that can be executed per second is very limited. State channel networks are one of the core primitives aiming to address these challenges. They form a second layer over the slow and expensive blockchain, thereby enabling instantaneous contract processing at negligible costs.In this work we present the first complete description of a state channel network that exhibits the following key features. First, it supports virtual multi-party state channels, i.e. state channels that can be created and closed without blockchain interaction and that allow contracts with any number of parties. Second, the worst case time complexity of our protocol is constant for arbitrary complex channels. This is in contrast to the existing virtual state channel construction that has worst case time complexity linear in the number of involved parties. In addition to our new construction, we provide a comprehensive model for the modular design and security analysis of our construction.

2018

CRYPTO

On Tightly Secure Non-Interactive Key Exchange
📺
Abstract

We consider the reduction loss of security reductions for non-interactive key exchange (NIKE) schemes. Currently, no tightly secure NIKE schemes exist, and in fact Bader et al. (EUROCRYPT 2016) provide a lower bound (of $$\varOmega (n^2)$$, where $$n$$ is the number of parties an adversary interacts with) on the reduction loss for a large class of NIKE schemes.We offer two results: the first NIKE scheme with a reduction loss of $$n/2$$ that circumvents the lower bound of Bader et al., but is of course still far from tightly secure. Second, we provide a generalization of Bader et al.’s lower bound to a larger class of NIKE schemes (that also covers our NIKE scheme), with an adapted lower bound of $$n/2$$ on the reduction loss. Hence, in that sense, the reduction for our NIKE scheme is optimal.

2018

PKC

Graded Encoding Schemes from Obfuscation
Abstract

We construct a graded encoding scheme (GES), an approximate form of graded multilinear maps. Our construction relies on indistinguishability obfuscation, and a pairing-friendly group in which (a suitable variant of) the strong Diffie–Hellman assumption holds. As a result of this abstract approach, our GES has a number of advantages over previous constructions. Most importantly:
We can prove that the multilinear decisional Diffie–Hellman (MDDH) assumption holds in our setting, assuming the used ingredients are secure (in a well-defined and standard sense). Hence, our GES does not succumb to so-called “zeroizing” attacks if the underlying ingredients are secure.Encodings in our GES do not carry any noise. Thus, unlike previous GES constructions, there is no upper bound on the number of operations one can perform with our encodings. Hence, our GES essentially realizes what Garg et al. (EUROCRYPT 2013) call the “dream version” of a GES.
Technically, our scheme extends a previous, non-graded approximate multilinear map scheme due to Albrecht et al. (TCC 2016-A). To introduce a graded structure, we develop a new view of encodings at different levels as polynomials of different degrees.

#### Program Committees

- TCC 2019
- PKC 2018

#### Coauthors

- Michel Abdalla (1)
- Christian Badertscher (2)
- Ran Canetti (1)
- Pierre-Alain Dupont (1)
- Stefan Dziembowski (1)
- Lisa Eckey (1)
- Andreas Erwig (1)
- Pooya Farshim (1)
- Sebastian Faust (1)
- Björn Haase (1)
- Gottfried Herold (1)
- Dennis Hofheinz (5)
- Kristina Hostáková (1)
- Lisa Kohl (2)
- Roman Langrehr (1)
- Enrique Larraia (1)
- Maximilian Orlt (1)
- David Pointcheval (1)
- Carla Ràfols (1)
- Leonid Reyzin (1)
- Siavash Riahi (1)
- Andy Rupp (2)
- Bjoern Tackmann (1)
- Sophia Yakoubov (1)
- Vassilis Zikas (2)