## CryptoDB

### Andy Rupp

#### Publications

**Year**

**Venue**

**Title**

2021

ASIACRYPT

Onion Routing with Replies
Abstract

Onion routing (OR) protocols are a crucial tool for providing anonymous internet communication. An OR protocol enables a user to anonymously send requests to a server. A fundamental problem of OR protocols is how to deal with replies: ideally, we would want the server to be able to send a reply back to the anonymous user without knowing or disclosing the user's identity.
Existing OR protocols do allow for such replies, but do not provably protect the payload (i.e., message) of replies against manipulation. Kuhn et al. (IEEE S&P 2020) show that such manipulations can in fact be leveraged to break anonymity of the whole protocol.
In this work, we close this gap and provide the first framework and protocols for OR with protected replies. We define security in the sense of an ideal functionality in the universal composability model, and provide corresponding (less complex) game-based security notions for the individual properties.
We also provide two secure instantiations of our framework: one based on updatable encryption, and one based on succinct non-interactive arguments (SNARGs) to authenticate payloads both in requests and replies. In both cases, our central technical handle is an implicit authentication of the transmitted payload data, as opposed to an explicit, but insufficient authentication (with MACs) in previous solutions. Our results exhibit a new and surprising application of updatable encryption outside of long-term data storage.

2019

EUROCRYPT

(R)CCA Secure Updatable Encryption with Integrity Protection
Abstract

An updatable encryption scheme allows a data host to update ciphertexts of a client from an old to a new key, given so-called update tokens from the client. Rotation of the encryption key is a common requirement in practice in order to mitigate the impact of key compromises over time. There are two incarnations of updatable encryption: One is ciphertext-dependent, i.e. the data owner has to (partially) download all of his data and derive a dedicated token per ciphertext. Everspaugh et al. (CRYPTO’17) proposed CCA and CTXT secure schemes in this setting. The other, more convenient variant is ciphertext-independent, i.e., it allows a single token to update all ciphertexts. However, so far, the broader functionality of tokens in this setting comes at the price of considerably weaker security: the existing schemes by Boneh et al. (CRYPTO’13) and Lehmann and Tackmann (EUROCRYPT’18) only achieve CPA security and provide no integrity protection. Arguably, when targeting the scenario of outsourcing data to an untrusted host, plaintext integrity should be a minimal security requirement. Otherwise, the data host may alter or inject ciphertexts arbitrarily. Indeed, the schemes from BLMR13 and LT18 suffer from this weakness, and even EPRS17 only provides integrity against adversaries which cannot arbitrarily inject ciphertexts. In this work, we provide the first ciphertext-independent updatable encryption schemes with security beyond CPA, in particular providing strong integrity protection. Our constructions and security proofs of updatable encryption schemes are surprisingly modular. We give a generic transformation that allows key-rotation and confidentiality/integrity of the scheme to be treated almost separately, i.e., security of the updatable scheme is derived from simple properties of its static building blocks. An interesting side effect of our generic approach is that it immediately implies the unlinkability of ciphertext updates that was introduced as an essential additional property of updatable encryption by EPRS17 and LT18.

2018

PKC

Non-malleability vs. CCA-Security: The Case of Commitments
Abstract

In this work, we settle the relations among a variety of security notions related to non-malleability and CCA-security that have been proposed for commitment schemes in the literature. Interestingly, all our separations follow from two generic transformations. Given two appropriate security notions X and Y from the class of security notions we compare, these transformations take a commitment scheme that fulfills notion X and output a commitment scheme that still fulfills notion X but not notion Y.Using these transformations, we are able to show that some of the known relations for public-key encryption do not carry over to commitments. In particular, we show that, surprisingly, parallel non-malleability and parallel CCA-security are not equivalent for commitment schemes. This stands in contrast to the situation for public-key encryption where these two notions are equivalent as shown by Bellare et al. at CRYPTO ‘99.

2016

TCC

2008

EPRINT

A Real-World Attack Breaking A5/1 within Hours
Abstract

In this paper we present a real-world hardware-assisted attack on the well-known A5/1 stream cipher which is (still) used to secure GSM communication in most countries all over the world. During the last ten years A5/1 has been intensively analyzed. However, most of the proposed attacks are just of theoretical interest since they lack from practicability due to strong preconditions, high computational demands and/or huge storage requirements and have never been fully implemented.
In contrast to these attacks, our attack which is based on the work by Keller and Seitz [KS01] is running on an existing special-purpose hardware device, called COPACOBANA. With the knowledge of only 64 bits of keystream the machine is able to reveal the corresponding internal 64-bit state of the cipher in about 7 hours on average. Besides providing a detailed description of our attack architecture as well as implementation results, we propose and analyze an optimization that leads again to an improvement of about 16% in computation time.

2008

EPRINT

On Black-Box Ring Extraction and Integer Factorization
Abstract

