ความสัมพันธ์ระหว่างผลหารข้อความรหัสและระดับพหุนามใน RLWE คืออะไร

ในปัญหา Ring Learning with Errors ขนาดของผลหารข้อความไซเฟอร์ $คิว$ กำหนดขนาดของดีกรีพหุนาม $n$ หรือในทางกลับกัน กล่าวอีกนัยหนึ่ง ปัญหา rlwe นั้นยากก็ต่อเมื่อมีการตั้งค่าระดับพหุนามเมื่อเทียบกับผลหาร อย่างไรก็ตาม ฉันไม่แน่ใจว่าค่าของพารามิเตอร์ทั้งสองมีความสัมพันธ์กันอย่างไร

ใครช่วยอธิบายให้ฉันหรือชี้ให้ฉันดูแหล่งข้อมูลได้บ้าง

ไม่มี "ความสัมพันธ์" ระหว่างพารามิเตอร์ทั้งสองนี้ เนื่องจากสิ่งที่เรียกว่า การสลับโมดูลัส. ประมาณได้รับตัวอย่าง LWE $\bmod q$เราสามารถเปลี่ยนเป็นอินสแตนซ์ LWE ได้ $\bmod p$ ด้วยต้นทุนที่ค่อนข้างน้อยสำหรับความหลากหลาย $p$. มีผลลัพธ์มากมายตามบรรทัดเหล่านี้ แต่ฉันจะอธิบายจาก การลดขนาดตัวพิมพ์เล็กและตัวพิมพ์ใหญ่ที่สุดสำหรับโมดูล Lattices.

อนุญาต $\psi$ เป็นการกระจายความน่าจะเป็นบน $\mathbb{T}_{R^\vee}$, และ $s\in(R^\vee_q)^d$ เป็นเวกเตอร์ เรากำหนด $A^{(M)}_{q,s,\psi}$ เป็น จัดจำหน่ายเมื่อ $(R_q)^d à \mathbb{T}_{R^\vee}$ ได้จากการเลือกเวกเตอร์ a $s\in(R_q)^d$ สุ่มอย่างเท่าเทียมกันและ $e \in \mathbb{T}_{R^\vee}$ ตาม $\psi$, และกลับมา $(a, \frac{1}{q}\langle a, s\rangle + e)$.

ม.ล.ว: สำหรับจำนวนเต็ม $q \geq 2$ และจัดจำหน่าย $\Psi$ ในครอบครัวของการกระจายมากกว่า $K_\mathbb{R}$. รุ่นการตัดสินใจของ ปัญหาการเรียนรู้โมดูลด้วยข้อผิดพลาด $M-LWE_{q, \Psi}$ มีดังนี้ ให้ $s \in (R^\vee_q)^d$ สุ่มอย่างเท่าเทียมกันและ $\psi$ ได้รับตัวอย่างจาก $\Psi$ ; เป้าหมายคือเพื่อแยกความแตกต่างระหว่างตัวอย่างอิสระจำนวนมากโดยพลการจาก $A^{(M)}_{q, s, \psi}$และกลุ่มตัวอย่างอิสระจำนวนเท่ากันจาก $U(R^d_q, \mathbb{T}_{R^\vee})$.

นี่เป็นเรื่องกว้างกว่า RLWE และลดเป็น RLWE เมื่อ $d = 1$. ครอบครัวของการกระจาย $\Psi_a$ เป็นการแจกแจงแบบเกาส์แบบวงรี ดูหัวข้อ 2.3

อย่างไรก็ตาม ผลการสลับโมดูลัสคือทฤษฎีบท 4.8 ที่นี่, $N = nd$ คือ "มิติรวม" ของอินสแตนซ์ MLWE การตั้งค่า $n = 1$ กู้คืนกรณีของ RLWE ที่คุณสนใจ

อนุญาต $p, q \in [2, 2^{N^{O(1)}} ]$ และ $\alpha, \beta â (0, 1)$ ดังนั้น $\beta \geq \alpha \max(1, \frac{q}{p})n^{1/4}N^{1/2}\omega(\log_2 N)$ และ $\alpha q \geq \omega(\sqrt{\log(N)/n})$. มีการลดเวลาพหุนามจาก $M-LWE_{q,\Psi_\alpha}$ ถึง $M-LWE_{p,\Psi_\beta}$.

ทั้งหมดนี้เป็นการบอกว่าคุณสามารถลดค่าโมดูลัสตามอำเภอใจได้ $คิว$ ไปยังโมดูลัสอื่นโดยพลการ $p$ในราคาที่สูงเกินจริงอัตราเสียงจาก $\alpha\mapsto \frac{q}{p}\alpha\sqrt{N}\omega(\log_2 N)$. นี่ไม่ใช่ โดยสิ้นเชิง ฟรี (มีเพิ่มเติม $\sqrt{N}$ แฟกเตอร์) แต่กำหนดว่าโมดูลี $q, p$ โดยทั่วไปจะเป็นพหุนามขนาดเล็กใน $N$ค่าใช้จ่ายที่คุณจ่ายค่อนข้างน้อยเมื่อเทียบกับขนาดพารามิเตอร์

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

สำหรับวิธีตั้งค่าสิ่งเหล่านี้จริง ๆ ผู้คนมักจะป้อนพารามิเตอร์ของตนลงใน ตัวประมาณ LWEซึ่งให้ค่าประมาณการรักษาความปลอดภัยบิตสำหรับชุดพารามิเตอร์เฉพาะแต่ละชุด