LWE และฟังก์ชั่นกรงเล็บประตูกลแบบขยายเพิ่มเติม

อนุญาต $q \geq 2$ เป็นจำนวนเต็มเฉพาะ พิจารณาสองฟังก์ชันที่กำหนดโดย:

$$f(b, x) = ขวาน + b \cdot u + e~~~(\text{mod}~q),$$ $$g(b, x) = ขวาน + b \cdot (As + e') + e~~~(\text{mod}~q),$$

ที่เรามี: \begin{จัด} ข &\in \{0, 1\}, \ x &\in \mathbb{Z}_{q}^{n}, \ s &\in \mathbb{Z}_{q}^{m}, \ &\in \mathbb{Z}_{q}^{n \times m}, \ e' &\in \mathbb{Z}_{q}^{m}, \ คุณ &\in \mathbb{Z}_{q}^{m}, \end{จัด}

$e$ สุ่มตัวอย่างจากการแจกแจง:

\begin{สมการ} D_{\mathbb{Z}_q, B^{'}}(x) = \frac{e^{\frac{- \pi ||x||^{2}}{B^{'2}}} }{\sum_{x \in \mathbb{Z}_q^{n}, ||x|| \leq B'} e^{\frac{- \pi ||x||^{2}}{B^{'2}}}}, \end{สมการ} ที่ไหน $$B' = \frac{q}{C_{T} \sqrt{mn \log q}},$$ $C_{T}$ เป็นค่าคงที่คงที่

ใน นี้ กระดาษ ฟังก์ชันที่กำหนดไว้ในสมการ 29 และมีการกล่าวถึงในกรณีที่เลวร้ายที่สุดกว่า $A$, $u$ และ $e'$สมมติว่า LWE ยากสำหรับอัลกอริธึมคลาสสิคของเวลาพหุนาม โดยแยกแยะระหว่าง $f$ และ $g$ ก็ยากเช่นกัน $A$ และให้ (พหุนามมาก) "ตัวอย่าง" (ตั้งแต่ $e$ เป็นการแจกแจงความน่าจะเป็น ผลลัพธ์ของ $f$ หรือ $g$ เป็นตัวอย่าง) จากอย่างใดอย่างหนึ่ง $f$ หรือ $g$.

การลด LWE ยังถือเป็นกรณีเฉลี่ย

กระดาษยังระบุด้วยว่าฟังก์ชันทั้งสองนี้เป็นตระกูลของ "ฟังก์ชันกรงเล็บประตูกับดักแบบขยาย (คำจำกัดความ 5, 6, 7)"

เพื่อเป็นการอ้างอิงถึงการพิสูจน์ข้อเท็จจริงข้างต้นเหล่านี้ กระดาษอ้างอิง นี้ กระดาษ (บทที่ 9.3) อย่างไรก็ตาม ในขณะที่พิสูจน์บทแทรก 9.3 เอกสารฉบับที่สองยังอ้างอิงเอกสารอื่นๆ เช่น นี้ หนึ่ง. หลักฐานไม่ชัดเจนสำหรับฉันในเอกสารใด ๆ

ฉันต้องการถามวิธีลดงานของการแยกแยะระหว่าง $f$ และ $g$ ถึง LWE ฉันยังต้องการถามเกี่ยวกับความสำคัญของฟังก์ชันที่ "ขยายกรงเล็บประตูกับดัก" ในการลดลงนั้น

จากความเข้าใจของฉันความแข็งของ LWE บอกว่าถ้าเราได้รับ $A$แยกแยะความแตกต่างระหว่างตัวอย่างสุ่มแบบสม่ำเสมอและตัวอย่างจาก $เป็น + e'$ เป็นเรื่องยาก ฉันไม่แน่ใจว่าเป็นอย่างไร $ข$ และ $x$ หรือพารามิเตอร์อื่น ๆ เป็นปัจจัยในข้อเท็จจริงนั้น นั่นคือจุดที่เราต้องการหลักฐานที่ปราศจากกรงเล็บแบบขยายประตูกับดักหรือไม่?