ในวิทยาการคอมพิวเตอร์ปัญหาแลตติสเป็นกลุ่มของ ปัญหา การหาค่าเหมาะสมที่สุดที่เกี่ยวข้องกับวัตถุทางคณิตศาสตร์ที่เรียกว่าแลตติส ความยากลำบากใน การแก้ ปัญหาดังกล่าว ที่คาดการณ์ไว้เป็นหัวใจสำคัญในการสร้างระบบเข้ารหัสลับที่ปลอดภัยบนพื้นฐานแลต ติส ปัญหาแลตติสเป็นตัวอย่างของ ปัญหา NP-hardซึ่งได้รับการพิสูจน์แล้วว่าเป็นปัญหา ที่ยากใน กรณีเฉลี่ย (average-case hard)ซึ่งเป็นกรณีทดสอบสำหรับความปลอดภัยของอัลกอริธึมการเข้ารหัสลับ นอกจากนี้ ปัญหาแลตติสบางปัญหาที่ยากที่สุด (worst-case hard) สามารถใช้เป็นพื้นฐานสำหรับแผนการเข้ารหัสลับที่ปลอดภัยอย่างยิ่ง การใช้ความยากในกรณีที่แย่ที่สุดในแผนการดังกล่าวทำให้แผนการเหล่านั้นเป็นหนึ่งในแผนการไม่กี่แผนที่น่าจะปลอดภัยแม้กระทั่งกับคอมพิวเตอร์ควอนตัมสำหรับการใช้งานในระบบเข้ารหัสลับ ดังกล่าว โดยทั่วไปจะพิจารณา แลตติสบนปริภูมิเวกเตอร์ (มักจะเป็น) หรือโมดูลอิสระ (มักจะเป็น) ${\displaystyle \mathbb {Q} ^{n}}$${\displaystyle \mathbb {Z} ^{n}}$

สำหรับปัญหาทั้งหมดด้านล่าง ให้ถือว่าเราได้รับ (นอกเหนือจากข้อมูลป้อนเข้าที่เฉพาะเจาะจงอื่นๆ) ฐานสำหรับปริภูมิเวกเตอร์Vและนอร์มNนอร์มที่พิจารณาโดยทั่วไปคือนอร์มยุคลิดL ²อย่างไรก็ตาม นอร์มอื่นๆ (เช่นL ^p ) ก็ได้รับการพิจารณาและปรากฏในผลลัพธ์ที่หลากหลายเช่นกัน^{[ 1 ]}

ในบทความนี้ ให้แทนความยาวของเวกเตอร์ที่ไม่เป็นศูนย์ที่สั้นที่สุดในโครงข่ายLนั่นคือ ${\displaystyle \lambda (L)}$

${\displaystyle \lambda (L)=\min _{v\in L\smallsetminus \{\mathbf {0} \}}\|v\|_{N}.}$

ในปัญหา SVP (Single Value Proposition) จะมี การกำหนด ฐานของปริภูมิเวกเตอร์Vและนอร์มN (มักจะ^เป็นL² ) สำหรับแลตทิซ Lและต้องหาเวกเตอร์ที่ไม่เป็นศูนย์ที่สั้นที่สุดในVโดยวัดจากNในLกล่าวอีกนัยหนึ่งคือ อัลกอริทึมควรส่งออกเวกเตอร์ที่ไม่เป็นศูนย์vที่มีคุณสมบัติ⁠ ⁠${\displaystyle \|v\|_{N}=\แลมบ์ดา (L)}$ต่อไปนี้ ขนาดของปัญหาจะระบุด้วยnซึ่งเป็น มิติของปริภูมิเวกเตอร์V

ในเวอร์ชันการประมาณค่า γ ของ SVP γ _นั้นต้องหาเวกเตอร์แลตติซที่ไม่เป็นศูนย์ซึ่งมีความยาวไม่เกินสำหรับค่าที่กำหนด${\displaystyle \gamma \cdot \lambda (L)}$${\displaystyle \gamma \geq 1}$

