## CryptoDB

### Nigel P. Smart

#### Affiliation: Katholieke Universiteit Leuven

#### Publications

**Year**

**Venue**

**Title**

2021

EUROCRYPT

Large Scale, Actively Secure Computation from LPN and Free-XOR Garbled Circuits
Abstract

Whilst secure multiparty computation (MPC) based on garbled circuits is concretely efficient for
a small number of parties $n$, the gap between the complexity of practical protocols, which
is $O(n^2)$ per party, and the theoretical complexity, which is $O(n)$ per party, is prohibitive for large values of $n$.
In order to bridge this gap, Ben-Efraim, Lindell and Omri (ASIACRYPT 2017)
introduced a garbled-circuit-based MPC protocol with an almost-practical pre-processing, yielding $O(n)$ complexity per party.
However, this protocol is only passively secure and does not support
the free-XOR technique by Kolesnikov and Schneider (ICALP 2008), on which almost all practical garbled-circuit-based protocols rely on for their efficiency.
In this work, to further bridge the gap between theory and practice, we present a new $n$-party garbling technique based on a new variant of standard LPN-based encryption.
Using this approach we can describe two new garbled-circuit based protocols,
which have practical evaluation phases.
Both protocols are in the preprocessing model, have $O(n)$ complexity per party,
are actively secure and support the free-XOR technique.
The first protocol tolerates full threshold corruption and ensures the garbled circuit
contains no adversarially introduced errors, using a rather expensive garbling phase.
The second protocol assumes that at least $n/c$ of the parties are honest (for an
arbitrary fixed value $c$) and allows a significantly lighter preprocessing, at the cost of a small sacrifice in online efficiency.
We demonstrate the practicality of our approach with an implementation of the evaluation phase using different circuits.
We show that like the passively-secure protocol of Ben-Efraim, Lindell and Omri,
our approach starts to improve upon other practical protocols with $O(n^2)$ complexity when the number of parties is around $100$.

2021

PKC

Round-optimal Verifiable Oblivious Pseudorandom Functions from Ideal Lattices
📺
Abstract

Verifiable Oblivious Pseudorandom Functions (VOPRFs) are protocols that allow a client to learn verifiable pseudorandom function (PRF) evaluations on inputs of their choice. The PRF evaluations are computed by a server using their own secret key. The security of the protocol prevents both the server from learning anything about the client's input, and likewise the client from learning anything about the server's key. VOPRFs have many applications including password-based authentication, secret-sharing, anonymous authentication and efficient private set intersection. In this work, we construct the first round-optimal (online) VOPRF protocol that retains security from well-known subexponential lattice hardness assumptions. Our protocol requires constructions of non-interactive zero-knowledge arguments of knowledge (NIZKAoK). Using recent developments in the area of post-quantum zero-knowledge arguments of knowledge, we show that our VOPRF may be securely instantiated in the quantum random oracle model. We construct such arguments as extensions of prior work in the area of lattice-based zero-knowledge proof systems.

2019

JOFC

Efficient Constant-Round Multi-party Computation Combining BMR and SPDZ
Abstract

Recently, there has been huge progress in the field of concretely efficient secure computation, even while providing security in the presence of malicious adversaries. This is especially the case in the two-party setting, where constant-round protocols exist that remain fast even over slow networks. However, in the multi-party setting, all concretely efficient fully secure protocols, such as SPDZ, require many rounds of communication. In this paper, we present a constant-round multi-party secure computation protocol that is fully secure in the presence of malicious adversaries and for any number of corrupted parties. Our construction is based on the constant-round protocol of Beaver et al. (the BMR protocol) and is the first version of that protocol that is concretely efficient for the dishonest majority case. Our protocol includes an online phase that is extremely fast and mainly consists of each party locally evaluating a garbled circuit. For the offline phase, we present both a generic construction (using any underlying MPC protocol) and a highly efficient instantiation based on the SPDZ protocol. Our estimates show the protocol to be considerably more efficient than previous fully secure multi-party protocols.

2018

CRYPTO

CAPA: The Spirit of Beaver Against Physical Attacks
📺
Abstract

