มีอัลกอริทึมควอนตัมเพื่อค้นหาการชนกันของ SHA256 หรือไม่

ในปี 2009 ดีเจ. เบิร์นสไตน์ได้เขียนบทความเกี่ยวกับหัวข้อนี้ในยุคแรกๆ มีให้ที่นี่:

นามธรรมระบุว่า:

ข้อเสนอปัจจุบันสำหรับฮาร์ดแวร์การแยกตัวประกอบเพื่อวัตถุประสงค์พิเศษ จะล้าสมัยหากมีการสร้างคอมพิวเตอร์ควอนตัมขนาดใหญ่: ตะแกรงช่องตัวเลขจะปรับขนาดได้แย่กว่าอัลกอริทึมควอนตัมของShorâ สำหรับ การแยกตัวประกอบ จะกลายเป็นฮาร์ดแวร์เข้ารหัสสำหรับวัตถุประสงค์พิเศษทั้งหมด ล้าสมัยในโลกหลังควอนตัม? อัลกอริทึมควอนตัมโดย Brassard, Høyer และ Tapp มีอยู่บ่อยครั้ง อ้างว่าลดต้นทุนของ $ข$บิตแฮชชนจาก $2^{b/2}$ ถึง $2^{b/3}.$ บทความนี้วิเคราะห์อัลกอริทึมของ BrassardâHøyerâTapp และแสดงให้เห็นว่า มันมีอัตราส่วนราคาต่อประสิทธิภาพที่แย่กว่าคลาสสิก van OorschotâWiener hash-collision circuits แม้จะอยู่ภายใต้สมมติฐานในแง่ดีเกี่ยวกับความเร็วของคอมพิวเตอร์ควอนตัม

เมื่อเร็ว ๆ นี้ Hosoyamada และ Sasaki รายงานความคืบหน้าบางส่วนใน CRYPTO 2021 เกี่ยวกับ SHA-256 และ SHA-512 รุ่นลดรอบ ดู ที่นี่; อาจมีเวอร์ชันสาธารณะที่เข้าถึงได้ในเซิร์ฟเวอร์ preprint ของ iacr.org แก้ไข: มีสไลด์และการพูดคุย ที่นี่

นามธรรมระบุว่า:

ในบทความนี้ เราศึกษาเฉพาะการโจมตีแบบควอนตัมชนบน SHA-256 และ SHA-512 เป็นครั้งแรก การโจมตีถึง 38 และ 39 ขั้นตามลำดับ ซึ่งปรับปรุงการโจมตีแบบดั้งเดิมเป็น 31 และ 27 ขั้นอย่างมีนัยสำคัญ การโจมตีทั้งสองใช้เฟรมเวิร์กของงานก่อนหน้านี้ที่แปลงการชนกันแบบกึ่งอิสระจำนวนมากเป็นการชนกันแบบ 2 ช่วงตึก และรวดเร็วกว่าการโจมตีทั่วไปในเมตริกต้นทุนของการแลกเปลี่ยนระหว่างพื้นที่และเวลา เราสังเกตเห็นว่าจำนวนของการชนกันแบบกึ่งอิสระเริ่มต้นที่ต้องการสามารถลดลงได้ในการตั้งค่าควอนตัม ซึ่งทำให้เราสามารถแปลงการชนแบบกึ่งอิสระแบบคลาสสิก 38 และ 39 ขั้นก่อนหน้านี้เป็นการชนกันได้ แนวคิดเบื้องหลังการโจมตีของเรานั้นเรียบง่ายและยังใช้ได้กับฟังก์ชันแฮชการเข้ารหัสอื่นๆ