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:20220123T215045Z
UID:indico-event-6179@indico.math.cnrs.fr
DESCRIPTION:Rank Decoding (RD) is the main underlying problem in rank-base
d cryptography. Based on this problem and quasi-cyclic versions of it\, ve
ry efficient schemes have been proposed recently\, such as those in the RO
LLO and RQC submissions\, which have reached the second round of the NIST
Post-Quantum competition. Two main approaches have been studied to solve R
D: combinatorial ones and algebraic ones. While the former has been studie
d extensively\, a better understanding of the latter was recently obtained
by Bardet et al. (EUROCRYPT20) where it appeared that algebraic attacks c
an often be more efficient than combinatorial ones for cryptographic param
eters. This paper gives substantial improvements upon this attack in terms
both of complexity and of the assumptions required by the cryptanalysis.
We present attacks for ROLLO-I-128\, 192\, and 256 with bit complexity res
pectively in 70\, 86\, and 158\, to be compared to 117\, 144\, and 197 for
the aforementionned previous attack. Moreover\, unlike this previous atta
ck\, ours does not need generic Gröbner basis algorithms since it only re
quires to solve a linear system. For a case called overdetermined\, this m
odeling allows us to avoid Gröbner basis computations by going directly t
o solving a linear system. For the other case\, called underdetermined\, w
e also improve the results from the previous attack by combining the Ouriv
ski-Johansson modeling together with a new modeling for a generic MinRank
instance\; the latter modeling allows us to refine 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 completely broken by our new
attack\, we give examples of new parameters for ROLLO and RQC that make t
hem resistant to our attacks. These new parameters 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://ind
ico.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