Score:2

การสุ่มที่ใช้ร่วมกันระหว่างการเข้ารหัสดั้งเดิมสองแบบทำให้อาร์กิวเมนต์ไฮบริดซับซ้อนสำหรับการคำนวณที่แยกไม่ออกหรือไม่

ธง in

อนุญาต $(Enc, ธ.ค.)$ เป็นแบบแผนการเข้ารหัสที่ปลอดภัยของ IND-CPA โดยที่ $Enc: \mathcal{K} \times \mathcal{M}_1 \rightarrow \mathcal{C}_1$, และ $F: \mathcal{K} \times \mathcal{M}_2 \rightarrow \mathcal{C}_2$ เป็นฟังก์ชันสุ่มเทียม

ลองพิจารณาตัวอย่างง่ายๆ ที่เราอาจต้องการพิสูจน์การกระจาย $(Enc_k(m_1), F_k(m_2))$ (ซึ่งการสุ่มมาจากการ รหัสที่ใช้ร่วมกัน $k \leftarrow \mathcal{K}$) แยกไม่ออกจากการคำนวณแบบแจกแจงแบบเดียวกันบน $\mathcal{C}_1 \times \mathcal{C}_2$. เห็นได้ชัดว่าเราสามารถแสดงการกระจายของ $Enc_k(m_1)$ แยกไม่ออกจากการคำนวณการแจกแจงแบบสม่ำเสมอบน $\คณิตศาสตร์แคล{C}_1$ ผ่านการลดความปลอดภัย IND-CPA โดยแทนที่ $Enc_k(m_1)$ ด้วยองค์ประกอบแบบสุ่ม $r_1 \leftarrow \mathcal{C}_1$เราสามารถรับลูกผสมระดับกลางได้ $(r_1, F_k(m_2))$. คำถามของฉันคือ:

จากนั้นเราสามารถใช้การสุ่มเทียมของ $F$ จะเข้ามาแทนที่ $F_k(m_2)$ ด้วยองค์ประกอบสุ่มอื่น $r_2 \leftarrow \mathcal{C}_2$เพื่อพิสูจน์ความแตกต่างทางการคำนวณข้างต้น?

จากมุมมองของฉัน ตัวแปรสุ่มสองตัว $Enc_k(m_1)$ และ $F_k(m_2)$ เป็น ไม่ เป็นอิสระเนื่องจากพวกเขาแบ่งปันการสุ่มแบบเดียวกัน $k$. นี่เป็นการเตือนความทรงจำว่าทำไมเราจึงควรพิจารณาการกระจายร่วมกันของทูเพิล view-output ของใครบางคนมากกว่ามุมมองของมันในการคำนวณที่ปลอดภัย ดังนั้นฉันคิดว่าการสุ่มที่ใช้ร่วมกันที่นี่จะป้องกันไม่ให้อาร์กิวเมนต์แบบไฮบริดธรรมดาผ่านไปได้ ข้อสรุปนี้ถูกต้องหรือไม่? ขอบคุณมาก.

Marc Ilunga avatar
tr flag
เราสามารถรับประกันได้หรือไม่ว่า $\mathcal C_1 \times \mathcal C_2$ นั้นแยกไม่ออกจากการสุ่ม ผู้โจมตีจะไม่ง่ายที่จะแยกแยะ $\mathcal C_1$ หรือไม่ หากการเข้ารหัสเป็นโหมดที่ใช้ตัวนับ
X. G. avatar
in flag
@MarcIlunga ฉันคิดว่าการรักษาความปลอดภัย IND-CPA ช่วยให้มั่นใจได้ว่าผลลัพธ์ของ $Enc$ ควรเป็นแบบปลอมแปลง ตราบใดที่คีย์สเปซ $\mathcal{K}$ มีเอนโทรปีเพียงพอ เช่น $\kappa$ บิต
Marc Ilunga avatar
tr flag
à ฉันไม่แน่ใจว่า CPA สามารถ *เสมอ* ให้การรับประกันนั้น ตัวอย่างทางพยาธิวิทยา: แก้ไขแบบแผน CPA เพื่อต่อท้าย $0$ เช่น $ctxt = c|0$ สิ่งนี้ยังคงปลอดภัย CPA แต่สามารถแยกความแตกต่างจากการสุ่ม ตัวอย่างที่ดีกว่าคือโหมดการทำงาน CTR กับ nonces ดังนั้น $ctxt = n | ค$ ฉันคิดว่าสามารถแยกแยะได้จากการสุ่มหาก $n$ เป็นตัวนับและไม่ได้สุ่ม
Marc Ilunga avatar
tr flag
คำถามเดิมเกี่ยวกับการสุ่มที่ใช้ร่วมกันยังคงรบกวนอยู่ tho :)
X. G. avatar
in flag
@MarcIlunga ขอบคุณสำหรับความคิดเห็นของคุณ คำถามของฉันไม่มีคำจำกัดความอย่างเป็นทางการของ IND-CPA ในที่นี้ ฉันใช้คำว่า "IND-CPA" อย่างไม่เป็นทางการเพื่ออ้างถึงคุณสมบัติที่โครงร่างการเข้ารหัสอาจส่งผลให้เกิดข้อความเข้ารหัสปลอมใน $\mathcal{C}_1$
Marc Ilunga avatar
tr flag
ฉันขอแนะนำให้เพิ่ม CPA เวอร์ชันนี้ในคำถามอย่างชัดเจน เป็นที่น่าสังเกตว่านี่ไม่ใช่แนวคิด CPA มาตรฐานและดูเหมือนว่าจะเป็นข้อกำหนดที่เข้มงวดเกินไปตัวอย่าง CTR มีข้อพิสูจน์สำหรับ CPA มาตรฐาน แต่ไม่เป็นไปตามแนวคิด CPA ที่ไม่ได้มาตรฐานนี้
Score:1
ธง ng

