จะแมปข้อความกับเวกเตอร์ของน้ำหนัก t ใน Niederreiter cryptosystem ได้อย่างไร

ใน Niederreiter cryptosystem เรากำหนดให้ข้อความเป็นเวกเตอร์ของน้ำหนัก $t$ ใน $F_q^n$ ในการเข้ารหัส สมมติ $t$ คือความสามารถในการแก้ไขข้อผิดพลาดของรหัส แต่แผนที่คืออะไร? วิธีหนึ่งที่เป็นไปได้คือการจับคู่ข้อความความยาว $k$ เป็นโค้ดเวิร์ดที่มีน้ำหนักคงที่ $t$ รหัสเชิงเส้น เช่น $[n,k]_q$ รหัส. ด้วยวิธีนี้พื้นที่ข้อความคือ $q^k$. มีวิธีอื่นที่ดีกว่านี้ไหม เช่น พื้นที่ข้อความใหญ่ขึ้น

คำถามสนุก! เราสามารถตระหนักถึงขนาดพื้นที่ข้อความสูงสุดได้อย่างมีประสิทธิภาพ $(q-1)^t({n\atop t})$.

ให้เราเริ่มต้นด้วยกรณี $q=2$. เราต้องการสร้างสตริงความยาวบิต $n$ และแฮมมิ่งน้ำหนักเป๊ะ $t$. มี $C:=({n\atop t})$ สตริงดังกล่าวและเราต้องการแมปข้อความจำนวนเต็มจากช่วงเวลา $[0,C-1]$ ชุดนี้สองฝ่าย ชุดของสตริงบิตสอดคล้องกับ การรวมกัน (โดยเฉพาะ $t$- ผลรวมของจำนวนเต็ม 0 ถึง $n-1$). เราสามารถเขียนสตริงของเราใหม่เป็นลำดับที่ลดลงอย่างเข้มงวดของ $t$ ค่า $n-1\ge c_t>c_{t-1}>\ldots>c_1\ge 0$ โดยเขียนดัชนีตำแหน่งของเลข 1

ตอนนี้ ทฤษฎีบททางคณิตศาสตร์อันสวยหรูที่ Knuth กล่าวถึง Ernesto Pascal นักคณิตศาสตร์ในศตวรรษที่ 19 กล่าวว่าตัวเลขทุกตัว $N$ สามารถเป็นตัวแทนใน ระบบจำนวนเชิงผสม $$N=\left({c_t\atop t}\right)+\cdots+\left({c_1\atop 1}\right)$$ และขั้นตอนการเรียงลำดับนี้ผ่านการรวมกันคือลำดับคำศัพท์ (สำหรับจุดประสงค์ของเรา อันดับแรก $({n\atop t})$ รายการน้ำหนักรายการ $t$ สายยาว $n$). ดังนั้นถ้าเรามีจำนวนเต็ม $N\ใน [0,C-1]$ เราสามารถใช้อัลกอริทึมโลภเพื่อกู้คืน $N$น้ำหนัก $t$ สตริงไบนารีที่กำหนดโดยระบบจำนวนเชิงผสม นี่คือรหัสเทียมบางส่วน:

เริ่มต้น i:=n-1, j:=t, ส่วนที่เหลือ=N
ในขณะที่ฉัน>=0
   ถ้าทวินาม(i,j) > ส่วนที่เหลือ
      ตั้งค่าบิต i ของสตริงเป็น 0
   อื่น
      ตั้งค่าบิต i ของสตริงเป็น 1
         เจ--
         ส่วนที่เหลือ -= ทวินาม (i,j)
   ผม--

แผนที่ย้อนกลับตรงไปตรงมา

ตัวอย่างเช่นกับ $n=10$, $t=3$ มีชุดค่าผสมที่เป็นไปได้ 120 ชุด ให้เราหาชุดที่ 17 (นับ 0 ขึ้นไป) ก่อนอื่นเราจะหาจำนวนจัตุรมุขที่เล็กที่สุดไม่เกิน 17; นี่คือ $({5\atop 3})=10$; เราทำเครื่องหมายจุดที่ 5 และเหลืออีก 7 ตอนนี้เราพบจำนวนสามเหลี่ยมที่เล็กที่สุดไม่เกิน 7; นี่คือ $({4\atop 2})=6$; เราทำเครื่องหมายจุดที่ 4 และเหลืออีก 1 ตอนนี้เราพบว่าจำนวนที่น้อยที่สุดไม่เกิน 1; นี้ $({1\atop 1})=1$; เราทำเครื่องหมายจุดที่ 1 และไม่เหลืออะไรเลย สตริงของเราคือ 0000110010. ถ้าเราได้รับสตริงที่เราคำนวณ $({5\atop 3})+({4\atop 2})+({1\atop 1})=10+6+1=17$.

สำหรับตัวอักษรทั่วไป เราสามารถใช้กระบวนการข้างต้นเพื่อสร้างตำแหน่งข้อผิดพลาด จากนั้นเลือกจาก $q-1$ ค่าความผิดพลาดที่เป็นไปได้สำหรับแต่ละตำแหน่ง ให้อย่างเป็นรูปธรรม $M=C(q-1)^t$ เป็นขนาดของพื้นที่ข้อความของเรา ได้รับข้อความ $m\in[0,M-1]$ เราปล่อยให้ $N=[m/(q-1)^t]$ ดังนั้น $N\in[0,C-1]$ และสร้างรายการสถานที่ตามด้านบน เราก็ปล่อยให้ $B=m\mod{(q-1)^t}$ และเขียน $B$ เป็น ก $t$- เลขฐาน $(q-1)$ (ให้เลขศูนย์นำหน้า) และกำหนดค่าหลัก +1 ให้กับแต่ละตำแหน่ง แผนที่ย้อนกลับนั้นตรงไปตรงมาอีกครั้ง

ตัวอย่างเช่น สมมติว่าเรามีตัวอักษรทศนิยมและพิจารณาสตริงที่มีความยาว 10 โดยมีข้อผิดพลาด 3 รายการ มี 120*729=87480 ข้อความที่เป็นไปได้; ให้เราหา 12707 เราพบว่า $N=[12707/729]=17$ และสร้างสตริงบิตเดียวกันกับด้านบน เราพบว่า $B=12707\mod{729}=314$ ซึ่งก็คือ 378 ในฐาน 9 ข้อความของเราแปลงเป็นสตริงข้อผิดพลาด 0000480090. อีกครั้งถ้าเราได้รับสตริงนี้ เราจะดึงตัวเลขที่ไม่ใช่ศูนย์ออกมาตามลำดับและลบออกจากแต่ละหลักเพื่อให้เลขฐาน 9 เป็น 378 เพื่อให้ $B=314$ เราก็รู้เช่นเดียวกัน $N=17$ จากตำแหน่งข้อผิดพลาดและสามารถคำนวณได้ $m=729N+B=12707$.

บทที่ 7.2.1.3 "การสร้างชุดค่าผสมทั้งหมด" ของ "ศิลปะแห่งการเขียนโปรแกรมคอมพิวเตอร์" ขั้นสุดท้ายของ Donald Knuth เป็นบัญชีที่ยอดเยี่ยม ครอบคลุม (แม้ว่าจะเสียสมาธิ) ของอัลกอริทึมอื่นๆ สำหรับการสร้างชุดค่าผสม