A Polynomial-Time Attack on the BBCRS Scheme

DOI10.1007/978-3-662-46447-2_8zbMATH Open1345.94054arXiv1501.03736OpenAlexW1562964166WikidataQ62039159 ScholiaQ62039159MaRDI QIDQ2941191FDOQ2941191

Authors: Alain Couvreur, Ayoub Otmani, Jean-Pierre Tillich, Valérie Gauthier-Umaña 

Publication date: 27 August 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: The BBCRS scheme is a variant of the McEliece public-key encryption scheme where the hiding phase is performed by taking the inverse of a matrix which is of the form $mathbfT+mathbfR$ where $mathbfT$ is a sparse matrix with average row/column weight equal to a very small quantity $m$, usually $m<2$, and $mathbfR$ is a matrix of small rank $zgeqslant1$. The rationale of this new transformation is the reintroduction of families of codes, like generalized Reed-Solomon codes, that are famously known for representing insecure choices. We present a key-recovery attack when $z=1$ and $m$ is chosen between $1$ and $1+R+O(frac1sqrtn)$ where $R$ denotes the code rate. This attack has complexity $O(n^6)$ and breaks all the parameters suggested in the literature.

Full work available at URL: https://arxiv.org/abs/1501.03736

Recommendations

• scientific article; zbMATH DE number 1925556
• A ciphertext-only attack on Polly Two
• Polynomial-time targeted attacks on coin tossing for any number of corruptions
• A polynomial-time key-recovery attack on MQQ cryptosystems
• A Practical Attack on Broadcast RC4
• A Polynomial Time Attack on RSA with Private CRT-Exponents Smaller Than N 0.073
• Timing attack against protected RSA-CRT implementation used in PolarSSL
• Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems
• Pollard's rho attack on ECDLP and Threshold Schemes
• A New Attack on RSA and CRT-RSA

zbMATH Keywords

generalized Reed-Solomon codescode-based cryptographydistinguisherkey-recoverycomponent-wise product of codes

Mathematics Subject Classification ID

Cryptography (94A60)

Cited In (10)

• Two modifications for Loidreau's code-based cryptosystem
• Encryption scheme based on expanded Reed-Solomon codes
• Cryptanalysis of Ivanov-Krouk-Zyablov cryptosystem
• On the security of a Loidreau rank metric code based encryption scheme
• A new McEliece-type cryptosystem using Gabidulin-Kronecker product codes
• Cryptanalysis of the BBCRS system on Reed-Muller binary code
• Classification of Hadamard products of one-codimensional subcodes of Reed-Muller codes
• Polynomial-time targeted attacks on coin tossing for any number of corruptions
• A Hadamard product of linear codes: algebraic properties and algorithms for calculating it
• Theoretical analysis of decoding failure rate of non-binary QC-MDPC codes

This page was built for publication: A Polynomial-Time Attack on the BBCRS Scheme

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941191)