In this paper we introduce two things: On one hand we introduce the Tile-Probe-and-Fault model, a model generalising the wire-probe model of Ishai et al. extending it to cover both more realistic side-channel leakage scenarios on a chip and also to cover fault and combined attacks. Secondly we introduce CAPA: a combined Countermeasure Against Physical Attacks. Our countermeasure is motivated by our model, and aims to provide security against higher-order SCA, multiple-shot FA and combined attacks. The tile-probe-and-fault model leads one to naturally look (by analogy) at actively secure multi-party computation protocols. Indeed, CAPA draws much inspiration from the MPC protocol SPDZ. So as to demonstrate that the model, and the CAPA countermeasure, are not just theoretical constructions, but could also serve to build practical countermeasures, we present initial experiments of proof-of-concept designs using the CAPA methodology. Namely, a hardware implementation of the KATAN and AES block ciphers, as well as a software bitsliced AES S-box implementation. We demonstrate experimentally that the design can resist second-order DPA attacks, even when the attacker is presented with many hundreds of thousands of traces. In addition our proof-of-concept can also detect faults within our model with high probability in accordance to the methodology.

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.

2015

EPRINT

2010

EPRINT

The Fiat--Shamir Transform for Group and Ring Signature Schemes
Abstract

The Fiat-Shamir (FS) transform is a popular tool to produce
particularly efficient digital signature schemes out of identification protocols.
It is known that the resulting signature scheme is secure (in the
random oracle model) if and only if the identification protocol is secure
against passive impersonators. A similar results holds for constructing
ID-based signature schemes out of ID-based identification protocols.
The transformation had also been applied to identification protocols with
additional privacy properties. So, via the FS transform, ad-hoc group
identification schemes yield ring signatures and identity escrow schemes
yield group signature schemes. Unfortunately, results akin to those above
are not known to hold for these latter settings and the security of the
resulting schemes needs to be proved from scratch, or worse, it is often
simply assumed. Therefore, the security of the schemes obtained this
way does not clearly follow from that of the base identification protocol
and needs to be proved from scratch. Even worse, some papers seem to
simply assume that the transformation works without proof.
In this paper we provide the missing foundations for the use of the FS
transform in these more complex settings.We start with defining a formal
security model for identity escrow schemes (a concept proposed earlier
but never rigorously formalized). Our main result constists of necessary
and sufficient conditions for an identity escrow scheme to yield (via the
FS transform) a secure group signature schemes. In addition, we discuss
several variants of this result that account for the constructions of group
signatures that fulfill weaker notions of security. In addition, using the
similarity between group and ring signature schemes we give analogous
results for the latter primitive.

2008

EPRINT

A Modular Security Analysis of the TLS Handshake Protocol
Abstract

We study the security of the widely deployed Secure Session
Layer/Transport Layer Security (TLS) key agreement
protocol.
Our analysis identifies, justifies, and exploits the modularity
present in the design of the protocol:
the {\em application keys} offered to higher level applications are
obtained from a {\em master key}, which in turn is derived, through
interaction, from a {\em pre-master key}.
Our first contribution consists of formal models that clarify the
security level enjoyed by each of these types of keys. The models
that we provide fall under well established paradigms in defining
execution, and security notions.
We capture the realistic setting where only one of the two parties
involved in the execution of the protocol (namely the server) has a
certified public key, and where the same master key is used to
generate multiple application keys.
The main contribution of the paper is a modular and generic proof of
security for the application keys established through the TLS
protocol.
We show that the transformation used by TLS to derive master keys
essentially transforms an {\em arbitrary} secure pre-master key
agreement protocol into a secure master-key agreement protocol.
Similarly, the transformation used to derive application keys works
when applied to an arbitrary secure master-key agreement protocol.
These results are in the random oracle model.
The security of the overall protocol then follows from proofs of
security for the basic pre-master key generation protocols employed by
TLS.

2007

EPRINT

Executing Modular Exponentiation on a Graphics Accelerator
Abstract