The black-box extraction problem over rings has (at least) two important interpretations in cryptography: An efficient algorithm for this problem implies (i) the equivalence of computing discrete logarithms and solving the Diffie-Hellman problem and (ii) the in-existence of secure ring-homomorphic encryption schemes.
In the special case of a finite field, Boneh/Lipton and Maurer/Raub showed that there exist algorithms solving the black-box extraction problem in subexponential time. It is unknown whether there exist more efficient algorithms.
In this work we consider the black-box extraction problem over finite rings of characteristic $n$, where $n$ has at least two different prime factors. We provide a polynomial-time reduction from factoring $n$ to the black-box extraction problem for a large class of finite commutative unitary rings. Under the factoring assumption, this implies the in-existence of certain efficient generic reductions from computing discrete logarithms to the Diffie-Hellman problem on the one side, and might be an indicator that secure ring-homomorphic encryption schemes exist on the other side.

2008

EPRINT

Time-Area Optimized Public-Key Engines: MQ-Cryptosystems as Replacement for Elliptic Curves?
Abstract

In this paper ways to efficiently implement public-key schemes based onMultivariate Quadratic polynomials (MQ-schemes for short) are investigated. In particular, they are claimed to resist quantum computer attacks. It is shown that such schemes can have a much better time-area product than elliptic curve cryptosystems. For instance, an optimised FPGA implementation of amended TTS is estimated to be over 50 times more efficient with respect to
this parameter. Moreover, a general framework for implementing small-field MQ-schemes in hardware is proposed which includes a systolic architecture performing Gaussian elimination over composite binary fields.

2008

ASIACRYPT

2008

CHES

2008

EPRINT

Lower Bounds on Black-Box Ring Extraction
Abstract

The black-box ring extraction problem is the problem of extracting a secret ring element from a black-box by performing only the ring operations and testing for equality of elements. An efficient algorithm for the black-box ring extraction problem implies the equivalence of the discrete logarithm and the Diffie-Hellman problem. At the same time this implies the inexistence of secure ring-homomorphic encryption schemes.
It is unknown whether the known algorithms for the black-box ring extraction problem are optimal. In this paper we derive exponential-time lower complexity bounds for a large class of rings satisfying certain conditions. The existence of these bounds is surprising, having in mind that there are subexponential-time algorithms for certain rings which are very similar to the rings considered in this work. In addition, we introduce a novel technique to reduce the problem of factoring integers to the black-box ring extraction problem, extending previous work to a more general class of algorithms and obtaining a much tighter reduction.

2007

EPRINT

Sufficient Conditions for Computational Intractability Regarding Generic Algorithms
Abstract

The generic group model is a valuable methodology for analyzing the
computational hardness of the number-theoretic problems used in
cryptography. Although generic hardness proofs exhibit many similarities,
still the computational intractability of every newly introduced problem
needs to be proven from scratch, a task that can easily become complicated
and cumbersome when done rigorously.
In this paper we make the first steps towards overcoming this
problem by identifying verifiable criteria which if met by a
cryptographic problem guarantee its hardness with respect to generic
algorithms. As useful means for formalization of definitions and
proofs we relate the concepts of generic algorithms and
straight-line programs that have only been used independently in
cryptography so far.
The class of problems we cover includes a significant number of the
cryptographic problems currently known, and is general enough to
also include many future problems.
Moreover, we strengthen the conventional generic model by
incorporating a broader class of possible oracles (operations) since
the underlying algebraic groups may possibly be related through
mappings such as isomorphisms, homomorphisms or multilinear maps.
Our approach could serve as an appropriate basis for
tool-aided hardness verification in the generic model.

2007

EPRINT

Faster Multi-Exponentiation through Caching: Accelerating (EC)DSA Signature Verification
Abstract

We consider the task of computing power products $\prod_{1 \leq i \leq k} g_i^{e_i}$ ("multi-exponentiation") where base elements $g_2, ..., g_k$ are fixed while $g_1$ is variable between multi-exponentiations but may repeat, and where the exponents are bounded (e.g., in a finite group). We present a new technique that entails two different ways of computing such a result. The first way applies to the first occurrence of any $g_1$ where, besides obtaining the actual result, we create a cache entry based on $g_1$, investing very little memory or time overhead. The second way applies to any multi-exponentiation once such a cache entry exists for the $g_1$ in question: the cache entry provides for a significant speed-up. Our technique is useful for ECDSA or DSA signature verification with common domain parameters and recurring signers.

#### Coauthors

- Kristina Altmann (1)
- Endre Bangerter (2)
- Andrey Bogdanov (3)
- Brandon Broadnax (1)
- Alexander W. Dent (2)
- Thomas Eisenbarth (3)
- Valerie Fetzer (1)
- Timo Gendrullis (2)
- Gunnar Hartung (1)
- Gottfried Herold (2)
- Julia Hesse (4)
- Dennis Hofheinz (7)
- Tibor Jager (4)
- Björn Kaidel (1)
- Michael Klooß (1)
- Jessica Koch (1)
- Alexander Koch (1)
- Christiane Kuhn (1)
- Gregor Leander (3)
- Anja Lehmann (1)
- Bodo Möller (1)
- Jörn Müller-Quade (1)
- Martin Novotny (2)
- Carla Ràfols (2)
- Ahmad-Reza Sadeghi (2)
- Thorsten Strufe (1)
- Christopher Wolf (2)