2024 - T3 - WS3 - Quantum technologies for cryptography

Collection 2024 - T3 - WS3 - Quantum technologies for cryptography

Organisateur(s) Kahrobaei, Delaram ; Movassagh, Ramis ; Perret, Ludovic ; Broadbent, Anne
Date(s) 02/12/2024 - 06/12/2024
URL associée https://indico.math.cnrs.fr/event/5778/
14 15

Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs

De Pouria Fallahpour

The Learning With Errors (LWE) problem asks to find a vector s from an input of the form (A, b = As+e), for a matrix A and a vector e that has small-magnitude entries. In this talk, I focus on the task of sampling LWE instances. As these are extremely sparse in their range, it may seem plausible that the only way to proceed is to first create s and e and then set b = As+e. In particular, such an instance sampler knows the solution. This raises the question whether it is possible to obliviously sample (A, As+e), namely, without knowing the underlying secret s. A variant of the assumption that oblivious LWE sampling is hard has been used in a series of works to analyze the security of candidate constructions of Succinct Non-interactive Arguments of Knowledge (SNARKs). As the assumption is related to LWE, these SNARKs have been conjectured to be secure in the presence of quantum adversaries. The main focus of the talk is a quantum polynomial-time algorithm that samples well-distributed LWE instances while provably not knowing the solution, under the assumption that LWE is hard. Moreover, the approach works for a vast range of LWE parameterizations, including those used in the above-mentioned SNARKs. This invalidates the assumptions used in their security analyses, although it does not yield attacks against the constructions themselves.

Informations sur la vidéo

Données de citation

  • DOI 10.57987/IHP.2024.T3.WS3.014
  • Citer cette vidéo Fallahpour, Pouria (06/12/2024). Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs. IHP. Audiovisual resource. DOI: 10.57987/IHP.2024.T3.WS3.014
  • URL https://dx.doi.org/10.57987/IHP.2024.T3.WS3.014

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow




Inscrivez-vous

  • Mettez des vidéos en favori
  • Ajoutez des vidéos à regarder plus tard &
    conservez votre historique de consultation
  • Commentez avec la communauté
    scientifique
  • Recevez des notifications de mise à jour
    de vos sujets favoris
Donner son avis