หลักฐานของฉันเกี่ยวกับเอกลักษณ์ของความลับของ Ring-LWE ถูกต้องหรือไม่

สมมติว่า $n$ เป็นกำลังสอง $q=3\pmod 8$, ไพรม์ และ $R=\mathbb{Z}[X]/(X^n+1)$. แสดงว่า $\Vert\cdot\Vert$ เป็นบรรทัดฐานอินฟินิตี้ใน $R_q=R/qR$ เกี่ยวกับค่าสัมประสิทธิ์ขององค์ประกอบใน $R_q$. ค่าสัมประสิทธิ์จะถือว่าอยู่ใน $[-\frac{q-1}{2},\frac{q-1}{2}]$. ฉันจะอ้างถึงข้อเท็จจริงบางอย่างที่จะใช้ในการพิสูจน์ของฉัน:

1. $X^n+1$ แยกออกเป็นสองปัจจัยแบบโมดูโลที่ลดไม่ได้ $คิว$โดยที่แต่ละปัจจัยมีระดับ $n/2$ ดูเล็มมา 3 จาก ที่นี่
2. อันเป็นผลมาจากข้อเท็จจริงข้างต้นได้รับการแก้ไข $s\ใน R_q$, $s\neq 0$, จำนวนที่แตกต่างกัน $a\cdot s\ใน R_q$, โดยรวม $a\ใน R_q$ เป็นอย่างน้อย $q^{n/2}$ตามที่กล่าวอ้างแต่ปราศจากการพิสูจน์อย่างเข้มงวดจาก หน้า 7.

ตอนนี้ข้อเรียกร้องของฉันคือการสุ่มอย่างสม่ำเสมอ $a\ใน R_q$ตัวอย่าง RLWE $b=เป็น+e$ (ที่ไหน $s,e$ ได้รับเลือกจากการแจกแจงแบบเกาส์เซียนแบบไม่ต่อเนื่อง $\mathbb{Z}^n$ ดังนั้นด้วยความน่าจะเป็นอย่างท่วมท้น $\Vert s\Vert, \Vert e\Vert\leq \beta$, สำหรับบางคน $\เบต้า$) มีความลับที่ไม่เหมือนใคร $s$. ดังนั้นการพิสูจน์จึงขัดแย้งกัน:

1. สมมติว่าได้รับการสุ่มอย่างสม่ำเสมอ $a\ใน R_q$สมมติว่า $b=as+e=as^\prime+e^\prime$, ที่ไหน $s\neq s^\ไพรม์$ และ $s,s^\prime,e,e^\prime$ ถูกเลือกจากการแจกแจงแบบเกาส์เซียนแบบแยกส่วนข้างต้นเพื่อให้บรรทัดฐานทั้งหมดเป็น $\leq \เบต้า$ ด้วยความเป็นไปได้อย่างล้นหลาม
2. ดังนั้น เราสามารถเขียนสมการข้างต้นใหม่ได้เป็น $a(s-s^\prime)=(e^\prime-e)$ และเราอ้างว่าสิ่งนี้เกิดขึ้นด้วยความน่าจะเป็นเพียงเล็กน้อยเท่านั้น $a,s,s^\prime,e,e^\prime$.
3. เราดำเนินการในหลายขั้นตอน: ขั้นแรกให้แก้ไข $e,e^\prime,s,s^\prime$ และถามความน่าจะเป็นที่สมการข้างต้นมีทั้งหมด $a\ใน R_q$นั่นคือ ความน่าจะเป็นที่ $a(s-s^\prime)=(e^\prime-e)$ สำหรับการสุ่มแบบสม่ำเสมอ $a\ใน R_q$? คำตอบของฉันสำหรับคำถามนี้คือตั้งแต่นั้นมา $a(s-s^\prime)$ ใช้เวลาอย่างน้อย $q^{n/2}$ ค่าที่แตกต่างกันทั้งหมด $a\ใน R_q$แล้วสมการข้างต้นถือด้วยความน่าจะเป็น $\leq \dfrac{1}{q^{n/2}}$.
4. ในที่สุดเราก็ยึดสหภาพทั้งหมด $s,s^\prime,e,e^\prime$ นำมาจากการแจกแจงแบบเกาส์เซียนแบบแยกส่วน เพื่อให้ทั้งหมดมีบรรทัดฐาน $\leq \เบต้า$ ด้วยความน่าจะเป็นอย่างท่วมท้น แล้วความน่าจะเป็นโดยรวมที่ $a(s-s^\prime)=(e^\prime-e)$ เป็น $\leq \dfrac{(2\beta+1)^{4n}}{q^{n/2}}$เนื่องจากจำนวนองค์ประกอบใน $R_q$ ที่มีอินฟินิตี้นอร์มอลน้อยกว่า $\เบต้า$ เป็น $(2\beta+1)^n$ และโดยอสมการสามเหลี่ยม

ฉันแสดงหลักฐานนี้ให้อาจารย์ดูแต่มันไม่สมเหตุสมผลสำหรับเขาและบอกว่าฉันทำพลาดโดยเฉพาะอย่างยิ่งในขั้นตอนที่ 3 ของการพิสูจน์ของฉัน

ตอนนี้ ฉันไม่เข้าใจว่าเหตุใดหลักฐานของฉันจึงไม่ถูกต้อง และเขาไม่ได้ระบุว่าเหตุใดหลักฐานของฉันจึงไม่ถูกต้อง ฉันพยายามอธิบายหลักฐานของฉันให้เขาฟังแต่ถูกปิดเพราะสำหรับเขาแล้ว ฉันทำพลาดมหันต์

ดังนั้นใครก็ตามที่สามารถช่วยและให้ความกระจ่างในเรื่องนี้จะได้รับการชื่นชมอย่างมาก