การเข้ารหัสแบบใช้แลตทิซเป็นคำทั่วไปสำหรับโครงสร้างของพรีมิทีฟการเข้ารหัสที่เกี่ยวข้องกับแลตทิซไม่ว่าจะเป็นในโครงสร้างเองหรือในการพิสูจน์ความปลอดภัย โครงสร้างแบบใช้แลตทิซสนับสนุนมาตรฐานที่สำคัญของการเข้ารหัสหลังควอนตัม [ ^{1 ] แตก} ต่างจากระบบกุญแจสาธารณะที่ใช้กันอย่างแพร่หลายและเป็นที่รู้จัก เช่นRSA , Diffie-Hellmanหรือ ระบบการเข้ารหัส เส้นโค้งวงรีซึ่งในทางทฤษฎีแล้วสามารถถูกโจมตีได้โดยใช้อัลกอริทึมของ Shorบนคอมพิวเตอร์ควอนตัมโครงสร้างแบบใช้แลตทิซบางอย่างดูเหมือนจะทนทานต่อการโจมตีจากทั้งคอมพิวเตอร์แบบคลาสสิกและควอนตัม ยิ่งไปกว่านั้น โครงสร้างแบบใช้แลตทิซจำนวนมากถือว่าปลอดภัยภายใต้สมมติฐาน ที่ว่า ปัญหาแลตทิซการคำนวณที่ได้รับการศึกษามาอย่างดีบางอย่างไม่สามารถแก้ไขได้อย่างมีประสิทธิภาพ

ในปี 2024 NISTได้ประกาศมาตรฐานลายเซ็นดิจิทัลแบบโมดูลแลตติซสำหรับการเข้ารหัสลับหลังควอนตัม^{[ 2 ]}

ในปี พ.ศ. 2539 Miklós Ajtaiได้นำเสนอโครงสร้างการเข้ารหัสแบบแลตติสเป็นครั้งแรก ซึ่งความปลอดภัยสามารถอิงตามความยากของปัญหาแลตติสที่ได้รับการศึกษามาเป็นอย่างดี^{[ 3 ]}และCynthia Dworkได้แสดงให้เห็นว่าปัญหาแลตติสกรณีเฉลี่ยบางอย่างที่เรียกว่าโซลูชันจำนวนเต็มสั้น (SIS) นั้นยากต่อการแก้ไขอย่างน้อยก็เท่ากับปัญหาแลตติสกรณีที่เลวร้ายที่สุด^{[ 4 ]}จากนั้นเธอก็ได้แสดงฟังก์ชันแฮชการเข้ารหัสที่มีความปลอดภัยเทียบเท่ากับความยากในการคำนวณของ SIS

ในปี พ.ศ. 2541 Jeffrey Hoffstein , Jill PipherและJoseph H. Silverman ได้นำเสนอแผนการ เข้ารหัสกุญแจสาธารณะแบบอิงแลตทิซซึ่งรู้จักกันในชื่อNTRU [ ^{5 ] อย่างไรก็ตาม}แผนการของพวกเขายังไม่เป็นที่ทราบแน่ชัดว่ายากอย่างน้อยเท่ากับการแก้ปัญหาแลตทิซกรณีที่เลวร้ายที่สุด

โครงการเข้ารหัสแบบกุญแจสาธารณะแบบใช้แลตทิซโครงการแรกที่ได้รับการพิสูจน์ความปลอดภัยภายใต้สมมติฐานความยากในกรณีที่เลวร้ายที่สุดนั้น ได้รับการแนะนำโดยOded Regevในปี 2548 ^{[ 6 ]}พร้อมกับ ปัญหา การเรียนรู้ที่มีข้อผิดพลาด (LWE) ตั้งแต่นั้นมา งานวิจัยที่ตามมาจำนวนมากได้มุ่งเน้นไปที่การปรับปรุงการพิสูจน์ความปลอดภัยของ Regev ^{[ 7 ] [ 8 ]}และการปรับปรุงประสิทธิภาพของโครงการดั้งเดิม^{[ 9 ] [ 10 ] [ 11 ] [ 12 ]}งานวิจัยจำนวนมากได้ทุ่มเทให้กับการสร้างพรีมิทีฟการเข้ารหัสเพิ่มเติมโดยอิงจาก LWE และปัญหาที่เกี่ยวข้อง ตัวอย่างเช่น ในปี 2552 Craig Gentryได้แนะนำ โครงการ เข้ารหัสแบบโฮโมมอร์ฟิกเต็มรูปแบบโครงการ แรก ซึ่งอิงจากปัญหาแลตทิซ^{[ 13 ]}

