Difference between revisions of "Code-based cryptography"
en>Admin |
m (1 revision imported) |
Latest revision as of 23:36, 12 May 2021
Code-based Problems
1. Syndrome Decoding
SDP – Syndrome Decoding [1]
Let be positive integers. A distribution is sampled by choosing and where , and ouputing .
PROBLEM. Search-SDP
Given a vector , , and a positive interger .
Goal. Find vector such that and .
PROBLEM. Decisional-SDP
Goal. Distinguish with a non-negligible advantage between samples from the SD distribution and samples from the uniform distribution over .
RSD – Rank Syndrome Decoding
Let be positive integers. A distribution is sampled by choosing and where , and ouputing .
PROBLEM. Search-RSD
Given a vector , , and a positive interger .
Goal. Find vector such that and .
PROBLEM. Decisional-RSD
Goal. Distinguish with a non-negligible advantage between samples from distribution and samples from the uniform distribution over .
An Algebraic Attack on Rank Metric Code-Based Cryptosystems
Magali Bardet and Pierre Briaud and Maxime Bros and Philippe Gaborit and Vincent Neiger and Olivier Ruatta and Jean-Pierre Tillich.
arXiv, 2019.
New Technique for Decoding Codes in the Rank Metric and Its Cryptography Applications
A. V. Ourivski and T. Johansson.
Problems of Information Transmission, 2002.
On the complexity of the Rank Syndrome Decoding problem
Philippe Gaborit and Olivier Ruatta and Julien Schrek.
arXiv, 2013.
Ideal RSD – Ideal Rank Syndrome Decoding[2]
Let be an irreducilbe polynomial of degree and be positive integers. Let be the set of parity-check matrices under systematic form of ideal codes of type . The IRSD distribution is sampled by choosing uniformly at random a matrix H from , a vector from such that and, and ouputing .
PROBLEM. Search Ideal RSD
Given be an irreducilbe polynomial of degree and be positive integers. Given a random parity check matrix under systematic form of ideal codes and .
Goal. Find from such that and, and ouputing .
PROBLEM. Decisional Ideal RSD
Given be an irreducilbe polynomial of degree and be positive integers. Let be the set of parity-check matrices under systematic form of ideal codes of type .
Goal. Distinguish with a non-negligible advantage between samples from distribution and samples from the uniform distribution over .
QC-SDP – Quasi-Cyclic Syndrome Decoding
DEFINITION. Quasi-cyclic code (QC) [3]
A linear code of length is a QC code of order and index if is generated by parity-check matrix where is an circulant matrix.
PROBLEM. Search QC-SDP
Given a set of matrices , a positive integer and a vector . Define as the circulant matrix generated by .
Goal. Find vector with and .
2. Ideal LRPC – Ideal Low Rank Parity Check
The definition of the Low Rank Parity Check[4] (LRPC) codes was proposed by Gaborit, Murat, Ruatta, and Zémor in 2013.
DEFINITION. Low Rank Parity Check codes (LRPC)
A LRPC code of rank , length and dimension over is a code where it has a parity-check matrix . The coefficients of generate a sub-vector space of of small dimension .
DEFINITION. Ideal Low Rank Parity Check codes (Ideal LRPC)[5]
Let be a sub-vector space of a small dimension of , two vectors of of support and a polynomial of degree . Let The code with parity-check matrix is an ideal LRPC code of type .
PROBLEM. Decisional Ideal LRPC[5]
Given a polynomial of degree and a vector
Goal. Distinguish an ideal code with the parity-check matrix generated by is a random linear code or if it is an ideal LRPC code of weight .
Submissions in NIST
|
|
References
- ↑
On the inherent intractability of certain coding problems
Berlekamp, E. and McEliece, R. and van Tilborg, H..
in IEEE Transactions on Information Theory, vol. 24, no. 3, pp. 384-386, May 1978.. - ↑
Low rank parity check codes and their application to cryptography
Carlos Aguilar Melchor, Nicolas Aragon, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Adrien Hauteville, • Alain Couvreur.
NIST submission. - ↑
Reducing Key Length of the McEliece Cryptosystem
Berger, Thierry P. and Cayrel, Pierre-Louis and Gaborit, Philippe and Otmani, Ayoub..
AFRICACRYPT '09., 2009. - ↑
Low rank parity check codes and their application to cryptography
Philippe Gaborit, Gaétan Murat, Olivier Ruatta, Gilles Zemor..
Proceedings of the Workshop on Coding and Cryptography WCC., 2013. - ↑ 5.0 5.1
Low rank parity check codes and their application to cryptography
Carlos Aguilar Melchor, Nicolas Aragon, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Adrien Hauteville, Olivier Ruatta, Jean-Pierre Tillich, Gilles Zémor.
NIST submission.
Cite error: <ref>
tag with name "MTSB13" defined in <references>
is not used in prior text.