Demand in the consumer market for graphics hardware that accelerates rendering of 3D images has resulted in commodity devices capable of astonishing levels of performance. These results were achieved by specifically tailoring the hardware for the target domain. As graphics accelerators become increasingly programmable this performance makes them an attractive target for other domains. Specifically, they have motivated the transformation of costly algorithms from a general purpose computational model into a form that executes on said graphics hardware. We investigate the implementation and performance of modular exponentiation using a graphics accelerator, with the view of using it to execute operations required in the RSA public key cryptosystem.

2006

EPRINT

High Security Pairing-Based Cryptography Revisited
Abstract

The security and performance of pairing based cryptography has provoked a
large volume of research, in part because of the exciting new cryptographic
schemes that it underpins. We re-examine how one should implement pairings over
ordinary elliptic curves for various practical levels of security. We conclude,
contrary to prior work, that the Tate pairing is more efficient than the
Weil pairing for all such security levels. This is achieved by using efficient exponentiation techniques
in the cyclotomic subgroup backed by efficient squaring routines within the
same subgroup.

2006

EPRINT

The Eta Pairing Revisited
Abstract

In this paper we simplify and extend the Eta pairing, originally
discovered in the setting of supersingular curves by Baretto et al.,
to ordinary curves. Furthermore, we show that by swapping the
arguments of the Eta pairing, one obtains a very efficient algorithm
resulting in a speed-up of a factor of around six
over the usual Tate pairing, in the case of curves
which have large security parameters, complex multiplication
by $D=-3$, and when the trace of Frobenius is chosen to be suitably small.
Other, more minor savings are obtained for more general curves.

2006

EPRINT

Identity-Based Encryption Gone Wild
Abstract

In this paper we introduce a new primitive called identity-based encryption with wildcards, or WIBE for short. It allows to encrypt messages to a whole range of users simultaneously whose identities match a certain pattern. This pattern is defined through a sequence of fixed strings and wildcards, where any string can take the place of a wildcard in a matching identity. Our primitive can be applied to provide an intuitive way to send encrypted email to groups of users in a corporate hierarchy. We propose a full security notion and give efficient implementations meeting this notion under different pairing-related assumptions, both in the random oracle model and in the standard model.

2006

EPRINT

A Built-in Decisional Function and Security Proof of ID-based Key Agreement Protocols from Pairings
Abstract

In recent years, a large number of identity-based key agreement
protocols from pairings have been proposed. Some of them are elegant
and practical. However, the security of this type of protocols has
been surprisingly hard to prove. The main issue is that a simulator
is not able to deal with reveal queries, because it requires solving
either a computational problem or a decisional problem, both of
which are generally believed to be hard (i.e., computationally
infeasible). The best solution of security proof published so far
uses the gap assumption, which means assuming that the existence of a
decisional oracle does not change the hardness of the corresponding
computational problem. The disadvantage of using this solution to
prove the security for this type of protocols is that such
decisional oracles, on which the security proof relies, cannot be
performed by any polynomial time algorithm in the real world,
because of the hardness of the decisional problem. In this paper we
present a method incorporating a built-in decisional function in
this type of protocols. The function transfers a hard decisional
problem in the proof to an easy decisional problem.
We then discuss the resulting efficiency of the schemes and the
relevant security reductions in the context of different pairings
one can use.

2006

EPRINT

Pairings for Cryptographers
Abstract

Many research papers in pairing based cryptography
treat pairings as a ``black box''. These papers build
cryptographic schemes making use of various properties of
pairings.
If this approach is taken, then it is easy for authors to
make invalid assumptions concerning the properties of pairings.
The cryptographic schemes developed
may not be realizable in practice, or may not be
as efficient as the authors assume.
The aim of this paper is to outline, in as simple a fashion
as possible, the basic choices that are available when
using pairings in cryptography. For each choice, the main
properties and efficiency issues are summarized. The paper is
intended to be of use to non-specialists who are interested
in using pairings to design cryptographic schemes.

2006

EPRINT

On Computing Products of Pairings
Abstract

