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

Philippe Gaborit

Philippe Gaborit contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Cryptography and SecurityInformation Theorymath.AGmath.IT

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
4topics
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

Code-based Signatures from New Proofs of Knowledge for the Syndrome Decoding Problem

In this paper, we study code-based signatures constructed from Proof of Knowledge (PoK). This line of work can be traced back to Stern who introduces the first efficient PoK for the syndrome decoding problem in 1993. Afterward, different variations were proposed in order to reduce signature's size. In practice, obtaining a smaller signature size relies on the interaction of two main considerations: (i) the underlying protocol and its soundness error and (ii) the type of optimizations which are compatible with a given protocol. Over the years, different variations were proposed to improve the Stern scheme such as the Veron scheme (with public key a noisy codeword rather than a syndrome), the AGS scheme which is a 5-pass protocol with cheating probability asymptotically equal to 1/2 and more recently the FJR approach which permits to decrease the cheating probability to 1/N but induces a performance overhead. Overall the length of the signature depends on a trade-off between: the scheme in itself, the possible optimizations and the cost of the implementation. The recent approaches which increase the cost of the implementation opens the door to many different type of trade-offs. In this paper we propose three new schemes and different trade-offs, which are all interesting in themselves, since depending on potential future optimizations a scheme may eventually become more efficient than another. All the schemes we propose use a trusted helper: a first scheme permits to get a 1/2 cheating probability, a second scheme permits to decrease the cheating probability in 1/N but with a different approach than the recent FJR scheme and at last a third scheme propose a Veron-like adaptation of the FJR scheme in which the public key is a noisy codeword rather than a syndrome. We provide an extensive comparison table which lists various trade-offs between our schemes and previous ones.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

LRPC codes with multiple syndromes: near ideal-size KEMs without ideals

We introduce a new rank-based key encapsulation mechanism (KEM) with public key and ciphertext sizes around 3.5 Kbytes each, for 128 bits of security, without using ideal structures. Such structures allow to compress objects, but give reductions to specific problems whose security is potentially weaker than for unstructured problems. To the best of our knowledge, our scheme improves in size all the existing unstructured post-quantum lattice or code-based algorithms such as FrodoKEM or Classic McEliece. Our technique, whose efficiency relies on properties of rank metric, is to build upon existing Low Rank Parity Check (LRPC) code-based KEMs and to send multiple syndromes in one ciphertext, allowing to reduce the parameters and still obtain an acceptable decoding failure rate. Our system relies on the hardness of the Rank Support Learning problem, a well-known variant of the Rank Syndrome Decoding problem. The gain on parameters is enough to significantly close the gap between ideal and non-ideal constructions. It enables to choose an error weight close to the rank Gilbert-Varshamov bound, which is a relatively harder zone for algebraic attacks. We also give a version of our KEM that keeps an ideal structure and permits to roughly divide the bandwidth by two compared to previous versions of LRPC KEMs submitted to the NIST with a Decoding Failure Rate (DFR) of $2^{-128}$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Quasi-Cyclic Stern Proof of Knowledge

The ongoing NIST standardization process has shown that Proof of Knowledge (PoK) based signatures have become an important type of possible post-quantum signatures. Regarding code-based cryptography, the original approach for PoK based signatures is the Stern protocol which allows to prove the knowledge of a small weight vector solving a given instance of the Syndrome Decoding (SD) problem over F2. It features a soundness error equal to 2/3. This protocol was improved a few years later by Véron who proposed a variation of the scheme based on the General Syndrome Decoding (GSD) problem which leads to better results in term of communication. A few years later, the AGS protocol introduced a variation of the Véron protocol based on Quasi-Cyclic (QC) matrices. The AGS protocol permits to obtain an asymptotic soundness error of 1/2 and an improvement in term of communications. In the present paper, we introduce the Quasi-Cyclic Stern PoK which constitutes an adaptation of the AGS scheme in a SD context, as well as several new optimizations for code-based PoK. Our main optimization on the size of the signature can't be applied to GSD based protocols such as AGS and therefore motivated the design of our new protocol. In addition, we also provide a special soundness proof that is compatible with the use of the Fiat-Shamir transform for 5-round protocols. This approach is valid for our protocol but also for the AGS protocol which was lacking such a proof. We compare our results with existing signatures including the recent code-based signatures based on PoK leveraging the MPC in the head paradigm. In practice, our new protocol is as fast as AGS while reducing its associated signature length by 20%. As a consequence, it constitutes an interesting trade-off between signature length and execution time for the design of a code-based signature relying only on the difficulty of the SD problem.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

RQC revisited and more cryptanalysis for Rank-based Cryptography

We propose two main contributions: first, we revisit the encryption scheme Rank Quasi-Cyclic (RQC) by introducing new efficient variations, in particular, a new class of codes, the Augmented Gabidulin codes; second, we propose new attacks against the Rank Support Learning (RSL), the Non-Homogeneous Rank Decoding (NHRSD), and the Non-Homogeneous Rank Support Learning (NHRSL) problems. RSL is primordial for all recent rank-based cryptosystems such as Durandal (Aragon et al., EUROCRYPT 2019) or LRPC with multiple syndromes (arXiv:2206.11961), moreover, NHRSD and NHRSL, together with RSL, are at the core of our new schemes. The new attacks we propose are of both types: combinatorial and algebraic. For all these attacks, we provide a precise analysis of their complexity. Overall, when all of these new improvements for the RQC scheme are put together, and their security evaluated with our different attacks, they enable one to gain 50% in parameter sizes compared to the previous RQC version. More precisely, we give very competitive parameters, around 11 KBytes, for RQC schemes with unstructured public key matrices. This is currently the only scheme with such short parameters whose security relies solely on pure random instances without any masking assumptions, contrary to McEliece-like schemes. At last, when considering the case of Non-Homogeneous errors, our scheme permits to reach even smaller parameters.

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
preprint2020arXiv

HQC-RMRS, an instantiation of the HQC encryption framework with a more efficient auxiliary error-correcting code

The HQC encryption framework is a general code-based encryption scheme for which decryption returns a noisy version of the plaintext. Any instantiation of the scheme will therefore use an error-correcting procedure relying on a fixed auxiliary code. Unlike the McEliece encryption framework whose security is directly related to how well one can hide the structure of an error-correcting code, the security reduction of the HQC encryption framework is independent of the nature of the auxiliary decoding procedure which is publicly available. What is expected from it is that the decoding algorithm is both efficient and has a decoding failure rate which can be easily modelized and analyzed. The original error-correction procedure proposed for the HQC framework was to use tensor products of BCH codes and repetition codes. In this paper we consider another code family for removing the error vector deriving from the general framework: the concatenation of Reed-Muller and Reed-Solomon codes. We denote this instantiation of the HQC framework by HQC-RMRS. These codes yield better decoding results than the BCH and repetition codes: overall we gain roughly 17\% in the size of the key and the ciphertext, while keeping a simple modelization of the decoding error rate. The paper also presents a simplified and more precise analysis of the distribution of the error vector output by the HQC protocol.

0 citations0 reviewsNo code linkedOpen access