## CryptoDB

### Martijn Stam

#### Affiliation: University of Bristol

#### Publications

**Year**

**Venue**

**Title**

2020

TCHES

Redundant Code-based Masking Revisited
Abstract

Masking schemes are a popular countermeasure against side-channel attacks. To mask bytes, the two classical options are Boolean masking and polynomial masking. The latter lends itself to redundant masking, where leakage emanates from more shares than are strictly necessary to reconstruct, raising the obvious question how well such “redundant” leakage can be exploited by a side-channel adversary. We revisit the recent work by Chabanne et al. (CHES’18) and show that, contrary to their conclusions, said leakage can—in theory—always be exploited. For the Hamming weight scenario in the low-noise regime, we heuristically determine how security degrades in terms of the number of redundant shares for first and second order secure polynomial masking schemes.Furthermore, we leverage a well-established link between linear secret sharing schemes and coding theory to determine when different masking schemes will end up with essentially equivalent leakage profiles. Surprisingly, we conclude that for typical field sizes and security orders, Boolean masking is a special case of polynomial masking. We also identify quasi-Boolean masking schemes as a special class of redundant polynomial masking and point out that the popular “Frobenius-stable” sets of interpolations points typically lead to such quasi-Boolean masking schemes, with subsequent degraded leakage performance.

2017

TOSC

Modes of Operation Suitable for Computing on Encrypted Data
Abstract

We examine how two parallel modes of operation for Authenticated Encryption (namely CTR+PMAC and OTR mode) work when evaluated in a multiparty computation engine. These two modes are selected because they suit the PRFs examined in previous works. In particular the modes are highly parallel, and do not require evaluation of the inverse of the underlying PRF. In order to use these modes one needs to convert them from their original instantiation of being defined on binary blocks of data, to working on elememts in a large prime finite field. The latter fitting the use case of many secret-sharing based MPC engines. In doing this conversion we examine the associated security proofs of PMAC and OTR, and show that they carry over to this new setting.

2017

TOSC

Turning Online Ciphers Off
Abstract

CAESAR has caused a heated discussion regarding the merits of one-pass encryption and online ciphers. The latter is a keyed, length preserving function which outputs ciphertext blocks as soon as the respective plaintext block is available as input. The immediacy of an online cipher affords a clear performance advantage, but it comes at a price: ciphertext blocks cannot depend on later plaintext blocks, limiting diffusion and hence security. We show how one can attain the best of both worlds by providing provably secure constructions, achieving full cipher security, based on applications of an online cipher around blockwise reordering layers. Explicitly, we show that with just two calls to the online cipher, prp security up to the birthday bound is both attainable and maximal. Moreover, we demonstrate that three calls to the online cipher suffice to obtain beyond birthday bound security. We provide a full proof of this for a prp construction, and, in the ±prp setting, security against adversaries who make queries of any single length. As part of our investigation, we extend an observation by Rogaway and Zhang by further highlighting the close relationship between online ciphers and tweakable blockciphers with variable-length tweaks.

2016

ASIACRYPT

2010

EPRINT

The collision security of Tandem-DM in the ideal cipher model
Abstract

We prove that Tandem-DM, one of the two ``classical'' schemes for turning a blockcipher of $2n$-bit key into a double block length hash function, has birthday-type collision resistance in the ideal cipher model. A collision resistance analysis for Tandem-DM achieving a similar birthday-type bound was already proposed by Fleischmann, Gorski and Lucks at FSE 2009. As we detail, however, the latter analysis is wrong, thus leaving the collision resistance of Tandem-DM as an open problem until now.

2008

EPRINT

Another Glance At Blockcipher Based Hashing
Abstract

