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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Rank Decoding (RD) is the main underlying problem in rank-based cryptography.Based on this problem and quasi-cyclic versions of it, very efficient schemeshave been proposed recently, such as those in the ROLLO and RQC submissions,which have reached the second round of the NIST Post-Quantum competition. Twomain approaches have been studied to solve RD: combinatorial ones and algebraicones. While the former has been studied extensively, a better understanding ofthe latter was recently obtained by Bardet et al. (EUROCRYPT20) where itappeared that algebraic attacks can often be more efficient than combinatorialones for cryptographic parameters. This paper gives substantial improvementsupon this attack in terms both of complexity and of the assumptions required bythe cryptanalysis. We present attacks for ROLLO-I-128, 192, and 256 with bitcomplexity respectively in 70, 86, and 158, to be compared to 117, 144, and 197for the aforementionned previous attack. Moreover, unlike this previous attack,ours does not need generic Gr\"obner basis algorithms since it only requires tosolve a linear system. For a case called overdetermined, this modeling allowsus to avoid Gr\"obner basis computations by going directly to solving a linearsystem. For the other case, called underdetermined, we also improve the resultsfrom the previous attack by combining the Ourivski-Johansson modeling togetherwith a new modeling for a generic MinRank instance; the latter modeling allowsus to refine the analysis of MinRank's complexity given in the paper by Verbelet al. (PQC19). Finally, since the proposed parameters of ROLLO and RQC arecompletely broken by our new attack, we give examples of new parameters forROLLO and RQC that make them resistant to our attacks. These new parametersshow that these systems remain attractive, with a loss of only about 50\% interms of key size for ROLLO-I.

Improvements of Algebraic Attacks for solving the Rank Decoding and MinRank problems