Score:2

ทำลายเลขรหัส Mansour ด้วยการค้นหาช่วงเวลาควอนตัม: ความน่าจะเป็นของการชนที่ไม่ต้องการ

ธง cn

กระดาษ การทำลายระบบเข้ารหัสลับแบบสมมาตรโดยใช้การหาช่วงเวลาควอนตัม แสดงวิธีทำลายรหัสเลขคู่ของ Mansour โดยใช้อัลกอริทึมของ Simon แม้แต่ Mansour ใช้สองปุ่ม $k_1, k_2$ และการเปลี่ยนรูปสาธารณะแบบสุ่ม $พี$ เพื่อเข้ารหัสข้อความ $x$:

$$E_{k_1, k_2}(x) = P(x \oplus k_1) \oplus k_2$$

ในสถานการณ์สมมติของข้อความธรรมดาที่รู้จักควอนตัม เราสามารถใช้การค้นหาช่วงเวลาควอนตัม (อัลกอริทึมของไซมอน) เพื่อค้นหาช่วงเวลา $k_1$ ในฟังก์ชันต่อไปนี้: $$f(x) = P(x \oplus k_1) \oplus k_2 \oplus P(x)$$ เห็นได้ชัดว่า $f(x) = f(x \oบวก k_1)$ เท่านี้ก็น่าติดตามแล้วครับ กระดาษนั้นให้เหตุผลว่าถ้ามีช่วงเวลาอื่น $t \ไม่อยู่ใน \{0,k_1\}$ ดังนั้น $$Pr[f(x) = f(x \oplus t)] \geq \frac{1}{2}$$ จากนั้นจะมีลำดับส่วนต่างที่สูงขึ้นสำหรับ P เพราะเช่นนั้นจะถือว่า: $$Pr[P(x) \oplus P(x \oplus k_1) \oplus P(x \oplus t) \oplus P(x \oplus t \oplus k_1)] \geq \frac{1}{2}$ $ มันไม่ชัดเจนสำหรับฉันว่าทำไม การมีอยู่ของช่วงเวลาอื่นจะไม่เพียงบ่งบอกว่า: $$P(x \oplus k_1) \oplus P(x) = P(x \oplus k_1 \oplus k_1) \oplus P(x \oplus k_1) = P(x \oplus t \oplus k_1) \oplus P( x \oplus t) = P(x \oplus t \oplus k_1 \oplus k_1) \oplus P(x \oplus t \oplus k_1)$$ ส่วนต่างลำดับที่สูงกว่าสามารถติดตามได้อย่างไร

Score:2
ธง sa

ประการแรก คุณพิมพ์ผิด [missing $=0$] สิ่งที่คุณต้องแสดงก็คือ $$Pr[P(x) \oplus P(x \oplus k_1) \oplus P(x \oplus t) \oplus P(x \oplus t \oplus k_1)=0] \geq \frac{1}{2 }$$

หากคุณใส่คำจำกัดความของ $ฉ(x)$ ในความสัมพันธ์ $$ Pr[f(x)=f(x\oplus t)]\geq \frac{1}{2}, $$ คุณได้รับ $$ Pr\left[P(x \oplus k_1) \oplus k_2 \oplus P(x) = P(x \oplus k_1 \oplus t) \oplus k_2 \oplus P(x \oplus t)\right]\geq \frac{1}{2} $$ ซึ่งลดลงเป็นนิพจน์ที่ต้องการหลังจากการยกเลิกบางอย่าง

cryptobeginner avatar
cn flag
ขอบคุณมาก! คุณช่วยอธิบายให้ฉันฟังถึงที่มาของข้อโต้แย้งเดียวกันสำหรับการก่อสร้างการก่อสร้าง LRW (หน้า 13) ได้ไหม ตรงนั้น ฟังก์ชันคือ $f(x) = E_K[x \oplus h(t_0)] \oplus h(t_0) \oplus E_k[x \oplus h(t_1)] \oplus h(t_1)$ และเราต้องการ แสดง $Pr[E_k[x] \oplus E_k[x \oplus s] \oplus E[x \oplus t] \oplus E_K[x \oplus s \oplus t]] \geq 1/2$ ถ้าความน่าจะเป็นของ การชนกันที่ไม่ต้องการมีค่ามากกว่า $1/2$ โดยที่จุดคือ $s = h(t_0) \oplus h(t_1)$

โพสต์คำตอบ

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