In many pairing-based protocols often the evaluation of the product
of many pairing evaluations is required. In this paper we consider
methods to compute such products efficiently. Focusing on pairing-friendly fields
in particular, we evaluate methods for the Weil, Tate and Ate pairing algorithms
for ordinary elliptic curves at various security levels. Our operation counts
indicate that the minimal cost of each additional pairing relative to the cost of
one is $\approx 0.61$, $0.45$, and $0.43$, for each of these pairings
respectively at the 128-bit security level.
For larger security levels the Ate pairing can have a relative
additional cost of as low as $0.13$ for each additional pairing.
These estimates allow implementors to make optimal algorithm choices for
given scenarios, in which the number of pairings in the product,
the security level, and the embedding degree are
factors under consideration.

2006

EPRINT

Identity-based Key Agreement Protocols From Pairings
Abstract

In recent years, a large number of identity-based key agreement
protocols from pairings have been proposed. Some of them are
elegant and practical. However, the security of this type of
protocols has been surprisingly hard to prove. The main issue is
that a simulator is not able to deal with reveal queries, because
it requires solving either a computational problem or a decisional
problem, both of which are generally believed to be hard (i.e.,
computationally infeasible). The best solution of security proof
published so far uses the gap assumption, which means assuming
that the existence of a decisional oracle does not change the
hardness of the corresponding computational problem. The
disadvantage of using this solution to prove the security for this
type of protocols is that such decisional oracles, on which the
security proof relies, cannot be performed by any polynomial time
algorithm in the real world, because of the hardness of the
decisional problem. In this paper we present a method
incorporating a built-in decisional function in this type of
protocols. The function transfers a hard decisional problem in the
proof to an easy decisional problem. We then discuss the resulting
efficiency of the schemes and the relevant security reductions in
the context of different pairings one can use. We pay particular
attention, unlike most other papers in the area, to the issues
which arise when using asymmetric pairings.

2005

EPRINT

Generic Constructions of Identity-Based and Certificateless KEMs
Abstract

We extend the concept of key encapsulation mechanisms to the
primitives of ID-based and certificateless encryption.
We show that the natural combination of ID-KEMs or CL-KEMs
with data encapsulation mechanisms results in encryption schemes
which are secure in a strong sense.
In addition, we give generic constructions of ID-KEMs and
CL-KEMs, as well as specific instantiations, which are provably
secure.

2005

EPRINT

On Computable Isomorphisms in Efficient Asymmetric Pairing Based Systems
Abstract

In this paper we examine the hard problems underlying asymmetric pairings, their precise relationships and how they affect a number of existing protocols. Furthermore, we present a new model for the elliptic curve groups used in asymmetric pairings, which allows both an efficient pairing and an efficiently computable isomorphism.

2005

EPRINT

An Efficient ID-KEM Based On The Sakai-Kasahara Key Construction
Abstract

We describe an identity based key encapsulation mechanism (ID-KEM).
It is possible to use this ID-KEM to build a secure identity based
encryption scheme using the techniques of Bentahar et al. The
resulting encryption scheme has a number of performance advantages
over existing methods.

2005

EPRINT

First Steps Toward a Cryptography-Aware Language and Compiler
Abstract

When developing secure, high-performance cryptographic software, the programmer is presented with a wide range of problems. Not only must they be conversant with pertinent scientific results, they must efficiently translate said results into a practical context. Unlike when writing normal programs, they are given little help from either the language or compiler: both are typically too general purpose to offer domain specific optimisation or analysis that would save the programmer time and reduce the potential for error. As a step toward solving this problem we present CAO, a cryptography-aware domain-specific language and associated compiler system. Rather than being a panacea, we pitch CAO as a mechanism for transferring and automating the expert knowledge of cryptographers into a form which is accessible to anyone writing security conscious software.

2004

EPRINT

A comparison of MNT curves and supersingular curves
Abstract

We compare both the security and performance issues related to the
choice of MNT curves against supersingular curves in characteristic three,
for pairing based systems.
We pay particular attention to equating the relevant security levels and
comparing not only computational performance and bandwidth performance.
The paper focuses on the BLS signature scheme and the Boneh--Franklin
encryption scheme, but a similar analysis can be applied to many other
pairing based schemes.

