International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Nicolas Gama

Publications

Year
Venue
Title
2023
EUROCRYPT
The Return of the SDitH
This paper presents a code-based signature scheme based on the well-known syndrome decoding (SD) problem. The scheme builds upon a recent line of research which uses the Multi-Party-Computation-in-the-Head (MPCitH) approach to construct efficient zero-knowledge proofs, such as Syndrome Decoding in the Head (SDitH), and builds signature schemes from them using the Fiat-Shamir transform. At the heart of our proposal is a new approach, Hypercube-MPCitH, to amplify the soundness of any MPC protocol that uses additive secret sharing. An MPCitH protocol with N parties can be repeated D times using parallel composition to reach the same soundness as a protocol run with N^D parties. However, the former comes with D times higher communication costs, often mainly contributed by the usage of D `auxiliary' states (which in general have a significantly bigger impact on size than random states). Instead of that, we begin by generating N^D shares, arranged into a D-dimensional hypercube of side N containing only one `auxiliary' state. We derive from this hypercube D sharings of size N which are used to run D instances of an N party MPC protocol. Hypercube-MPCitH leads to a protocol with 1/N^D soundness error, requiring N^D offline computation, but with only N*D online computation, and only one `auxiliary'. As the (potentially offline) share generation phase is generally inexpensive, this leads to trade-offs that are superior to just using parallel composition. Our novel method of share generation and aggregation not only improves certain MPCitH protocols in general but also shows in concrete improvements of signature schemes. Specifically, we apply it to the work of Feneuil, Joux, and Rivain (CRYPTO'22) on code-based signatures, and obtain a new signature scheme that achieves a 8.1x improvement in global runtime and a 30x improvement in online runtime for their shortest signatures size (8,481 Bytes). It is also possible to leverage the fact that most computations are offline to define parameter sets leading to smaller signatures: 6,784 Bytes for 26 ms offline and 5,689 Bytes for 320 ms offline. For NIST security level 1, online signature cost is around 3 million cycles (<1 ms on commodity processors), regardless of signature size.
2023
JOFC
Manticore: A Framework for Efficient Multiparty Computation Supporting Real Number and Boolean Arithmetic
We propose a novel framework, $$\texttt{Manticore}$$ Manticore , for multiparty computations, with full threshold and semi-honest security model, supporting a combination of real number arithmetic (arithmetic shares), Boolean arithmetic (Boolean shares) and garbled circuits (Yao shares). In contrast to prior work (Mohassel and Zhang, in 2017 IEEE symposium on security and privacy (SP), 2017; Mohassel and Rindal, in Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, 2018), $$\texttt{Manticore}$$ Manticore mitigates overflows, which is of paramount importance for machine learning applications, without compromising efficiency or security. Compared to other overflow-free recent techniques such as MP-SPDZ (Escudero et al., in 40th annual international cryptology conference, CRYPTO. Lecture notes in computer science, 2020) that convert arithmetic to Boolean shares, $$\texttt{Manticore}$$ Manticore uses an efficient modular lifting/truncation method that allows for scalable high numerical precision computations with optimal numerical windows and hence, highly efficient online phases. We adapt basic MPC operations such as real-valued polynomial evaluation, division, logarithms, exponentials, Fourier series evaluations and oblivious comparisons to $$\texttt{Manticore}$$ Manticore by employing our modular lift in combination with existing efficient conversions between arithmetic, Boolean and Yao shares. We also describe a highly scalable computations of logistic regression models with real-world training data sizes and high numerical precision through PCA and blockwise variants (for memory and runtime optimizations) based on second-order optimization techniques. On a dataset of 50 M samples and 50 features distributed among two players, the online phase completes in 14.5 h with at least 10 decimal digits of precision compared to plaintext training. The setup phase of $$\texttt{Manticore}$$ Manticore is supported in both the trusted dealer and the interactive models allowing for tradeoffs between efficiency and stronger security. The highly efficient online phase makes the framework particularly suitable for MPC applications where the output of the setup phase is part of the input of the protocol (such as MPC-in-the-head or Prio ).
2023
ASIACRYPT
To attest or not to attest, this is the question – Provable attestation in FIDO2
FIDO2 is currently the main initiative for passwordless authentication in web servers. It mandates the use of secure hardware authenticators to protect the authentication protocol's secrets from compromise. However, to ensure that only secure authenticators are being used, web servers need a method to attest their properties.The FIDO2 specifications allow for authenticators and web servers to choose between different attestation modes to prove the characteristics of an authenticator, however the properties of most these modes have not been analysed in the context of FIDO2. In this work, we analyse the security and privacy properties of FIDO2 when the different attestation modes included in the standard are used, and show that they lack good balance between security, privacy and revocation of corrupted devices. For example, the basic attestation mode prevents remote servers from tracing user's actions across different services while requiring reduced trust assumptions. However in case one device is compromised, all the devices from the same batch (e.g., of the same brand or model) need to be recalled, which can be quite complex (and arguably impractical) in consumer scenarios. As a consequence we suggest a new attestation mode based on the recently proposed TokenWeaver, which provide more convenient mechanisms for revoking a single token while maintaining user privacy.
2019
JOFC
TFHE: Fast Fully Homomorphic Encryption Over the Torus
This work describes a fast fully homomorphic encryption scheme over the torus (TFHE) that revisits, generalizes and improves the fully homomorphic encryption (FHE) based on GSW and its ring variants. The simplest FHE schemes consist in bootstrapped binary gates. In this gate bootstrapping mode, we show that the scheme FHEW of Ducas and Micciancio (Eurocrypt, 2015) can be expressed only in terms of external product between a GSW and an LWE ciphertext. As a consequence of this result and of other optimizations, we decrease the running time of their bootstrapping from 690 to 13 ms single core, using 16 MB bootstrapping key instead of 1 GB, and preserving the security parameter. In leveled homomorphic mode, we propose two methods to manipulate packed data, in order to decrease the ciphertext expansion and to optimize the evaluation of lookup tables and arbitrary functions in $${\mathrm {RingGSW}}$$RingGSW-based homomorphic schemes. We also extend the automata logic, introduced in Gama et al. (Eurocrypt, 2016), to the efficient leveled evaluation of weighted automata, and present a new homomorphic counter called $$\mathrm {TBSR}$$TBSR, that supports all the elementary operations that occur in a multiplication. These improvements speed up the evaluation of most arithmetic functions in a packed leveled mode, with a noise overhead that remains additive. We finally present a new circuit bootstrapping that converts $$\mathsf {LWE}$$LWE ciphertexts into low-noise $${\mathrm {RingGSW}}$$RingGSW ciphertexts in just 137 ms, which makes the leveled mode of TFHE composable and which is fast enough to speed up arithmetic functions, compared to the gate bootstrapping approach. Finally, we provide an alternative practical analysis of LWE based schemes, which directly relates the security parameter to the error rate of LWE and the entropy of the LWE secret key, and we propose concrete parameter sets and timing comparison for all our constructions.
2017
ASIACRYPT
2016
EUROCRYPT
2016
ASIACRYPT
2010
ASIACRYPT
2010
EUROCRYPT
2008
EUROCRYPT
2007
PKC
2006
CRYPTO
2006
EUROCRYPT

Program Committees

Eurocrypt 2017