มิติของรหัส Goppa

สำหรับระบบเข้ารหัสของ McEliece/Niederreiter ทางเลือกของรหัสที่ดูเหมือนว่ามีประสิทธิภาพและปลอดภัยคือรหัส Goppa แบบไบนารีที่ลดไม่ได้ ซึ่งกำหนดโดยรหัสที่ลดไม่ได้ $g(x)\in GF(2^m)[x]$ ของปริญญา $t$ และเวกเตอร์สนับสนุน $L=(\alpha_0,\ldots,\alpha_{n-1})$ ด้วยความแตกต่าง $\alpha_i\ใน GF(2^m)$.

รหัสตัวเองคือ $GF(2)$เวกเตอร์ที่มีค่าในเคอร์เนลของเมทริกซ์การตรวจสอบพาริตี $$ H=\left( \begin{อาร์เรย์}{cccc} g(\alpha_0)^{-1}&g(\alpha_1)^{-1}&\ldots&g(\alpha_{n-1})^{-1}\ g(\alpha_0)^{-1}\alpha_0&g(\alpha_1)^{-1}\alpha_1&\ldots&g(\alpha_{n-1})^{-1}\alpha_{n-1}\ \vdots&\vdots&\ldots&\vdots\ g(\alpha_0)^{-1}\alpha_0^{t-1}&g(\alpha_1)^{-1}\alpha_1^{t-1}&\ldots&g(\alpha_{n-1})^{ -1}\alpha_{n-1}^{t-1}\ \end{อาร์เรย์}\right) $$ โปรดทราบว่า $H$ เป็นแบบเต็มยศ เพื่อสร้างเมทริกซ์ตรวจสอบพาริตี $H'$ เกิน $GF(2)$หนึ่งสามารถแทนที่รายการของ $H$ ด้วยเวกเตอร์คอลัมน์ใน $GF(2)$ (ใช้พื้นฐานบางส่วนในการต่อ $GF(2^m)/GF(2)$).

แหล่งข้อมูลเกือบทั้งหมดที่ฉันปรึกษาแสดงรายการรหัสผลลัพธ์เป็น $[n,k]=[n, n-mt]$แต่การก่อสร้างทั่วไป (พูดสำหรับรหัสอื่น) ให้ $k=n-mt$ เป็น ก ขอบเขตล่าง เพื่อมิติ $k$ ของรหัสพื้นที่ย่อยที่เป็นผลลัพธ์

คำถามของฉันคือ:

1. อันดับที่เกิดขึ้นบ่อยแค่ไหน $k=n-mt$? ในการตั้งค่า AG ฉันเดาว่านี่คือมิติข้อมูลของ Riemann-Roch ดังนั้น geometer เชิงพีชคณิตอาจตอบได้
2. ไม่สำคัญว่าเรามีแถวที่ซ้ำซ้อนในการตรวจสอบพาริตีหรือไม่ $H'$? สิ่งนี้ส่งผลกระทบต่อการใช้งานระบบเข้ารหัสลับหรือไม่?

ฉันเดาว่าสิ่งนี้กล่าวถึงในตัวสร้างคีย์จาก https://eprint.iacr.org/2017/595.pdf (ส่วน 5.2) หากเพียงเพื่อส่งคืนความล้มเหลวและเริ่มกระบวนการสร้างคีย์ใหม่เมื่อ rref ไม่สำเร็จ พวกเขาให้ 29% เป็นความน่าจะเป็นของความสำเร็จโดยพิจารณาจากความหนาแน่นของ $GL_{mt}(GF(2))$ ใน $Mat_{mt\times mt}(GF(2))$เช่น ความหนาแน่นเชิงซีมโทติคคือ $$ \prod_{i=1}^{\infty}\left(1-\frac{1}{2^i}\right)=0.288\ldots $$

ในความคิดที่สองเกี่ยวกับ 1) ฉันเดาว่ามันเป็นคำถามมากกว่าเมื่อเคอร์เนลของแผนที่เชิงเส้นถูกกำหนดผ่านฟิลด์ย่อย (เช่นเคอร์เนลของ $x-\sqrt{2}y$ มีมิติมากกว่าหนึ่ง $\mathbb{Q}(\sqrt{2})$ แต่มิติเป็นศูนย์เมื่อจำกัดไว้ที่ $\mathbb{Q}$).

1. จากมุมมองของฮิวริสติก (สำหรับพารามิเตอร์ของความสนใจในการเข้ารหัส) มันค่อนข้างไม่น่าเป็นไปได้ ไบนารี่ $n\times(n-r)$ เมทริกซ์ที่มีรายการสุ่มมีค่าน้อยกว่า $2^{-n+r}$ มีโอกาสขาดอันดับ อาจมีคำตอบทางเรขาคณิตที่แม่นยำกว่านี้

2. รหัสน่าจะถูกคำนวณโดยการใส่โดยใช้การแปลงแถวเพื่อใส่ $H'$ ในรูปแบบที่เป็นระบบ $(I|A)$ แล้วรับรหัสไบนารี Goppa เป็น $(I|A^t)$. ถ้า $H'$ ขาดอันดับ ดังนั้นการดำเนินการจะต้องมีวิธีการตรวจสอบว่ารูปแบบที่เป็นระบบเต็มรูปแบบยังไม่บรรลุผล และขยะแถวที่เหลือของ $H'$. ถ้ายศ $H'$ เป็น $r$ จากนั้นเมทริกซ์ตัวสร้างรหัสไบนารี Goppa ของเราจะเป็น $n\times(n-r)$ ซึ่งอาจมีขนาดใหญ่กว่าหน่วยความจำที่จัดสรรไว้ (และเพิ่มปัญหาแบนด์วิธที่เจ็บปวดอยู่แล้ว) ตอนนี้บางแถวของเมทริกซ์ตัวสร้างจะต้องถูกทิ้ง เราต้องการหลีกเลี่ยงคอลัมน์ที่ซ้ำซ้อนเพื่อให้ชุดข้อมูลถอดรหัสยาก ดังนั้นเราอาจต้องการยกเลิกการจัดระบบเมทริกซ์ตัวสร้างแบบสุ่มก่อนที่จะลบแถว เรียงแถวคอลัมน์และจัดระบบใหม่ มีปัญหาที่น่าสนใจที่แถวที่ถูกลบที่อ่านไม่ออกสามารถแสดงต่อตัวถอดรหัสของเราและแก้ไขได้สำเร็จกับบางสิ่งที่ไม่อยู่ในขอบเขตของเมทริกซ์ตัวสร้างของเรา แต่ตัวถอดรหัสของเราน่าจะใช้เมทริกซ์ที่ปรับระบบใหม่ของเราเพื่อแมปกับช่วงของ เมทริกซ์เครื่องกำเนิดไฟฟ้า การใช้งานไม่น่าจะพร้อมสำหรับสิ่งนี้และอาจแสดงพฤติกรรมที่คาดเดาไม่ได้ โดยรวมแล้วน่าจะดีกว่าที่จะเลือกใหม่ $ก(X)$ และเริ่มต้นใหม่