Score:2

Enc และ Dec จำเป็นต้องเป็นฟังก์ชันสุ่มหลอกเพื่อให้โครงร่างมีความปลอดภัย CPA หรือไม่

ธง br

ขณะนี้ฉันกำลังทบทวนคำถามของรอบชิงชนะเลิศที่ผ่านมาเป็นแบบฝึกหัดสำหรับการสอบของฉัน และไม่มีคำตอบให้

คำถามที่ฉันกำลังทำอยู่คือ:

ให้ â = (Enc, Dec, Gen) เป็นรูปแบบการเข้ารหัสที่ปลอดภัยของ CPA พิสูจน์หรือหักล้าง ต่อไปนี้สองข้อความ: ก) Enc ต้องเป็นฟังก์ชันสุ่มหลอก ข) ธ.ค. ต้องเป็นฟังก์ชันสุ่มหลอก

สำหรับ ก) โดยสัญชาตญาณฉันรู้ว่ามันต้องเป็นการสุ่มหลอก แต่ฉันไม่แน่ใจว่าจะพิสูจน์อย่างเป็นทางการได้อย่างไร เนื่องจากฝ่ายตรงข้ามสามารถเข้าถึงออราเคิลเข้ารหัสได้ เราจึงต้องการให้แน่ใจว่าพวกเขาไม่สามารถแยกความแตกต่างระหว่างข้อความต่างๆ และไม่เรียนรู้ข้อมูลที่เป็นประโยชน์ใดๆ เกี่ยวกับรูปแบบ และเนื่องจากการสุ่มเทียมนั้นแยกไม่ออกจากการสุ่ม ดังนั้นจำเป็นหรือไม่?

สำหรับ b) ฉันไม่คิดว่ามันจริง เพียงเพราะบนพื้นฐานของการโจมตี CPA พวกเขาไม่เกี่ยวข้องกับการถอดรหัส ดังนั้นจึงไม่มีประโยชน์ที่จะเป็นฟังก์ชันสุ่มเทียม อย่างไรก็ตาม หาก Enc เป็น pseudorandom ก็ไม่จำเป็นต้องใช้ฟังก์ชัน pseudorandom ในการถอดรหัสใช่หรือไม่

ใครช่วยบอกฉันทีว่าความคิดนี้มาถูกทางแล้ว ถ้าไม่ใช่ โปรดให้คำอธิบาย

ขอขอบคุณ.

Morrolan avatar
ng flag
สัญชาตญาณของคุณสำหรับ a) ค่อนข้างถูกต้อง ฉันคิดว่าคุณได้ทำให้ IND-CPA-security เป็นทางการโดยใช้ 'เกม' ซึ่งเล่นโดยฝ่ายตรงข้าม หากเป็นเช่นนั้น ให้พิจารณาว่าฟังก์ชันการเข้ารหัสของโครงร่างของคุณถูกกำหนดโดยสมบูรณ์ นั่นคือ $Enc_{k}(m)$ (โดยใช้การเข้ารหัสของออราเคิล) จะให้ผลลัพธ์เดียวกันเสมอสำหรับคีย์คงที่ $k$ และข้อความ $m$ จากนั้นคุณสามารถกำหนด $A$ ของฝ่ายตรงข้ามซึ่งมีข้อได้เปรียบที่ไม่มีนัยสำคัญในการชนะเกมได้หรือไม่?
Morrolan avatar
ng flag
สำหรับ b) ให้พิจารณาว่าจะเกิดอะไรขึ้นหากฟังก์ชันการถอดรหัสของโครงร่างไม่ได้ถูกกำหนดขึ้น นั่นคือ $Dec_k(c)$ จะไม่ให้ผลลัพธ์เดียวกันเสมอไปสำหรับคีย์ตายตัว $k$ และ ciphertext $c$ โครงการดังกล่าวจะเป็นประโยชน์หรือไม่? จะมีผลอย่างไร เช่น คุณสมบัติความถูกต้องของโครงการ?
paul lacher avatar
br flag
@Morrolan เรากำหนดให้เป็น P (ความสำเร็จ)
paul lacher avatar
br flag
@Morrolan โอ้ สมเหตุสมผลสำหรับ b) ขอบคุณ!
paul lacher avatar
br flag
@Morrolan จะนำไปใช้กับการรักษาความปลอดภัย IND-CCA หรือไม่ ฉันไม่แน่ใจเพราะสำหรับ CCA ฝ่ายตรงข้ามสามารถเข้าถึงการถอดรหัสของออราเคิลได้ ธ.ค. จะต้องเป็น PRF หรือไม่ แต่นั่นไม่สมเหตุสมผลเลยเพราะเราไม่ต้องการรับข้อความที่ผิดพลาด ดังนั้น Enc จึงยังคงต้องใช้ PRF เนื่องจากในบริบทของการรักษาความปลอดภัย CCA เราเห็นการตั้งค่านี้ในการตั้งค่าคีย์สาธารณะ และถ้าไม่มีการสุ่ม ก็จะกลายเป็นการกำหนดขึ้น
Morrolan avatar
ng flag
"ถ้ามันถูกกำหนดไว้แล้ว [...] มีโอกาสมากกว่า 1/2 ที่ฝ่ายตรงข้ามจะแยกแยะความแตกต่างของข้อความธรรมดา" ใช่สวยมาก :) สำหรับข้อสอบ คุณอาจต้องการอธิบายขั้นตอนที่ $A$ ฝ่ายตรงข้ามทำ เช่น $A$ เรียกออราเคิลการเข้ารหัสด้วยวิธีใด และวิธีที่พวกเขาใช้เอาต์พุตนั้นเพื่อแยกแยะว่าข้อความเข้ารหัสที่ $c$ ได้รับนั้นเป็นการเข้ารหัสของ $m_0$ หรือ $m_1$ ที่ให้มา เมื่อทำเช่นนั้นแล้ว คุณจะสามารถระบุโอกาสที่แน่นอนที่ $A$ มีในการแยกแยะสิ่งนี้ได้อย่างถูกต้องได้อย่างง่ายดาย
Morrolan avatar
ng flag
สำหรับการรักษาความปลอดภัย IND-CCA คุณสามารถโต้แย้งแบบเดียวกับที่คุณทำกับ IND-CPA
paul lacher avatar
br flag
@Morrolan ขอบคุณ! มันช่วยให้ฉันชัดเจนขึ้นจริงๆ
Score:1
ธง in

คำแนะนำบางประการ:

ฟังก์ชันสุ่มเทียมต้องเป็น กำหนด ฟังก์ชันจากคีย์และอินพุตไปยังเอาต์พุต นอกจากนี้ ผลลัพธ์ควร “ปรากฏแบบสุ่มและเป็นอิสระต่อกัน” เมื่อคีย์ถูกเลือกแบบสุ่ม (และคงที่) และผู้โจมตีเลือกอินพุต

สำหรับ (a): ในรูปแบบการเข้ารหัสที่ปลอดภัยของ CPA Enc สามารถกำหนดได้ด้วยวิธีนี้หรือไม่ ทำไมหรือทำไมไม่?

สำหรับ (b): ในรูปแบบการเข้ารหัสที่ปลอดภัย CPA ด้วยการสุ่ม $sk$, ต้องผลลัพธ์ของ $\text{ธ.ค}_{sk}(\cdot)$ ปรากฏแบบสุ่มและเป็นอิสระเมื่อผู้โจมตีเปลี่ยนอินพุต? ทำไมหรือทำไมไม่?

paul lacher avatar
br flag
โอเค ขอบคุณ!

โพสต์คำตอบ

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