Cryptosystem McEliece basé sur les codes LDPC

Craignant un ordinateur quantique capable de casser les méthodes de cryptage modernes, les cryptographes du monde entier continuent à rechercher des systèmes cryptographiques résistants à l'attaque d'un ordinateur quantique. L'un de ces cryptosystèmes a été inventé en 1978 et est basé sur la théorie du codage algébrique. Cet article fournit une vue d'ensemble de la cryptographie de code basée sur des codes de contrôle de parité à faible densité (ou simplement des codes LDPC). Je demande à tout le monde intéressé sous le chat.

Contenu

1. introduction
2. Codes linéaires
3. Cryptographie de code
4. Codes basse densité (LDPC)
5. Cryptographie LDPC
6. Conclusion
7. Littérature

---

introduction

, , . , , , . , , .

$$$G$ $$ :

, $$$GF(2)$, $$$x_{ij}$ 0 1.

$$$G$ $$$I$ — $$$P$. $$$H$, :

, $$$G$ . , $$$H$ $$$G$ : $$$GH^{T}=0$. : $$$= mG$, $$$m$ — , $$$c$ — .

, . $$$s$ , $$$s = Hc^{T}$. -, . $$$c$ $$$'=+$, $$$e$ — ( , , 1).

$$$c'$, . (maximum likelihood decoding) $$$e$, $$$He^{T} = s$. :

: $$$c'$ $$$c$ ( ). ( ).

(, LDPC , , belief propagation bit-flipping, ). — NP- .

: NP- , .

:

• (, ) $$$G$ $$$G'$
• $$$G'$, $$$e$
• , $$$G$, $$$G'$ ,

-

- . .

:

• :
• : ( )

-.

:

1. $$$G$ — (k, n)- (n, k)- , $$$t$
2. (k, k)- $$$S$
3. (n, n)- $$$P$
4. : $$$(SGP, t)$, $$$SGP = G'$
5. : $$$(S, G, P)$

: $$$S$ $$$P$ , , , t , , , .

( 3 !), . , , .

:

1. $$ $$$n$ $$$w$ $$$t$
2. : $$$c = mG’ + e$

c:

1. $$$c’ = cP^{-1}$
2. $$$c'$ c , $$$m'$
3. $$$m = m’S^{-1}$

:

, . : , -, , -, LDPC, LRPC, , - .

, : . .

, :

• MDPC ( LDPC )

LDPC — MDPC .

(LDPC)

, — .

, LDPC , .

LDPC

:

• : 0 n. .
• . "" "" ( . "soft-decision" "hard-decision" decoding).
• : LDPC .
• (QC-LDPC) .

LDPC

LDPC -, :

1. LDPC "" .
2. .
3. QC-LDPC .

:

1. LDPC ( t , density evolution).
2. (, ).
3. , .

LDPC

LDPC: MDPC (QC-MDPC).

MDPC

MDPC (Moderate Density Parity-Check) — "" LDPC . LDPC w 10, MDPC $$$w = \sqrt{n\cdot log(n)}$, n — - (, ).

MDPC , : .

(QC-LDPC) . (n, n)-, , — :

, , : , .

, , (p, n)-QC-LDPC n = 9602 p = 4801 ( ):

1. P(n, n): ~11 Mb --> P’(n): ~9.5 Kb. , .
2. G(n, p): ~5.5 Mb --> G’(n): ~1.2 Kb.
3. S(p, p): ~2.75 Mb --> S’(p): ~0.6 Kb. S , , .

: 1760 ! , .

, .

, - (1024, 524, 101)- 50 ( $$$2^{50}$ ).

: MDPC n = 9602 w = 90 80 . , (, ), .

— . , .

, : .

, , , — . , . , .

1. A Public-Key Cryptosystem Based On Algebraic Coding Theory (R. J. McEliece)
2. An Introduction to Low-Density Parity Check Codes (Daniel J. Costello, Jr.)
3. On the Usage of LDPC Codes in the McEliece Cryptosystem (Marco Baldi)
4. LDPC codes in the McEliece cryptosystem: attacks and countermeasures (Marco Baldi)
5. QC-LDPC Code-Based Cryptography (Marco Baldi)
6. MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes (Rafael Misoczki and Jean-Pierre Tillich and Nicolas Sendrier and Paulo S. L. M. Barreto)
7. Modern Coding Theory (Tom Richardson, Rudiger Urbanke)