เวอร์ชันที่แน่นอนของปัญหาเป็นที่ทราบกันว่าเป็นNP-hardสำหรับการลดแบบสุ่ม เท่านั้น ^{[ 2 ] [ 3 ]} ในทางตรงกันข้าม ปัญหาที่สอดคล้องกันเกี่ยวกับบรรทัดฐานแบบเอกรูปเป็นที่ทราบกันว่าเป็นNP- hard ^{[ 4 ]}

เพื่อแก้ปัญหา SVP เวอร์ชันที่แน่นอนภายใต้บรรทัดฐานยุคลิด มีวิธีการต่างๆ มากมายที่เป็นที่รู้จัก ซึ่งสามารถแบ่งออกเป็นสองประเภท: อัลกอริทึมที่ต้องการเวลาและหน่วยความจำแบบซูเปอร์เอ็กซ์โพเนนเชียล ( ) และอัลกอริทึมที่ต้องการทั้งเวลาและพื้นที่แบบเอ็กซ์โพเนนเชียล ( ) ในมิติของแลตทิซ อัลกอริทึมประเภทแรกที่โดดเด่นที่สุด ได้แก่ การแจงนับแลตทิซ^{[ 5 ] [ 6 ] [ 7 ]}และการลดการสุ่มตัวอย่างแบบสุ่ม^{[ 8 ] [ 9 ]}ในขณะที่ประเภทหลัง ได้แก่ การกรองแลตทิซ^{[ 10 ] [ 11 ] [ 12 ]}การคำนวณเซลล์โวโรนอยของแลตทิซ^{[ 13 ] [ 14 ]}และการสุ่มตัวอย่างแบบเกาส์เซียนแบบไม่ต่อเนื่อง^{[ 15 ]}ปัญหาที่ยังเปิดอยู่คือ มีอัลกอริทึมสำหรับการแก้ปัญหา SVP ที่แน่นอนที่ทำงานในเวลาแบบเอ็กซ์โพเนนเชียลเดี่ยว ( ) และต้องการหน่วยความจำที่ปรับขนาดแบบพหุนามในมิติของแลตทิซ หรือไม่ ^{[ 16 ]}${\displaystyle 2^{\โอเมก้า (n)}}$${\displaystyle \operatorname {poly} (n)}$${\displaystyle 2^{\Theta (n)}}$${\displaystyle 2^{O(n)}}$

เพื่อแก้ปัญหา SVP γ เวอร์ชันประมาณค่า_γสำหรับนอร์มยุคลิด วิธีการที่รู้จักกันดีที่สุดคือการใช้การลดฐานแลตติสสำหรับค่า ⁠ ⁠ ขนาดใหญ่อัลก อริทึม Lenstra –Lenstra–Lovász (LLL)สามารถหาคำตอบได้ในเวลาพหุนามตามมิติของแลตติส สำหรับค่า ⁠ ที่เล็กกว่าอัลกอริทึม Block Korkine-Zolotarev (BKZ) ^{[ 17 ] [ 18 ] [ 19 ]}มักใช้กัน โดยที่อินพุตของอัลกอริทึม (ขนาดบล็อก) จะกำหนดความซับซ้อนของเวลาและคุณภาพของเอาต์พุต: สำหรับปัจจัยการประมาณค่าขนาดใหญ่ขนาดบล็อกเล็ก ๆก็เพียงพอแล้ว และอัลกอริทึมจะสิ้นสุดอย่างรวดเร็ว สำหรับค่า ⁠ ที่เล็กกว่า จำเป็นต้องใช้ค่า ⁠ ที่ใหญ่กว่าเพื่อหาเวกเตอร์แลตติสที่สั้นเพียงพอ และอัลกอริทึมจะใช้เวลานานขึ้นในการหาคำตอบ อัลกอริทึม BKZ ใช้ขั้นตอนวิธี SVP ที่แม่นยำเป็นขั้นตอนย่อยภายใน (ทำงานในแลตทิซที่มีมิติไม่เกิน) และความซับซ้อนโดยรวมของมันมีความสัมพันธ์อย่างใกล้ชิดกับต้นทุนของการเรียกใช้ SVP เหล่านี้ในมิติ⁠ ⁠${\displaystyle \gamma >1}$${\displaystyle \gamma =2^{\โอเมก้า (n)}}$${\displaystyle \gamma }$${\displaystyle \beta }$${\displaystyle \gamma }$${\displaystyle \beta }$${\displaystyle \gamma }$${\displaystyle \beta }$${\displaystyle \beta }$${\displaystyle \beta }$

