[GPV] และ [MP] (ข้อมูลอ้างอิงด้านล่าง) ให้โครงสร้างของฟังก์ชันประตูกลที่กำหนดโดย
$$
f_{\mathbf A} (\mathbf x) = \mathbf A \mathbf x
$$
ที่ไหน $\mathbf A \in \mathbb Z_q^{n \times m}$ เป็นการสุ่มแบบสม่ำเสมอ และโดเมนคือ $\{ \mathbf x \in \mathbb Z^m \กลาง \lVert x \rVert \le \beta\}$. กำหนดใด ๆ $\mathbf y \in \mathbb Z_q^n$ประตูกลลับช่วยให้สามารถคำนวณภาพล่วงหน้าได้ $\mathbf x$ ของ $\mathbf y$, เช่น. $\mathbf A \mathbf x = \mathbf y$ และ $\lVert \mathbf x \rVert \le \beta$.
ประตูกลใน [GPV] เป็นชุดระดับเต็ม $\mathbf S \in \mathbb Z^{m \times m}$ ดังนั้น $\mathbf A \mathbf S = 0$. ประตูกลใน [MP] คือ $\mathbf R$ ดังนั้น $\mathbf A \begin{bmatrix} \mathbf R \ \mathbf I \end{bmatrix} = \mathbf G$, ที่ไหน $\mathbf G$ เป็นเมทริกซ์แกดเจ็ตสาธารณะพิเศษ ไม่ว่าในกรณีใด ประตูกลแต่ละบานจะมีปริมาณที่สัมพันธ์กัน $s$ ที่อธิบายคุณภาพของมัน สำหรับ $\mathbf เอส$, $s=$ บรรทัดฐานสูงสุดของคอลัมน์ของ Gram-Schmidt $\tilde{\mathbf S}$ ของ $\mathbf เอส$. สำหรับ $\mathbf R$, $s = $ ค่าเอกพจน์ที่ใหญ่ที่สุดของ $\mathbf R$.
กำหนดใด ๆ $\mathbf y$ประตูกลแห่งคุณภาพ $s$ อนุญาตให้สุ่มตัวอย่างจากการแจกแจงแบบเกาส์เซียนแบบไม่ต่อเนื่อง $\{\mathbf{x} \กลาง \mathbf A\mathbf x = \mathbf y\}$ ของความกว้าง $\sigma \ge s\cdot\omega(\sqrt{\log m})$, ซึ่งจะช่วยให้ $\lVert x \rVert \le \sigma\sqrt m$ (ด้วยความน่าจะเป็นอย่างท่วมท้น).
คำถามของฉันเกี่ยวกับการย้อนกลับ สมมติว่าเรามี oracle สำหรับการสุ่มตัวอย่างแบบ Gaussian preimage ที่แสดงผลโซลูชันสำหรับ $\mathbf A \mathbf x = \mathbf y$ กับ $\lVert x \rVert \le \beta$ สำหรับการเลือกโดยพลการ $\mathbf y$. เราสามารถกู้คืนประตูกลบางอย่างได้หรือไม่ $\mathbf A$ ที่ช่วยให้เราคำนวณภาพล่วงหน้า $\mathbf x'$ ของการสุ่ม $\mathbf y'$ ที่ไม่ได้ถามถึง oracle ด้วยความน่าจะเป็นที่ไม่สำคัญ?
ความพยายามที่ชัดเจนอย่างหนึ่งคือการสอบถาม $\mathbf A \mathbf x = \mathbf 0$ เพื่อลองกู้คืนชุดเต็มระดับ "สั้น" $\mathbf เอส$ ดังนั้น $\mathbf A \mathbf S = \mathbf 0$. แต่นี่ $\mathbf เอส$ ดูเหมือนจะไม่สั้นพอที่จะคำนวณคำตอบของความยาว $\le \เบต้า$. เราลองลดแลตทิซได้ แต่ฉันไม่รู้ว่าการลดโครงตาข่ายที่ทันสมัยสำหรับปัญหานี้คืออะไร พยายามที่จะทำให้พื้นฐานสั้นลงจากพื้นฐานที่สั้นอยู่แล้ว
- [จีพีวี] https://eprint.iacr.org/2007/432
- [MP] https://eprint.iacr.org/2011/501