Score:1

ความแตกต่างของฝ่ายตรงข้ามพร้อมข้อความเพิ่มเติม

ธง br

สมมติว่าเราเล่นเกมจาก Adversarial Indistinguishability แต่ Adversarial สามารถเลือกข้อความได้สามข้อความ $m_0, m_1, m_2$. แน่นอน, $Pr[M=m_i]=1/3$ สำหรับ $i=0,1,2$. ฉันคิดว่าการมีฝ่ายตรงข้ามที่แยกไม่ออกไม่มีใครมีความได้เปรียบมากกว่า $1/3$. คำถามคือว่าสิ่งนี้แข็งแกร่งกว่าเวอร์ชันที่มีข้อความสองข้อความหรือไม่ โดยสัญชาตญาณมันเป็นอย่างนั้น แต่จากนั้นเราสามารถรับข้อความได้มากขึ้นและทำให้ข้อได้เปรียบของฝ่ายตรงข้ามน้อยลงและน้อยลง จำเป็นหรือไม่? ด้วยเหตุผลบางอย่างในคำจำกัดความมีสองข้อความ - เพียงพอหรือไม่

Score:0
ธง cn

หมายเหตุ: ที่นี่ฉันใช้ดัชนี $0,1,2$ และ $0,1$ แทน $1, 2, 3$ และ $1,2$.

เราต้องแสดง $3$ปัญหาการแยกแยะไม่ได้เทียบเท่ากับ $2$- แยกแยะไม่ได้ 1.

$2$-แยกไม่ออกง่ายกว่า $3$- แยกแยะไม่ออก

ก่อนอื่นให้พิจารณาว่ามีศัตรูอยู่ $\คณิตศาสตร์แคล{A}_3$ ต่อต้าน $3$- ปัญหาการแยกแยะไม่ออกกับความได้เปรียบ $\epsilon$.

กำหนด $\mathcal{B}^{\mathcal{A}_3}_2$:

  • รับสามข้อความ $(m_0, m_1, m_2)$ จาก $\คณิตศาสตร์แคล{A}_3$

  • $x \xleftarrow{\$} \mathbb{Z}_3$

  • $(m^\prime_0, m^\prime_1) := (m_{(1+ x \mod 3)}, m_{(2+ x \mod 3)})$

  • ส่ง $(m^\prime_0, m^\prime_1)$ ต่อผู้ท้าชิงและรับ $ค$.

  • ส่ง $ค$ ถึง $\คณิตศาสตร์แคล{A}_3$ และรับ $ข$.

  • ถ้า $b=x$ จากนั้นส่งคืนบิตแบบสุ่ม $b^\ไพรม์$ อย่างอื่นกลับมา $(b- x \mod 3)$.

เรามาพิสูจน์กันก่อนว่า $\คณิตศาสตร์แคล{B}_2$ มีโอกาสที่จะชนะ $\frac{1-\epsilon}{4} +\epsilon$.

ให้โทร $b''$ บิตที่ผู้ท้าชิงเลือก

$\mathbb{P}(\mathcal{B}_2 ชนะ)= \mathbb{P}(b- x \mod 3 = b'')\mathbb{P}(\mathcal{B}_2 ชนะ| b- x \mod 3 = b'') + \mathbb{P}(b- x \mod 3 \neq b'')\mathbb{P}(\mathcal{B}_2 ชนะ| b- x \mod 3 \neq b'')$

$= \epsilon \cdot 1 + (1 - \epsilon)\mathbb{P}((b=x) \wedge b^\prime =b'' | b- x \mod 3 \neq b^{\prime\prime}) $

$= \epsilon + (1 - \epsilon)\frac{1}{2}\cdot\frac{1}{2}.qed$

ตอนนี้เราสามารถดูข้อได้เปรียบ: $|\frac{1}{2} - (\frac{1-\epsilon}{4} +\epsilon)|=|\frac{1- 3 \epsilon}{4}| = \frac{1}{12}|\frac{1}{3}- \epsilon|$.

ถ้า $|\frac{1}{3}- \epsilon|$ ไม่สำคัญก็หมายความว่า $|\frac{1}{2} - (\frac{1-\epsilon}{4} +\epsilon)|$ ก็ไม่น้อยหน้าเช่นกัน

$3$-แยกไม่ออกง่ายกว่า $2$- แยกแยะไม่ออก

ตอนนี้ให้พิจารณาว่ามีศัตรูอยู่ $\คณิตศาสตร์แคล{A}_2$ ต่อต้าน $2$- ปัญหาการแยกแยะไม่ออกกับความได้เปรียบ $\epsilon$.

