International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Nigel P. Smart

ORCID: 0000-0003-3567-3304

Publications

Year
Venue
Title
2023
JOFC
2023
ASIACRYPT
MPC With Delayed Parties Over Star-Like Networks
This paper examines multi-party computation protocols in the presence of two major constraints present in deployed systems. Firstly, we consider the situation where the parties are connected not by direct point-to-point connections, but by a star-like topology with a few central post-office style relays. Secondly, we consider MPC protocols with a strong honest majority ($t \gg n/2$) in which we have stragglers (some parties are progressing slower than others). We model stragglers by allowing the adversary to delay messages to and from some parties for a given length of time. We first show that having only a single honest relay is enough to ensure consensus of the messages sent within a protocol; secondly, we show that special care must be taken to describe multiplication protocols in the case of relays and stragglers; thirdly, we present an efficient honest-majority MPC protocol which can be run ontop of the relays and which provides active-security with abort in the case of a strong honest majority, even when run with stragglers. We back up our protocol presentation with both experimental evaluations and simulations of the effect of the relays and delays on our protocol.
2022
ASIACRYPT
FINAL: Faster FHE instantiated with NTRU and LWE 📺
The NTRU problem is a promising candidate to build efficient Fully Homomorphic Encryption (FHE).However, all the existing proposals (e.g. LTV, YASHE) need so-called `overstretched' parameters of NTRU to enable homomorphic operations. It was shown by Albrecht~et~al. (CRYPTO~2016) that these parameters are vulnerable against subfield lattice attacks. Based on a recent, more detailed analysis of the overstretched NTRU assumption by Ducas and van Woerden (ASIACRYPT~2021), we construct two FHE schemes whose NTRU parameters lie outside the overstretched range.The first scheme is based solely on NTRU and demonstrates competitive performance against the state-of-the-art FHE schemes including TFHE. Our second scheme, which is based on both the NTRU and LWE assumptions, outperforms TFHE with a 28\% faster bootstrapping and 45\% smaller bootstrapping and key-switching keys.
2021
JOFC
High-Performance Multi-party Computation for Binary Circuits Based on Oblivious Transfer
We present a unified view of the two-party and multi-party computation protocols based on oblivious transfer first outlined in Nielsen et al. (CRYPTO 2012) and Larraia et al. (CRYPTO 2014). We present a number of modifications and improvements to these earlier presentations, as well as full proofs of the entire protocol. Improvements include a unified pre-processing and online MAC methodology, mechanisms to pass between different MAC variants and fixing a minor bug in the protocol of Larraia et al. in relation to a selective failure attack. It also fixes a minor bug in Nielsen et al. resulting from using Jensen’s inequality in the wrong direction in an analysis.
2021
EUROCRYPT
Large Scale, Actively Secure Computation from LPN and Free-XOR Garbled Circuits 📺
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 📺
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.
2021
ASIACRYPT
Gladius: LWR based efficient hybrid public key encryption with distributed decryption 📺
Standard hybrid encryption schemes based on the KEM-DEM framework are hard to implement efficiently in a distributed manner whilst maintaining the CCA security property of the scheme. This is because the DEM needs to be decrypted under the key encapsulated by the KEM, before the whole ciphertext is declared valid. In this paper we present a new variant of the KEM-DEM framework, closely related to Tag-KEMs, which sidesteps this issue. We then present a post-quantum KEM for this framework based on Learning-with-Rounding, which is designed specifically to have fast distributed decryption. Our combined construction of a hybrid encryption scheme with Learning-with-Rounding based KEM, called Gladius, is closely related to the NIST Round 3 candidate called Saber. Finally, we give a prototype distributed implementation that achieves a decapsulation time of 4.99 seconds for three parties.
2021
JOFC
Actively Secure Setup for SPDZ
We present the first actively secure, practical protocol to generate the distributed secret keys needed in the SPDZ offline protocol. As an added bonus our protocol results in the resulting distribution of the public and secret keys are such that the associated SHE ‘noise’ analysis is the same as if the distributed keys were generated by a trusted setup. We implemented the presented protocol for distributed BGV key generation within the SCALE-MAMBA   framework. Our method makes use of a new method for creating doubly (or even more) authenticated bits in different MPC engines, which has applications in other areas of MPC-based secure computation. We were able to generate keys for two parties and a plaintext size of 64 bits in around 5 min, and a little more than 18 min for a 128-bit prime.
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
PKC
2015
CRYPTO
2014
CRYPTO
2014
ASIACRYPT
2014
CHES
2013
ASIACRYPT
2012
EUROCRYPT
2012
CRYPTO
2012
CRYPTO
2012
PKC
2011
JOFC
2010
PKC
2010
PKC
2010
JOFC
2009
ASIACRYPT
2009
ASIACRYPT
2008
JOFC
2008
ASIACRYPT
2007
PKC
2006
CRYPTO
2005
CHES
2004
CHES
2004
EUROCRYPT
2003
CHES
2002
CHES
2002
CRYPTO
2002
EUROCRYPT
2002
JOFC
2001
CHES
2001
CHES
2001
CHES
2001
EUROCRYPT
1999
EUROCRYPT
1999
JOFC
1999
JOFC
1999
JOFC

Program Committees

Eurocrypt 2022
Eurocrypt 2018
Crypto 2018
Eurocrypt 2016
Crypto 2016
Asiacrypt 2015
Crypto 2015
Crypto 2013
Eurocrypt 2013
PKC 2013
Asiacrypt 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 (2)
Martin R. Albrecht (1)
Victor Arribas (1)
Aner Ben-Efraim (1)
Naomi Benger (1)
Emad Heydari Beni (1)
Kamel Bentahar (1)
Begül Bilgin (1)
James Birkett (1)
Charlotte Bonte (1)
Sai Sheshank Burra (1)
Dario Catalano (1)
Liqun Chen (1)
Ashish Choudhary (1)
Kelong Cong (2)
Daniele Cozzo (1)
Ivan Damgård (1)
Alex Davidson (1)
Lauren De Meyer (1)
Alexander W. Dent (2)
Amit Deo (1)
Pooya Farshim (1)
Steven D. Galbraith (1)
Mariana Gama (1)
Pierrick Gaudry (1)
Craig Gentry (3)
Essam Ghadafi (1)
P. J. Green (1)
Shai Halevi (3)
Florian Hess (2)
Ilia Iliashenko (1)
Jeongeun Park (1)
Antoine Joux (1)
Enrique Larraia (2)
Peter J. Leadbitter (1)
Reynald Lercier (1)
Pierre-Yvan Liardet (1)
Yehuda Lindell (3)
Jake Loftus (1)
John Malone-Lee (4)
Varun Maram (1)
David May (1)
Payman Mohassel (1)
Paul Morrissey (3)
Henk L. Muller (1)
David Naccache (1)
Gregory Neven (2)
Jesper Buus Nielsen (1)
Ventzislav Nikov (1)
Svetla Nikova (1)
Richard Noad (1)
Peter Sebastian Nordholt (1)
Eran Omri (1)
Claudio Orlandi (1)
Emmanuela Orsini (6)
Daniel Page (2)
Valerio Pastro (1)
Arpita Patra (1)
Hilder Vitor Lima Pereira (1)
Duong Hieu Phan (1)
Benny Pinkas (3)
David Pointcheval (2)
Joop van de Pol (2)
Oscar Reparaz (1)
Dragos Rotaru (2)
Seyed Saeed Sadeghian (1)
Thomas Schneider (1)
Peter Scholl (1)
Jacob C. N. Schuldt (1)
Samir Siksek (1)
Eduardo Soria-Vazquez (2)
Martijn Stam (1)
Jacques Stern (2)
Titouan Tanguy (1)
Frederik Vercauteren (3)
Bogdan Warinschi (4)
Stephen C. Williams (1)
Tim Wood (1)
Avishay Yanai (2)
Yuval Yarom (1)
Oliver Zajonc (1)
Sarah Zakarias (1)