Com medo de um computador quântico capaz de quebrar os métodos modernos de criptografia, os criptógrafos de todo o mundo continuam em busca de sistemas criptográficos que sejam resistentes ao ataque de um computador quântico. Um desses criptosistemas foi inventado em 1978 e é baseado na teoria da codificação algébrica. Este artigo fornece uma visão geral da criptografia de código com base em códigos de verificação de paridade de baixa densidade (ou simplesmente códigos LDPC). Peço a todos os interessados ​​sob o gato.
ConteĂşdo
- Introdução
- CĂłdigos Lineares
- Criptografia de cĂłdigo
- CĂłdigos de baixa densidade (LDPC)
- Criptografia LDPC
- ConclusĂŁo
- Literatura
Introdução
Este material destina-se a pessoas com conhecimentos básicos nas áreas de criptografia, teoria da informação e álgebra linear e foi escrito por uma estudante que gostava de estudar esta área disciplinar. A terminologia principal na qual confio é dada nas primeiras seções, mas para uma compreensão mais profunda, significa uma busca e estudo independente de informações adicionais sobre o assunto. Alguma literatura que contribui para isso é fornecida no final do artigo.
CĂłdigos Lineares
Codificação matricial
Vamos chamar a matriz geradora espaço linear matriz da forma:
Neste ponto, concordamos que todos os cálculos são realizados em então todo mundo pegue os valores 0 ou 1.
De forma sistemática, a matriz é a concatenação da matriz de identidade e a paridade da parte da matriz . , :
, . , : . : , — , — .
, . , . -, . , — ( , , 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)