ปัญหา GapSVP _βประกอบด้วยการแยกแยะระหว่างกรณีของ SVP ที่ความยาวของเวกเตอร์ที่สั้นที่สุดมีค่าไม่เกินหรือมากกว่า⁠ ⁠โดยที่ ⁠ สามารถเป็นฟังก์ชันคงที่ของมิติของแลตทิซ⁠ ⁠ได้ เมื่อกำหนดฐานสำหรับแลตทิซแล้ว อัลกอริทึมต้องตัดสินใจว่าหรือ⁠ ⁠ เช่นเดียวกับ ปัญหาสัญญาอื่นๆอัลกอริทึมสามารถผิดพลาดได้ในกรณีอื่นๆ ทั้งหมด ${\displaystyle 1}$${\displaystyle \beta }$${\displaystyle \beta }$${\displaystyle n}$${\displaystyle \lambda (L)\leq 1}$${\displaystyle \lambda (L)>\beta }$

ปัญหาอีกรูปแบบหนึ่งคือ GapSVP _ζ,γสำหรับฟังก์ชัน ζ และ γ บางฟังก์ชัน อินพุตของอัลกอริทึมคือฐานและตัวเลขรับประกันว่าเวกเตอร์ทั้งหมดในการตั้งฉากแบบ Gram–Schmidtมีความยาวอย่างน้อย 1 และ และ⁠ ⁠ โดยที่คือมิติ อัลกอริทึมต้องยอมรับถ้า⁠ ⁠และปฏิเสธถ้า⁠ ⁠สำหรับค่ามาก(เช่น⁠ ⁠ ) ปัญหาจะเทียบเท่ากับ GapSVP _γเนื่องจาก^{[ 20 ]}การประมวลผลล่วงหน้าที่ทำโดยใช้อัลกอริทึม LLLทำให้เงื่อนไขที่สอง (และด้วยเหตุนี้⁠ ⁠ ) ซ้ำซ้อน ${\displaystyle B}$${\displaystyle d}$${\displaystyle \lambda (L(B))\leq \zeta (n)}$${\displaystyle 1\leq d\leq \zeta (n)/\gamma (n)}$${\displaystyle n}$${\displaystyle \lambda (L(B))\leq d}$${\displaystyle \lambda (L(B))\geq \gamma (n)\cdot d}$${\displaystyle \zeta }$${\displaystyle \zeta (n)>2^{n/2}}$${\displaystyle \zeta }$

ใน CVP ( Continuous Value Problem) จะมีการกำหนดฐานของปริภูมิเวกเตอร์VและเมตริกM (มักจะ^เป็นL² ) สำหรับแลตทิซ Lรวมถึงเวกเตอร์vในVแต่ไม่จำเป็นต้องอยู่ในLสิ่งที่ต้องการคือการหาเวกเตอร์ในLที่อยู่ใกล้v มากที่สุด (วัดจากM ) ในCVP เวอร์ชันการประมาณค่า_γจะต้องหาเวกเตอร์แลตทิซที่ระยะห่างไม่เกิน ${\displaystyle \gamma }$${\displaystyle \gamma }$

ปัญหาเวกเตอร์ที่ใกล้ที่สุดเป็นการวางนัยทั่วไปของปัญหาเวกเตอร์ที่สั้นที่สุด แสดงให้เห็นได้ง่ายว่าเมื่อกำหนดออราเคิลสำหรับ CVP _γ (ที่กำหนดไว้ด้านล่าง) เราสามารถแก้ปัญหา SVP _γ ได้ โดยการสอบถามออราเคิลบางส่วน^{[ 21 ]}วิธีการแบบง่ายในการหาเวกเตอร์ที่สั้นที่สุดโดยการเรียกออราเคิล CVP _γเพื่อหาเวกเตอร์ที่ใกล้ที่สุดกับ 0 นั้นใช้ไม่ได้ผล เพราะ 0 เองก็เป็นเวกเตอร์แลตทิซ และอัลกอริทึมอาจส่งค่า 0 ออกมาได้

