Score:2

เหตุใดพื้นที่สุ่มจึงต้องใหญ่กว่าพื้นที่ผูกมัด |R|>>|C| อย่างมาก เพื่อสร้างสายผูกมัด?

ธง nl

ป้อนคำอธิบายรูปภาพที่นี่

เหตุใดพื้นที่สุ่มจึงต้องใหญ่กว่าพื้นที่ข้อผูกมัด |R|>|C| อย่างมาก ภาพมาจาก https://youtu.be/IkNZWJFcfcU?t=236

Score:1
ธง ru

สำหรับคุณสมบัติการซ่อน เรากำหนดให้ค่าการผูกมัดไม่มีข้อมูลเกี่ยวกับข้อความ โดยเฉพาะอย่างยิ่งเราหวังว่าสำหรับข้อความใดก็ตาม $m$ เป็นไปได้สำหรับ $H(m,r)$ เพื่อรับค่าที่เป็นไปได้ทั้งหมด $C$ (ไม่เช่นนั้นอาจยกเว้นบางข้อความตามข้อผูกมัดบางประการ) ถ้า $H$ ทำตัวเหมือนฟังก์ชั่นสุ่ม แล้วมันไม่น่าที่จะมีคุณสมบัติ surjective นี้ เว้นแต่ $|R|>|C|\log|C|$.

เราอาจต้องการค่าของ $H(m,r)$ สำหรับการแก้ไขใด ๆ $m$ ให้กระจายอย่างสม่ำเสมอในค่าของ $C$.

โปรดทราบว่าข้อกำหนดเหล่านี้เป็นข้อกำหนด "ความรู้เป็นศูนย์" ทางทฤษฎีมากกว่าข้อกำหนดที่มีขอบเขตด้านความซับซ้อน/การคำนวณ

Daniel S avatar
ru flag
สำหรับค่าลับใด ๆ การปิดตาแบบสุ่มของความมุ่งมั่นของ Pedersen จะครอบคลุมพื้นที่ภาพทั้งหมดอย่างเท่าเทียมกัน สามารถทำได้เนื่องจากการทำให้ไม่เห็นแบบสุ่มเป็นการเรียงสับเปลี่ยนแบบสุ่มแทนที่จะเป็นฟังก์ชันแบบสุ่ม
poncho avatar
my flag
"โดยเฉพาะอย่างยิ่ง เราหวังว่าสำหรับข้อความใดก็ตาม $m$ เป็นไปได้ที่ $H(m,r)$ จะรับค่าที่เป็นไปได้ทั้งหมดใน $C$"; แม้ว่าสิ่งนี้จะเพียงพอ แต่ก็ไม่จำเป็นจริงๆ สิ่งที่จำเป็นคือฝ่ายตรงข้ามที่น่าเชื่อถือไม่สามารถรับข้อมูลใด ๆ เกี่ยวกับ $m$ จากข้อผูกมัดได้ อย่างไรก็ตาม เนื่องจากฝ่ายตรงข้ามที่ไม่มีขอบเขตทางการคำนวณนั้นไม่น่าเชื่อถือ เราจึงสามารถพิจารณาเป้าหมายที่น้อยกว่าได้ (เช่น การอนุมานข้อมูลเกี่ยวกับ $m$ ที่เป็นไปไม่ได้ทางคอมพิวเตอร์..)
Daniel S avatar
ru flag
@poncho: มีสามระดับของการซ่อนในรูปแบบความมุ่งมั่น [สมบูรณ์แบบ สถิติ และการคำนวณ](https://en.wikipedia.org/wiki/Commitment_scheme#Perfect,_statistical,_and_computational_hiding) ผู้บรรยายต้องการการซ่อนทางสถิติโดยปริยาย (ด้วยเหตุนี้การอ้างอิงถึงทฤษฎีข้อมูลของฉัน) และข้อกำหนด $|R|\gg |C|$ เป็นสิ่งจำเป็นเพื่อให้เป็นไปตามนี้

โพสต์คำตอบ

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