Score:1

แผ่นเดียวพิสูจน์ปัญหา

ธง ms

เราทราบข้อความธรรมดา 2 ข้อความความยาว L และข้อความเข้ารหัส 2 ข้อความความยาว L (เราไม่รู้ว่าข้อความใดเป็นของใคร) สมมติว่าข้อความรหัสแต่ละข้อความที่สร้างขึ้นโดยการเข้ารหัสหนึ่งในข้อความธรรมดาที่กำหนดโดย XOR'ing (หรือเรียกเฉพาะหรือ) ด้วยรหัสเดียวกัน คีย์ความยาว L (เราไม่รู้คีย์) คำถามขอให้ฉันพิสูจน์ว่าถ้าคีย์ถูกเลือกอย่างสม่ำเสมอจากช่องว่างที่กำหนดโดยความยาว L จะไม่มีโปรแกรมใดที่สามารถให้คีย์ที่ถูกต้องเป็นเอาต์พุตที่มีความน่าจะเป็นมากกว่า ½ ฉันเพิ่งเริ่มเรียนวิชาการเข้ารหัส และฉันมีคำถามพิสูจน์มากมายเช่นนี้ ฉันสามารถจินตนาการได้ว่าทำไมความน่าจะเป็นถึงเป็น ½ แต่ไม่สามารถพิสูจน์อย่างเป็นทางการได้

IngIng avatar
ms flag
ขออภัยฉันแก้ไขคำถาม @kelalaka เราใช้การแนะนำการเข้ารหัสสมัยใหม่โดย Jonathan Katz และ Yehuda Lindell แต่นี่ไม่ใช่คำถามจากหนังสือ คุณช่วยพิสูจน์อย่างเป็นทางการหรือให้เบาะแสฉันหน่อยได้ไหม ขอบคุณ.
Maarten Bodewes avatar
in flag
@Maeher เคล็ดลับคือคุณจะได้รู้ค่าแยกกันเท่านั้นไม่ใช่ข้อความธรรมดา / ciphertext *pairs* Ining มีกี่คีย์ที่เป็นไปได้? เขียน $M_1 \oplus C_2$ ใหม่!
IngIng avatar
ms flag
@Maarten Bodewes เรามี 2 ข้อความที่เข้ารหัสด้วยคีย์เดียวกัน $M1âC2 = M2âC1$ และ $M1âC1 = M2âC2$ เรามี 2 คีย์ที่เป็นไปได้เท่ากัน ฉันเห็นว่าความน่าจะเป็นคือ $1/2$ แต่ฉันจะเขียนคำตอบนี้เป็นทางการได้อย่างไร
Maarten Bodewes avatar
in flag
ไม่แน่ใจ อย่างน้อยฉันจะแนะนำ $K'$ และระบุว่าความน่าจะเป็นที่ $P_1$ เป็นข้อความธรรมดาของ $C_2$ นั้นสูงเท่ากับ $C_1$ ทุกประการ เนื่องจาก OTP ไม่มีข้อมูลใดที่สามารถแยกความแตกต่างของทั้งสองได้ เนื่องจาก $K$ เป็นแบบสุ่มทั้งหมด
Titanlord avatar
tl flag
คุณคุ้นเคยกับการทดลองการเข้ารหัสหรือไม่? มีการทดลองที่แยกไม่ออกที่สมบูรณ์แบบ และสำหรับการพิสูจน์ที่เป็นทางการ คุณสามารถใช้สิ่งนั้นเป็นพื้นฐานในการคำนวณความน่าจะเป็น

โพสต์คำตอบ

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