Cryptosystem McEliece berdasarkan kode LDPC

Karena takut komputer kuantum mampu melanggar metode enkripsi modern, para kriptografer di seluruh dunia terus mencari sistem kriptografi yang tahan terhadap serangan komputer kuantum. Salah satu kriptosistem ini ditemukan kembali pada tahun 1978 dan didasarkan pada teori pengkodean aljabar. Artikel ini memberikan gambaran umum tentang kriptografi kode berdasarkan kode pemeriksaan paritas kepadatan rendah (atau hanya kode LDPC). Saya meminta semua orang yang tertarik dengan kucing itu.

Kandungan

1. pengantar
2. Kode linier
3. Kriptografi kode
4. Kode kepadatan rendah (LDPC)
5. Kriptografi LDPC
6. Kesimpulan
7. literatur

---

pengantar

, , . , , , . , , .

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