2004

EPRINT

Escrow-Free Encryption Supporting Cryptographic Workflow
Abstract

Since Boneh and Franklin published their seminal paper on identity
based encryption (IBE) using the Weil pairing , there has been a great
deal of interest in cryptographic primitives based on elliptic-curve pairings.
One particularly interesting application has been to control access to
data, via possibly complex policies.
In this paper we continue the research in this vein. We present an
encryption scheme such that the receiver of an encrypted message can
only decrypt if it satisfies a particular policy chosen by
the sender at the time of encryption.
Unlike standard IBE, our encryption scheme is escrow free in that no
key-issuing authority (or colluding set of key-issuing authorities) is
able to decrypt ciphertexts itself.
In addition we describe a security model for the scenario in question
and provide proofs of security for our scheme (in the random oracle model).

2003

EPRINT

Projective Coordinates Leak
Abstract

Denoting by $P=[k]G$ the elliptic-curve double-and-add
multiplication of a public base point $G$ by a secret $k$,
we show that allowing an adversary access to the projective
representation of $P$ results in information being revealed about $k$.
Such access might be granted to an adversary by a poor
software implementation that does not erase the $Z$
coordinate of $P$ from the computer's memory or by a computationally-constrained secure token that
sub-contracts the affine conversion of $P$ to the external world.
From a wider perspective, our result proves that the choice of
representation of elliptic curve points {\sl can reveal}
information about their underlying discrete logarithms, hence
casting potential doubt on the appropriateness of blindly
modelling elliptic-curves as generic groups.
As a conclusion, our result underlines the necessity to sanitize
$Z$ after the affine conversion or, alternatively,
randomize $P$ before releasing it out.

2002

EPRINT

Point Multiplication on Ordinary Elliptic Curves over Fields of Characteristic Three
Abstract

In this paper we investigate the efficiency of cryptosystems based on
ordinary elliptic curves over fields of characteristic three.
We look at different representations for curves and consider some of
the algorithms necessary to perform efficient point multiplication.
We give example timings for our operations and compare them with
timings for curves in characteristic two of a similar level of security.
We show that using the Hessian form in characteristic three
produces a point multiplication algorithm under $50$ percent slower
than the equivalent system in characteristic two.
Thus it is conceivable that curves in characteristic three, could
offer greater performance than currently perceived by the community.

2002

EPRINT

Cryptanalysis of MQV with partially known nonces
Abstract

In this paper we present the first lattice attack on an authenticated
key agreement protocol, which does not use a digital signature algorithm
to produce the authentication.
We present a two stage attack on MQV in which one party may recover
the other party's static private key from partial knowledge of the nonces
from several runs of the protocol.
The first stage reduces the attack to a hidden number problem which
is partially solved by considering a closest vector problem and using
Babai's algorithm.
This stage is closely related to the attack of Nguyen and Shparlinski
on DSA but is complicated by a non-uniform distribution
of multipliers.
The second stage recovers the rest of the key using the baby-step/giant-step
algorithm or Pollard's Lambda algorithm and runs in time $O(q^{1/4})$.
The attack has been proven to work with high probability and validated
experimentally.
We have thus reduced the security from $O(q^{1/2})$ down to $O(q^{1/4})$
when partial knowledge of the nonces is given.

2001

EPRINT

Extending the GHS Weil Descent Attack
Abstract

In this paper we extend the Weil descent attack
due to Gaudry, Hess and Smart (GHS) to
a much larger class of elliptic curves.
This extended attack still only works for fields of composite
degree over $\F_2$.
The principle behind the extended attack is to use
isogenies to
find a new elliptic curve for which the GHS attack is
effective.
The discrete logarithm problem on the target curve
can be transformed into a discrete logarithm problem
on the new isogenous curve.
One contribution of the paper is to give
an improvement to an algorithm of Galbraith
for constructing isogenies between elliptic curves,
and this is of independent interest in
elliptic curve cryptography.
We conclude that fields of the form $\F_{q^7}$ should be
considered weaker from a cryptographic standpoint than
other fields.
In addition we show that a larger proportion than previously
thought of elliptic curves over $\F_{2^{155}}$ should be
considered weak.

