Por temor a una computadora cuántica capaz de romper los métodos de cifrado modernos, los criptógrafos de todo el mundo continúan buscando sistemas criptográficos que sean resistentes al ataque de una computadora cuántica. Uno de estos criptosistemas se inventó en 1978 y se basa en la teoría de la codificación algebraica. Este artículo proporciona una descripción general de la criptografía de código basada en códigos de verificación de paridad de baja densidad (o simplemente códigos LDPC). Le pregunto a todos los interesados debajo del gato.
Contenido
- Introducción
- Códigos lineales
- Criptografía de código
- Códigos de baja densidad (LDPC)
- Criptografía LDPC
- Conclusión
- Literatura
Introducción
, , . , , , . , , .
:
, , 0 1.
— . , :
, . , : . : , — , — .
, . , . -, . , — ( , , 1).
, . (maximum likelihood decoding) , . :
: ( ). ( ).
(, LDPC , , belief propagation bit-flipping, ). — NP- .
: NP- , .
:
- (, )
- ,
- , , ,
-
- . .
:
- :
- : ( )
-.
:
- — (k, n)- (n, k)- ,
- (k, k)-
- (n, n)-
- : ,
- :
: , , , t , , , .
( 3 !), . , , .
:
- :
c:
- c ,
:
, . : , -, , -, LDPC, LRPC, , - .
, : . .
, :
- MDPC ( LDPC )
LDPC — MDPC .
(LDPC)
, — .
LDPC
:
- : 0 n. .
- . "" "" ( . "soft-decision" "hard-decision" decoding).
- : LDPC .
- (QC-LDPC) .
LDPC
LDPC -, :
- LDPC "" .
- .
- QC-LDPC .
:
- LDPC ( t , density evolution).
- (, ).
- , .
LDPC
LDPC: MDPC (QC-MDPC).
MDPC
MDPC (Moderate Density Parity-Check) — "" LDPC . LDPC w 10, MDPC , n — - (, ).
MDPC , : .
(QC-LDPC) . (n, n)-, , — :
, , : , .
, , (p, n)-QC-LDPC n = 9602 p = 4801 ( ):
- P(n, n): ~11 Mb --> P’(n): ~9.5 Kb. , .
- G(n, p): ~5.5 Mb --> G’(n): ~1.2 Kb.
- S(p, p): ~2.75 Mb --> S’(p): ~0.6 Kb. S , , .
: 1760 ! , .
, .
, - (1024, 524, 101)- 50 ( ).
: MDPC n = 9602 w = 90 80 . , (, ), .
— . , .
, : .
, , , — . , . , .
- A Public-Key Cryptosystem Based On Algebraic Coding Theory (R. J. McEliece)
- An Introduction to Low-Density Parity Check Codes (Daniel J. Costello, Jr.)
- On the Usage of LDPC Codes in the McEliece Cryptosystem (Marco Baldi)
- LDPC codes in the McEliece cryptosystem: attacks and countermeasures (Marco Baldi)
- QC-LDPC Code-Based Cryptography (Marco Baldi)
- 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)
- Modern Coding Theory (Tom Richardson, Rudiger Urbanke)