ขีดจำกัดของการสลับโมดูลัสในการเข้ารหัส BFV คืออะไร

ในระยะสั้น

พิจารณาว่าคุณกำลังทำงานบนวงแหวน $R_Q = \mathbb{Z}_Q[X] / \langle X^N + 1 \rangle$. ตามกฎทั่วไป คุณต้องพิจารณาว่าสัญญาณรบกวนหลังจากการสลับโมดูลัสนั้นมากกว่า $N$. โดยเฉพาะอย่างยิ่งจะไม่มีเพียง 5 บิตตามตัวอย่างของคุณเพราะ $N$ โดยทั่วไปจะมีขนาดใหญ่กว่า $2^{13}$ ในโครงการ FV

ในรายละเอียดเพิ่มเติม

สมมติว่าคุณมี RLWE ciphertext $c = (a, b) \ใน R_Q^2$, กับ $b = a\cdot s + e + (q / t) \cdot m$เช่นเดียวกับในโครงการ FV

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

$$e' := e \cdot q / Q + \epsilon' + \epsilon \cdot s$$

โดยที่ทั้งสอง $\epsilon'$ และ $\epsilon$ เป็นพหุนามที่มีค่าสัมประสิทธิ์เป็นช่วง $[-1/2,\, 1/2]$.

มักจะเป็นความจริงที่ผิดพลาดใหม่ $e'$ ใกล้เคียงกับข้อผิดพลาดที่ปรับขนาด $e \cdot Q / q$ เพราะข้ออื่นมีน้อยเมื่อเทียบกับข้อนี้. อย่างไรก็ตาม เมื่อข้อผิดพลาดในการปรับขนาดมีขนาดเล็กเกินไป นั่นจะไม่เป็นความจริงอีกต่อไป เช่น $\epsilon \cdot s$ เริ่มครอบงำบรรทัดฐานของ $e'$และนี่คือ "ขีดจำกัดของการสลับโมดูลัส" ในรายละเอียดเพิ่มเติมบรรทัดฐานของ $\epsilon \cdot s$ สามารถใหญ่ได้ถึง $N \cdot || \epsilon || \cdot || s ||$. ดังนั้น แม้จะใช้คีย์ไบนารีหรือเทอร์นารีคีย์ (เช่น $|| ส || = 1$), เรามี $N \cdot || \epsilon || \cdot || ส || = N \cdot || \epsilon || \ประมาณ N/2$.