In this note we revisit the rate-1 blockcipher based hash
functions as first studied by Preneel, Govaerts and Vandewalle (Crypto'93) and later extensively analysed by Black,
Rogaway and Shrimpton (Crypto'02). We analyze a further generalization where any pre- and postprocessing is considered. By introducing a new
tweak to earlier proof methods, we obtain a simpler proof
that is both more general and more tight than existing
results. As added benefit, this also leads to a clearer understanding
of the current classification of rate-1 blockcipher based schemes as introduced by Preneel et al. and refined by Black et al.

2008

EPRINT

The CCA2-Security of Hybrid Damgård's ElGamal
Abstract

We consider a hybrid version of Damgård's ElGamal public-key
encryption scheme that incorporates the use of a symmetric cipher and a hash function for key-derivation. We prove that under appropriate choice of the hash function this scheme is IND-CCA secure
under the Decisional Diffie-Hellman assumption in the standard model.
Our results can be generalized to universal hash proof systems where our main technical contribution can be viewed as an efficient generic transformation from 1-universal to 2-universal hash proof systems.

2008

EPRINT

A New Randomness Extraction Paradigm for Hybrid Encryption
Abstract

We present a new approach to the design of IND-CCA2 secure hybrid encryption schemes in the standard model. Our approach provides an efficient generic transformation from 1-universal to 2-universal hash proof systems. The transformation involves a randomness extractor based on a 4-wise independent hash function as the key derivation function. Our methodology can be instantiated with efficient schemes based on standard intractability assumptions such as DDH, QR and Paillier. Interestingly, our framework also allows to prove IND-CCA2 security of a hybrid version of 1991s Damgaards ElGamal public-key encryption
scheme under the DDH assumption.

2007

EPRINT

Building a Collision-Resistant Compression Function from Non-Compressing Primitives
Abstract

We consider how to build an efficient compression function from a small
number of random, non-compressing primitives (fixed-key blockciphers
were our original motivation). Our main goal is to achieve a level of
collision resistance as close as possible to the optimal birthday
bound. We present a $2n$-to-$n$ bit compression function based on
three independent $n$-to-$n$ bit random functions, each called only
once. We show that if the three random functions are treated as
black boxes (i.e., modelled as random oracles),
finding collisions requires $\Theta(2^{n/2}/n^c)$ queries
for $c\approx 1$. We also give a heuristic,
backed by experimental results, suggesting that the security loss is
at most four bits for block sizes up to 256 bits.
We believe this is the best result to date on the matter of building
a collision resistant compression function from non-compressing functions.
It also relates to an open question from Black et al. (Eurocrypt'05), who
showed that compression functions that invoke a single non-compressing
random function cannot suffice.

2006

EPRINT

Obfuscation for Cryptographic Purposes
Abstract

An obfuscation O of a function F should satisfy two requirements: firstly, using O it should be possible to evaluate F; secondly, O should not reveal anything about F that cannot be learnt from oracle access to F. Several definitions for obfuscation exist. However, most of them are either too weak for or incompatible with cryptographic applications, or have been shown impossible to achieve, or both.
We give a new definition of obfuscation and argue for its reasonability and usefulness. In particular, we show that it is strong enough for cryptographic applications, yet we show that it has the potential for interesting positive results. We illustrate this with the following two results:
- If the encryption algorithm of a secure secret-key encryption scheme can be obfuscated according to our definition, then the result is a secure public-key encryption scheme.
- A uniformly random point function can be easily obfuscated according to our definition, by simply applying a one-way permutation. Previous obfuscators for point functions, under varying notions of security, are either probabilistic or in the random oracle model (but work for arbitrary distributions on the point function).
On the negative side, we show that
- Following Hada and Wee, any family of deterministic functions that can be obfuscated according to our definition must already be ``approximately learnable.'' Thus, many deterministic functions cannot be obfuscated. However, a probabilistic functionality such as a probabilistic secret-key encryption scheme can potentially be obfuscated. In particular, this is possible for a public-key encryption scheme when viewed as a secret-key scheme.
- There exists a secure probabilistic secret-key encryption scheme that cannot be obfuscated according to our definition. Thus, we cannot hope for a general-purpose cryptographic obfuscator for encryption schemes.

2004

EPRINT

On Small Characteristic Algebraic Tori in Pairing-Based Cryptography
Abstract

The output of the Tate pairing on an elliptic curve over a finite
field may be viewed as an element of an algebraic torus.
Using this simple observation, we transfer techniques recently
developed for torus-based cryptography to pairing-based cryptography,
resulting in more efficient computations, and lower bandwidth
requirements. To illustrate the efficacy of this approach, we
apply the method to pairings on supersingular elliptic curves in
characteristic three.

2004

EPRINT

Hardware and Software Normal Basis Arithmetic for Pairing Based Cryptography in Characteristic Three
Abstract

Although identity based cryptography offers a number of functional advantages over conventional public key methods, the computational costs are significantly greater. The dominant part of this cost is the Tate pairing which, in characteristic three, is best computed using the algorithm of Duursma and Lee. However, in hardware and constrained environments this algorithm is unattractive since it requires online computation of cube roots or enough storage space to pre-compute required results. We examine the use of normal basis arithmetic in characteristic three in an attempt to get the best of both worlds: an efficient method for computing the Tate pairing that requires no pre-computation and that may also be implemented in hardware to accelerate devices such as smart-cards. Since normal basis arithmetic in characteristic three has not received much attention before, we
also discuss the construction of suitable bases and associated curve
parameterisations.

2004

EPRINT

Practical Cryptography in High Dimensional Tori
Abstract

At Crypto 2004, van Dijk and Woodruff introduced a new way of using the algebraic tori T_n in cryptography, and obtained an asymptotically optimal n/phi(n) savings in bandwidth and storage for a number of cryptographic applications. However, the computational requirements of compression and decompression in their scheme were impractical, and it was left open to reduce them to a practical level. We give a new method that compresses orders of magnitude faster than the original, while also speeding up the decompression and improving on the compression factor (by a constant term). Further, we give the first efficient implementation that uses T_30, compare its performance to XTR, CEILIDH, and ECC, and present new applications. Our methods achieve better compression than XTR and CEILIDH for the compression of as few as two group elements. This allows us to apply our results to ElGamal encryption with a small message domain to obtain ciphertexts that are 10% smaller than in previous schemes.

#### Program Committees

- CHES 2019
- Eurocrypt 2019
- Crypto 2018
- FSE 2018
- FSE 2017
- Eurocrypt 2017
- Eurocrypt 2015
- FSE 2015
- FSE 2014
- Crypto 2013
- Eurocrypt 2012
- Eurocrypt 2011
- FSE 2011
- PKC 2010
- PKC 2008

#### Coauthors

- Elena Andreeva (2)
- Frederik Armknecht (1)
- Paul Baecher (1)
- Guy Barwell (4)
- Ritam Bhaumik (1)
- John Black (1)
- Alexandra Boldyreva (3)
- Joppe W. Bos (1)
- Nicolas Costes (1)
- Ronald Cramer (1)
- Jean Paul Degabriele (4)
- Alexander W. Dent (1)
- Yevgeniy Dodis (2)
- Pooya Farshim (1)
- Serge Fehr (1)
- Marc Fischlin (3)
- Ewan Fleischmann (1)
- Jake Longo Galea (2)
- Robert Granger (4)
- Dennis Hofheinz (3)
- Tibor Jager (1)
- Dimitar Jetchev (2)
- Eike Kiltz (3)
- Matthias Krause (1)
- Jooyoung Lee (5)
- Anja Lehmann (1)
- Arjen K. Lenstra (2)
- Tianren Liu (2)
- John Malone-Lee (3)
- Mark Manulis (1)
- Daniel P. Martin (6)
- Luke Mather (1)
- Mridul Nandi (1)
- Jonathan F. O'Connell (2)
- Elisabeth Oswald (6)
- Onur Özen (1)
- Onur Özen (4)
- Dan Page (7)
- Daniel Page (2)
- Kenneth G. Paterson (4)
- Krzysztof Pietrzak (3)
- Thomas Ristenpart (1)
- Phillip Rogaway (1)
- Dragos Rotaru (1)
- Karl Rubin (2)
- Dominique Schröder (1)
- Jacob C. N. Schuldt (1)
- Thomas Shrimpton (5)
- Alice Silverberg (2)
- Nigel P. Smart (1)
- Ryan Stanley-Oakes (1)
- John P. Steinberger (6)
- Stefano Tessaro (1)
- Susan Thomson (1)
- Michael Tunstall (1)
- Marten van Dijk (2)
- Bogdan Warinschi (2)
- David P. Woodruff (2)
- Moti Yung (3)