การใช้เมทริกซ์กลับด้านแบบสุ่มบนเขตข้อมูลจำกัดเพื่อกำหนดแฮชของรายการ

นี่คือการติดตามผลจากคำถามก่อนหน้า การคูณเมทริกซ์ของการย่อยแฮชยอมรับการจัดการผลลัพธ์หรือไม่; สูตรนี้ล้มเหลวเพราะมันยอมรับเมทริกซ์เอกพจน์และดังนั้นจึงเสื่อมลงเป็นศูนย์เมทริกซ์หลังจากคูณองค์ประกอบเพียงพอ ผู้ตอบแนะนำให้ใช้ฟิลด์เช่น $GF(256)$ แทนที่จะเป็นวงแหวนและปฏิเสธเมทริกซ์เอกพจน์ ซึ่งเป็นสิ่งที่คำถามนี้สำรวจ

นี่คือการโพสต์ข้าม จากคศ.คณิตศาสตร์

พิจารณาลำดับขององค์ประกอบที่เรียงลำดับ $a_n$, ฟังก์ชัน $h$ ที่ได้มาจากเมทริกซ์ที่พลิกกลับได้เหนือเขตข้อมูลจำกัด ââ â จากแฮชการเข้ารหัสขององค์ประกอบเดียว และฟังก์ชัน $H$ ที่ค้นหาผลคูณของเมทริกซ์ดังกล่าวทั้งหมดจากลำดับ:

$H(a) = \prod_{i = 1}^{n} h(a_i)$

กำหนด $H(ก)$ เพื่อเป็นแฮชของลำดับ $a_n$.

โปรดทราบว่าเนื่องจากการเชื่อมโยง ได้รับสองลำดับ $a_n$, $b_m$, แล้ว $H(a)*H(b) = H(a ⧺ b)$ (ที่ไหน $⧺$ หมายถึงเชื่อมลำดับ)

สมมติว่าเราสามารถเชื่อถือได้ว่าฟังก์ชันอนุพันธ์ของเมทริกซ์ผกผันมีคุณสมบัติของฟังก์ชันแฮชการเข้ารหัส มีอัลกอริทึมที่ดีกว่ากำลังดุร้ายที่สามารถค้นหาสองลำดับที่แตกต่างกันที่มีแฮชเหมือนกันหรือไม่?

ฉันเขียนโค้ดตัวอย่างคำจำกัดความนี้ในสมุดบันทึกของ Julia ที่ฉัน เผยแพร่ที่นี่.