แฮชที่ทนต่อการชนสามารถคืนค่าศูนย์ได้หรือไม่

เมื่อเร็ว ๆ นี้ฉันได้อ่านต้นฉบับ การพิสูจน์ ของ สกสค.

มันกล่าวถึงคุณสมบัติของ "เกือบสากล" และ "คืนค่าศูนย์" สำหรับฟังก์ชันแฮช

ฉันสงสัยว่ามีความเกี่ยวข้องกันระหว่างคนทั้งสองนั่นคือ

หากฟังก์ชันแฮชทนต่อการชนกัน แสดงว่า "ไม่น่าเป็นไปได้" คืนค่าศูนย์

ในทางที่เป็นทางการ เรามีดังต่อไปนี้:

สำหรับ $\forall M, M^{'} \in \{0,1\}^{n}, M \ne M^{'}$,

ถ้า $\mathrm{Pr}\left[H_{K}(M)\oplus H_{K}(M^{'})=0^{n}\ \middle|\ K\stackrel{\$}{ \leftarrow} \{0,1\}^{n}\right] \le \epsilon_{1}$ ถือแล้ว $\mathrm{Pr}\left[H_{K}(M) =0^{n} \middle|\ K\stackrel{\$}{\leftarrow} \{0,1\}^{n} \right] \le \mathrm{Pr}\left[H_{K}(M)\oplus H_{K}(M^{'})=0^{n}\ \middle|\ K\stackrel{\ \$}{\leftarrow} \{0,1\}^{n}\right] \le \epsilon_{1}$ ยังถือ.

ข้อความนี้ถูกต้องหรือไม่?

• ถ้าเป็นเช่นนั้นจะพิสูจน์ได้อย่างไร
• ถ้าไม่ ความสัมพันธ์ระหว่างการต้านทานการชนกับผลลัพธ์แฮชเป็นศูนย์คืออะไร

ขอบคุณล่วงหน้า!

ข้อความนี้ถูกต้องหรือไม่?

ที่จริงแล้วในกรณีเฉพาะของ GHASH นั้นไม่ใช่

GHASH มีคุณสมบัติที่ $\forall k: H_k(0^n) = 0$; ดังนั้นนั่นแสดงว่าอสมการที่ต้องการไม่มีอยู่จริง

สิ่งที่เกิดขึ้นสำหรับ GHASH เรามีอยู่เสมอ $H_k(M) \oplus H_k(M') = H_k(M \oplus M')$; เรายังมี $\mathrm{Pr}\left[H_{K}(M) =0^{n} \middle|\ K\stackrel{\$}{\leftarrow} \{0,1\}^{n} \right] \le \epsilon$ สำหรับ $ม \นี 0^n$ซึ่งเป็นสาเหตุที่อสมการดั้งเดิมยังคงอยู่

ในหมายเหตุด้านข้าง คุณถามเกี่ยวกับ 'ฟังก์ชันแฮชที่ทนต่อการชนกัน'; ปรากฎว่า GHASH ไม่ใช่ฟังก์ชันแฮชที่ป้องกันการชนกัน แต่เป็น "$\เดลต้า$ ฟังก์ชันแฮชเกือบสากล" สมการแรกของคุณ (แทนที่ $0^n$ ด้วยตัวแปรอิสระ) เป็นหลักในการนิยาม

GHASH ไม่ใช่ฟังก์ชันแฮชที่ป้องกันการชนกัน เพราะหากคุณได้รับสิทธิ์ให้ Oracle เข้าถึง GHASH การกู้คืนจะทำได้ง่าย $k$และจากนั้นจะพบการชนกันได้ง่าย