การลดรูปจาก SVP _γไปเป็น CVP _γมีดังนี้: สมมติว่าอินพุตของ SVP _γคือฐานสำหรับแลตทิซพิจารณาฐานและให้เป็นเวกเตอร์ที่ส่งคืนโดยCVP _γ ( B ⁱ , b _i )ข้ออ้างคือ เวกเตอร์ที่สั้นที่สุดในเซตคือ เวกเตอร์ที่สั้นที่สุดในแลตทิซที่กำหนด ${\displaystyle B=[b_{1},b_{2},\ldots ,b_{n}]}$${\displaystyle B^{i}=[b_{1},\ldots ,2b_{i},\ldots ,b_{n}]}$${\displaystyle x_{i}}$${\displaystyle \{x_{i}-b_{i}\}}$

Goldreich และคณะแสดงให้เห็นว่าความแข็งของ SVP ใดๆ ก็ตามหมายถึงความแข็งของ CVP เช่นกัน^{[ 22 ] Arora และคณะใช้เครื่องมือ PCP แสดงให้เห็นว่า CVP นั้นยากที่จะประมาณค่าได้ภายในปัจจัย เว้นแต่ [ 23 ] Dinur}และคณะได้เสริมความแข็งแกร่งให้^{กับสิ่ง}นี้โดยให้ผลลัพธ์ความแข็งแบบ^NPสำหรับ[ ^{24 ]}${\displaystyle 2^{\log ^{1-\epsilon }(n)}}$${\displaystyle \operatorname {NP} \subseteq \operatorname {DTIME} (2^{\operatorname {poly} (\log n)})}$${\displaystyle \epsilon =(\log \log n)^{c}}$${\displaystyle c<1/2}$

อัลกอริทึมสำหรับ CVP โดยเฉพาะตัวแปร Fincke และ Pohst ^{[ 6 ]}ถูกนำมาใช้สำหรับการตรวจจับข้อมูลในระบบสื่อสารไร้สายแบบหลายอินพุตหลายเอาต์พุต ( MIMO ) (สำหรับสัญญาณที่เข้ารหัสและไม่เข้ารหัส) ^{[ 25 ] [ 13 ]}ในบริบทนี้เรียกว่าการถอดรหัสทรงกลมเนื่องจากรัศมีที่ใช้ภายในโซลูชัน CVP จำนวนมาก^{[ 26 ]}

ได้มีการนำไปประยุกต์ใช้ในสาขาการแก้ปัญหาความกำกวมจำนวนเต็มของ GNSS เฟสคลื่นพาหะ (GPS) ^{[ 27 ]} ในสาขานี้ เรียกว่าวิธี LAMBDAในสาขาเดียวกันนี้ ปัญหา CVP ทั่วไปเรียกว่ากำลังสองน้อยที่สุดจำนวนเต็ม

ปัญหานี้คล้ายกับปัญหา GapSVP สำหรับ GapSVP _βข้อมูลนำเข้าประกอบด้วยฐานแลตติสและเวกเตอร์และอัลกอริทึมต้องตอบว่าเงื่อนไขใดเงื่อนไขหนึ่งต่อไปนี้เป็นจริง: ${\displaystyle v}$

• มีเวกเตอร์แลตติซตัวหนึ่งซึ่งระยะห่างระหว่างเวกเตอร์นั้นกับเวกเตอร์อื่นมีค่าไม่เกิน 1 และ${\displaystyle v}$
• เวกเตอร์แลตติซทุกตัวอยู่ ห่างจากจุดนั้นเป็นระยะทางมากกว่า${\displaystyle \beta }$${\displaystyle v}$

เงื่อนไขตรงกันข้ามคือ เวกเตอร์แลตติซที่ใกล้ที่สุดอยู่ห่างออกไปเป็นระยะทางหนึ่งจึงเป็นที่มาของชื่อGap CVP (ช่องว่างของ CVP) ${\displaystyle 1<\แลมบ์ดา (L)\leq \beta }$

ปัญหาดังกล่าวสามารถจัดการได้โดยง่ายในกลุ่มปัญหา NPสำหรับปัจจัยการประมาณค่าใดๆ ก็ตาม

