คำถามง่ายๆ เกี่ยวกับโครงการ BGV

ในขณะที่ฉันกำลังพยายามใช้โครงร่าง BGV ด้วยตัวเอง ฉันพบว่าฉันสับสนจริงๆ เกี่ยวกับการเข้ารหัสและถอดรหัสของโครงร่าง นี่คือความเข้าใจของฉัน:

อนุญาต $p$ เป็นโมดูลัสข้อความธรรมดาและ $คิว$ เป็นโมดูลัสไซเฟอร์เท็กซ์ (พวกมันคือโคไพรม์) อนุญาต $\mathbb{Z}_{m} = (-m/2, m/2] \cap \mathbb{Z}$ เป็นโมดูโลชุดตัวแทนคงที่ $m$ และ $[\cdot]_{m}: \mathbb{Z} \to \mathbb{Z}_{m}$ เป็นโมดูโล $m$ แผนที่. อนุญาต $R = \mathbb{Z}[x] / (x^{n} + 1)$, $R_{m} = \mathbb{Z}_{m}[x]/(x^{n}+1)$ เหมือนอย่างเคย ($n$ เป็นกำลังของ 2) ฉันจะเพิกเฉยต่อระดับและการบูตเครื่อง

• การสร้างคีย์

1. $a \leftarrow U_{q}$, ที่ไหน $U_{q}$ เป็นการกระจายแบบสม่ำเสมอทั่ว $R_{q}$
2. $s \leftarrow \{-1, 0, 1\}^{n}$
3. $e \leftarrow GD(\sigma)^{n}$, ที่ไหน $GD(\sigma)$ เป็นการแจกแจงแบบเกาส์ (แบบไม่ต่อเนื่อง) โดยมีค่าเบี่ยงเบนมาตรฐาน $\sigma$
4. $b = [as + pe]_{q} \in R_{q}$ และ $pk = (a, b) \ใน R_{q}^{2}$

• การเข้ารหัส:

1. $r \leftarrow \{-1, 0, 1\}^{n}$, กับ $P(X=0) = 1/2$ และ $P(X=-1) = P(X=1) = 1/4$.
2. $e_0, e_1 \leftarrow GD(\sigma)^{n}$.
3. ข้อความ $m \ใน R_{p}$
4. $c_{0} = [br + pe_{0} + m]_{q} \ใน R_{q}$
5. $c_{1} = [ar + pe_{1}]_{q} \ใน R_{q}$
6. เข้ารหัส $m$ เช่น $\mathrm{Enc}(m) = (c_{0}, c_{1}) \in R_{q}^{2}$

• ถอดรหัส

1. สำหรับไซเฟอร์เท็กซ์ $(c_{0}, c_{1})$ถอดรหัสเป็น $[[c_{0} - c_{1}s]_{q}]_{p}\ใน R_{p}$.

ฉันเข้าใจว่าสิ่งนี้มีจุดประสงค์อย่างไร $\mathrm{ธ.ค.}(\mathrm{Enc}(m)) = m$แต่เมื่อฉันพยายามทำตัวอย่างของเล่นด้วยมือของตัวเอง ฉันพบว่าตอนนี้มีบางอย่างที่ฉันขาดหายไป สิ่งที่ฉันคิดว่ามีโมดูลัสสองโมดูล (ข้อความธรรมดาและข้อความเข้ารหัส) และการใช้ทั้งสองอย่างนี้ทำให้การถอดรหัสล้มเหลว นี้เป็นเพราะ $[[x]_{q} + [y]_{q}]_{p} \neq [[x+y]_{q}]_{p}$ และ $[[x]_{q}[y]_{q}]_{p} \neq [[xy]_{q}]_{p}$ โดยทั่วไป โดยเฉพาะอย่างยิ่งถ้า $x + pe \not\in \mathbb{Z}_{q}$แล้วจึงลดโมดูโล $คิว$ จะทำให้ $[[x+pe]_{q}]_{p} \neq [[x]_{q}]_{p}$ ซึ่งทำให้การถอดรหัสล้มเหลวฉันคิดว่าฉันพลาดอะไรง่ายๆ ไปจริงๆ แต่ฉันคิดไม่ออก

คุณต้องเลือก q เพื่อไม่ให้สัญญาณรบกวนในข้อความเข้ารหัสมากเกินไป ตัวอย่างเช่น ถ้า $p = 2$ และ $n = 256$ คุณสามารถใช้ได้ $q = 7681$ (เอามาจาก ไคเบอร์). มีตัวอย่างที่เป็นไปได้มากมาย และประเด็นสำคัญก็คือบรรทัดฐาน $||c_0 - c_1 s||_\infty = ||p (e r + e_2 - e_1 s) + m||_\infty$ น้อยกว่า $คิว/2$.