ใช่คุณถูก.

คำถามของฉันไม่มีคำจำกัดความอย่างเป็นทางการของ IND-CPA ที่นี่ ฉันใช้คำว่า "IND-CPA" อย่างไม่เป็นทางการเพื่ออ้างถึงคุณสมบัติที่โครงร่างการเข้ารหัสอาจส่งผลให้เกิดข้อความรหัสเทียมเทียมใน $\คณิตศาสตร์แคล{C}_1$

แน่นอนว่านี่เป็นข้อสันนิษฐานที่หนักแน่นกว่าการเป็น IND-CPA แต่การชี้ประเด็นนี้เป็นเรื่องน่าเบื่อ จริงๆ สมมติฐานนี้เขียนได้เป็น

$\mathsf{Enc}_k$ เป็นครอบครัว PRF

บางทีการคิดเกี่ยวกับเรื่องนี้ในแง่ของ PRFs อาจตรงไปตรงมากว่า ดังนั้นฉันจะแสดงให้เห็นอย่างรวดเร็วว่าถ้า $F_k, G_k$ เป็น (รายบุคคล) PRF แล้ว $(ฟ_ก, ก_ก)$ ไม่จำเป็นต้องเป็น เช่น การแบ่งปันคีย์ PRF สามารถทำลายความปลอดภัยได้ นี่เป็นเพราะการพึ่งพาระหว่างองค์ประกอบด้านซ้ายและด้านขวาตามที่คุณคาดเดา

อนุญาต $F_k$ เป็น PRF และให้ $G_k = F_k^{\circ 2}$, เช่น. $G_k(x) = F_k(F_k(x))$. มันง่ายที่จะเห็นว่า $G_k$ เป็น (รายบุคคล) เป็น PRF --- ความแตกต่างใด ๆ สำหรับมันหมายถึงความแตกต่างสำหรับ $F_k$เนื่องจากคุณสามารถเลียนแบบการเข้าถึงแบบสอบถามได้อย่างมีประสิทธิภาพ $G_k$ ให้การเข้าถึงแบบสอบถามเพื่อ $F_k$.

ตอนนี้, $(F_k, F_k^{\circ 2})$ ไม่ใช่ PRF นี่เป็นเพราะได้รับคำพยากรณ์ $\mathcal{O}(\cdot)$ ไม่ว่าจะเป็นเรื่องจริงหรือเรื่องบังเอิญ คุณก็ทำได้

  1. $(y_1, y_2)\gets \mathcal{O}(x)$,
  2. $(z_1, z_2) \gets \mathcal{O}(y_1)$,
  3. เดา REAL ถ้า $y_2 = z_1$และ RANDOM มิฉะนั้น

ถ้า $\mathcal{O}(x) = (F_k(x), F_k^{\circ 2}(x))$ เป็น PRF ของคุณแล้ว $y_2 = F_k^{\circ 2}(x)$, และ $z_1 = F_k(y_1)= F_k(F_k(x)) = F_k^{\circ 2}(x)$ ชนกัน ในเกมสุ่ม ความน่าจะเป็นของค่าสองค่าใด ๆ ที่ชนกันนั้นค่อนข้างน้อย ดังนั้นสิ่งนี้จึงแสดงถึงความแตกต่างที่ค่อนข้างดีในทันที

มีปัญหาเฉพาะหน้ามากขึ้นแม้ว่า วิธีหนึ่งในการสร้าง $\mathsf{Enc}_k(ม)$ เป็นของ XORing $m$ ด้วย PRF เป็นต้น $\mathsf{Enc}_k(m) = (r, F_k(r)\oบวก ม)$. นี่เป็นเพียงโหมดตัวนับแบบสุ่ม (โดยที่ข้อความเป็นบล็อกเดียว) ในการตั้งค่านี้การก่อสร้างร่วมกันคือ $(m_1,m_2)\mapsto (r, F_k(r)\oplus m_1, F_k(m_2))$. อีกครั้งโดยการสอบถาม $(m_1, m_2)$แล้วสอบถาม $(m_3, r)$หนึ่งสามารถรับความแตกต่างที่มีประสิทธิภาพ นี่คือสิ่งก่อสร้างตามธรรมชาติ (ที่ $\mathsf{Enc}$ เป็นโหมดตัวนับแบบสุ่ม) ก็ไม่ปลอดภัยในการตั้งค่าของคุณเช่นกัน

X. G. avatar
in flag
ขอบคุณมากสำหรับตัวอย่างโดยละเอียด!
us flag
หรือเพียงแค่ $F=G$
Mark avatar
ng flag
@Mikero เป็นตัวอย่างที่น่าสนใจกว่ามาก เนื่องจากแสดงให้เห็นว่า $F, G$ เป็น PRF แยกกันนั้นไม่เพียงพอที่จะแสดงว่า $(F, G)$ เป็นแม้แต่ "PRF ที่อ่อนแอ" ซึ่งหมายความว่าฝ่ายตรงข้ามสามารถแยกแยะ $ (F_k(x), G_k(x))$ จากการสุ่ม แม้ว่า $x$ จะถูกสุ่มเลือก แทนที่จะเลือกฝ่ายตรงข้าม ฉันไม่สามารถแสดงสิ่งนี้โดยใช้ตัวอย่างในคำตอบของฉัน

โพสต์คำตอบ

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