บทนำ
ในปี 1994 นักวิทยาศาสตร์คอมพิวเตอร์ Peter Shor ค้นพบ ว่าหากมีการประดิษฐ์คอมพิวเตอร์ควอนตัม พวกเขาจะทำลายโครงสร้างพื้นฐานส่วนใหญ่ที่ใช้เพื่อปกป้องข้อมูลที่แชร์ทางออนไลน์ ความเป็นไปได้อันน่าสะพรึงกลัวนั้นทำให้นักวิจัยต้องดิ้นรนเพื่อสร้างแผนการเข้ารหัส "หลังควอนตัม" ใหม่ เพื่อบันทึกข้อมูลให้มากที่สุดเท่าที่จะทำได้จากการตกไปอยู่ในมือของแฮ็กเกอร์ควอนตัม
เมื่อต้นปีนี้ สถาบันมาตรฐานและเทคโนโลยีแห่งชาติ เปิดเผย ผู้เข้ารอบสี่คนสุดท้ายในการค้นหามาตรฐานการเข้ารหัสหลังควอนตัม สามคนใช้ "lattice cryptography" ซึ่งเป็นรูปแบบที่ได้รับแรงบันดาลใจจาก lattices การจัดเรียงจุดในอวกาศเป็นประจำ
การเข้ารหัส Lattice และความเป็นไปได้หลังควอนตัมอื่น ๆ แตกต่างจากมาตรฐานปัจจุบันในรูปแบบที่สำคัญ แต่พวกเขาทั้งหมดอาศัยความไม่สมดุลทางคณิตศาสตร์ ความปลอดภัยของระบบการเข้ารหัสในปัจจุบันจำนวนมากขึ้นอยู่กับการคูณและแฟคตอริ่ง: คอมพิวเตอร์ทุกเครื่องสามารถคูณตัวเลขสองตัวได้อย่างรวดเร็ว แต่อาจต้องใช้เวลาหลายศตวรรษในการแยกตัวประกอบจำนวนมากที่มีการเข้ารหัสเป็นองค์ประกอบหลัก ความไม่สมดุลนั้นทำให้ความลับเข้ารหัสง่ายแต่ถอดรหัสยาก
สิ่งที่ Shor เปิดเผยในอัลกอริธึมปี 1994 ของเขาคือความแปลกประหลาดของแฟคตอริ่งทำให้เสี่ยงที่จะถูกโจมตีโดยคอมพิวเตอร์ควอนตัม “เป็นสิ่งที่พิเศษและพิเศษมากที่คอมพิวเตอร์ควอนตัมสามารถทำได้” . กล่าว แคทเธอรีน สเตนจ์นักคณิตศาสตร์จากมหาวิทยาลัยโคโลราโด โบลเดอร์ ดังนั้นหลังจาก Shor นักเข้ารหัสได้งานใหม่: ค้นหาชุดปฏิบัติการทางคณิตศาสตร์ชุดใหม่ที่ทำได้ง่ายแต่แทบจะเป็นไปไม่ได้เลยที่จะเลิกทำ
การเข้ารหัส Lattice เป็นหนึ่งในความพยายามที่ประสบความสำเร็จมากที่สุด พัฒนาขึ้นครั้งแรกในปี 1990 โดยอาศัยความยากของผลรวมของคะแนนวิศวกรรมย้อนกลับ
นี่เป็นวิธีหนึ่งในการอธิบายการเข้ารหัสแบบแลตทิซ: ลองนึกภาพเพื่อนของคุณมีโครงข่าย ซึ่งเป็นเพียงจุดเล็กๆ ในรูปแบบปกติและทำซ้ำทั่วทั้งระนาบ เพื่อนของคุณต้องการให้คุณบอก 10 คะแนนเหล่านี้ แต่เขากำลังยาก และเขาจะไม่วาดโครงตาข่ายทั้งหมด แต่เขาแสดงเพียงสองจุด — จุดแรกด้วย an x-value 101 และ a y-ค่า 19 ส่วนอีกอันมีพิกัด [235, 44]
โชคดีที่คุณสามารถหาจุดใหม่บนโครงตาข่ายได้ง่าย เพราะเมื่อคุณบวกและลบจุดสองจุดบนโครงตาข่าย คุณจะได้จุดที่สามในโครงตาข่ายเดียวกัน สิ่งที่คุณต้องทำคือบวกคะแนนที่เพื่อนมอบให้คุณ หรือคูณมันด้วยจำนวนเต็มแล้วบวกมันเข้าด้วยกัน หรือทั้งสองอย่างรวมกัน ทำแปดวิธีที่แตกต่างกัน แล้วคุณจะสามารถตอบคำถามของเพื่อนคุณได้
แต่เพื่อนคุณยังไม่พอใจ เขาให้จุดเริ่มต้นสองจุดเหมือนกัน แล้วถามคุณว่าจุด [2, 1] อยู่บนเส้นตารางเดียวกันหรือไม่ ในการตอบคำถามนี้ให้ถูกต้อง คุณต้องหาผลรวมของ [101, 19] และ [235, 44] ที่ทำให้เกิด [2, 1] ปัญหานี้ยากกว่าข้อแรกมาก และสุดท้ายคุณก็อาจจะจบลงด้วยการคาดเดาและตรวจสอบเพื่อให้ได้คำตอบ* ความไม่สมมาตรนั้นเป็นสิ่งที่รองรับการเข้ารหัสขัดแตะ
หากคุณต้องการใช้การเข้ารหัสแบบแลตทิซเพื่อแบ่งปันข้อมูล ให้ทำดังต่อไปนี้ ลองนึกภาพว่าเพื่อน (คนที่ดีกว่า) ต้องการส่งข้อความที่ปลอดภัยถึงคุณ คุณเริ่มต้นด้วยตารางสี่เหลี่ยมของตัวเลข สมมติว่ามีสองแถวและสองคอลัมน์ และมีลักษณะดังนี้:
ตอนนี้คุณสร้าง "คีย์" ส่วนตัวที่มีเพียงคุณเท่านั้นที่รู้ ในตัวอย่างนี้ สมมติว่าคีย์ส่วนตัวของคุณเป็นเพียงตัวเลขลับสองตัว: 3 และ −2 คุณคูณตัวเลขในคอลัมน์แรกด้วย 3 และตัวเลขในคอลัมน์ที่สองด้วย −2 เพิ่มผลลัพธ์ในแต่ละแถวเพื่อให้ได้คอลัมน์ที่สามที่มีสองรายการ
ติดคอลัมน์ใหม่บนจุดสิ้นสุดของกริดของคุณ ตารางสามคอลัมน์ใหม่นี้เป็นคีย์สาธารณะของคุณ แบ่งปันได้อย่างอิสระ!
(สถานการณ์ในโลกแห่งความเป็นจริงจะซับซ้อนขึ้นเล็กน้อย เพื่อป้องกันไม่ให้แฮกเกอร์ถอดรหัสคีย์ส่วนตัวของคุณ คุณต้องเพิ่มสัญญาณรบกวนแบบสุ่มลงในคอลัมน์สุดท้ายของคุณ แต่ที่นี่เราจะข้ามขั้นตอนนั้นไปเพื่อความเรียบง่าย )
ตอนนี้เพื่อนของคุณจะใช้กุญแจสาธารณะเพื่อส่งข้อความถึงคุณ เธอนึกถึงตัวเลขลับสองหมายเลขของเธอเอง: 2 และ 0 เธอคูณตัวเลขในแถวแรกด้วย 2 และตัวเลขในแถวที่สองด้วย 0 จากนั้นเธอก็บวกผลลัพธ์ในแต่ละคอลัมน์เพื่อให้ได้แถวที่สาม
ตอนนี้เธอแนบแถวใหม่ไว้ที่ด้านล่างสุดของตารางแล้วส่งกลับมาให้คุณ (อีกครั้ง ในระบบจริง เธอต้องเพิ่มเสียงรบกวนให้กับแถวของเธอ)
ตอนนี้คุณจะอ่านข้อความ ในการทำเช่นนี้ คุณตรวจสอบเพื่อดูว่าแถวสุดท้ายของเพื่อนของคุณถูกต้องหรือไม่ ใช้คีย์ส่วนตัวของคุณกับสองรายการแรกของแถวของเธอ ผลลัพธ์ควรตรงกับรายการสุดท้าย
เพื่อนของคุณยังสามารถเลือกที่จะส่งแถวที่มีหมายเลขผิดในคอลัมน์สุดท้ายให้คุณได้ เธอรู้ว่าตัวเลขนี้ไม่ตรงกับการคำนวณของคุณ
หากเพื่อนของคุณส่งแถวที่ตัวเลขสุดท้ายถูกต้อง คุณจะตีความว่าเป็น 0 หากเธอส่งแถวที่ตัวเลขไม่ถูกต้อง คุณจะตีความว่าเป็น 1 แถวนั้นจึงเข้ารหัสเป็นแถวเดียว บิต: 0 หรือ 1
โปรดทราบว่าผู้โจมตีภายนอกจะไม่สามารถเข้าถึงคีย์ส่วนตัวหรือของเพื่อนคุณได้ หากไม่มีสิ่งเหล่านี้ ผู้โจมตีจะไม่ทราบว่าหมายเลขสุดท้ายถูกต้องหรือไม่
ในทางปฏิบัติ คุณต้องการส่งข้อความที่ยาวกว่าหนึ่งบิต ดังนั้นผู้ที่ต้องการรับข้อความ 100 บิตจะสร้างคอลัมน์ใหม่ 100 คอลัมน์แทนที่จะเป็นเพียงคอลัมน์เดียว จากนั้นผู้ส่งข้อความจะสร้างแถวใหม่ขึ้นมาหนึ่งแถว โดยแก้ไข 100 รายการสุดท้ายเพื่อเข้ารหัส 0 หรือ 1 สำหรับแต่ละรายการ
หากมีการใช้การเข้ารหัสแบบ Lattice จริง ๆ จะมีความแตกต่างมากมายที่ไม่ครอบคลุมในสถานการณ์นี้ ตัวอย่างเช่น หากคุณต้องการให้ข้อความปลอดภัยจากการสอดรู้สอดเห็นจริง ๆ เมทริกซ์ต้องมีจำนวนข้อมูลที่คิดไม่ถึง ทำให้ทั้งมวลเทอะทะมากจนไม่คุ้มที่จะใช้ เพื่อหลีกเลี่ยงปัญหานี้ นักวิจัยใช้เมทริกซ์ที่มีสมมาตรที่เป็นประโยชน์ซึ่งสามารถลดจำนวนพารามิเตอร์ได้ นอกจากนั้น ยังมีชุดปรับแต่งทั้งหมดที่สามารถนำไปใช้กับปัญหาได้ วิธีการรวมข้อผิดพลาด และอื่นๆ อีกมากมาย
แน่นอน เป็นไปได้เสมอที่ใครบางคนจะพบข้อบกพร่องร้ายแรงในการเข้ารหัสแบบตาข่าย เหมือนกับที่ Shor ทำสำหรับแฟคตอริ่ง ไม่มีการรับประกันว่ารูปแบบการเข้ารหัสเฉพาะจะทำงานเมื่อเผชิญกับการโจมตีใดๆ การเข้ารหัสทำงานจนแตก อันที่จริงช่วงต้นฤดูร้อนนี้ แผนการเข้ารหัสหลังควอนตัมที่มีแนวโน้มหนึ่งถูกถอดรหัส ไม่ใช้คอมพิวเตอร์ควอนตัม แต่เป็นแล็ปท็อปธรรมดา สำหรับ Stange โครงการทั้งหมดทำให้เกิดความขัดแย้งที่ไม่สบายใจ: “สิ่งที่ฉันพบว่าน่าทึ่งมากเกี่ยวกับการเข้ารหัสคือการที่เราได้สร้างโครงสร้างพื้นฐานนี้สำหรับเผ่าพันธุ์มนุษย์ด้วยความเชื่อที่มั่นคงว่าความสามารถของเราในฐานะมนุษย์นั้นมีจำกัด” เธอกล่าว “มันล้าหลังมาก”
*: ถ้าคุณสงสัย คำตอบคือ 7 × [101, 19] – 3 × [235, 44] = [2, 1] [กลับไปที่บทความ]
