Informations pratiques

Description de la ressource

Résumé

In the next three sessions, I will explain how to reduce the key size of code-based cryptosystem. Circulant matrices are the central point in many attempts to reduce the key size of code-based cryptosystems since they provide efficient representation. A circulant matrix is a square matrix, its rows are obtained by cyclically shifting the first row. An alternative representation of an n-tuple of elements is using polynomial. Thus, this matrix can be described by a polynomial. And the i-th row of a circulant matrix can be expressed by this formula. Circulant matrices are closed under product and sum. Thus, this operation preserves cyclicity. So, we have the following proposition. Circulant matrices of size r, with elements in Fq are equivalent to polynomials in this quotient ring. Block-Circulant matrices are formed by concatenating circulant blocks of identical size. Quasi-cyclic codes have been defined as a linear code that admits a block-circulant matrix.  We will consider quasi-cyclic codes that can be written in block-circulant systematic form. Quasi-cyclic subcodes of BCH codes were proposed by Gaborit in 2005. Take notice that these codes can be efficiently decoded. Thus, there are suitable families for code-based cryptosystem. This table presents the parameters suggested by the author. Note that the key size for the same level of security drops considerably compared to the original scheme with Goppa code.  The minimum size for Goppa code is around 700 000  bits for 80 bits of security while with this security level with quasi-cyclic subcode of BCH code, we just need 12 000 bits.

"Domaine(s)" et indice(s) Dewey

• Analyse numérique (518)
• Théorie de l'information (003.54)
• données dans les systèmes informatiques (005.7)
• cryptographie (652.8)
• Mathématiques (510)

Domaine(s)

• Cette ressource fait partie de
  • 2: McEliece Cryptosystem