ในพีชคณิตเชิงเส้นแลตทิซ คือเซตของผลรวมเชิงเส้นจำนวนเต็มทั้งหมดของเวกเตอร์จากฐานของ กล่าว อีกนัยหนึ่ง คือ ตัวอย่างเช่นเป็นแลตทิซที่สร้างขึ้นจากฐานมาตรฐานสำหรับที่สำคัญคือ ฐานสำหรับแลตทิซนั้นไม่ซ้ำกัน ตัวอย่างเช่น เวกเตอร์, , และเป็นฐานทางเลือกสำหรับ ${\displaystyle L\subset \mathbb {R} ^{n}}$${\displaystyle \{\mathbf {b} _{1},\ldots ,\mathbf {b} _{n}\}}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle L={\Big \{}\sum a_{i}\mathbf {b} _{i}:a_{i}\in \mathbb {Z} {\Big \}}.}$${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle (3,1,4)}$${\displaystyle (1,5,9)}$${\displaystyle (2,-1,0)}$${\displaystyle \mathbb {Z} ^{3}}$

ปัญหาการคำนวณบนโครงข่ายแลตทิซที่สำคัญที่สุดคือปัญหาเวกเตอร์ที่สั้นที่สุด (SVP หรือบางครั้งเรียกว่า GapSVP) ซึ่งถามถึงความยาวแบบยุคลิดขั้นต่ำโดยประมาณของเวกเตอร์แลตทิซที่ไม่เป็นศูนย์ ปัญหานี้เชื่อกันว่ายากที่จะแก้ได้อย่างมีประสิทธิภาพ แม้จะใช้ปัจจัยการประมาณค่าที่เป็นพหุนามในและแม้กระทั่งใช้คอมพิวเตอร์ควอนตัมก็ตาม โครงสร้างการเข้ารหัสบนโครงข่ายแลตทิซจำนวนมาก (แต่ไม่ใช่ทั้งหมด) เป็นที่ทราบกันดีว่าปลอดภัยหาก SVP ยากจริง ๆ ในขอบเขตนี้ ${\displaystyle n}$

ส่วนนี้จะนำเสนอรูปแบบโครงสร้างแบบแลตติสที่คัดเลือกมา โดยจัดกลุ่มตามรูปแบบพื้นฐาน

รูปแบบการเข้ารหัสที่เลือกไว้:

• รูปแบบการเข้ารหัส GGHซึ่งอิงตามปัญหาเวกเตอร์ที่ใกล้ที่สุด (CVP) ในปี พ.ศ. 2542 Nguyen ได้เผยแพร่ข้อบกพร่องที่สำคัญในการออกแบบรูปแบบดังกล่าว^{[ 14 ]}
• NTRUEncrypt .

รูปแบบ การเข้ารหัสแบบโฮโมมอร์ฟิกที่เลือกใช้:

• แผนเดิมของเจนทรี^{[ 13 ]}
• เบรกเกอร์สกี้ และไวกุนตนาธาน. ^{[ 15 ] [ 16 ]}

รูปแบบการเข้ารหัสลับแบบแลตติสที่เลือกใช้สำหรับการแฮช:

• สวิฟท์
• ฟังก์ชันแฮชแบบอิงตามแลตทิซ (LASH) ^{[ 17 ] [ 18 ]}

รูปแบบที่เลือกใช้สำหรับการแลกเปลี่ยนกุญแจ หรือเรียกอีกอย่างว่า การสร้างกุญแจ การห่อหุ้มกุญแจ และกลไกการห่อหุ้มกุญแจ (KEM):