ในปี 1987 Schnorrแสดงให้เห็นว่าอัลกอริทึมเวลาพหุนามเชิงกำหนดสามารถแก้ปัญหาสำหรับ[ ^{28 ] Ajtai}และคณะแสดงให้เห็นว่าอัลกอริทึมเชิงความน่าจะเป็นสามารถบรรลุปัจจัยการประมาณที่ดีขึ้นเล็กน้อยของ^{[ 10 ]}${\displaystyle \beta =2^{O(n(\log \log n)^{2}/\log n)}}$${\displaystyle \beta =2^{O(n\log \log n/\log n)}}$

ในปี 1993 Banaszczyk แสดงให้เห็นว่า GapCVP _nอยู่ใน[ ^{29 ] ใน}ปี 2000 Goldreich และ Goldwasser แสดงให้เห็นว่าทำให้ปัญหานี้อยู่ในทั้ง NP และcoAM [ ^{30 ] ใน}ปี 2005 Aharonov และ Regev แสดงให้เห็นว่าสำหรับค่าคงที่บางค่าปัญหาที่มีอยู่ใน^{[ 31 ]}${\displaystyle {\mathsf {NP\cap coNP}}}$${\displaystyle \beta ={\sqrt {n/\log n}}}$${\displaystyle c}$${\displaystyle \beta =c{\sqrt {n}}}$${\displaystyle {\mathsf {NP\cap coNP}}}$

สำหรับขอบเขตล่าง Dinur et al. แสดงให้เห็นในปี 1998 ว่าปัญหานี้เป็นปัญหา NP-hard สำหรับ^{[ 32 ]}${\displaystyle \beta =n^{o(1/\log {\log {n}})}}$

