Score:1

การต่อฟังก์ชันทางเดียวสองฟังก์ชันเป็นฟังก์ชันทางเดียวเมื่อแต่ละฟังก์ชันรับอินพุตต่างกันหรือไม่

ธง mx

คล้ายกับ คำถามนี้แต่มีสองอินพุตแยกกันสำหรับแต่ละความยาวโดยคงฟังก์ชันทางเดียวไว้ $f$ และ $g$, เช่น. $h: \lbrace 0,1 \rbrace^{2\kappa} \ถึง \lbrace 0,1 \rbrace^{2\kappa}, h(x) = f(x_1)||g(x_2)$ ที่ไหน $x_1$ และ $x_2$ เป็นสอง $\กัปปะ$ บิตแบ่งครึ่งของ x

ฉันคิดว่า $h$ จะเป็นวิธีหนึ่ง แต่ฉันไม่แน่ใจเกี่ยวกับการลดลงที่เหมาะสมในการแสดงสิ่งนี้

ฉันคิดว่าฉันไม่จำเป็นต้องแสดงว่าความน่าจะเป็นของผู้โจมตีที่ถอดรหัสสิ่งนี้มีน้อยมากในเวลาพหุนาม แต่ควรลดปัญหาของความเป็นทางเดียวของ $f$ และ $g$ และรู้ว่าเป็นทางเดียวก็ควรแสดงให้เห็นตามความเป็นจริง $h$ เป็นวิธีหนึ่ง

Morrolan avatar
ng flag
ดูเหมือนว่าจะเป็นตัวเลือกที่ดีสำหรับการพิสูจน์ด้วยความขัดแย้ง สมมติว่าคุณสามารถกลับ $h(x_1 || x_2)$ (ด้วยความน่าจะเป็นที่ไม่สำคัญ)คุณสามารถใช้ประโยชน์จากความสามารถนี้เพื่อสลับค่า $f(x_1)$ หรือ $g(x_2)$ (ด้วยความน่าจะเป็นที่ไม่มีนัยสำคัญ) ได้หรือไม่

โพสต์คำตอบ

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