English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Rank Decoding problem (RD) is at the core of rank-based cryptography.This problem can also be seen as a structured version of MinRank, which isubiquitous in multivariate cryptography. Recently, \cite{BBBGNRT20,BBCGPSTV20}proposed attacks based on two new algebraic modelings, namely the MaxMinorsmodeling which is specific to RD and the Support-Minors modeling which appliesto MinRank in general. Both improved significantly the complexity of algebraicattacks on these two problems. In the case of RD and contrarily to what wasbelieved up to now, these new attacks were shown to be able to outperformcombinatorial attacks and this even for very small field sizes.  However, we prove here that the analysis performed in \cite{BBCGPSTV20} forone of these attacks which consists in mixing the MaxMinors modeling with theSupport-Minors modeling to solve RD is too optimistic and leads tounderestimate the overall complexity. This is done by exhibiting lineardependencies between these equations and by considering an $\fqm$ version ofthese modelings which turns out to be instrumental for getting a betterunderstanding of both systems. Moreover, by working over $\Fqm$ rather thanover $\ff{q}$, we are able to drastically reduce the number of variables in thesystem and we (i) still keep enough algebraic equations to be able to solve thesystem, (ii) are able to analyze rigorously the complexity of our approach.This new approach may improve the older MaxMinors approach on RD from\cite{BBBGNRT20,BBCGPSTV20} for certain parameters. We also introduce a newhybrid approach on the Support-Minors system whose impact is much more generalsince it applies to any MinRank problem. This technique improves significantlythe complexity of the Support-Minors approach for small to moderate fieldsizes.

Revisiting Algebraic Attacks on MinRank and on the Rank Decoding Problem