LWE-cryptosystem เป็นเพียง CPA-secure ดังตัวอย่างที่ระบุไว้ใน ทศวรรษแห่งการเข้ารหัสแบบ Lattice-Based. พิจารณาระบบต่อไปนี้ที่อธิบายไว้ในนั้น (ข้อ 5.2)
- รหัสลับเป็นความลับ LWE ที่เหมือนกัน $s \in \mathbb{Z}_q^n$และคีย์สาธารณะคือบางส่วน $m \ประมาณ (n+1) \log(q)$ ตัวอย่าง $(\bar{a}_i, b_i = \left <\bar{a}_i, s \right > +e$ รวบรวมเป็นคอลัมน์ของเมทริกซ์ $A$
$$A = \begin{pmatrix} \bar{A} \ b^t \end{pmatrix} \in \mathbb{Z}_q^{(n+1) \times m}$$
ที่ไหน $b^t = s^t \bar{A} +e e^t \mod q$.
- เพื่อเข้ารหัสบิต $\mu \in \mathbb{Z}_2 = \{0,1\}$ โดยใช้รหัสสาธารณะ $A$หนึ่งเลือกยูนิฟรอม $x \ใน {0,1}^m$ และส่งออกไซเฟอร์เท็กซ์
$$c = A \cdot x + (0, \mu \cdot \lfloor \frac{q}{2} \rceil) \in \mathbb{Z}_q^{n+1}$$
- ในการถอดรหัสโดยใช้รหัสลับ $\mathbb{s}$หนึ่งเครื่องคำนวณ:
$$(-s, 1)^t \cdot c = (-s, 1)^t \cdot A \cdot x +\mu \cdot \lfloor \frac{q}{2} \rceil) \in \mathbb {Z}_q^{n+1}$$
$$ = e^t \cdot x + \mu \cdot \lfloor \frac{q}{2} \rceil) \in \mathbb{Z}_q^{n+1}$$
$$\around \mu \cdot \lfloor \frac{q}{2} \rceil \in \mathbb{Z}_q^{n+1} \mod q$$
และทดสอบว่าใกล้จะถึงหรือยัง $0$ หรือ $\frac{q}{2} \mod q$.
กระดาษระบุว่า "เราทราบว่าระบบสามารถแตกหักได้เล็กน้อยภายใต้การโจมตีแบบแอ็กทีฟหรือที่เลือกไว้"
การโจมตีดังกล่าวจะมีลักษณะอย่างไร? ฉันจะพิจารณาที่จะเข้ารหัส $0$ สักหน่อยด้วย $x$ เป็นทั้งหมด $1$-s เวกเตอร์ที่จะดึง $e$ แล้วเรียกคืน $s$ ทาง $\bar{A}^{-1} \cdot (b-e)$. มีวิธีอื่นที่ทราบหรือไม่? และมีวิธีใดบ้างที่เป็นที่รู้จักในการขยายการโจมตีเหล่านี้ไปยังผู้สมัครที่เข้ารอบสุดท้าย NIST-pqc เวอร์ชันที่ปลอดภัย CPA เช่น Kyber