ระบบเข้ารหัสลับ LWE ที่ปลอดภัยของ CPA จะถูกทำลายโดยผู้โจมตีที่ใช้งานอยู่ได้อย่างไร

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