BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Magali Bardet

Magali Bardet contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Cryptography and SecurityInformation Theorymath.ITData Structures and Algorithmsmath.AGSymbolic Computation

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
6topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2022arXiv

Improvement of algebraic attacks for solving superdetermined MinRank instances

The MinRank (MR) problem is a computational problem that arises in many cryptographic applications. In Verbel et al. (PQCrypto 2019), the authors introduced a new way to solve superdetermined instances of the MinRank problem, starting from the bilinear Kipnis-Shamir (KS) modeling. They use linear algebra on specific Macaulay matrices, considering only multiples of the initial equations by one block of variables, the so called ''kernel'' variables. Later, Bardet et al. (Asiacrypt 2020) introduced a new Support Minors modeling (SM), that consider the Pl{ü}cker coordinates associated to the kernel variables, i.e. the maximal minors of the Kernel matrix in the KS modeling. In this paper, we give a complete algebraic explanation of the link between the (KS) and (SM) modelings (for any instance). We then show that superdetermined MinRank instances can be seen as easy instances of the SM modeling. In particular, we show that performing computation at the smallest possible degree (the ''first degree fall'') and the smallest possible number of variables is not always the best strategy. We give complexity estimates of the attack for generic random instances.We apply those results to the DAGS cryptosystem, that was submitted to the first round of the NIST standardization process. We show that the algebraic attack from Barelli and Couvreur (Asiacrypt 2018), improved in Bardet et al. (CBC 2019), is a particular superdetermined MinRank instance.Here, the instances are not generic, but we show that it is possible to analyse the particular instances from DAGS and provide a way toselect the optimal parameters (number of shortened positions) to solve a particular instance.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

An algebraic approach to the Rank Support Learning problem

Rank-metric code-based cryptography relies on the hardness of decoding a random linear code in the rank metric. The Rank Support Learning problem (RSL) is a variant where an attacker has access to N decoding instances whose errors have the same support and wants to solve one of them. This problem is for instance used in the Durandal signature scheme. In this paper, we propose an algebraic attack on RSL which clearly outperforms the previous attacks to solve this problem. We build upon Bardet et al., Asiacrypt 2020, where similar techniques are used to solve MinRank and RD. However, our analysis is simpler and overall our attack relies on very elementary assumptions compared to standard Gr{ö}bner bases attacks. In particular, our results show that key recovery attacks on Durandal are more efficient than was previously thought.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

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

Rank Decoding (RD) is the main underlying problem in rank-based cryptography. Based on this problem and quasi-cyclic 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 have been studied to solve RD: combinatorial ones and algebraic ones. While the former has been studied extensively, a better understanding of the latter was recently obtained by Bardet et al. (EUROCRYPT20) where it appeared that algebraic attacks can often be more efficient than combinatorial ones for cryptographic parameters. 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 respectively in 70, 86, and 158, to be compared to 117, 144, and 197 for the aforementionned previous attack. Moreover, unlike this previous attack, ours does not need generic Gröbner basis algorithms since it only requires to solve a linear system. For a case called overdetermined, this modeling allows us to avoid Gröbner basis computations by going directly to solving a linear system. For the other case, called underdetermined, we also improve the results from the previous attack by combining the Ourivski-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 them 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An Algebraic Attack on Rank Metric Code-Based Cryptosystems