• CRYSTALS-Kyber [ ^{19 ] ซึ่ง}สร้างขึ้นบนโมดูลการเรียนรู้ที่มีข้อผิดพลาด (module-LWE) Kyber ได้รับเลือกให้เป็นมาตรฐานโดย NIST ในปี 2023 ^{[ 1 ]}ในเดือนสิงหาคม 2023 NIST ได้เผยแพร่ FIPS 203 (Initial Public Draft) และเริ่มอ้างอิงถึงเวอร์ชัน Kyber ของพวกเขาในชื่อ Module-Lattice-based Key Encapsulation Mechanism (ML-KEM) ^{[ 20 ]}
• FrodoKEM ^{[ 21 ] [ 22 ]}เป็นแผนการที่ใช้การเรียนรู้จากข้อผิดพลาด (LWE) FrodoKEM เข้าร่วมการเรียกมาตรฐานที่ดำเนินการโดยสถาบันมาตรฐานและเทคโนโลยีแห่งชาติ (NIST) [ ^{1 ] และผ่านเข้ารอบที่ 3}ของกระบวนการ จากนั้นก็ถูกยกเลิกเนื่องจากประสิทธิภาพต่ำ ในเดือนตุลาคม พ.ศ. 2565 บัญชี Twitter ที่เกี่ยวข้องกับนักเข้ารหัสลับDaniel J. Bernsteinได้โพสต์ปัญหาด้านความปลอดภัยใน frodokem640 ^{[ 23 ]}
• NewHopeอิงตามปัญหาการเรียนรู้แบบวงแหวนที่มีข้อผิดพลาด (RLWE) ^{[ 24 ]}
• NTRU Prime. ^{[ 25 ]}
• งานของ Peikertซึ่งอิงตามปัญหาการเรียนรู้แบบวงแหวนที่มีข้อผิดพลาด (RLWE) ^{[ 10 ]}
• Saber ^{[ 26 ]}ซึ่งอิงตามปัญหาการเรียนรู้โมดูลที่มีการปัดเศษ (โมดูล-LWR)

ส่วนนี้แสดงรายการตัวเลือกของรูปแบบโครงสร้างแบบแลตติสสำหรับการลงลายมือชื่อดิจิทัล

• CRYSTALS-Dilithium ^{[ 27 ] [ 28 ]}ซึ่งสร้างขึ้นบนโมดูลการเรียนรู้ที่มีข้อผิดพลาด (module-LWE) และโมดูลการแก้ปัญหาจำนวนเต็มสั้น (module-SIS) Dilithium ได้รับเลือกให้เป็นมาตรฐานโดย NIST ^{[ 1 ]}ตามข้อความจาก Ray Perlner ซึ่งเขียนในนามของทีม NIST PQC มาตรฐานการลงนามโมดูล LWE ของ NIST จะขึ้นอยู่กับข้อกำหนด Dilithium เวอร์ชัน 3.1

• Falconซึ่งสร้างขึ้นบนโซลูชันจำนวนเต็มสั้น (SIS) บน NTRU Falcon ได้รับเลือกให้เป็นมาตรฐานโดย NIST ^{[ 29 ] [ 1 ]}
• รูปแบบลายเซ็น GGH
• งานของ Güneysu, Lyubashevsky และ Pöppelmann ซึ่งอิงตามการเรียนรู้แบบวงแหวนที่มีข้อผิดพลาด (RLWE) ^{[ 30 ]}
• MITAKA เวอร์ชันหนึ่งของเหยี่ยว^{[ 31 ]}
• NTRUSign​
• qTESLA ซึ่งอิงตามการเรียนรู้แบบวงแหวนที่มีข้อผิดพลาด (RLWE) โครงร่าง qTESLA เข้าร่วมการเรียกมาตรฐานที่ดำเนินการโดยสถาบันมาตรฐานและเทคโนโลยีแห่งชาติ (NIST ) ^{[ 32 ] [ 1 ]}

