คำอธิบาย RLWE

ใน RLWE เรามักจะเลือกวงแหวนพหุนามดังต่อไปนี้ โดยที่ q เป็นจำนวนเฉพาะ และ n เป็นกำลังของ 2 เช่น $2^k$ $$\mathbb Z_q[X]/(X^n + 1)$$

เรารู้ว่า ${X^{2^k}} + 1$ เป็นพหุนามลดค่าไม่ได้ภายใต้ $Z$, เพราะว่า Cyclotomic Polynomial, แต่ใน นี้ คำถาม, กำลังพิจารณา $$\mathbb Z_{17}[X]/(X^4 + 1)$$ $(X^4 + 1)$ สามารถแยกตัวประกอบเป็น $$\mathbb (X^2 + 4)(X^2 - 4) = X^4 - 16 = X^4 + 1$$ เพราะว่า $Z_{17}$นอกจากนี้ยังสามารถแยกตัวประกอบได้เป็น $(x + 15)(x + 9)(x + 8)(x + 2)$ ภายใต้ $Z_{17}$

แล้วทำไมเราต้องเลือกพหุนามแบบลดค่าไม่ได้ ${X^{2^k}} + 1$ ที่แรกเมื่อลดขนาดลงได้ $Z_q$นอกจากนี้ข้อดีของการเลือกคืออะไร ${X^{2^k}} + 1$ เป็นของเรา ในอุดมคติและการเลือกไพรม์ q ที่ใหญ่พอ (มากกว่า 17 มาก) จะป้องกันไม่ให้สถานการณ์ข้างต้นเกิดขึ้นหรือไม่

ขอบคุณ!

พหุนามไซโคลโทมิกใช้ในการพิสูจน์ว่าปัญหาแลตทิซในกรณีที่เลวร้ายที่สุดลดลงเป็น RLWE หากคุณพยายามยกตัวอย่าง RLWE ด้วยพหุนามอื่นๆ แสดงว่าคุณไม่มีการรับประกันอย่างเป็นทางการเกี่ยวกับความแข็งของปัญหา คุณสามารถตรวจสอบ สไลด์ชุดนี้ของพีเคิร์ต สำหรับบทนำ จากนั้นอ่านข้อมูลอ้างอิงหากต้องการรายละเอียดเพิ่มเติม

และการเลือก $คิว$ ดังนั้นการที่พหุนามไซโคลโทมิกไม่แยกออกอย่างสมบูรณ์นั้นไร้ประโยชน์ เนื่องจากความแข็งของปัญหา RLWE ขึ้นอยู่กับความยาวของบิตเท่านั้น $คิว$ไม่ใช่ในรูปแบบ

อย่างไรก็ตาม เมื่อเราปรับใช้ BGV, FV, CKKS หรือแผนการอื่นๆ ตาม RLWE เรามักจะจำกัดทางเลือกของเรา $คิว$ เพื่อบังคับให้ $X^n + 1$ แตกออกให้หมดจึงจะใช้ได้ การเป็นตัวแทน RNS (หรือที่เรียกว่า double-CRT).