วิธีที่เร็วที่สุดในการตรวจสอบว่าเวกเตอร์ที่กำหนดสั้นที่สุดในแลตทิซคืออะไร

กำหนดแลตทิซ L และเวกเตอร์ $v_1$ อ้างว่าสั้นที่สุด วิธีตรวจสอบ/ยืนยันว่าเร็วที่สุดคืออะไร $v_1$ สั้นที่สุดในตาข่ายจริงหรือ?

วิธีมาตรฐานที่ทำให้ SVP เป็นทางการคือสิ่งที่คุณถามไม่เกี่ยวข้องกับการแสดงจริงๆ $SVP\in\mathsf{NP}$. พิธีการทั่วไปของ SVP คือ (สำหรับบรรทัดฐานโดยพลการ $\lVert\cdot\rVert$ บน $\mathbb{R}^n$ --- โปรดทราบว่าความแข็งของ SVP สามารถขึ้นอยู่กับตัวเลือกบรรทัดฐานเฉพาะ):

อนุญาต $n\in\mathbb{N}$, และ $\gamma\in\mathbb{R}_{\geq 0}$. อินสแตนซ์ของ SVP เป็นคู่ $(\แลมบ์ดา, \gamma)$, ที่ไหน $\Lambda\subseteq\mathbb{R}^n$ เป็นตาข่ายและ $\gamma$ ค่าคงที่ เราบอกว่าอินสแตนซ์ SVP $(\Lambda,\gamma)$ ยอมรับถ้า: $$\min_{v\in\Lambda\setminus\{0\}}\lVert v\rVert \leq\gamma$$ และปฏิเสธเป็นอย่างอื่น

ในแง่ของการกำหนดปัญหานี้ NP เป็นพยานถึงตัวอย่างปัญหา $(\แลมบ์ดา, \gamma)$ เป็นเวกเตอร์ใดๆ $v\in\Lambda\setminus\{0\}$ ดังนั้น $\lVert v\rVert \leq \gamma$. สิ่งเหล่านี้สามารถอธิบายได้อย่างมีประสิทธิภาพ และควรชัดเจนว่าจะตรวจสอบได้อย่างมีประสิทธิภาพได้อย่างไร $(\Lambda,\gamma)$ จะยอมรับหรือปฏิเสธก็ตามที่ได้รับจากพยานดังกล่าว

แน่นอน คำถามของคุณมีการตีความที่กว้างขึ้น --- เราสามารถระบุได้อย่างมีประสิทธิภาพว่าเวกเตอร์ที่สั้นที่สุดของผู้สมัครบางคนหรือไม่ $v$ เวกเตอร์ที่สั้นที่สุดในแลตทิซคือ "จริง" หรือไม่ ฉันไม่ใช่ผู้เชี่ยวชาญ แต่:

1. ฉันไม่เชื่อว่าสิ่งนี้เป็นที่รู้จักในกรณีที่เลวร้ายที่สุด (แต่ฉันไม่แน่ใจ)
2. ในกรณีทั่วไป (ซึ่งเป็นสิ่งที่ทุกคนให้ความสำคัญ) สมาธิที่มากพอจะส่งผล $\lambda_1(\แลมบ์ดา)$ รู้ว่าไม่สำคัญ

โดยเฉพาะอย่างยิ่ง สำหรับการแจกแจงแบบ "ยาก" ของตัวเลือกส่วนใหญ่บนแลตทิซ $\Lambda\gets \mathcal{D}$, $\lambda_1(\แลมบ์ดา)$ มีความเข้มข้นสูงตามค่าที่ทราบ ดังนั้นเพื่อ "ตรวจสอบ" ว่าเวกเตอร์ตัวเลือกบางตัวหรือไม่ $v$ สั้นที่สุดในตารางแบบสุ่ม $\แลมบ์ดา$ก็เพียงพอแล้วที่จะตรวจสอบว่า $\lVert v\rVert$ ใกล้เคียงกับค่าที่ทราบของ $\mathbb{E}_{\Lambda\gets\mathcal{D}}[\lambda_1(\Lambda)]$. ดูตัวอย่าง Lattices แบบสุ่ม: ทฤษฎีและการปฏิบัติซึ่งรวมถึงตัวชี้ไปยังงานทางคณิตศาสตร์ที่เกี่ยวข้อง