บรรจวบ เข้าสู่ระบบ
Score:0
Zoey avatar Crypto

XOR ของ $f(x)$ บิตฮาร์ดคอร์ทั้งหมด

ธง cn
Zoey

ทำไมต้องพิจารณาแบบสุ่ม $r$ ในการสร้างภาคแสดงฮาร์ดคอร์ในทฤษฎีบท Goldreich Levin? ทำไมไม่พิจารณาเฉพาะ XOR ของบิตทั้งหมดของอินพุต

76
0 + 0
cn flag
Maeher
ให้ $f : \{0,1\}^n \to \{0,1\}^n$ เป็นฟังก์ชันทางเดียว พิจารณาฟังก์ชัน $g : \{0,1\}^n \to \{0,1\}^{n+1}$ กำหนดเป็น $g(x) = g(x_1\ldots x_n) := f( x)\Vert \bigoplus_{i=1}^{n} x_i$ $g$ เที่ยวเดียวหรือเปล่า? xor ของบิตอินพุตทั้งหมดเป็นเพรดิเคตฮาร์ดคอร์สำหรับ $g$ หรือไม่
2
ตอบกลับ
Zoey avatar
cn flag
Zoey
มันไม่ใช่เพราะมันเป็นส่วนหนึ่งของผลลัพธ์ แต่ทำไมจึงทำแบบเดียวกันไม่ได้ . หากคุณรวมสิ่งนั้นไว้ในผลลัพธ์ที่จะไม่ฮาร์ดคอร์เกินไปใช่ไหม XOR ไม่ใช่กรณีพิเศษเมื่อ r คือทั้งหมด 1s หรือไม่
0
ตอบกลับ
cn flag
Maeher
โปรดจำไว้ว่า GL กำหนด *เฉพาะ* OWF ซึ่งผลิตภัณฑ์ภายในเป็นแบบฮาร์ดคอร์
0
ตอบกลับ
cn flag
Maeher
$r$ เป็นส่วนหนึ่งของ *input* คุณไม่สามารถ *ตั้งค่า* ให้เป็นอะไรก็ได้ มันจะถูกสุ่มเลือกอย่างสม่ำเสมอ แต่สิ่งสำคัญคือมันไม่ได้เป็นส่วนหนึ่งของอินพุตของฟังก์ชัน *พื้นฐาน* ดังนั้นฟังก์ชันนั้นจึงไม่สามารถทำอะไรตลกๆ ได้
1
ตอบกลับ
Zoey avatar
cn flag
Zoey
ให้ฉันพยายามทำความเข้าใจที่นี่: XOR ของบิตไม่ใช่บิตที่ไม่ยอมใครง่ายๆ สำหรับ OWF ใด ๆ เพราะเราสามารถสร้างหนึ่งโดยที่ XOR เป็นส่วนหนึ่งของเอาต์พุต XOR สามารถเป็นฮาร์ดคอร์ของฟังก์ชันพื้นฐาน $f$ ซึ่งจะเกิดขึ้นหาก $r= 11...1$ (ทั้งหมด 1 วินาที) เป็นตัวเลือกที่สุ่มเลือกสำหรับอินพุตของการแปลง GL ของ $f$ เช่น $g$ .
0
ตอบกลับ
ธงชาติไทย
Kulap
คำถามนี้เป็นภาษาอื่นๆ:

โพสต์คำตอบ

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