CRYSTALS-Kyber: KEM ที่ใช้แลตทิซ

CRYSTALS-Kyber ซึ่ง NIST เปลี่ยนชื่อเป็น ML-KEM ใน FIPS 203 เป็นกลไกการห่อหุ้มกุญแจ (KEM) ที่อิง Module-LWE โดยใช้แทน RSA และ ECDH สำหรับการแลกเปลี่ยนกุญแจ และให้ความต้านทานต่อควอนตัมด้วยประสิทธิภาพที่ใช้งานได้จริง

KEM จะห่อหุ้มความลับร่วม โดยผู้ส่งสร้างกุญแจ K แบบสุ่ม แล้วเข้ารหัสด้วยกุญแจสาธารณะของผู้รับ (ห่อหุ้ม) ทำให้ได้ข้อความเข้ารหัส C ผู้รับจะคลายการห่อหุ้ม C ด้วยกุญแจส่วนตัวเพื่อกู้คืน K โดยไม่จำเป็นต้องแลกเปลี่ยนกุญแจแบบโต้ตอบ

Kyber ใช้ Module-LWE เหนือริง R_q = Z_q[x]/(x^256+1) โดยมี q=3329 มิติ k=2 (Kyber-512), k=3 (Kyber-768), k=4 (Kyber-1024) ระดับความปลอดภัยอยู่ที่ประมาณ 128, 192 และ 256 บิตตามลำดับ โดยแนะนำให้ใช้ k=3 (Kyber-768) เป็นค่าเริ่มต้น

สร้างเมทริกซ์ A ∈ R_q^{k×k} จากค่าเริ่มต้น ρ (ซึ่งสามารถขยายได้) สุ่มค่าลับ s และสัญญาณรบกวน e จากการแจกแจงทวินามที่มีศูนย์กลาง (สัมประสิทธิ์มีค่าขนาดเล็ก) กุญแจสาธารณะ: (ρ, t=As+e) กุญแจส่วนตัว: s สัญญาณรบกวน e มีขนาดเล็ก แต่ช่วยป้องกันไม่ให้กู้คืน s จากกุญแจสาธารณะได้

หากต้องการส่งความลับร่วมให้ผู้ถือกุญแจสาธารณะ (ρ, t) ให้สุ่ม r, e1, e2 จากการแจกแจงสัญญาณรบกวน คำนวณ u = A^T r + e1, v = t^T r + e2 + round(q/2)*m โดย m เป็นข้อความสุ่มขนาด 256 บิต ความลับร่วม K = KDF(m) ข้อความเข้ารหัส = (u, v)

เมื่อมีกุญแจส่วนตัว s ให้คำนวณ m' = decompress(v - s^T u) = decompress(t^T r + e2 + round(q/2)*m - s^T(A^T r + e1)) พจน์สัญญาณรบกวนจะหักล้างกันโดยประมาณ ทำให้เหลือ m'≈m จากนั้นคำนวณ K = KDF(m') ความน่าจะเป็นที่การคลายการห่อหุ้มจะล้มเหลวคือ < 2^{-139}

Kyber-768: กุญแจสาธารณะ 1184 ไบต์, กุญแจส่วนตัว 2400 ไบต์, ข้อความเข้ารหัส 1088 ไบต์, ความลับร่วม 32 ไบต์ เมื่อเปรียบเทียบกับ ECDH-P256 ซึ่งมีกุญแจสาธารณะ 65 ไบต์และข้อความเข้ารหัส 32 ไบต์ Kyber มีขนาดใหญ่กว่าประมาณ 15 เท่า แต่ปลอดภัยต่อควอนตัม และยังทำงานได้รวดเร็ว โดยการห่อหุ้มและคลายการห่อหุ้มใช้เวลาน้อยกว่า 1 มิลลิวินาทีบนหน่วยประมวลผลสมัยใหม่

การคูณพหุนามใน R_q = Z_q[x]/(x^256+1) ใช้การแปลงเชิงทฤษฎีจำนวน (NTT) ซึ่งเป็นรูปแบบเลขคณิตมอดูลาร์ที่เทียบเท่ากับ FFT NTT ลดความซับซ้อนของการคูณพหุนามจาก O(n^2) เป็น O(n log n) โดยเลือก q=3329 เพื่อให้มีคุณสมบัติของ NTT ที่ดีสำหรับ n=256

ระหว่างการย้ายไปใช้ PQC ให้ใช้การแลกเปลี่ยนกุญแจแบบผสม โดยรวม ECDH และ Kyber เข้าด้วยกัน ความลับร่วม = KDF(ECDH_output || Kyber_output) ความปลอดภัยต้องอาศัยการทำลายทั้งสองส่วน ฝ่ายตรงข้ามแบบดั้งเดิมไม่สามารถทำลายได้ทั้งคู่ ส่วนฝ่ายตรงข้ามแบบควอนตัมทำลาย ECDH ได้แต่ทำลาย Kyber ไม่ได้ ร่างมาตรฐาน TLS 1.3 (IETF RFC 8446) รองรับ KEM แบบผสม

การคลายการห่อหุ้มของ Kyber ไม่ได้ใช้เวลาคงที่ในการนำไปใช้งานแบบพื้นฐาน เนื่องจากขั้นตอนการสุ่มตัวอย่างแบบปฏิเสธทำให้เวลาการทำงานรั่วไหล การนำไปใช้งานอ้างอิงใช้ NTT ที่ใช้เวลาคงที่และการเปรียบเทียบข้อความเข้ารหัสแบบบีบอัดที่ใช้เวลาคงที่ โปรดใช้โค้ดอ้างอิงจากเอกสารส่งของ NIST หรือการนำไปใช้งานในไลบรารีที่ผ่านการตรวจสอบแล้ว

NIST เผยแพร่ FIPS 203 (ML-KEM) ในเดือนสิงหาคม 2024 Chrome เพิ่มการรองรับ Kyber ใน TLS 1.3 เมื่อปี 2023 Cloudflare, Google และ AWS กำลังนำ ECDH+Kyber แบบผสมไปใช้งาน OpenSSL 3.x เพิ่มการรองรับ ML-KEM แล้ว ส่วนการนำไปใช้งานใน LibSSH และ WireGuard อยู่ระหว่างดำเนินการ

เอกสารมาตรฐานใดของ NIST ที่กำหนดมาตรฐาน CRYSTALS-Kyber

Kyber (ML-KEM) คือ KEM ที่อิง Module-LWE และใช้แทน ECDH ขนาดกุญแจประมาณ 1 KB ใช้เลขคณิต NTT ที่รวดเร็ว และต้านทานควอนตัม ควรนำไปใช้งานแบบผสมกับ ECDH ในระหว่างการย้ายระบบ โดยได้รับการกำหนดมาตรฐานเป็น FIPS 203 บทถัดไป: รูปแบบลายเซ็น CRYSTALS-Dilithium และ Falcon