กำหนดให้แลตทิซ L มีมิติnอัลกอริทึมจะต้องส่งออกค่าที่เป็นอิสระเชิงเส้นจำนวนn ค่า โดยที่ด้านขวามือพิจารณาฐานทั้งหมดของแลตทิซ ${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$${\displaystyle \max \|v_{i}\|\leq \max _{B}\|b_{i}\|}$${\displaystyle B=\{b_{1},\ldots ,b_{n}\}}$

ใน เวอร์ชันประมาณ ค่า -approximate เมื่อ กำหนด แลตทิซ L ที่มีมิติnจะต้องหาเวกเตอร์อิสระเชิงเส้นn ตัว ที่มีความยาว⁠ ⁠โดยที่คือ ค่าต่ำสุดต่อเนื่อง ^{ลำดับ}ที่ของ⁠ ⁠${\displaystyle \gamma }$${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$${\displaystyle \max \|v_{i}\|\leq \gamma \lambda _{n}(L)}$${\displaystyle \แลมบ์ดา _{n}(L)}$${\displaystyle n}$${\displaystyle L}$

ปัญหานี้คล้ายกับปัญหาค่ากลาง (CVP) กล่าวคือ เมื่อกำหนดเวกเตอร์ที่มีระยะห่างจากโครงข่ายไม่เกินค่าหนึ่งอัลกอริทึมจะต้องแสดงผลลัพธ์เป็นเวกเตอร์โครงข่ายที่อยู่ใกล้ที่สุดกับเวกเตอร์นั้น ${\displaystyle \lambda (L)/2}$

เมื่อกำหนดฐานสำหรับโครงข่ายแล้ว อัลกอริทึมจะต้องค้นหาระยะทางที่มากที่สุด (หรือในบางเวอร์ชัน ค่าประมาณ) จากเวกเตอร์ใดๆ ไปยังโครงข่าย

ปัญหาหลายอย่างจะง่ายขึ้นหากฐานอินพุตประกอบด้วยเวกเตอร์สั้นๆ อัลกอริทึมที่แก้ปัญหาฐานที่สั้นที่สุด (Shortest Basis Problem หรือ SBP) จะต้องสร้างฐานที่เทียบเท่ากันโดยที่ความยาวของเวกเตอร์ที่ยาวที่สุดในฐานนั้นสั้นที่สุดเท่าที่จะเป็นไปได้ เมื่อกำหนดฐานแลตติส ให้${\displaystyle B}$${\displaystyle B'}$${\displaystyle B'}$

_{ปัญหา SBP γ}เวอร์ชันประมาณค่าประกอบด้วยการหาฐานที่มีเวกเตอร์ที่ยาวที่สุดยาวกว่าเวกเตอร์ที่ยาวที่สุดในฐานที่สั้นที่สุดไม่ เกิน เท่า${\displaystyle \gamma }$

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

ปัญหาแลตติสข้างต้นนั้นง่ายต่อการแก้ไขหากอัลกอริทึมได้รับฐานที่ดี อัลกอริทึมการ ลดแลตติสมีเป้าหมายที่จะสร้างฐานใหม่ที่ประกอบด้วยเวกเตอร์ ที่ค่อนข้างสั้นและเกือบ ตั้งฉาก กัน โดยกำหนด ฐานสำหรับแลตติสให้ อัลกอริทึมการลดฐานแลตติส Lenstra–Lenstra–Lovász (LLL) เป็นอัลกอริทึมที่มีประสิทธิภาพในยุคแรกสำหรับปัญหานี้ ซึ่งสามารถสร้างฐานแลตติสที่ลดลงเกือบทั้งหมดได้ในเวลาพหุนาม^{[ 33 ]}อัลกอริทึมนี้และการปรับปรุงเพิ่มเติมถูกนำมาใช้เพื่อทำลายแผนการเข้ารหัสหลายแบบ ทำให้มันกลายเป็นเครื่องมือที่สำคัญมากในการวิเคราะห์การเข้ารหัสความสำเร็จของ LLL บนข้อมูลทดลองนำไปสู่ความเชื่อว่าการลดแลตติสอาจเป็นปัญหาที่ง่ายในทางปฏิบัติ อย่างไรก็ตาม ความเชื่อนี้ถูกท้าทายในช่วงปลายทศวรรษ 1990 เมื่อมีผลลัพธ์ใหม่หลายอย่างเกี่ยวกับความยากของปัญหาแลตติส โดยเริ่มจากผลลัพธ์ของAjtai ^{[ 2 ]}

ในเอกสารสำคัญของเขา Ajtai แสดงให้เห็นว่าปัญหา SVP เป็นปัญหา NP-hard และค้นพบความเชื่อมโยงบางอย่างระหว่างความซับซ้อนในกรณีที่เลวร้ายที่สุดและความซับซ้อนในกรณีเฉลี่ยของปัญหาแลตทิซบางปัญหา^{[ 2 ] [ 3 ]}โดยอาศัยผลลัพธ์เหล่านี้ Ajtai และDworkได้สร้างระบบการเข้ารหัสแบบกุญแจสาธารณะซึ่งสามารถพิสูจน์ความปลอดภัยได้โดยใช้เพียงความยากในกรณีที่เลวร้ายที่สุดของ SVP เวอร์ชันหนึ่ง^{[ 34 ]}จึงทำให้เป็นผลลัพธ์แรกที่ใช้ความยากในกรณีที่เลวร้ายที่สุดเพื่อสร้างระบบที่ปลอดภัย^{[ 35 ]}

• การเรียนรู้จากความผิดพลาด
• ปัญหาการหาคำตอบจำนวนเต็มสั้น

• Agrell, E.; Eriksson, T.; Vardy, A.; Zeger, K. (2002). "การค้นหาจุดที่ใกล้ที่สุดในแลตติส" (PDF) . IEEE Trans. Inf. Theory . 48 (8): 2201– 2214. doi : 10.1109/TIT.2002.800499 .
• Micciancio, Daniele (2001). "ปัญหาเวกเตอร์ที่สั้นที่สุดเป็นปัญหา {NP}-hard ที่สามารถประมาณค่าได้ภายในค่าคงที่บางค่า" . SIAM Journal on Computing . 30 (6): 2008– 2035. CiteSeerX  10.1.1.93.6646 . doi : 10.1137/S0097539700373039 . S2CID  42794945 .
• Nguyen, Phong Q.; Stern, Jacques (2000). "การลดแลตติสในวิทยาการเข้ารหัสลับ: การอัปเดต"รายงานการประชุมสัมมนาวิชาการนานาชาติครั้งที่ 4 ว่าด้วยทฤษฎีจำนวนเชิงอัลกอริทึม Springer-Verlag. หน้า  85–112 . ISBN 978-3-540-67695-9.