## CryptoDB

### Julia Kastner

#### ORCID: 0000-0002-8879-8226

#### Publications

**Year**

**Venue**

**Title**

2024

PKC

Compact Selective Opening Security From LWE
Abstract

Selective opening (SO) security is a security notion for public-key
encryption schemes that captures security against adaptive corruptions of
senders. SO security comes in chosen-plaintext (SO-CPA) and chosen-ciphertext
(SO-CCA) variants, neither of which is implied by standard security notions
like IND-CPA or IND-CCA security.
In this paper, we present the first SO-CCA secure encryption scheme that
combines the following two properties: (1) it has a constant ciphertext
expansion (i.e., ciphertexts are only larger than plaintexts by a constant
factor), and (2) its security can be proven from a standard assumption.
Previously, the only known SO-CCA secure encryption scheme achieving (1) was
built from an ad-hoc assumption in the RSA regime.
Our construction builds upon LWE, and in particular on a new and surprisingly
simple construction of compact lossy trapdoor functions (LTFs). Our LTF can
be converted into an “all-but-many LTF” (or ABM-LTF), which is known to be
sufficient to obtain SO-CCA security. Along the way, we fix a technical
problem in that previous ABM-LTF-based construction of SO-CCA security.

2024

CRYPTO

Pairing-Free Blind Signatures from Standard Assumptions in the ROM
Abstract

Blind Signatures are a useful primitive for privacy preserving
applications such as electronic payments, e-voting, anonymous credentials,
and more. However, existing practical blind signature schemes based on
standard assumptions require either pairings or lattices. We present the
first construction of a round-optimal blind signature in the random oracle
model based on standard assumptions without resorting to pairings or
lattices. In particular, our construction is secure under the strong RSA
assumption and DDH (in pairing-free groups). For our construction, we
provide a NIZK-friendly signature based on strong RSA, and efficiently
instantiate a variant of Fischlin’s generic framework (CRYPTO’06). Our
Blind Signature scheme has signatures of size 4.28 KB and communication
cost 10.98 KB. On the way, we develop techniques that might be of
independent interest. In particular, we provide efficient relaxed range-
proofs for large ranges with subversion zero-knowledge and compact
commitments to elements of arbitrary groups.

2023

CRYPTO

The Power of Undirected Rewindings for Adaptive Security
Abstract

Existing proofs of adaptive security (e.g., in settings in which decryption keys are adaptively revealed) often rely on guessing arguments. Such guessing arguments can be simple (and, e.g., just involve guessing which keys are revealed), or more complex ``partitioning'' arguments. Since guessing directly and negatively impacts the loss of the corresponding security reduction, this leads to black-box lower bounds for a number of cryptographic scenarios that involve adaptive security.
In this work, we provide an alternative to such guessing arguments: instead of guessing in a security reduction which adaptive choices an adversary A makes, we rewind A many times until we can successfully embed a given computational challenge. The main benefit of using rewindings is that these rewindings can be arranged sequentially, and the corresponding reduction loss only accumulates additively (instead of multiplicatively, as with guessing). The main technical challenge is to show that A's success is not negatively affected after (potentially many) rewindings. To this end, we develop a machinery for ``undirected'' rewindings that preserve A's success across (potentially many) rewindings.
We use this strategy to show
- security of the ``Logical Key Hierarchy'' protocol underlying the popular TreeKEM key management protocol, and
- security of the Goldreich-Goldwasser-Micali (GGM) pseudorandom function (PRF) as a prefix-constrained PRF.
In both cases, we provide the first polynomial reductions to standard assumptions (i.e., to IND-CPA and PRG security, respectively), and in case of the GGM PRF, we also circumvent an existing lower bound.

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

TCC

The Price of Verifiability: Lower Bounds for Verifiable Random Functions
Abstract

Verifiable random functions (VRFs) are a useful extension of pseudorandom functions for which it is possible to generate a proof that a certain image is indeed the correct function value (relative to a public verification key). Due to their strong soundness requirements on such proofs, VRFs are notoriously hard to construct, and existing constructions suffer either from complex proofs (for function images), or rely on complex and non-standard assumptions.
In this work, we attempt to explain this phenomenon. We show that for a large class of pairing-based VRFs, it is not possible to obtain short proofs and a reduction to a simple assumption simultaneously. Since the class of "consecutively verifiable" VRFs we consider contains in particular the VRF of Lysyanskaya and that of Dodis-Yampolskiy, our results explain the large proof size, resp. the complex assumption of these VRFs.

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.

2020

EUROCRYPT

On Instantiating the Algebraic Group Model from Falsifiable Assumptions
📺
Abstract

We provide a standard-model implementation (of a relaxation) of the algebraic group model (AGM, [Fuchsbauer, Kiltz, Loss, CRYPTO 2018]). Specifically, we show that every algorithm that uses our group is algebraic, and hence "must know" a
representation of its output group elements in terms of its input group
elements. Here, "must know" means that a suitable extractor can extract such
a representation efficiently. We stress that our implementation relies only on
falsifiable assumptions in the standard model, and in particular does not use
any knowledge assumptions.
As a consequence, our group allows to transport a number of results obtained in
the AGM into the standard model, under falsifiable assumptions. For instance,
we show that in our group, several Diffie-Hellman-like assumptions (including
computational Diffie-Hellman) are equivalent to the discrete logarithm
assumption. Furthermore, we show that our group allows to prove the Schnorr
signature scheme tightly secure in the random oracle model.
Our construction relies on indistinguishability obfuscation, and hence should
not be considered as a practical group itself. However, our results show that
the AGM is a realistic computational model (since it can be instantiated in the
standard model), and that results obtained in the AGM are also possible with
standard-model groups.

#### Coauthors

- Thomas Agrikola (1)
- Nicholas Brandt (1)
- Yu-ichi Hayashi (1)
- Dennis Hofheinz (4)
- Kristina Hostáková (1)
- Julia Kastner (8)
- Karen Klein (2)
- Alexander Koch (1)
- Julian Loss (2)
- Daiki Miyahara (1)
- Takaaki Mizuki (1)
- Ky Nguyen (1)
- Michael Reichle (1)
- Hideaki Sone (1)
- Akin Ünal (1)
- Akın Ünal (1)
- Stefan Walzer (1)
- Jiayu Xu (2)