ไม่มี "ความสัมพันธ์" ระหว่างพารามิเตอร์ทั้งสองนี้ เนื่องจากสิ่งที่เรียกว่า การสลับโมดูลัส.
ประมาณได้รับตัวอย่าง 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ซึ่งให้ค่าประมาณการรักษาความปลอดภัยบิตสำหรับชุดพารามิเตอร์เฉพาะแต่ละชุด