กระดาษ "วิธีการใช้ Tternary LWE Keys": t คืออะไรและใช้อย่างไร

ดังนั้นหลังจากผ่านไปหลายสัปดาห์ ฉันก็หาคำตอบสำหรับคำถามของฉันได้สำเร็จ

มันไม่สุ่มจริงๆ หรือฉันพลาดอะไรไปหรือเปล่า?

ใช่ t มีไว้เพื่อลดความคลุมเครือของพื้นที่ค้นหา ทุกอย่างเริ่มต้นจากแนวคิดที่ว่า: $ \begin{bmatrix} 1 \ -1 \ 0 \ -1 \ 1 \ 0 \ \end{bmatrix} = \begin{bmatrix} 1 \ 0 \ 0 \ -1 \ 0 \ 0 \ \end{bmatrix} + \begin{bmatrix} 0 \ -1 \ 0 \ 0 \ 1 \ 0 \ \end{bmatrix} = \begin{bmatrix} 1 \ -1 \ 0 \ 0 \ 0 \ 0 \ \end{bmatrix} + \begin{bmatrix} 0 \ 0 \ 0 \ -1 \ 1 \ 0 \ \end{bmatrix} $

การรวมกันของเวกเตอร์ 2 แบบนี้นำไปสู่ผลลัพธ์เดียวกัน แต่การเรียกดูทั้งคู่นั้นไร้ประโยชน์เนื่องจากชุดค่าผสมนั้นเหมือนกันดังนั้นจึงเป็นไปได้ที่จะลดพื้นที่การค้นหาโดยละเว้นชุดค่าผสมที่ซ้ำซ้อน และในการทำเช่นนั้น เราตั้งค่าบางค่าเป็นค่าคงที่ในส่วนขวาของสมการ LWE (เช่น $เป็น$ และไม่ $s$) เนื่องจากคุณสมบัติทางคณิตศาสตร์บางอย่าง (homomorphism ของการฉายภาพ A. May แนะนำ)

ทำไมมันถึงขนาด $r$?

$r=floor(log_q(R))$ ที่ไหน $R$ คือขนาดของพื้นที่การแสดงของเวกเตอร์ที่เราค้นหา ในตัวอย่างข้างต้น $R\geq2$ เพราะเราพบ 2 วิธีในการแทนเวกเตอร์ ดังนั้น $log_q$ ของสิ่งนั้น $R$ คือจำนวนพิกัดในพื้นที่ $\mathbb{Z}_r^q$ ที่เราสามารถกำหนดเป็นค่าคงที่เพื่อลดพื้นที่การค้นหา อย่างไรก็ตาม จำนวนพิกัดนี้ต้องเป็นจำนวนเต็ม ดังนั้นเราจะใช้การปัดเศษพื้นของสิ่งที่เราได้รับ

เราจะลดพื้นที่การค้นหาของ $s_1$ โดยใช้สมการที่กล่าวถึงและเทียบเท่ากับ $s_2$?

วิธีการใช้ประโยชน์จากมันคือการใช้วิธีการจับคู่และตัวกรอง:

1. สร้างครึ่งที่เป็นไปได้ทั้งหมดของ $s_1$ อย่างที่อ.เมย์อธิบาย
2. รวมเข้าด้วยกันและกรอง นั่นคือปฏิเสธที่ได้รับ $s_1$ ถ้า $\pi_r(As_1) \ne t$ หรือหากไม่ใช่เวกเตอร์ที่ประกอบไปด้วย ternary ที่มีน้ำหนักแฮมมิ่งที่ดี
3. ทำเทียบเท่ากับ $s_2$ (สังเกตสมการด้วย $t$ ไม่เหมือนที่เราอยู่ส่วนขวาของต้นไม้)
4. รวมเวกเตอร์เหล่านี้เข้ากับการแฮชของ Odlyzko และตรวจสอบสมการ LWE

แน่นอนว่าต้องปรับให้เข้ากับต้นไม้ใหญ่