Score:1

$H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ และ $a \mapsto g^a\bmod p$ กับ $p$ ไพรม์ (อย่างยิ่ง) ปราศจากการชนกันหรือไม่

ธง us

อนุญาต $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ และ $a \mapsto g^a\bmod p$ สำหรับ $g \in \mathbb{Z}_{p}^{*}$ ที่ไหน $p$ เป็นนายก ฟังก์ชันนี้มีความหมายว่าปราศจากการชนกัน (อย่างยิ่ง) ที่เราไม่สามารถหาได้จริงหรือไม่ $x_1$,$x_2$ ดังนั้น $H(x_1)=H(x_2)$?

ฉันไม่โต้แย้งด้วยเหตุผลต่อไปนี้: $A$ เป็นอัลกอริทึมที่สร้าง $x_1 \neq x_2$ ดังนั้น $H(x_1)=H(x_2)$ และกำหนด $A: \mathbb{N} \rightarrow (X_1,X_2)$ $A: n \mapsto (n,n+(p-1))=(x_1,x_2)$ เราพบทฤษฎีบทเล็กน้อยของแฟร์มาต์ว่า $g^{x_2}=g^{n+(p-1)}=g^{n}g^{p-1}=g^{n}=g^{x_1}$

ความกลัวที่ยิ่งใหญ่ของฉันอยู่ที่นี่ที่ฉันสับสน (อ่อนแอ) ที่ไม่ชนกับไม่ชนอย่างแรง หากมีข้อผิดพลาดใด ๆ แนะนำให้ทำอะไรให้ดีขึ้น

fgrieu avatar
ng flag
คำแนะนำ: ดูอีกครั้งที่ชุดอินพุตสำหรับ $H$ ถ้า $p$ เป็นจำนวนเฉพาะ (หรือโดยทั่วไปรู้จักการแยกตัวประกอบ) นั่นทำให้สามารถแสดงภาพล่วงหน้าที่สองได้หรือไม่ สิ่งนั้นเหมาะสมกับคำจำกัดความของ "ปราศจากการชนกัน (อย่างมาก)" ที่คุณใช้อยู่ (และควรเป็นส่วนหนึ่งของคำถาม BTW) หรือไม่
Iwan5050 avatar
us flag
ฉันเห็นข้อผิดพลาด lol ไม่ ตามคำจำกัดความของเราที่เรากำลังใช้อยู่นั้นไม่ (อย่างยิ่ง) ปราศจากการชนกัน เนื่องจากเราสามารถหา $x_1,x_2$ ดังกล่าวได้จริง (แม้ภายในไม่กี่วินาที) โดยที่ $H(x_1)=H(x_2)$ จึงไม่ (อย่างยิ่ง) ปราศจากการชนกัน
SSA avatar
ng flag
SSA
การแม็พของคุณเป็นแบบโฮโมมอร์ฟิซึ่มเชิงเสริม โดยที่ x และ x+p จะแมปกับองค์ประกอบโคโดเมนเดียวกัน ${x \equiv x+p}$ นอกจากนี้ เคอร์เนลของการแมปของคุณคือ ${
fgrieu avatar
ng flag
@SSA: หากไพรม์ $p$ เป็นแบบสาธารณะ ดังนั้น $p$ ขนาดใหญ่นั้นไม่ดีพอที่จะทำให้ $H$ ป้องกันการชนกันได้ ใน crypto เราถือว่าฝ่ายตรงข้ามที่ชาญฉลาด (จำลองโดยอัลกอริทึม ตามทฤษฎีแล้ว อัลกอริทึมใดๆก็ตาม ในทางปฏิบัติ อัลกอริทึมที่ออกแบบโดยมนุษย์หรือ AI) และคาดว่าพวกเขา (ฝ่ายตรงข้าม อัลกอริทึม) จะใช้ประโยชน์จากข้อมูลสาธารณะ รวมถึงพารามิเตอร์ต่างๆ พวกเขาไม่ผูกพันกับการสร้างการชนกันแบบสุ่ม (ซึ่งจะล้มเหลวสำหรับ $p$ ขนาดใหญ่)
SSA avatar
ng flag
SSA
@fgrieu, Chaum-van Heijst-Pfitzmann Hash Function คล้ายกับสิ่งนี้ มันตอบสนองคุณสมบัติทั้ง 3 ข้อซึ่งจำเป็นต้องใช้ฟังก์ชันแฮช แต่ไม่เห็นการใช้งานเนื่องจากใช้งานได้ช้า
Score:1
ธง us

ไม่ ตามคำจำกัดความของเราที่เรากำลังใช้อยู่นั้นไม่ (อย่างยิ่ง) ปราศจากการชนกัน เพราะด้วยอัลกอริทึม $A$ เราได้สร้างวิธีที่รวดเร็วในการคำนวณดังกล่าวแล้ว $x_1,x_2$ กับ $H(x_1)=H(x_2)$ และตามคำนิยามแล้วสิ่งนี้ขัดแย้งกับเงื่อนไขที่ปราศจากการชนกัน

fgrieu avatar
ng flag
คุณควรจะสามารถยอมรับคำตอบนี้ได้ภายในสองสามวัน ฉันจะพยายามลบความคิดเห็นนั้น
fgrieu avatar
ng flag
ฉันต้องการพิสูจน์ด้วยตัวอย่าง: "อินพุต $a=1$ และ $a=p$ ของ $H$ เป็นของโดเมนคำจำกัดความ $\mathbb Z$ และโดย FLT ผลลัพธ์จะชนกันเนื่องจาก $p$ เป็นจำนวนเฉพาะ" ( และบางที "คู่ที่ชนกันดังกล่าวสามารถแสดงโดยฝ่ายตรงข้ามได้เนื่องจาก $p$ เป็นพารามิเตอร์สาธารณะ") ตามด้วย "ดังนั้น $H$ จึงไม่สามารถต้านทานการชนกันได้"

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา