เหตุใดฟังก์ชันแฮชสากลจึงป้องกันศัตรู แต่ฟังก์ชันแฮชแบบเดียวกันไม่ป้องกัน

ก่อนที่ฉันจะระบุคำถามจริงของฉัน ให้ฉันห้าคำศัพท์ก่อน เพื่อให้เราทุกคนอยู่ในหน้าเดียวกัน:

อนุญาต $U=\{k_1,...,k_u\}$ จักรวาลของกุญแจที่เป็นไปได้ $|U|=u$. เราใช้ตารางแฮช $T$ กับ $m$ เซลล์นับจาก $0$ ถึง $m-1$. เราใช้ตระกูลฟังก์ชันแฮช $H$เช่นนั้นแต่ละ $h\ ใน H$ มีความน่าจะเป็น $1/ตรม คีย์ที่แตกต่างกันสองคีย์นั้น $k$ และ $k'$ แฮชมีค่าเท่ากัน นั่นคือ $P(h(k)=h(k'))=1/m$.

สุดท้าย การแฮชแบบสากลหมายความว่าสำหรับการแฮช ฟังก์ชันแฮชแบบสุ่ม (ตอบสนอง $1/ตรม ข้อกำหนดที่กล่าวถึงข้างต้น) ถูกเลือกจาก H ตามการวิจัยของฉัน (และดูเหมือนว่าจะสอดคล้องกับตำราอัลกอริทึม CLRS ที่รู้จักกันดี) เรามักจะใช้เพียง a เดี่ยว ฟังก์ชันแฮชตลอดรันไทม์ของตารางแฮชของเรา องค์ประกอบอื่นๆ ในตระกูลแฮชจึงมีความเกี่ยวข้องเฉพาะในขณะที่กำลังสร้างตาราง (เช่น ในการเรียกโปรแกรมครั้งแรก) แต่ฟังก์ชันนี้ได้รับเลือกให้แก้ไขแล้ว ส่วนอื่นๆ ทั้งหมดไม่เกี่ยวข้องอีกต่อไป สิ่งนี้ก็สมเหตุสมผลเช่นกัน เพราะถ้าคุณเลือกฟังก์ชันแฮชที่แตกต่างกันสำหรับคีย์ต่างๆ คุณก็ต้องมีการแมปจากคีย์ไปยังฟังก์ชันที่ใช้อีกครั้ง ซึ่งไม่สมเหตุสมผลเลย นี่คือปัญหาที่เราจะแก้ไข : รู้ว่าจะเก็บกุญแจไว้ที่ไหน แต่ฟังก์ชันแฮชที่เลือกจะขึ้นอยู่กับคีย์ ดังนั้นเราจะได้ความขัดแย้ง :) ดังนั้นจึงค่อนข้างมีเหตุผลที่เราจะเลือกเพียงหนึ่งฟังก์ชันตลอดรันไทม์ทั้งหมด

โดยชี้แจงว่า คำถามของฉัน:

การเลือกฟังก์ชันแฮชแบบสุ่มช่วยให้เราป้องกันฝ่ายตรงข้ามได้อย่างไร หากยังคงแก้ไขตลอดอายุการใช้งานของตาราง ฉันไม่เห็นความแตกต่างใด ๆ ที่จะมีการแก้ไขฟังก์ชันแฮชเดียวล่วงหน้า

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

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

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

ดังนั้นหากเราคิดว่าฟังก์ชันนั้นไม่ได้เปิดเผยต่อสาธารณะและฝ่ายตรงข้ามสามารถอนุมานได้ "อย่างใด" (เป็นไปได้หรือไม่ โดยการวัดรันไทม์ เป็นต้น) ก็ไม่สร้างความแตกต่างไม่ว่าจะมีสิ่งใดที่ได้รับการแก้ไขล่วงหน้า หรือว่าจะได้รับการแก้ไขหลังจากเริ่มต้นตารางแล้วเท่านั้น

ดังนั้น ไม่ว่าจะด้วยวิธีใด ข้อโต้แย้งของฝ่ายตรงข้ามก็ดูเหมือนจะไม่ได้ผล -- ดูเหมือนว่าจะผิด เว้นแต่ว่าฟังก์ชันแฮชที่ใช้นั้นจะเปิดเผยต่อสาธารณะจริง ๆ ซึ่งฉันก็ไม่อยากจะเชื่อเลย แล้วเกิดอะไรขึ้นที่นี่?