Score:2

Katz/Lindell 2.4 - สรุปจาก 2 ข้อความไปยังพื้นที่ข้อความใด ๆ ?

ธง fr

ฉันกำลังพยายามแก้ปัญหา 2.4 ใน "Introduction to Modern Cryptography" (ฉบับที่ 2) เพื่อการศึกษาด้วยตนเอง

ปัญหาขอให้พิสูจน์ความลับที่สมบูรณ์แบบนั้น $$ ราคา[M = m | C = c] = Pr[M = ม.] $$

หมายถึง

$$ Pr[Enc_k(m) = c] = Pr[Enc_k(m') = c] $$

วิธีแก้ไขมีดังนี้:

แก้ไขสองข้อความ $ม, ม'$ และไซเฟอร์เท็กซ์ $ค$ ที่เกิดขึ้นด้วยความน่าจะเป็นที่ไม่เป็นศูนย์ และพิจารณาการแจกแจงแบบสม่ำเสมอ $\{m, m'\}$. ความลับที่สมบูรณ์แบบบ่งบอกเป็นนัยว่า $Pr[M = ม. | C = c] = \frac{1}{2} = Pr[M = m' | ค = ค]$ ดังนั้น

$$ \frac{1}{2} = Pr[M = m| C = c] = \frac{Pr[C = c| M = m] * Pr[M = m]}{Pr[C = c]} $$

ลดความซับซ้อนไป

$$ \frac{\frac{1}{2}Pr[C = c | M = m]}{Pr[C = c]} $$

และอื่น ๆ $Pr[C = ค | ม = ม]$ = $Pr[Enc_k(m) = c]$ = $Pr[C = c]$. เนื่องจากการคำนวณแบบอะนาล็อกถือเป็น $m'$ เช่นกัน เราสรุปได้ว่า $Pr[Enc_k(m) = c]$ = $Pr[Enc_k(m') = c]$

ปัญหาของฉันคือโซลูชันนี้ใช้พื้นที่ข้อความเป็น 2 ซึ่งไม่สามารถทำให้เป็นแบบทั่วไปได้

มีบางอย่างที่ฉันขาดหายไปซึ่งทำให้โซลูชันนี้เป็นแบบทั่วไปได้หรือไม่

แก้ไข: เพื่อให้ชัดเจน นี่คือข้อความปัญหาทั้งหมด

บทแทรก 2.4: รูปแบบการเข้ารหัส (Gen, Enc, Dec) พร้อมพื้นที่ข้อความ $M$ เป็นความลับอย่างสมบูรณ์ก็ต่อเมื่อสมการ (2.1) มีไว้สำหรับทุกๆ $m,m' \ใน M$ และทุกๆ $c \ใน C$. โดยที่สมการ 2.1 คือความเท่าเทียมกันอันดับ 2 ในโพสต์นี้

โจทย์ขอให้พิสูจน์ "ทิศทางอื่น" ซึ่งในกรณีนี้หมายถึงการพิสูจน์ความลับที่สมบูรณ์แบบ => สมการ 2.1 (ในตำรามีการพิสูจน์การกลับทิศไว้แล้ว).

Myath avatar
in flag
คุณหมายถึงอะไร "ทางออก"? หนังสือมีวิธีแก้ปัญหาดังกล่าวหรือไม่?
Foobar avatar
fr flag
ใช่หนังสือไม่
kelalaka avatar
in flag
ไม่ หนังสือไม่มีทางออก มีวิธีแก้ปัญหาที่สามารถซื้อแยกต่างหากได้ คุณจะเห็นผลลัพธ์ว่าไม่มี $1/2$ ดังนั้นคุณอาจคาดเดาได้ว่ามันจะยกเลิก การทำงานพื้นที่ข้อความขนาดใหญ่จะต้องใช้ $1/n$ เล่นด้วยวิธีนี้ไหม
Score:3
ธง ru

นี่ไม่ใช่การอ้างสิทธิ์เกี่ยวกับ "พื้นที่ข้อความขนาด 2" พื้นที่ข้อความสามารถใหญ่ได้ตามที่คุณต้องการ และการกำหนดลักษณะเฉพาะแบบที่สองจะบอกว่าสำหรับทุกๆ $ม,ม'$ คุณเลือกจากพื้นที่ข้อความนี้ และสำหรับทุกข้อความเข้ารหัสที่เป็นไปได้ $ค$, ความน่าจะเป็นที่ $m$ ถูกเข้ารหัสเป็น $ค$ ก็เหมือนกับของ $m'$ ถูกเข้ารหัสเป็น $ค$ซึ่งเขียนว่า $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$.

ในส่วนที่เกี่ยวกับร่างโซลูชันที่คุณให้ไว้ มันไม่จริงเลยที่จะ "สมมติ" พื้นที่ข้อความขนาดสอง คุณต้องการพิสูจน์การอ้างสิทธิ์เกี่ยวกับข้อความคงที่สองข้อความ $m$ และ $m'$ (กล่าวคือคุณต้องการพิสูจน์ว่า $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$) และคุณต้องการทำในขณะที่ใช้ความลับที่สมบูรณ์แบบซึ่งระบุไว้สำหรับทุกข้อความ $\mu$ และไซเฟอร์เท็กซ์ทุกตัว $\gamma$,$^*$ และที่สำคัญมาก สำหรับการแจกจ่ายทุกครั้ง $M$ เหนือพื้นที่ข้อความก็ถือเอาว่า $\Pr[M=\mu|C=\gamma] = \Pr[M=\mu]$.

เนื่องจากความลับที่สมบูรณ์แบบสำหรับการเผยแพร่ใด ๆ เราสามารถเลือกการเผยแพร่ใด ๆ ที่จะช่วยเราในการพิสูจน์การอ้างสิทธิ์ของเรา โซลูชันที่คุณเสนอใช้การแจกแจงความน่าจะเป็นที่สุ่มตัวอย่าง $m$ ด้วยความน่าจะเป็น $1/2$, $m'$ ด้วยความน่าจะเป็นด้วย $1/2$และข้อความอื่นๆ ทั้งหมดจะถูกสุ่มตัวอย่างด้วยความน่าจะเป็น $0$. เราสามารถพูดได้ว่าพื้นที่ข้อความถูก "จำกัด" ไว้ $\{m,m'\}$แต่สิ่งที่เกิดขึ้นจริงคือสิ่งที่ฉันพูดก่อนหน้านี้ ตอนนี้เราได้แก้ไขการแจกแจงความน่าจะเป็นแล้ว เราก็แก้ไขด้วย $\mu = ม$ และ $\gamma = c$ ขั้นแรก ใช้ความลับที่สมบูรณ์แบบ แล้วจึงแก้ไข $\mu = m'$ และใช้ความลับที่สมบูรณ์แบบอีกครั้งเพื่อให้ได้นิพจน์ต่างๆ ที่สามารถปรับเปลี่ยนเพื่อให้ได้มาซึ่งสิ่งที่เราต้องการ

ในระยะสั้นนี่เป็นเพียงสิ่งประดิษฐ์ของการพิสูจน์ เนื่องจากการอ้างสิทธิ์ที่คุณต้องการพิสูจน์นั้นเกี่ยวข้องเฉพาะกับคู่ของข้อความที่ตายตัวเท่านั้น $ม,ม'$, แล้วคุณละ สามารถ จำกัดการแจกแจงความน่าจะเป็นเฉพาะสององค์ประกอบนี้ และใช้ความลับที่สมบูรณ์แบบในการแจกแจงนี้


$^*$ สังเกตว่าฉันใช้ชื่ออื่นแทน $m$ และ $ค$เนื่องจากสิ่งหลังได้รับการแก้ไขแล้วในบริบทของเรา