CRYSTALS-Dilithium หรือเรียกง่ายๆ ว่า Dilithium ^{[ 27 ] [ 28 ]}สร้างขึ้นบนโมดูล LWE และโมดูล SIS Dilithium ได้รับเลือกโดย NIST ให้เป็นพื้นฐานสำหรับมาตรฐานลายเซ็นดิจิทัล^{[ 1 ]}ตามข้อความจาก Ray Perlner ซึ่งเขียนในนามของทีม NIST PQC มาตรฐานการลงนามโมดูล LWE ของ NIST จะอิงตามข้อกำหนด Dilithium เวอร์ชัน 3.1 การเปลี่ยนแปลงของ NIST ใน Dilithium 3.1 มีจุดประสงค์เพื่อรองรับความสุ่มเพิ่มเติมในการลงนาม (การลงนามแบบเฮดจ์) และการปรับปรุงอื่นๆ^{[ 33 ]}

ไดลิเทียมเป็นหนึ่งในสองรูปแบบลายเซ็นดิจิทัลที่ NIST เลือกใช้ในขั้นตอนการเข้ารหัสลับหลังควอนตัม โดยอีกรูปแบบหนึ่งคือSPHINCS+ซึ่งไม่ได้ใช้โครงสร้างแลตติส แต่ใช้ฟังก์ชันแฮชแทน

ในเดือนสิงหาคม พ.ศ. 2566 NIST ได้เผยแพร่ FIPS 204 (Initial Public Draft) และเริ่มเรียกไดลิเธียมว่า "อัลกอริทึมลายเซ็นดิจิทัลแบบโมดูลแลตติซ" (ML-DSA) ^{[ 34 ]}

ตามรายงานของ Falko Strenzke ณ เดือนตุลาคม 2023 ML-DSA กำลังถูกนำไปใช้เป็นส่วนหนึ่งของLibgcrypt ^{[ 35 ]}

ในเดือนสิงหาคม พ.ศ. 2567 NISTได้กำหนดมาตรฐาน CRYSTALS-Dilithium อย่างเป็นทางการภายใต้ชื่อ ML-DSA โดยกำหนดให้เป็นมาตรฐานหลัก (FIPS 204 ^{[ 36 ]} ) สำหรับลายเซ็นดิจิทัลที่ทนต่อควอนตัม^{[ 37 ]}

โครงสร้างการเข้ารหัสแบบแลตทิซมีแนวโน้มที่ดีสำหรับ การเข้ารหัสแบบ กุญแจสาธารณะหลังควอนตัม [ ^{38 ] อัน}ที่จริง รูปแบบทางเลือกหลักของการเข้ารหัสแบบกุญแจสาธารณะคือแผนการที่อิงตามความยากของการแยกตัวประกอบและปัญหาที่เกี่ยวข้องและแผนการที่อิงตามความยากของลอการิทึมแบบไม่ต่อเนื่องและปัญหาที่เกี่ยวข้องอย่างไรก็ตาม ทั้งปัญหาการแยกตัวประกอบและปัญหาลอการิทึมแบบไม่ต่อเนื่องเป็นที่ทราบกันดีว่าสามารถแก้ไขได้ในเวลาพหุนามบนคอมพิวเตอร์ควอนตัม [ ^{39 ] ยิ่ง}ไปกว่านั้น อัลกอริทึมสำหรับการแยกตัวประกอบมักจะให้ผลลัพธ์เป็นอัลกอริทึมสำหรับลอการิทึมแบบไม่ต่อเนื่อง และในทางกลับกัน สิ่งนี้กระตุ้นให้เกิดการศึกษาโครงสร้างที่อิงตามสมมติฐานทางเลือก เช่น ความยากของปัญหาแลตทิซ