กำหนด $\mathcal{B}^{\mathcal{A}_2}_3$:

  • รับสองข้อความ $(m_0, m_1)$จาก $\คณิตศาสตร์แคล{A}_2$

  • $b \xleftarrow{\$} \mathbb{Z}_2$

  • $m_2 := m_{b}$

  • ส่ง $(m_0, m_1, m_2)$ ต่อผู้ท้าชิงและรับ $ค$.

  • ส่ง $ค$ ถึง $\คณิตศาสตร์แคล{A}_2$ และรับ $b^\ไพรม์$.

  • $x \xleftarrow{\$} \big\{b, 2\big\}$

  • ถ้า $b^\prime=b$ จากนั้นส่งคืน x มิฉะนั้นส่งคืน $b^\ไพรม์$

เมื่อพิสูจน์ครั้งแรกคำนวณความน่าจะเป็นที่จะชนะ $\คณิตศาสตร์แคล{B}_3$.

$\mathbb{P}(\mathcal{B}_3 ชนะ) = \frac{1}{3}\mathbb{P}(\mathcal{B}_3 ชนะ|b''=2) + \frac{1}{3}\mathbb{P}(\mathcal{B}_3 ชนะ| b''=b)+ \frac{1}{3}\mathbb{P}(\mathcal{B}_3 ชนะ| b''=1 - b) $

$\mathbb{P}(\mathcal{B}_3 ชนะ) = \frac{1}{3}\mathbb{P}(b'=b \wedge x=2|b''=2) + \frac{1}{3}\mathbb{P}(b'=b \wedge x=b| b''=b)+ \frac{\epsilon}{3}.$

เพราะ $x$ ถูกเลือกโดยไม่ขึ้นกับ $ข'$:

$\mathbb{P}(\mathcal{B}_3 ชนะ)$ $= \frac{1}{3}\mathbb{P}(b'=b|b''=2) \cdot \mathbb{P}(x=2|b''=2) + \frac{1}{3}\mathbb{P}(b'=b|b''=b') \cdot \mathbb{P}(x=b''|b''=b')+ \frac{\epsilon}{3} $

$\mathbb{P}(\mathcal{B}_3 ชนะ) = \frac{1}{3}\epsilon \cdot \frac1 2 + \frac{1}{3}\epsilon \cdot \frac1 2+ \frac{\epsilon}{3} = \frac{2\epsilon}{3}.$

ตอนนี้เราคำนวณความได้เปรียบของ $\คณิตศาสตร์แคล{B}_3$: $|\frac1 3 - \frac{2\epsilon}{3} |= \frac1 6 |\frac 1 2 - \epsilon|.$

ถ้า $|\frac{1}{2}- \epsilon|$ ไม่สำคัญก็หมายความว่า $|\frac{1}{3} - \frac{2\epsilon}{3}|$ ก็ไม่น้อยหน้าเช่นกัน

เราสรุปได้ว่าปัญหาเหล่านี้เทียบเท่ากัน

cn flag
มีบางคำหายไปในขั้นตอนสุดท้ายของการลดครั้งแรกที่ฉันคิด (หรืออย่างน้อยฉันก็ไม่เข้าใจประโยค)
Ievgeni avatar
cn flag
ฉันได้แก้ไขข้อสรุปสองประโยคแล้ว
cn flag
ฉันกำลังพูดถึง "ถ้า $b=x$ ส่งคืนบิตแบบสุ่ม ให้ส่งคืน $(b- x \mod 3)+1$" ฉันเดาว่า "$=$" ควรเป็น "$\neq$" และมี "else" หายไป แต่ฉันไม่ค่อยแน่ใจว่าคุณต้องการอะไร
Ievgeni avatar
cn flag
โอเค ขอบคุณ ฉันได้แก้ไขขั้นตอนนี้แล้ว และเปลี่ยนสัญลักษณ์เพื่อให้ชัดเจนขึ้น
Awerde avatar
br flag
คุณช่วยชี้แจงข้อพิสูจน์ที่สองได้ไหม ฉันไม่เข้าใจว่าทำไมจึงมี $\frac{1}{3}\mathbb{P}(\mathcal{B}_3wins|b''=2)...$ เราใช้ $b''=2$ เพราะ $m_2=m_b$ หรือไม่
Ievgeni avatar
cn flag
@Awerde การลดครั้งที่สองของฉันผิด ฉันได้แก้ไขแล้ว

โพสต์คำตอบ

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