Cryptosystem McEliece baseado em cĂłdigos LDPC

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



  1. Introdução
  2. CĂłdigos Lineares
  3. Criptografia de cĂłdigo
  4. CĂłdigos de baixa densidade (LDPC)
  5. Criptografia LDPC
  6. ConclusĂŁo
  7. 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 G espaço linear A PARTIR DE matriz da forma:



imagem



Neste ponto, concordamos que todos os cálculos são realizados em GF(2)então todo mundo xEuj pegue os valores 0 ou 1.



De forma sistemática, a matriz G é a concatenação da matriz de identidade Eu e a paridade da parte da matriz P. H, :







, G . , H G : GHT=0. : a partir de=mG, m — , c — .





, . s , s=HcT. -, . c a partir de′=a partir de+e, e — ( , , 1).



c′, . (maximum likelihood decoding) e, HeT=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. e 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=n⋅euog(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 ( 250 ).



: 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)



All Articles