International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Nigel P. Smart

Affiliation: Katholieke Universiteit Leuven

Publications

Year
Venue
Title
2019
JOFC
Efficient Constant-Round Multi-party Computation Combining BMR and SPDZ
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 📺
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
Dragos Rotaru Nigel P. Smart Martijn Stam
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
EUROCRYPT
2016
TCC
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
PKC
2015
CRYPTO
2014
CRYPTO
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
ASIACRYPT
2014
CHES
2013
ASIACRYPT
2012
EUROCRYPT
2012
CRYPTO
2012
CRYPTO
2012
PKC
2011
JOFC
2010
PKC
2010
PKC
2010
JOFC
2010
EPRINT
The Fiat--Shamir Transform for Group and Ring Signature Schemes
M.-F. Lee Nigel P. Smart B. Warinschi
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.
2009
ASIACRYPT
2009
ASIACRYPT
2008
JOFC
2008
EPRINT
A Modular Security Analysis of the TLS Handshake Protocol
P. Morrissey Nigel P. Smart B. Warinschi
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.
2008
ASIACRYPT
2007
PKC
2007
EPRINT
Executing Modular Exponentiation on a Graphics Accelerator
Andrew Moss Dan Page Nigel P. Smart
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
CRYPTO
2006
EPRINT
High Security Pairing-Based Cryptography Revisited
R. Granger Nigel P. Smart D. Page
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
F. Hess Nigel P. Smart F. Vercauteren
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
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
L. Chen Nigel P. Smart Z. Cheng
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
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
R Granger Nigel P. Smart
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
L. Chen Nigel P. Smart Z. Cheng
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
CHES
2005
EPRINT
Generic Constructions of Identity-Based and Certificateless KEMs
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
Nigel P. Smart Frederik Vercauteren
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
L. Chen Z. Cheng J. Malone-Lee Nigel P. Smart
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
M. Barbosa R. Noad D. Page Nigel P. Smart
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
CHES
2004
EUROCRYPT
2004
EPRINT
A comparison of MNT curves and supersingular curves
D. Page Nigel P. Smart F. Vercauteren
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
S.S. Al-Riyami J. Malone-Lee Nigel P. Smart
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
CHES
2003
EPRINT
Projective Coordinates Leak
David Naccache Nigel P. Smart Jacques Stern
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
CHES
2002
CRYPTO
2002
EUROCRYPT
2002
EPRINT
Point Multiplication on Ordinary Elliptic Curves over Fields of Characteristic Three
Nigel P. Smart J. Westwood
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
P.J. Leadbitter Nigel P. Smart
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.
2002
JOFC
2001
CHES
2001
CHES
2001
CHES
2001
EUROCRYPT
2001
EPRINT
Extending the GHS Weil Descent Attack
Steven D. Galbraith F. Hess Nigel P. Smart
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
Nigel P. Smart
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.
1999
EUROCRYPT
1999
JOFC
1999
JOFC
1999
JOFC

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
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