LDPCコードに基づく暗号システムMcEliece

現代の暗号化手法を破ることができる量子コンピューターを恐れて、世界中の暗号学者は、量子コンピューターの攻撃に耐性のある暗号化システムを探し続けています。これらの暗号システムの1つは、1978年に発明され、代数コーディングの理論に基づいています。この記事では、低密度パリティチェックコード（または単にLDPCコード）に基づくコード暗号化の概要を説明します。猫の下に興味のある人はみんなお願いします。

コンテンツ

1. 前書き
2. 線形コード
3. コード暗号化
4. 低密度（LDPC）コード
5. LDPC暗号化
6. 結論
7. 文献

---

前書き

この資料は、暗号学、情報理論、線形代数の基本的な知識を持つ人々を対象としており、この主題分野を研究するのが好きな学生によって書かれました。私が依存する主な用語は最初のセクションに記載されていますが、より深く理解するために、それはトピックに関する追加情報の独立した検索と研究を意味します。これに貢献するいくつかの文献は、記事の最後に提供されています。

線形コード

マトリックスコーディング

生成行列と呼びます $$$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)