BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Improvements of Algebraic Attacks for solving the Rank Decoding an
d MinRank problems
DTSTART;VALUE=DATE-TIME:20201203T093000Z
DTEND;VALUE=DATE-TIME:20201203T103000Z
DTSTAMP;VALUE=DATE-TIME:20221207T003100Z
UID:indico-event-6179@indico.math.cnrs.fr
DESCRIPTION:Speakers: Maxime Bros\n\nRank Decoding (RD) is the main underl
ying problem in rank-based cryptography. Based on this problem and quasi-c
yclic versions of it\, very efficient schemes have been proposed recently\
, such as those in the ROLLO and RQC submissions\, which have reached the
second round of the NIST Post-Quantum competition. Two main approaches hav
e been studied to solve RD: combinatorial ones and algebraic ones. While t
he former has been studied extensively\, a better understanding of the lat
ter was recently obtained by Bardet et al. (EUROCRYPT20) where it appeared
that algebraic attacks can often be more efficient than combinatorial one
s for cryptographic parameters. This paper gives substantial improvements
upon this attack in terms both of complexity and of the assumptions requir
ed by the cryptanalysis. We present attacks for ROLLO-I-128\, 192\, and 25
6 with bit complexity respectively in 70\, 86\, and 158\, to be compared t
o 117\, 144\, and 197 for the aforementionned previous attack. Moreover\,
unlike this previous attack\, ours does not need generic Gröbner basis al
gorithms since it only requires to solve a linear system. For a case calle
d overdetermined\, this modeling allows us to avoid Gröbner basis computa
tions by going directly to solving a linear system. For the other case\, c
alled underdetermined\, we also improve the results from the previous atta
ck by combining the Ourivski-Johansson modeling together with a new modeli
ng for a generic MinRank instance\; the latter modeling allows us to refin
e the analysis of MinRank's complexity given in the paper by Verbel et al.
(PQC19). Finally\, since the proposed parameters of ROLLO and RQC are com
pletely broken by our new attack\, we give examples of new parameters for
ROLLO and RQC that make them resistant to our attacks. These new parameter
s show that these systems remain attractive\, with a loss of only about 50
\\% in terms of key size for ROLLO-I.\n\nReference: https://arxiv.org/abs/
2002.08322\n\nhttps://indico.math.cnrs.fr/event/6179/
LOCATION:https://bbb.unilim.fr/b/vac-m6r-7dv
URL:https://indico.math.cnrs.fr/event/6179/
END:VEVENT
END:VCALENDAR