เป็นที่ทราบกันดีว่าแผนการเข้ารหัสแบบแลตทิซจำนวนมากมีความปลอดภัยโดยถือว่าปัญหาแลตทิซบางอย่างมีความยากในกรณีที่เลวร้ายที่สุด^{[ 3 ] [ 6 ] [ 7 ]}กล่าวคือ หากมีอัลกอริทึมที่สามารถทำลายแผนการเข้ารหัสได้อย่างมีประสิทธิภาพด้วยความน่าจะเป็นที่ไม่น้อย ก็จะมีอัลกอริทึมที่มีประสิทธิภาพที่สามารถแก้ปัญหาแลตทิซบางอย่างบนอินพุตใดๆ ก็ได้ อย่างไรก็ตาม สำหรับโครงสร้างแบบแลตทิซที่ใช้งานได้จริง (เช่น แผนการที่ใช้ NTRU และแม้แต่แผนการที่ใช้ LWE ที่มีพารามิเตอร์ที่มีประสิทธิภาพ) ยังไม่มีการรับประกันความปลอดภัยตามการลดทอนที่มีความหมาย

การประเมินระดับความปลอดภัยที่ได้รับจากข้อโต้แย้งการลดจากปัญหาที่ยาก—โดยอิงจากขนาดพารามิเตอร์ที่แนะนำ การประมาณมาตรฐานของความซับซ้อนในการคำนวณของปัญหาที่ยาก และการตรวจสอบขั้นตอนโดยละเอียดในการลด—เรียกว่าความปลอดภัยที่เป็นรูปธรรมและบางครั้ง เรียกว่าความปลอดภัยที่พิสูจน์ ได้ซึ่งมุ่งเน้นการปฏิบัติ^{[ 40 ]}ผู้เขียนบางคนที่ได้ตรวจสอบความปลอดภัยที่เป็นรูปธรรมสำหรับระบบการเข้ารหัสแบบแลตทิซพบว่าผลลัพธ์ความปลอดภัยที่พิสูจน์ได้สำหรับระบบดังกล่าวไม่ได้ให้ความปลอดภัยที่เป็นรูปธรรมที่มีความหมายสำหรับค่าพารามิเตอร์ในทางปฏิบัติ^{[ 41 ]}

^{สำหรับฟังก์ชันการเข้ารหัสพื้นฐานจำนวนมาก โครงสร้างที่รู้จักเพียงอย่างเดียว นั้น}ขึ้นอยู่กับแลตทิซหรือวัตถุที่เกี่ยวข้องอย่างใกล้ชิด ฟังก์ชันพื้นฐานเหล่านี้รวมถึงการเข้ารหัสโฮโมมอร์ฟิกอย่างสมบูรณ์ [ ^{13 ]}การปกปิดที่ไม่สามารถแยกแยะได้ [ ^{42 ] แผนที่}เชิงเส้นหลายตัวของการเข้ารหัสและการเข้ารหัสเชิงฟังก์ชัน^{[ 42 ]}

• ปัญหาโครงตาข่าย
• การเรียนรู้จากความผิดพลาด
• การเข้ารหัสแบบโฮโมมอร์ฟิก
• การเข้ารหัสลับหลังควอนตัม
• การเรียนรู้แบบวงแหวนพร้อมข้อผิดพลาด
• การเรียนรู้แบบวงแหวนพร้อมการแลกเปลี่ยนคีย์ข้อผิดพลาด

• Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai (1997). "ระบบเข้ารหัสแบบกุญแจสาธารณะจากปัญหาการลดแลตติส" Crypto '97: รายงานการประชุมวิชาการนานาชาติด้านการเข้ารหัสลับประจำปีครั้งที่ 17 ว่าด้วยความก้าวหน้าในการเข้ารหัสลับลอนดอนสหราชอาณาจักร: Springer-Verlag หน้า  112–131 doi : 10.1007 /BFb0052231 ISBN 978-3-540-63384-6.
• Regev, Oded (2006). "การเข้ารหัสแบบใช้โครงสร้างแลตติส" ความก้าวหน้าทางด้านวิทยาการเข้ารหัส (CRYPTO) Springer-Verlag. หน้า  131–141 . doi : 10.1007/11818175_8 . ISBN 978-3-540-37432-9.

• การสาธิตการใช้งาน Dilithium ใน Excel - ตัวอย่างการใช้งานและการสาธิตใน Excel (โดยไม่ใช้มาโคร) โดย Tim Wambach