อัลกอริธึมการเข้ารหัสอันโด่งดังได้รับการอัปเกรด | นิตยสารควอนต้า

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

เครื่องมือสำคัญอย่างหนึ่งในงานนี้คืออัลกอริทึม LLL ซึ่งตั้งชื่อตามนักวิจัยที่ เผยแพร่แล้ว ในปี 1982 — Arjen Lenstra, Hendrik Lenstra Jr. และ László Lovász LLL พร้อมด้วยผู้สืบทอดจำนวนมาก สามารถทำลายรูปแบบการเข้ารหัสได้ในบางกรณี การศึกษาพฤติกรรมของพวกเขาช่วยให้นักวิจัยออกแบบระบบที่เสี่ยงต่อการถูกโจมตีน้อยกว่า และความสามารถของอัลกอริธึมมีมากกว่าการเข้ารหัส นอกจากนี้ยังเป็นเครื่องมือที่มีประโยชน์ในแวดวงคณิตศาสตร์ขั้นสูง เช่น ทฤษฎีจำนวนเชิงคำนวณ

ในช่วงหลายปีที่ผ่านมา นักวิจัยได้พัฒนารูปแบบต่างๆ ของ LLL เพื่อให้แนวทางนี้ใช้งานได้จริงมากขึ้น แต่ก็เพียงแต่ตรงประเด็นเท่านั้น ตอนนี้นักเข้ารหัสลับคู่หนึ่งได้สร้างอัลกอริธึมสไตล์ LLL ใหม่พร้อมการเพิ่มประสิทธิภาพอย่างมาก เทคนิคใหม่ซึ่งได้รับรางวัล รางวัลกระดาษดีเด่น ที่ การประชุมวิทยาการเข้ารหัสลับนานาชาติประจำปี 2023ขยายขอบเขตของสถานการณ์ที่นักวิทยาศาสตร์คอมพิวเตอร์และนักคณิตศาสตร์สามารถใช้แนวทางที่คล้ายกับ LLL ได้อย่างเป็นไปได้

“มันน่าตื่นเต้นจริงๆ” กล่าว คริส ไพเคิร์ตนักเขียนวิทยาการเข้ารหัสลับจากมหาวิทยาลัยมิชิแกนซึ่งไม่ได้เกี่ยวข้องกับรายงานฉบับนี้ เครื่องมือนี้เป็นจุดสนใจของการศึกษามานานหลายทศวรรษ เขากล่าว “เป็นเรื่องดีเสมอเมื่อเป้าหมายที่ทำมายาวนาน … แสดงให้เห็นว่ายังมีเรื่องประหลาดใจให้พบ”

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

ขัดแตะสามารถอธิบายได้โดยใช้ "พื้นฐาน" นี่คือชุดของเวกเตอร์ (โดยพื้นฐานแล้วคือรายการตัวเลข) ที่คุณสามารถรวมเข้าด้วยกันได้หลายวิธีเพื่อให้ได้ทุกจุดในโครงตาข่าย ลองจินตนาการถึงโครงตาข่ายที่มีพื้นฐานประกอบด้วยเวกเตอร์สองตัว: [3, 2] และ [1, 4] ตาข่ายเป็นเพียงจุดทั้งหมดที่คุณสามารถเข้าถึงได้โดยการเพิ่มและลบสำเนาของเวกเตอร์เหล่านั้น

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

นี่คืองานสำหรับ LLL: ให้พื้นฐานของโครงตาข่ายหลายมิติแก่มัน (หรือพี่น้องของมัน) แล้วมันจะคายงานที่ดีกว่าออกมา กระบวนการนี้เรียกว่าการลดพื้นฐานขัดแตะ

ทั้งหมดนี้เกี่ยวข้องกับการเข้ารหัสอย่างไร? ปรากฎว่าในบางกรณีงานทำลายระบบการเข้ารหัสสามารถนำมาสร้างใหม่เป็นอีกปัญหาหนึ่งได้ นั่นก็คือการค้นหาเวกเตอร์ที่ค่อนข้างสั้นในโครงตาข่าย และบางครั้ง เวกเตอร์นั้นสามารถถูกดึงออกจากฐานรีดิวซ์ที่สร้างโดยอัลกอริธึมสไตล์ LLL กลยุทธ์นี้ได้ช่วยให้นักวิจัยโค่นล้มระบบที่เมื่อดูผิวเผินแล้ว ดูเหมือนจะไม่เกี่ยวอะไรกับโครงตาข่ายเลย

ตามทฤษฎีแล้ว อัลกอริธึม LLL ดั้งเดิมจะทำงานอย่างรวดเร็ว: เวลาที่ใช้ในการรันไม่ได้ปรับขนาดแบบเอกโปเนนเชียลตามขนาดของอินพุต นั่นคือขนาดของโครงตาข่ายและขนาด (เป็นบิต) ของตัวเลขใน เวกเตอร์พื้นฐาน แต่มันจะเพิ่มขึ้นตามฟังก์ชันพหุนาม และ “ถ้าคุณต้องการทำจริง เวลาพหุนามไม่ได้เป็นไปได้เสมอไป” กล่าว ลีโอ ดูคัสซึ่งเป็นผู้เข้ารหัสลับที่สถาบันวิจัยแห่งชาติ CWI ในประเทศเนเธอร์แลนด์

