BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen - ECPv5.7.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
X-ORIGINAL-URL:https://www.greyc.fr
X-WR-CALDESC:évènements pour GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20250330T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20251026T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20250416T140000
DTEND;TZID=Europe/Paris:20250416T150000
DTSTAMP:20260421T115420
CREATED:20250404T100723Z
LAST-MODIFIED:20250404T100753Z
UID:11821-1744812000-1744815600@www.greyc.fr
SUMMARY:Kévin Carrier - Combinatorial Attacks On The Decoding Problem
DESCRIPTION:The decoding problem is fundamental in post-quantum cryptography. It can be broadly described as essentially solving a linear system with a non-linear constraint on the solution. Phrased this way\, the problem applies to both code-based and lattice-based cryptography. For example\, the linear system may be defined over FF_q\, with the non-linear constraint being a condition on the Hamming weight of the solution (McEliece\, BIKE\, HQC\, Wave\, SDitH…) or even a condition on the subgroup in which the solution resides (CROSS). The system may also be defined over FF_q^m\, with the non-linear constraint being a condition on the rank of the vector space spanned by the solution vectors (Mirath\, Ryde). In lattice-based cryptography\, the system is generally defined over ZZ_q\, with the non-linear constraint being a condition on the Euclidean length of the solution (Kyber\, Falcon\, Dilithium\, Hawk…). The list above is far from exhaustive and can extend to other areas such as Fully Homomorphic Encryption (FHE) or the blind code recognition problem (reverse of telecomunication). \nCombinatorial techniques for solving the decoding problem (in both codes and lattices) can be classified into two categories: primal attacks and dual attacks. Primal attacks aim to recover a set of information about the solution\, essentially a compressed description of the solution. Exhaustive search can then be accelerated using techniques like the Birthday Paradox (collision search). More recently\, techniques based on nearest-neighbor searches have emerged and significantly sped up primal attacks. The nearest-neighbor problem involves finding close pairs in a list. The notion of closeness can be extended to adapt to the non-linear constraint of the original decoding problem. However\, this requires adapting known techniques to these different variants of the nearest-neighbor problem. \nIt turns out that primal decoding techniques are often more effective when there are few equations in the system relative to the number of unknowns. Therefore\, when the number of equations is close to the number of unknowns\, is it possible to reduce the problem to another decoding problem where the number of equations is smaller? One approach to this is to dualize the decoding problem: instead of searching for a solution in a specific subspace\, could we reduce the problem to finding a solution in the orthogonal/dual subspace? Some recent attacks\, known as dual attacks\, offer an initial attempt at such a reduction. However\, dual attacks are a topic of controversy. In particular\, the recent dual attack by Matzov\, which claims to significantly lower the security level of Kyber\, a lattice-based cryptosystem currently being standardized by NIST\, has not been widely accepted. The analysis behind this attack relies on a set of assumptions that\, in certain scenarios\, have been shown to contradict established theorems or well-tested heuristics. Nonetheless\, we present new techniques for analyzing dual attacks. Specifically\, we avoid the same independence assumption made in Matzov’s work\, allowing us to reassess the complexity of dual attacks on Kyber and demonstrate that its security levels fall below the NIST requirements.
URL:https://www.greyc.fr/event/kevin-carrier-combinatorial-attacks-on-the-decoding-problem/
LOCATION:Sciences 3- S3 351
CATEGORIES:General,News,Safe,Séminaire Cryptologie et sécurité
END:VEVENT
END:VCALENDAR