อนุญาต $k\ge2$ เป็นค่าคงที่ที่กำหนดในระดับปานกลาง และ $H:[0,k)\times\{0,1\}^*\to\{0,1\}^b$ เป็น $ข$บิตที่ได้รับฟังก์ชันแฮชหลอมรวมเข้ากับออราเคิลแบบสุ่ม ตัวอย่างเช่น $H(i,M)=\operatorname{SHAKE256}((\underline i\mathbin\|M),b)$ ที่ไหน $\ขีดเส้นใต้ i$ เป็น $i$ รหัสต่อ ASN.1 DER
การคำนวณหาได้ยากเพียงใด $k$ สตริง $M_i$ เช่น XOR ของ $k$ กัญชา $H(i,M_i)$ กับ $0\le ฉัน<k$ เป็นศูนย์?
แรงจูงใจกำลังประเมินต้นทุนของการโจมตี นี้ มาตรการ.
ฉันเห็นว่าสำหรับ $k=2$ เรามีแนวโน้มที่จะประสบความสำเร็จกับ $2^{b/2+2}$ แฮชและแจกจ่าย Pollard's rho ด้วยคะแนนพิเศษ และฝ่ายตรงข้ามที่มีอำนาจโดยพลการที่มีการเข้าถึงแฮชของออราเคิลสามารถทำได้ด้วยการสืบค้นแฮชที่น้อยกว่ามากเมื่อ $k$ มีขนาดใหญ่ขึ้น แต่ฉันมีช่วงเวลาที่ยากลำบากในการคำนวณงานเชิงปริมาณ
ถ้าคุณคำนวณ $2^{b/k}$ ค่าของแบบฟอร์ม $H(i,\cdot)$, แต่ละ $i$แล้วมีความเป็นไปได้สูงที่จะมี บาง ชุดของตัวแทนที่ XOR เป็นศูนย์ โดยสัญชาตญาณจะมี $(2^{b/k})^k$ วิธีการเลือกตัวแทนของแต่ละ $i$ดังนั้นหนึ่งในวิธีเหล่านี้จึงมีแนวโน้มที่จะ XOR เป็นศูนย์ ความท้าทายคือการหาทางออกดังกล่าวอย่างมีประสิทธิภาพ
ปัญหานี้ศึกษาโดย Wagner ใน ปัญหาวันเกิดทั่วไป. เขาแสดงอัลกอริทึมที่ทำงานตามเวลา $O(k \cdot 2^{b/(1+\log k)})$. อัลกอริทึมไม่ได้ปรับปรุงมากเท่ากับ $k$ เพิ่มขึ้นแม้ว่าสำหรับ $k=4$ เราได้รับแล้ว $O(2^{b/3})$ ซึ่งเป็นก้าวกระโดดครั้งใหญ่จาก $k=2$ กรณี.
ฉันพบ กระดาษติดตามผลโดย Brakerski, Stephens-Davidowitz & Vaikuntanathanซึ่งแสดงหลักฐานว่าอัลกอริทึมที่เร็วกว่าไม่น่าเป็นไปได้
โปรดทราบว่าเมื่อ $k \ge ข$คำตอบสามารถพบได้ในเวลาพหุนามผ่านพีชคณิตเชิงเส้นอย่างง่าย ดูภาคผนวก A ของ กระดาษแผ่นนี้.
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