The Rank metric decoding problem is the main problem considered in cryptography based on codes in the rank metric. Very efficient schemes based on this problem or quasi-cyclic versions of it have been proposed recently, such as those in the submissions ROLLO and RQC currently at the second round of the NIST Post-Quantum Cryptography Standardization Process. While combinatorial attacks on this problem have been extensively studied and seem now well understood, the situation is not as satisfactory for algebraic attacks, for which previous work essentially suggested that they were ineffective for cryptographic parameters. In this paper, starting from Ourivski and Johansson's algebraic modelling of the problem into a system of polynomial equations, we show how to augment this system with easily computed equations so that the augmented system is solved much faster via Groebner bases. This happens because the augmented system has solving degree $r$, $r+1$ or $r+2$ depending on the parameters, where $r$ is the rank weight, which we show by extending results from Verbel et al. (PQCrypto 2019) on systems arising from the MinRank problem; with target rank $r$, Verbel et al. lower the solving degree to $r+2$, and even less for some favorable instances that they call superdetermined. We give complexity bounds for this approach as well as practical timings of an implementation using Magma. This improves upon the previously known complexity estimates for both Groebner basis and (non-quantum) combinatorial approaches, and for example leads to an attack in 200 bits on ROLLO-I-256 whose claimed security was 256 bits.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Permutation Code Equivalence is not Harder than Graph Isomorphism when Hulls are Trivial

The paper deals with the problem of deciding if two finite-dimensional linear subspaces over an arbitrary field are identical up to a permutation of the coordinates. This problem is referred to as the permutation code equivalence. We show that given access to a subroutine that decides if two weighted undirected graphs are isomorphic, one may deterministically decide the permutation code equivalence provided that the underlying vector spaces intersect trivially with their orthogonal complement with respect to an arbitrary inner product. Such a class of vector spaces is usually called linear codes with trivial hulls. The reduction is efficient because it essentially boils down to computing the inverse of a square matrix of order the length of the involved codes. Experimental results obtained with randomly drawn binary codes having trivial hulls show that permutation code equivalence can be decided in a few minutes for lengths up to 50,000.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Practical Algebraic Attack on DAGS

DAGS scheme is a key encapsulation mechanism (KEM) based on quasi-dyadic alternant codes that was submitted to NIST standardization process for a quantum resistant public key algorithm. Recently an algebraic attack was devised by Barelli and Couvreur (Asiacrypt 2018) that efficiently recovers the private key. It shows that DAGS can be totally cryptanalysed by solving a system of bilinear polynomial equations. However, some sets of DAGS parameters were not broken in practice. In this paper we improve the algebraic attack by showing that the original approach was not optimal in terms of the ratio of the number of equations to the number of variables. Contrary to the common belief that reducing at any cost the number of variables in a polynomial system is always beneficial, we actually observed that, provided that the ratio is increased and up to a threshold, the solving can be heavily improved by adding variables to the polynomial system. This enables us to recover the private keys in a few seconds. Furthermore, our experimentations also show that the maximum degree reached during the computation of the Gröbner basis is an important parameter that explains the efficiency of the attack. Finally, the authors of DAGS updated the parameters to take into account the algebraic cryptanalysis of Barelli and Couvreur. In the present article, we propose a hybrid approach that performs an exhaustive search on some variables and computes a Gröbner basis on the polynomial system involving the remaining variables. We then show that the updated set of parameters corresponding to 128-bit security can be broken with 2^83 operations.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Algebraic Properties of Polar Codes From a New Polynomial Formalism

Polar codes form a very powerful family of codes with a low complexity decoding algorithm that attain many information theoretic limits in error correction and source coding. These codes are closely related to Reed-Muller codes because both can be described with the same algebraic formalism, namely they are generated by evaluations of monomials. However, finding the right set of generating monomials for a polar code which optimises the decoding performances is a hard task and channel dependent. The purpose of this paper is to reveal some universal properties of these monomials. We will namely prove that there is a way to define a nontrivial (partial) order on monomials so that the monomials generating a polar code devised fo a binary-input symmetric channel always form a decreasing set. This property turns out to have rather deep consequences on the structure of the polar code. Indeed, the permutation group of a decreasing monomial code contains a large group called lower triangular affine group. Furthermore, the codewords of minimum weight correspond exactly to the orbits of the minimum weight codewords that are obtained from (evaluations) of monomials of the generating set. In particular, it gives an efficient way of counting the number of minimum weight codewords of a decreasing monomial code and henceforth of a polar code.

0 citations0 reviewsNo code linkedOpen access