Sommaire

  • Cet exposé a été présenté le 23 février 2018.

Description

  • Orateur

    Weiqiang Wen - ENS de Lyon

The hardness of the learning with errors (LWE) problem is one of the most fruitful resources of modern cryptography. In particular, it is one of the most prominent candidates for secure post-quantum cryptography. Understanding its quantum complexity is therefore an important goal. We show that under quantum polynomial time reductions, LWE is equivalent to a relaxed version of the dihedral coset problem (DCP), which we call extrapolated DCP (eDCP). The extent of extrapolation varies with the LWE noise rate. By considering different extents of extrapolation, our result generalizes Regev's famous proof that if DCP is in BQP (quantum poly-time) then so is LWE (FOCS'02). We also discuss a connection between eDCP and Childs and Van Dam's algorithm for generalized hidden shift problems (SODA'07). Our result implies that a BQP solution for LWE might not require the full power of solving DCP, but rather only a solution for its relaxed version, eDCP, which could be easier.

Prochains exposés

  • Chiffrement homomorphe à l'aide des groupes après Nuida

    • 27 novembre 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Pierre Guillot - Ravel Technologies/Université de strasbourg

    Nuida et d'autres ont montré comment on peut obtenir un protocole de chiffrement pleinement homomorphe si l'on sait chiffrer les éléments d'un groupe G convenable, tout en sachant faire l'opération de G "en homomorphe". Les exemples étaient jusqu'à présent limités au chiffrement d'un bit à la fois, avec beaucoup d'opérations à effectuer pour "simuler" les portes logiques usuelles. Je vais[…]
    • Cryptography

  • Post-Quantum Signatures from Symmetric-Key-Friendly Techniques: From MPC-in-the-Head to VOLE-in-the-Head

    • 04 décembre 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Dung Bui - Northwestern University

    The MPC-in-the-Head (MPCitH) paradigm turns a secure multiparty computation protocol into a zero-knowledge proof and, via Fiat–Shamir, into a signature scheme whose security relies only on symmetric-key primitives. The framework of Katz, Kolesnikov and Wang (KKW, CCS18), which moves most of the MPC work into a committed preprocessing phase that the verifier checks by opening all-but-one of the[…]
  • Distinguishing and Attacking McEliece Cryptosystems Using GRS Codes with Higher-Weight Mask

    • 11 décembre 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Michael Schaller - University of Zürich, Applied Algebra group

    Due to the insecurity of McEliece cryptosystems instantiated with Generalized Reed-Solomon (GRS) codes, there have been several proposals of McEliece type systems that replace the permutation matrix by a matrix $M$ with larger row and column weight. In many of them, the secret key is still a GRS code.There have been successful attacks on some of those schemes with row and column weight between $1$[…]
  • Nouveaux doctorants

    • 08 janvier 2027 (13:45 - 14:45)

    • Salle Guernesey à l'ISTIC

    Exposés courts des nouveaux doctorants (Elouan, Quentin, Eliot)
Voir les exposés passés