基于LDPC码的密码系统McEliece

由于担心量子计算机能够突破现代加密方法，世界各地的密码学家继续寻找能够抵抗量子计算机攻击的密码系统。这些密码系统之一是在1978年发明的，它基于代数编码理论。本文提供了基于低密度奇偶校验码（或简称为LDPC码）的代码加密概述。我问所有感兴趣的人。

内容

1. 介绍
2. 线性码
3. 代码加密
4. 低密度（LDPC）码
5. LDPC密码学
6. 结论
7. 文学

---

介绍

该材料面向密码学，信息论和线性代数领域的基础知识的人，由只喜欢学习此学科领域的学生编写。在第一部分中给出了我所依赖的主要术语，但是为了更深入地理解，它意味着独立搜索和研究有关该主题的其他信息。本文末尾提供了一些有助于此的文献。

线性码

矩阵编码

我们称生成矩阵 $$线性空间G$G$$$矩阵：

至此，我们同意所有计算均在 $$，所以全部$GF(2)$$$取值0或1。$x_{ij}$

以系统的形式，矩阵 $$$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)