พิจารณาปัญหาของความแตกต่างระหว่างตัวอย่างพหุนามจำนวนมากของอย่างใดอย่างหนึ่ง
\begin{สมการ}
(x, b, As + e) ~~\text{or}~~\left(x, b, ~Ax + b\cdot(As + e) + e'\right)
\end{สมการ}
ที่นี่, $A$ เป็นเมทริกซ์สาธารณะและ $s$ เป็นเวกเตอร์ลับที่ถูกเลือกแบบสุ่ม $e$ และ $e'$ เป็นข้อผิดพลาด Gaussian $x$ และ $ข$ มีการสุ่มตัวอย่างอย่างสม่ำเสมอ
ขนาดของวัตถุต่างๆ มีดังนี้
\begin{จัด}
ข &\in \{0, 1\}, \
x &\in \mathbb{Z}_{q}^{n}, \
s &\in \mathbb{Z}_{q}^{n}, \
A &\in \mathbb{Z}_{q}^{m \times n}, \
e, e' &\in \mathbb{Z}_{q}^{m}, \
\end{แนว}
$q \geq 2$ เป็นจำนวนเต็มเฉพาะ
ทั้งสองกรณีนี้แยกไม่ออก (ในทางคำนวณ) เมื่อเราได้รับตัวอย่างพหุนามจำนวนมากหรือไม่? ฉันคิดว่าพวกเขาเป็น แต่ฉันไม่สามารถผูกเข้ากับการคาดเดาได้
โปรดทราบว่าโดย LWE
\begin{สมการ}
(x, b, As + e) ~~\text{and}~~\left(x, b, u\right),
\end{สมการ}
แยกไม่ออกทางคอมพิวเตอร์และเป็นเช่นนั้น
\begin{สมการ}
(x, b, ~Ax + b\cdot(As + e) + e') ~~\text{and}~~\left(x, b, ~Ax + b\cdot u + e'\right)
\end{สมการ}
$u$ เป็นการสุ่มอย่างสมํ่าเสมอ อย่างไรก็ตาม ฉันไม่สามารถลดกรณีของฉันเป็น LWE ได้