พิสูจน์ความปลอดภัยของ CPA

สมมติ $(Gen, Enc, ธ.ค.)$ เป็นรูปแบบการเข้ารหัสคีย์สาธารณะที่มีพื้นที่ข้อความ M ที่ปลอดภัย CPA พิสูจน์ว่ารูปแบบการเข้ารหัส $(Gen^2, Enc^2, ธันวาคม^2)$ มี CPA-secure

$Gen^2=(pk_0, sk_0) \leftarrow Gen, (pk_1, sk_1)\leftarrow Gen$ เอาต์พุต: $pk=(pk_0,pk_1)$ และ $sk=(sk_0,sk_1)$

$Enc^2(pk, (m_0,m_1))=(Enc(pk_0,m_0),Enc(pk_1,m_1))$

$Dec^2(sk, (c_0,c_1))=(ธ.ค.(sk_0,c_0),ธ.ค.(sk_1,c_1))$

ฉันได้ศึกษา Introduction to Modern Cryptography และหนังสืออื่นๆ บางเล่มแล้ว แต่ฉันไม่รู้ว่าจะเริ่มต้นพิสูจน์เรื่องนี้จากที่ใด ใครช่วยบอกใบ้หน่อย

เพื่อประโยชน์ในการอ่าน เราปรับสัญกรณ์เล็กน้อย อนุญาต $\Pi=(รุ่น,Enc,ธ.ค.)$ เป็น $\mathsf{CPA}$- รูปแบบการเข้ารหัสคีย์สาธารณะที่ปลอดภัยพร้อมพื้นที่ข้อความ $\คณิตศาสตร์แคล{M}$. เราต้องการพิสูจน์ว่า $\Pi^2=(Gen^2,Enc^2,Dec^2)$พร้อมพื้นที่ข้อความ $\mathcal{M}\times\mathcal{M}$ ยังเป็น $\mathsf{CPA}$- ปลอดภัยที่ไหน

$\ขีดเส้นใต้{(pk,sk)\gets Gen^2(1^n)}$:

• $(pk_\alpha,sk_\alpha)\gets Gen(1^n)$
• $(pk_\beta,sk_\beta)\gets Gen(1^n)$
• $(pk,sk):= \big((pk_\alpha,pk_\beta),(sk_\alpha,sk_\beta)\big)$

$\ขีดเส้นใต้{c\gets Enc^2(pk,m)}$:

• $(pk_\alpha,pk_\beta) := pk$
• $(m_\alpha,m_\beta) := m$
• $c_\alpha \gets Enc(pk_\alpha,m_\alpha)$
• $c_\beta \gets Enc(pk_b,m_\beta)$
• $c:=(c_\alpha,c_\beta)$

$\underline{m := Dec^2(sk,c)}$:

• $(sk_\alpha,sk_\beta) := sk$
• $(c_\alpha,c_\beta) := c$
• $m_\alpha := ธ.ค.(sk_\alpha, c_\alpha)$
• $m_\beta := ธ.ค.(sk_\beta, c_\beta)$
• $m := (m_\alpha,m_\beta)$.

เราสามารถพิสูจน์การอ้างสิทธิ์ต่อไปนี้ได้โดยการพิสูจน์สิ่งที่ตรงกันข้าม เช่น

$\underline{การอ้างสิทธิ์:}$ \begin{align*} &\Pi\text{ คือ $\mathsf{CPA}$-secure}\implies\Pi^2\text{ คือ $\mathsf{CPA}$-secure} \ \iff &\Pi^2\text{ คือ $\lnot\mathsf{CPA}$-secure}\implies\Pi\text{ คือ $\lnot\mathsf{CPA}$-secure} \end{จัดตำแหน่ง*}

$\ขีดเส้นใต้{หลักฐาน:}$

เพื่อพิสูจน์ความขัดแย้ง เราถือว่ามีศัตรูอยู่ $\คณิตศาสตร์แคล{A}^2$ ต่อต้าน $\Pi^2$, ดังนั้น $$\Pr[\mathsf{PubK}^{\mathsf{CPA}}_{\mathcal{A}^2,\Pi^2}(n)=1]>\frac{1}{2}+\ mathsf{negl}(n).$$ กล่าวอีกนัยหนึ่ง $\คณิตศาสตร์แคล{A}^2$ สามารถเอาชนะ $\Pi^2$ ใน $\mathsf{CPA}$ เกมที่มีความได้เปรียบที่ไม่ละเลย

ตอนนี้เราจะใช้ $\คณิตศาสตร์แคล{A}^2$ เพื่อสร้างศัตรู $\คณิตศาสตร์แคล{A}$ ต่อต้าน $\ปี่$ ใน $\mathsf{CPA}$ เกม.

เดอะ $\mathsf{CPA}$ เกมดำเนินการดังนี้:

1. $Gen(1^n)$ ถูกเรียกใช้เพื่อรับกุญแจ $(pk_\alpha, sk_\alpha)$.
2. ปฏิปักษ์ $\คณิตศาสตร์แคล{A}$ จะได้รับ $pk_\อัลฟ่า$ เช่นเดียวกับการเข้าถึงของออราเคิล $Enc(pk_\alpha,\cdot)$. ถัดไป, $\คณิตศาสตร์แคล{A}$ วิ่ง $Gen(1^n)$ ที่จะได้รับ $(pk_\beta, sk_\beta)$.
3. ปฏิปักษ์ $\คณิตศาสตร์แคล{A}^2$ จะได้รับ $pk:=(pk_\alpha,pk_\beta)$ เช่นเดียวกับการเข้าถึงของออราเคิล $Enc^2(pk,\cdot)$.
4. $\คณิตศาสตร์แคล{A}^2$ แสดงผลคู่ของข้อความที่แตกต่างกัน $m_0:=(m_{0_\alpha},m_{0_\beta}), m_1:=(m_{1_\alpha},m_{1_\beta}) \in\mathcal{M}\times\mathcal{ ล้าน$ กับ $m_{0_\beta} = m_{1_\beta}$ และ $|m_0|=|m_1|$. กล่าวอีกนัยหนึ่งข้อความ $m_0$, $m_1$ แตกต่างกัน แต่ครึ่งหลังเหมือนกัน
5. หลังจากได้รับ $m_0$ และ $m_1$ จาก $\คณิตศาสตร์แคล{A}^2$, ปฏิปักษ์ $\คณิตศาสตร์แคล{A}$ ส่งต่อเฉพาะส่วนแรกเท่านั้น $m_{0_\alpha}$,$m_{1_\alpha}$ ไปที่ $\mathsf{CPA}$ เกม.
6. เกมเลือกบิตสุ่ม $b \ใน \{0, 1\}$และไซเฟอร์เท็กซ์ของความท้าทาย $c_\alpha \gets Enc(pk_\alpha, m_{b_\alpha})$ ถูกคำนวณและมอบให้กับ $\คณิตศาสตร์แคล{A}$. $\คณิตศาสตร์แคล{A}$ ยังคงสามารถเข้าถึง $Enc(pk_\alpha,\cdot)$.
7. ตอนนี้ $\คณิตศาสตร์แคล{A}$ คำนวณครึ่งหลังของไซเฟอร์เท็กซ์ที่ท้าทายเป็น $c_\beta \gets Enc(pk_\beta, m_{0_\beta}=m_{1_\beta})$. โปรดทราบว่า $\คณิตศาสตร์แคล{A}$ ไม่จำเป็นต้องรู้บิตของความท้าทาย $ข$. แล้ว, $\คณิตศาสตร์แคล{A}$ ส่งรหัสลับที่ท้าทาย \begin{align*} c&:=(c_\alpha,c_\beta)\&:=\big(Enc(pk_\alpha, m_{b_\alpha}),Enc(pk_\beta, m_{0_\ เบต้า}=m_{1_\beta})\big)\end{align*} ถึง $\คณิตศาสตร์แคล{A}^2$. $\คณิตศาสตร์แคล{A}^2$ ยังคงสามารถเข้าถึง $Enc^2(pk,\cdot)$.
8. $\คณิตศาสตร์แคล{A}^2$ คืนบิตคาดเดา $b''$ ถึง $\คณิตศาสตร์แคล{A}$.
9. $\คณิตศาสตร์แคล{A}$ กำหนดบิตคาดเดาของตัวเอง $b':=b''$, และผลตอบแทน $ข'$ ไปที่ $\mathsf{CPA}$ เกม.
10. ผลลัพธ์ของเกมถูกกำหนดให้เป็น $1$ ถ้า $b'= b$, และ $0$ มิฉะนั้น.

จากการลดลงจะได้ว่า \begin{align*} \Pr[\mathsf{PubK}^{\mathsf{CPA}}_{\mathcal{A},\Pi}(n)=1]&=\Pr[\mathsf{PubK}^ {\mathsf{CPA}}_{\mathcal{A}^2,\Pi^2}(n)=1] \&>\frac{1}{2}+\mathsf{negl}(n) \end{จัดตำแหน่ง*} ในที่นี้ อสมการสุดท้ายตามมาจากสมมติฐานของเราที่ว่า $\คณิตศาสตร์แคล{A}^2$ สามารถเอาชนะ $\Pi^2$ ใน $\mathsf{CPA}$ เกมที่มีความได้เปรียบที่ไม่ละเลย
ในที่สุดสิ่งนี้ก็พิสูจน์คำกล่าวอ้างในเบื้องต้นได้ว่า $\Pi\text{ คือ $\mathsf{CPA}$-secure}\implies\Pi^2\text{ คือ $\mathsf{CPA}$-secure}$. $\;\blacksquare$