Publications associées à Apprentissage avec erreurs

Lattice-Based Blind Signatures: Short, Efficient, and Round-Optimal

We propose a 2-round blind signature protocol based on the random oracle heuristic and the hardness of standard lattice problems (Ring/Module-SIS/LWE and NTRU) with a signature size of 22 KB. The protocol is round-optimal and has a transcript size that can ...

Assoc Computing Machinery2023

Efficient protocols for oblivious linear function evaluation from ring-LWE

Juan Ramón Troncoso-Pastoriza

An oblivious linear function evaluation protocol, or OLE, is a two-party protocol for the function f (x) = ax + b, where a sender inputs the field elements a, b, and a receiver inputs x and learns f (x). OLE can be used to build secret-shared multiplicatio ...

IOS PRESS2022

Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier

Alessandro Chiesa

We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model when instantiated with any probabilistically checkable proof and any collapsing hash function (which in turn exist based on the post-quantum hardness ...

IEEE COMPUTER SOC2022

Optimization Over Banach Spaces: A Unified View on Supervised Learning and Inverse Problems

Shayan Aziznejad

In this thesis, we reveal that supervised learning and inverse problems share similar mathematical foundations. Consequently, we are able to present a unified variational view of these tasks that we formulate as optimization problems posed over infinite-di ...

EPFL2022

Revisiting Multivariate Ring Learning with Errors and Its Applications on Lattice-Based Cryptography

Juan Ramón Troncoso-Pastoriza

The “Multivariate Ring Learning with Errors” problem was presented as a generalization of Ring Learning with Errors (RLWE), introducing efficiency improvements with respect to the RLWE counterpart thanks to its multivariate structure. Nevertheless, the rec ...

2021

Towards Efficient LPN-Based Symmetric Encryption

Serge Vaudenay, Sonia Mihaela Bogos, Dario Korolija, Thomas Locher

Due to the rapidly growing number of devices that need to communicate securely, there is still significant interest in the development of efficient encryption schemes. It is important to maintain a portfolio of different constructions in order to enable a ...

Springer International Publishing AG2021

Multiparty Homomorphic Encryption from Ring-Learning-with-Errors

Jean-Pierre Hubaux, Juan Ramón Troncoso-Pastoriza, Jean-Philippe Léonard Bossuat, Christian Vincent Mouchet

We propose and evaluate a secure-multiparty-computation (MPC) solution in the semi-honest model with dishonest majority that is based on multiparty homomorphic encryption (MHE). To support our solution, we introduce a multiparty version of the Brakerski-Fa ...

2021

Byzantine machine learning

Rachid Guerraoui, Mahsa Taziki, El Mahdi El Mhamdi, Sébastien Louis Alexandre Rouault

The present invention concerns computer-implemented methods for training a machine learning model using Stochastic Gradient Descent, SGD. In one embodiment, the method is performed by a first computer in a distributed computing environment and comprises pe ...

2020

Multiquadratic Rings and Walsh-Hadamard Transforms for Oblivious Linear Function Evaluation

Juan Ramón Troncoso-Pastoriza

The Ring Learning with Errors (RLWE) problem has become one of the most widely used cryptographic assumptions for the construction of modern cryptographic primitives. Most of these solutions make use of power-of-two cyclotomic rings mainly due to its simpl ...

IEEE2020

Synthesis of Flexible Accelerators for Early Adoption of Ring-LWE Post-quantum Cryptography

Francesco Regazzoni, Subhadeep Banik, Hamid Nejatollahi

The advent of the quantum computer makes current public-key infrastructure insecure. Cryptography community is addressing this problem by designing, efficiently implementing, and evaluating novel public-key algorithms capable of withstanding quantum comput ...

ASSOC COMPUTING MACHINERY2020

Classical Misuse Attacks on NIST Round 2 PQC: The Power of Rank-Based Schemes

Serge Vaudenay, Loïs Evan Huguenin-Dumittan

The US National Institute of Standards and Technology (NIST) recently announced the public-key cryptosystems (PKC) that have passed to the second round of the post-quantum standardization process. Most of these PKC come in two flavours: a weak IND-CPA vers ...

Springer, Cham2020

Byzantine tolerant gradient descent for distributed machine learning with adversaries

Rachid Guerraoui, El Mahdi El Mhamdi, Julien Michel Stainer, Peva François Blanchard

The present application concerns a computer-implemented method for training a machine learning model in a distributed fashion, using Stochastic Gradient Descent, SGD, wherein the method is performed by a first computer in a distributed computing environmen ...

2019

Short Stickelberger Class Relations and Application to Ideal-SVP

Benjamin Pierre Charles Wesolowski

The worst-case hardness of finding short vectors in ideals of cyclotomic number fields (Ideal-SVP) is a central matter in lattice based cryptography. Assuming the worst-case hardness of Ideal-SVP allows to prove the Ring-LWE and Ring-SIS assumptions, and t ...

Springer International Publishing Ag2017

LPN in Cryptography : an Algorithmic Study

Sonia Mihaela Bogos

The security of public-key cryptography relies on well-studied hard problems, problems for which we do not have efficient algorithms. Factorization and discrete logarithm are the two most known and used hard problems. Unfortunately, they can be easily solv ...

EPFL2017

On solving LPN using BKW and variants Implementation and Analysis

Serge Vaudenay, Sonia Mihaela Bogos, Florian Tramèr

The Learning Parity with Noise problem (LPN) is appealing in cryptography as it is considered to remain hard in the post-quantum world. It is also a good candidate for lightweight devices due to its simplicity. In this paper we provide a comprehensive anal ...

Springer2016

Better Algorithms for LWE and LWR

Serge Vaudenay, Alexandre Raphaël Duc, Florian Tramèr

The Learning With Error problem (LWE) is becoming more and more used in cryptography, for instance, in the design of some fully homomorphic encryption schemes. It is thus of primordial importance to find the best algorithms that might solve this problem so ...

Springer2015

A sieve algorithm based on overlattices

Anja Annemone Becker

In this paper, we present a heuristic algorithm for solving exact, as well as approximate, shortest vector and closest vector problems on lattices. The algorithm can be seen as a modified sieving algorithm for which the vectors of the intermediate sets lie ...

Cambridge Univ Press2014