ความหมายด้านความปลอดภัยของเมทริกซ์ระบบที่ไม่เต็มอันดับใน McEliece cryptosystem คืออะไร

เดอะ McEliece คลาสสิก cryptosystem มีขั้นตอนการสร้างคีย์ดังต่อไปนี้:

1. เลือกเขตข้อมูล $\mathbb{F}_{2^m}$, พหุนามลดไม่ได้ $ก(x)$ ของปริญญา $t$, และ $n$ องค์ประกอบของฟิลด์ $\alpha_1, \cdots, \alpha_n$.
2. สร้าง $t \ครั้ง n$ เมทริกซ์ $\tilde{H} = (h_{ij}), h_{ij} = \frac{\alpha_j^{i - 1}}{g(\alpha_j)}$
3. แทนที่แต่ละส่วนประกอบใน $\tilde{H}$ ด้วยเวกเตอร์ไบนารีของความยาว $m$เพื่อรับเมทริกซ์ $\หมวก{H}$ ขนาด $mt \ครั้ง n$.
4. ลด $\หมวก{H}$ ถึงแบบฟอร์มระดับแถว $H$ (เรียกว่า "รูปแบบที่เป็นระบบ")

ข้อเสนอของ NIST กล่าวว่าหาก $H$ ไม่มีตำแหน่งเต็ม (หมายถึงมีแถวว่างในรูปแบบระดับแถว) ดังนั้นควรละทิ้งรหัส กระดาษแผ่นนี้ (หน้า 8) การกล่าวอ้างโดยไม่มีข้อพิสูจน์ว่าสถานการณ์ที่ไม่เต็มยศนั้นหายากมาก โดยมีความเป็นไปได้น้อยกว่า $2^{-256}$.

ความหมายด้านความปลอดภัยจะเป็นอย่างไรหากผู้ใช้ใช้รหัสสาธารณะที่ไม่ใช่แบบเต็มอันดับ เนื่องจากหายากมาก การค้นหาคีย์ส่วนตัวจะง่ายกว่าไหมถ้ามีใครรู้ว่ามีคีย์สาธารณะ $r$ แถวว่าง?