نظام التشفير McEliece بناءً على أكواد LDPC

خوفًا من وجود كمبيوتر كمي قادر على كسر طرق التشفير الحديثة ، يواصل المشفرون حول العالم البحث عن أنظمة تشفير تقاوم هجوم الكمبيوتر الكمومي. تم اختراع أحد أنظمة التشفير هذه في عام 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)