Daniel avatar
ru flag
@kelalaka เว้นแต่ว่าฉันจะพลาดบางสิ่งไป นี่ไม่ใช่ข้อสันนิษฐานต่อ se แต่เป็นทางเลือกที่คุณ *สามารถ* ใช้ในการพิสูจน์เพื่อให้มันใช้งานได้ ไม่ใช่ข้อสันนิษฐานในแง่ที่ว่ามันใช้งานไม่ได้กับการตั้งค่า "ทั่วไป" หรืออะไรทำนองนั้น การอ้างสิทธิ์นั้นเกี่ยวข้องกับคู่ของข้อความคงที่ $m,m'$ ถ้าใครต้องการอะไรที่กว้างกว่านั้นก็ควรดูที่การปรับเปลี่ยนลักษณะมากกว่าการพิสูจน์
Daniel avatar
ru flag
@kelalaka ฉันไม่แน่ใจว่าเรากำลังพูดถึงสิ่งเดียวกันที่นี่ด้วยซ้ำคุณพูดถูกว่าการรักษาความปลอดภัยที่สมบูรณ์แบบนั้นไม่ได้จำกัดอยู่เพียงชุดเดียว เนื่องจากใช้กับการกระจาย *ใดๆ* (ดังที่ฉันได้กล่าวไปแล้วในคำตอบของฉัน) แต่การพิสูจน์ลักษณะเฉพาะที่นี่พูดถึงคู่ของข้อความ *ใดๆ ที่คงที่* $m,m '$. เพื่อพิสูจน์ว่าการกำหนดลักษณะนี้เทียบเท่ากับการรักษาความปลอดภัยที่สมบูรณ์แบบ เราถือว่าพื้นที่ข้อความเป็น $\{m,m'\}$ และใช้การรักษาความปลอดภัยที่สมบูรณ์แบบ แต่นี่ไม่ใช่การทำให้เข้าใจง่ายหรือข้อสันนิษฐาน นี่เป็นเพียงส่วนหนึ่งของ หลักฐาน
Daniel avatar
ru flag
@kelalaka ที่กล่าวว่าเพื่อระบุสิ่งที่คุณพูดอย่างเป็นรูปธรรม: ลักษณะที่เสนอพูดถึง **คู่** $m,m'$ ดังนั้นจึงเป็นเรื่องปกติที่จะพิจารณาหลักฐานที่ใช้การรักษาความปลอดภัยที่สมบูรณ์แบบกับพื้นที่ข้อความ $\{ ม,ม'\}$ ฉันยืนยันว่านี่ไม่ใช่การทำให้เข้าใจง่าย นี่คือ *วิธี* ในการดำเนินการพิสูจน์ ถ้าใครต้องการ "ความหมายทั่วไป" ก็ต้องค้นหาลักษณะอื่นเพื่อพิสูจน์ เช่น "สำหรับทุกๆ $c$ ค่าของ $\Pr[\mathsf{Enc}_k(m) = c]$ จะคงที่ ไม่ว่า $ เอ็ม$"
kelalaka avatar
in flag
ฉันมีการศึกษามากขึ้น คำตอบของหนังสือเล่มนี้ทำให้ง่ายขึ้นเมื่อ `พิจารณาการกระจายตัวแบบเดียวกันบน {m1,m2}` นั่นคือประเด็นของฉัน ระหว่างย่อหน้าแรกและย่อหน้าที่สองของคำตอบของคุณ หลักฐานการกระจายพื้นที่ข้อความขนาดใหญ่ที่เหมือนกันจะหายไป! หลังจากนั้นมันเป็นเรื่องดีที่จะพูดคุยเกี่ยวกับการกระจายโดยพลการ
Daniel avatar
ru flag
@kelalaka สิ่งนี้ "พิจารณาการแจกแจงแบบสม่ำเสมอมากกว่า $\{m,m'\}$" คือ **ไม่ใช่** การทำให้เข้าใจง่าย แต่เป็น **วิธี** ในการดำเนินการพิสูจน์ต่อไป ฉันคิดว่าคุณกำลังแนะนำว่านี่เป็นเพียง "กรณีพื้นฐาน" เพื่อจุดประสงค์ในการอธิบาย และนั่นไม่ใช่กรณีทั่วไป แต่ฉันยืนยันว่านี่เป็นเพียง *ไม่ใช่* กรณี การอ้างสิทธิ์นั้นเกี่ยวกับคู่ของข้อความ $m,m'$ ซึ่งได้รับการแก้ไขแล้วเมื่อคุณเข้าสู่การพิสูจน์ และคุณสามารถเลือกการกระจายใด ๆ บนพื้นที่ที่อาจใหญ่กว่ามากเพื่อพิสูจน์ว่า $\Pr [\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$....
Daniel avatar
ru flag
@เกลลากะ ...คุณเลือกการแจกจ่ายที่กำหนด $1/2$ ถึง $m$ และ $1/2$ ถึง $m'$ และ $0$ ให้กับข้อความอื่นๆ ทั้งหมด ซึ่งสามารถใช้วลีเป็นการกระจายที่เหมือนกันกับ $\{m,m '\}$ แล้วใช้ความลับที่สมบูรณ์แบบกับการกระจายนี้ เพื่อให้ได้สิ่งที่คุณต้องการ หลักฐานมีความสมบูรณ์ 100% ณ จุดนี้ ไม่จำเป็นต้องกล่าวถึงกรณีทั่วไป
Foobar avatar
fr flag
@Daniel ขอบคุณสำหรับคำอธิบายโดยละเอียด! ฉันได้เพิ่มข้อความปัญหาทั้งหมดเพื่อให้ชัดเจนยิ่งขึ้น มันบอกว่าสมการจะต้องคงไว้สำหรับทุกๆ $m, m' \in M$ (ไม่แน่ใจว่ามันเปลี่ยนแปลงอะไรไหม)
Foobar avatar
fr flag
@Daniel ฉันได้เพิ่มโซลูชันแบบเต็มแล้ว
Daniel avatar
ru flag
@Roymunson แบบฝึกหัดขอให้คุณพิสูจน์ว่าสมมติว่าเป็นความลับที่สมบูรณ์แบบ (ซึ่งพูดถึงการแจกแจงตามอำเภอใจในพื้นที่ข้อความทั้งหมด) ตามนั้น **สำหรับทุกคู่** $m,m'$ และสำหรับทุกข้อความเข้ารหัส $c$ , $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$ ในการพิสูจน์ข้อความดังกล่าว คุณเริ่มต้นด้วยการแก้ไข $m,m'$ และ $c$ ดังนั้นสำหรับการพิสูจน์ที่เหลือ ค่าเหล่านี้เป็นเพียงค่าคงที่ และคุณสามารถใช้ความลับที่สมบูรณ์แบบกับการกระจาย *ใดๆ ก็ได้* ที่คุณเลือก โดยเฉพาะอย่างยิ่ง คุณ สามารถใช้อันที่กำหนด $1/2$ ให้กับทั้ง $m$ และ $m'$ และศูนย์ให้กับข้อความอื่นๆ ทั้งหมด
Foobar avatar
fr flag
@Daniel มันไม่ได้บอกเป็นนัยว่า $M$ อาจเป็นการกระจายใด ๆ ?
Daniel avatar
ru flag
@Roymunson ความสับสนที่นี่มาจากคณิตศาสตร์และการพิสูจน์ ไม่ใช่การเข้ารหัสคุณมีสองคำจำกัดความ: แบบแผนมีความปลอดภัยอย่างสมบูรณ์ ถ้าสำหรับทุก ๆ การกระจาย $M$ เหนือพื้นที่ข้อความ $\mathcal{M}$ สำหรับทุก ๆ ข้อความ $m$ และทุก ๆ ข้อความเข้ารหัส $c$ จะถือว่า $\Pr[ ม = ม | C = c] = \Pr[M = m]$ ในทางกลับกัน เรามาตั้งชื่อแนวคิดที่สองกัน สมมติว่าโครงร่างเป็น "ตัวแปร" ที่สมบูรณ์แบบ ปลอดภัย ถ้าสำหรับทุกคู่ของข้อความ $m$ และ $m'$ และทุกๆ ข้อความไซเฟอร์ $c$ จะถือได้ว่า $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$....
Daniel avatar
ru flag
@Roymunson ... โปรดทราบว่าคำจำกัดความที่สองของการรักษาความปลอดภัยที่สมบูรณ์แบบ "ตัวแปร" ไม่ * ไม่ * พูดถึงการกระจายในพื้นที่ข้อความเลยในขณะที่คำจำกัดความแรกทำ แนวคิดทั้งสองนี้มีความเท่าเทียมกัน แม้ว่าแนวคิดหนึ่งต้องการคุณสมบัติบางอย่างเพื่อคงไว้สำหรับการกระจายที่เป็นไปได้ *ใดๆ* ในขณะที่อีกแนวคิดหนึ่งไม่ได้พูดถึงการกระจายเลย

โพสต์คำตอบ

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