2001

EPRINT

An Identity Based Authenticated Key Agreement Protocol Based on the Weil Pairing
Abstract

We describe an ID based authenticated two pass key agreement
protocol which makes use of the Weil pairing.
The protocol is described and its properties are discussed
including the ability to add key confirmation.

#### Program Committees

- Eurocrypt 2018
- Crypto 2018
- Eurocrypt 2016
- Crypto 2016
- Asiacrypt 2015
- Crypto 2015
- Eurocrypt 2013
- PKC 2013
- Asiacrypt 2013
- Crypto 2013
- CHES 2012
- PKC 2012
- Asiacrypt 2012
- PKC 2011
- Asiacrypt 2011
- CHES 2011
- Asiacrypt 2010
- Eurocrypt 2009
- Eurocrypt 2008 (Program chair)
- Crypto 2007
- Asiacrypt 2007
- CHES 2006
- PKC 2005
- Asiacrypt 2005
- CHES 2005
- Asiacrypt 2004
- PKC 2004
- Crypto 2004
- Asiacrypt 2003
- Eurocrypt 2003
- Crypto 2002
- Eurocrypt 2002
- Asiacrypt 2001
- PKC 2001
- PKC 2000
- PKC 1999

#### Coauthors

- Michel Abdalla (3)
- Sattam S. Al-Riyami (1)
- Martin R. Albrecht (1)
- Victor Arribas (1)
- Manuel Barbosa (1)
- Aner Ben-Efraim (1)
- Naomi Benger (2)
- Kamel Bentahar (2)
- Begül Bilgin (1)
- James Birkett (1)
- Sai Sheshank Burra (1)
- Dario Catalano (2)
- Liqun Chen (4)
- Zhaohui Cheng (3)
- Ashish Choudhary (3)
- Kelong Cong (1)
- Anamaria Costache (1)
- Ivan Damgård (1)
- Alex Davidson (1)
- Lauren De Meyer (1)
- Alexander W. Dent (3)
- Amit Deo (1)
- Pooya Farshim (2)
- Steven D. Galbraith (3)
- Pierrick Gaudry (1)
- Craig Gentry (3)
- Essam Ghadafi (1)
- Robert Granger (2)
- P. J. Green (1)
- Shai Halevi (3)
- Florian Hess (4)
- Antoine Joux (1)
- Enrique Larraia (3)
- Peter J. Leadbitter (2)
- M.-F. Lee (1)
- Reynald Lercier (1)
- David Leslie (1)
- Pierre-Yvan Liardet (1)
- Yehuda Lindell (4)
- Jake Loftus (1)
- John Malone-Lee (8)
- David May (1)
- Payman Mohassel (2)
- Paul Morrissey (4)
- Andrew Moss (1)
- Henk L. Muller (1)
- David Naccache (2)
- Gregory Neven (3)
- Jesper Buus Nielsen (1)
- Ventzislav Nikov (1)
- Svetla Nikova (1)
- Richard Noad (2)
- Peter Sebastian Nordholt (1)
- Eran Omri (1)
- Claudio Orlandi (1)
- Emmanuela Orsini (8)
- Dan Page (6)
- Valerio Pastro (1)
- Kenneth G. Paterson (1)
- Arpita Patra (3)
- Duong Hieu Phan (1)
- Benny Pinkas (4)
- David Pointcheval (1)
- Joop van de Pol (5)
- Oscar Reparaz (1)
- Dragos Rotaru (1)
- Seyed Saeed Sadeghian (2)
- Thomas Schneider (1)
- Peter Scholl (1)
- Jacob C. N. Schuldt (1)
- Chris Sherfield (1)
- Samir Siksek (1)
- Eduardo Soria-Vazquez (2)
- Martijn Stam (1)
- Jacques Stern (3)
- Frederik Vercauteren (5)
- Bogdan Warinschi (6)
- J. Westwood (1)
- Stephen C. Williams (1)
- Avishay Yanai (3)
- Yuval Yarom (3)
- Sarah Zakarias (1)