ฉันสงสัยว่าใครสามารถใช้อัลกอริทึม Grover กับกลไกการห่อหุ้มคีย์เพื่อถอดรหัสคีย์ที่ใช้ร่วมกัน
นี่คือวิธีการทำงานของอัลกอริทึมของ Grover (แบบง่าย): คุณใช้ฟังก์ชัน 'ฟิตเนส' (ซึ่งคาดเดาค่าที่คุณกำลังค้นหาและประเมินค่าเป็น '1' หากการคาดเดาถูกต้อง และ '0' หากไม่ใช่ - สำหรับ AES ฟังก์ชันฟิตเนสอาจเป็น 'ใช้การเดาเป็นคีย์ AES และเข้ารหัสบล็อกข้อความธรรมดาที่รู้จัก และตรวจสอบว่าผลลัพธ์เป็นบล็อกข้อความไซเฟอร์ที่รู้จักหรือไม่)
จากนั้น ให้คุณใช้ฟังก์ชันฟิตเนสนี้ (และการดำเนินการควอนตัมอื่นๆ) และวนซ้ำหลายๆ ครั้ง ถ้าคุณวนซ้ำในจำนวนครั้งที่ถูกต้อง เมื่อคุณวัดผลลัพธ์ มีความเป็นไปได้สูงที่ค่าฟิตเนส ฟังก์ชันประเมินเป็น 1
ทีนี้ ถ้าเราคิดจะโจมตีโฟรโด มีสองวิธีในการโจมตีมัน อาจพยายามกู้คืนความลับที่แชร์โดยตรงจากคีย์สาธารณะที่ใช้ร่วมกัน ในกรณีนี้ เรามีฟังก์ชันฟิตเนสให้ใช้คีย์สาธารณะร่วมกัน และคาดเดาความลับที่ใช้ร่วมกันได้ อย่างไรก็ตาม เราไม่มีวิธีที่มีประสิทธิภาพในการตรวจสอบว่าการคาดเดานั้นถูกต้องหรือไม่ (ขึ้นอยู่กับการแชร์คีย์สาธารณะ) ดังนั้นเราจึงไม่ทราบวิธีสร้างฟังก์ชันฟิตเนสนี้ (และดูเหมือนว่า Grover's จะไม่มีผล)
ในทางกลับกัน เราสามารถพยายามกู้คืนเมล็ดพันธุ์ลับที่ Frodo ใช้ในการรับรหัสสาธารณะ [1] (หรืออีกวิธีหนึ่งคือภายในกระบวนการห่อหุ้ม Frodo) สำหรับ Frodo-640 (NIST ระดับ 1) เมล็ดพันธุ์ลับนี้คือ 128 บิต; เนื่องจากสามารถกำหนดการแมประหว่างค่า 128 บิตนี้ (และข้อมูลสาธารณะ นั่นคือ เมล็ดสาธารณะ) และคีย์สาธารณะ เราจึงสามารถใช้ค่านั้นเพื่อสร้างฟังก์ชันฟิตเนสได้
ตอนนี้ การโจมตีนี้ไม่ได้มีอยู่ในการเข้ารหัสหลังควอนตัม มันไม่ทำงานโดยการโจมตีความลับที่ใช้ร่วมกัน 128 บิตโดยตรง แต่แทนที่จะใช้วิธีที่ชุดพารามิเตอร์นี้ของ Frodo สร้างการแบ่งปันคีย์โดยใช้ค่าสุ่ม 128 บิตเป็น 'secret seed' สิ่งที่โฟรโดทำคือใช้เมล็ดพันธุ์ลับ 128 บิตนั้นและขยายโดยใช้ SHAKE เพื่อสร้างการแบ่งปันและข้อผิดพลาดที่ยาวขึ้นมาก นักออกแบบของ Frodo อาจใช้เมล็ดลับที่ยาวกว่านั้น และขยายไปยัง SHAKE ซึ่งจะทำให้ Grover ยากขึ้นมาก (เพราะเมล็ดลับที่จะกู้คืนนั้นยาวกว่ามาก และการพยายามกู้คืนสถานะ SHAKE ภายในหรือลำดับของเอาต์พุต SHAKE จะ ใช้เวลานานเกินไป) นักออกแบบของ Frodo ไม่ได้ทำเช่นนี้ อาจเป็นเพราะมันไม่ได้ปรับปรุงความปลอดภัยอย่างแท้จริง
ในทางที่สาม เรามักทำบางอย่างกับคีย์ที่ใช้ร่วมกัน เราอาจป้อนข้อมูลนั้นลงใน KDF (อาจร่วมกับข้อมูลสาธารณะบางอย่าง เช่น nonces) แล้วใช้ผลลัพธ์นั้นเป็นคีย์ AES เราสามารถสร้างฟังก์ชันฟิตเนสจากสิ่งนั้นได้ ดังนั้น Grover's จึงนำไปใช้กับระบบนั้น - เป็นไปได้มากว่า โครงสร้าง KDF/AES นี้จะนำไปใช้ภายใน Quantum Computer ได้ง่ายกว่ากระบวนการ Frodo public key (หรือการห่อหุ้ม) ดังนั้นจึงเป็นไปได้ง่ายกว่าที่จะโจมตีระบบที่นั่น (หากเป็นเพียงปัจจัยคงที่)
ประการที่สี่ มีเหตุผลที่จะถามว่า Grover's เป็นภัยคุกคามต่อความลับ 128 บิตจริงหรือไม่ - การประเมินฟังก์ชันการออกกำลังกายทั้งหมดนี้ทำตามลำดับ และการประเมินฟังก์ชันใดๆ นั้นเป็นไปไม่ได้ $2^{64}$ ครั้งติดต่อกัน และในขณะที่คุณสามารถพยายามแก้ไขปัญหานี้ได้โดยเรียกใช้ Grover's บนคอมพิวเตอร์ควอนตัมจำนวนมากโดยการแบ่งพื้นที่ลับ เราจะสูญเสียข้อได้เปรียบของ Grover ไปส่วนหนึ่งหากเราทำเช่นนั้น และท้ายที่สุดเราก็ใช้ มาก ของควอนตัมคอมพิวเตอร์
[1]: โปรดทราบว่าโฟรโดมีสองเมล็ด หนึ่งสาธารณะซึ่งกำหนดโครงตาข่ายที่จะใช้ และอีกอันหนึ่งซึ่งเป็นความลับ และใช้ในการสร้างตัวอย่างและเมทริกซ์ข้อผิดพลาด เนื่องจากเมล็ดพันธุ์สาธารณะอยู่ในคีย์สาธารณะ ผู้โจมตีจึงไม่จำเป็นต้องเดา สิ่งที่เขาต้องทำคือการกู้คืนเมล็ดลับ