ในทางปฏิบัติ หมายความว่าอัลกอริทึม LLL ดั้งเดิมไม่สามารถจัดการอินพุตที่มีขนาดใหญ่เกินไปได้ “นักคณิตศาสตร์และนักวิทยาการเข้ารหัสลับต้องการความสามารถในการทำอะไรมากกว่านี้” กล่าว คีแกน ไรอันนักศึกษาปริญญาเอกจากมหาวิทยาลัยแคลิฟอร์เนีย ซานดิเอโก นักวิจัยทำงานเพื่อเพิ่มประสิทธิภาพอัลกอริธึมแบบ LLL เพื่อรองรับอินพุตที่ใหญ่กว่า ซึ่งมักจะได้รับประสิทธิภาพที่ดี ถึงกระนั้น งานบางอย่างก็ยังคงอยู่อย่างดื้อรั้นจนเกินเอื้อม

บทความฉบับใหม่ซึ่งเขียนโดย Ryan และที่ปรึกษาของเขา นาเดีย เฮ็นนิงเกอร์รวมกลยุทธ์หลายอย่างเพื่อปรับปรุงประสิทธิภาพของอัลกอริทึมแบบ LLL ประการหนึ่ง เทคนิคนี้ใช้โครงสร้างแบบเรียกซ้ำที่แบ่งงานออกเป็นส่วนย่อยๆ อีกประการหนึ่ง อัลกอริธึมจะจัดการความแม่นยำของตัวเลขที่เกี่ยวข้องอย่างรอบคอบ โดยค้นหาสมดุลระหว่างความเร็วและผลลัพธ์ที่ถูกต้อง งานใหม่นี้ทำให้นักวิจัยสามารถลดฐานของโครงตาข่ายที่มีขนาดหลายพันมิติได้

งานที่ผ่านมาได้ปฏิบัติตามแนวทางที่คล้ายกัน: A กระดาษ 2021 ยังรวมการจัดการการเรียกซ้ำและความแม่นยำเข้าด้วยกันเพื่อให้ทำงานอย่างรวดเร็วกับโครงตาข่ายขนาดใหญ่ แต่จะใช้ได้กับโครงตาข่ายบางประเภทเท่านั้น ไม่ใช่ทั้งหมดที่มีความสำคัญในการเข้ารหัส อัลกอริธึมใหม่ทำงานได้ดีในช่วงที่กว้างกว่ามาก “ฉันดีใจมากที่มีคนทำมัน” กล่าว โธมัส เอสปิเตานักวิจัยด้านวิทยาการเข้ารหัสลับของบริษัท PQShield และเป็นผู้เขียนเวอร์ชันปี 2021 งานของทีมของเขานำเสนอ "การพิสูจน์แนวคิด" เขากล่าว; ผลลัพธ์ใหม่แสดงให้เห็นว่า “คุณสามารถลดขนาดโครงตาข่ายได้อย่างรวดเร็วด้วยวิธีที่ถูกต้อง”

เทคนิคใหม่ได้เริ่มพิสูจน์ว่ามีประโยชน์แล้ว ออเรล เพจนักคณิตศาสตร์จากสถาบันวิจัยแห่งชาติฝรั่งเศส Inria กล่าวว่าเขาและทีมงานได้นำอัลกอริธึมมาปรับใช้ในการทำงานกับงานทฤษฎีจำนวนเชิงคำนวณบางงาน

อัลกอริธึมแบบ LLL ยังสามารถมีบทบาทในการวิจัยที่เกี่ยวข้องกับระบบการเข้ารหัสแบบ Lattice ที่ออกแบบมาเพื่อ อยู่อย่างปลอดภัย แม้กระทั่งในอนาคตด้วยคอมพิวเตอร์ควอนตัมอันทรงพลัง พวกมันไม่ก่อให้เกิดภัยคุกคามต่อระบบดังกล่าว เนื่องจากการถอดพวกมันออกจำเป็นต้องค้นหาเวกเตอร์ที่สั้นกว่าที่อัลกอริธึมเหล่านี้สามารถทำได้ แต่นักวิจัยด้านการโจมตีที่ดีที่สุดรู้ดีว่าใช้อัลกอริธึมแบบ LLL เป็น "องค์ประกอบพื้นฐาน" กล่าว เวสเซล ฟาน โวเออร์เดน, นักเข้ารหัสที่มหาวิทยาลัยบอร์โดซ์ ในการทดลองเชิงปฏิบัติเพื่อศึกษาการโจมตีเหล่านี้ โครงสร้างนั้นสามารถทำให้ทุกอย่างช้าลงได้ การใช้เครื่องมือใหม่นี้ นักวิจัยอาจสามารถขยายขอบเขตการทดลองที่สามารถทำได้บนอัลกอริธึมการโจมตี โดยให้ภาพที่ชัดเจนยิ่งขึ้นเกี่ยวกับวิธีการทำงานของพวกเขา

ควอนตั้ม กำลังดำเนินการสำรวจชุดต่างๆ เพื่อให้บริการผู้ชมของเราได้ดียิ่งขึ้น เอาของเรา แบบสำรวจผู้อ่านวิทยาการคอมพิวเตอร์ และคุณจะถูกป้อนเพื่อรับรางวัลฟรี ควอนตั้ม สินค้า.