Score:1

แสดงว่ารหัสบล็อกที่มี CTR เป็น PRNG ที่ดี

ธง br

สมมติว่ารูปแบบการเข้ารหัสบล็อก $(KeyGen, Enc, ธ.ค.)$ มี CPA-secure แสดงว่า $CTR_{Enc_k(0^n)}$ เป็น PRNG ที่ดี

โหมดตัวนับทำงานดังนี้:

$Y_i = Enc_k(IV + f(i))$

$C_i = Y_i \bigoplus P_i = Y_i \bigoplus \{0^k\}= Y_i$

ผลลัพธ์ตรงนี้จึงเป็นเพียง $Enc_k(IV + f(i))$. ตอนนี้ PRNG ที่ดี ฉันเข้าใจว่ามันจะต้องแยกไม่ออกจากแหล่งสุ่ม สมมติว่ามันไม่ใช่ ดังนั้นหาก $X_0$ เป็นที่มาของเราและ $R$ เป็นแหล่งสุ่มอย่างแท้จริงที่เรามี $$|Pr[A(x)=0|x=X_0]-Pr[A(x)=0|x=R]|=\delta$$ และ $\เดลต้า$ เป็นสิ่งที่ไม่สำคัญ เนื่องจากเราสามารถแยกแยะเอาต์พุตได้ บล็อกจึงไม่เป็นอิสระจากกัน ดังนั้นจึงมีความสัมพันธ์บางอย่างระหว่าง $Enc_k(IV+f(i))$. ที่นี่ฉันไม่มีความคิดใด ๆ เกี่ยวกับวิธีดำเนินการต่อ ฉันเดาว่ามันขัดแย้งกับ CPA-security แต่ฉันไม่รู้ว่าจะแสดงสิ่งนี้อย่างไร

Maarten Bodewes avatar
in flag
ที่จริงแล้ว ถ้าคุณมีขนาดบล็อกเล็ก ฉันสงสัยว่า PRNG จะดีแค่ไหน เพราะคุณจะไม่มีความเป็นไปได้ที่บล็อกจะทำซ้ำ ฉันจะไม่แทงเลขเดียวกันในลอตเตอรี่ตัวนั้นอย่างแน่นอน หากคุณเรียกใช้ CTR บนรหัสบล็อกขนาด 8 ไบต์ หลังจากนั้น $2^{32}$ บล็อก / 32 GiB ของข้อมูล บล็อกหนึ่งใน $2^{32}$ จะไม่สามารถสร้างได้อีกต่อไป ฉันจะไม่เรียกว่าเป็นคุณสมบัติที่ดีสำหรับ PRNG ฉันเคยเห็นงานนี้มาก่อน และโดยส่วนตัวแล้วฉันคิดว่ามันค่อนข้างงี่เง่า พวกเขาลืมขนาดที่เล็กลงของชุดอินพุต / เอาต์พุตของการเรียงสับเปลี่ยน
Awerde avatar
br flag
@MaartenBodewes วิธีที่คุณพูด มันโง่มากจริงๆ ;) ฉันเดาว่าพวกเขาคงลืมมันไปเพราะมันไม่ใช่ประเด็นหลักที่นี่...
Maarten Bodewes avatar
in flag
ฉันไม่ได้ต่อต้านการทำให้เข้าใจง่าย แต่ฉันต่อต้านการมอบหมายงานหรือตัวอย่างที่พยายามและเรียนรู้บางอย่างแก่คุณ ในขณะเดียวกันก็สอนบางสิ่งที่ *ไม่ถูกต้อง* แก่คุณ ที่พยายามให้คุณเรียนรู้วิธีวิ่งขณะที่คุณยืนอยู่บนขอบหน้าผา แต่พอพูดฉันคิดว่า
Awerde avatar
br flag
@MaartenBodewes คุณบอกว่าคุณเห็นงานนี้มาก่อน บางทีคุณมีคำแนะนำอะไรให้ฉันไหม
Maarten Bodewes avatar
in flag
ฉันไม่ใช่คนที่ดีที่สุดที่จะให้คำแนะนำที่นี่ อาจเป็นเพราะการพิสูจน์อย่างเป็นทางการ ฉันจะรวมอาร์กิวเมนต์ความปลอดภัยสำหรับโหมด CTR หากปลอดภัยเนื่องจาก XOR คีย์สตรีมควรได้รับการสุ่มอย่างสมบูรณ์ แน่นอน คุณยังสามารถถือว่ามันเป็นสิ่งที่ตรงกันข้ามในข้อโต้แย้งของคุณ และพิสูจน์ว่าผิด การค้นหาอย่างรวดเร็วปรากฏขึ้น [การบรรยายนี้](https://www.csa.iisc.ac.in/~arpita/Cryptography15/CT2.pdf) พร้อมหลักฐาน CPA สำหรับ CTR
cn flag
@MaartenBodewes ข้อความนั้นเป็นจริงหรือไม่นั้นขึ้นอยู่กับบริบทที่เราไม่ได้รับ ในบริบทของคำจำกัดความความปลอดภัยเชิงซีมโทติค ข้อความนั้นถูกต้องอย่างยิ่ง ในบริบทของคำจำกัดความความปลอดภัย *รูปธรรม* จะขึ้นอยู่กับพารามิเตอร์ที่แน่นอน
cn flag
แนวคิด วิธีที่ง่ายที่สุดในการทำความเข้าใจข้อพิสูจน์คือ imho ผ่านทางชุดของการแจกแจงแบบไฮบริดเริ่มต้นด้วยการแจกแจงของคุณ $X_0$ และใช้คำจำกัดความความปลอดภัยของการเปลี่ยนรูปแบบเทียมแบบต่อเนื่อง, PRP/PRF Switching Lemma และการสังเกตว่าสำหรับฟังก์ชันสุ่มแบบสม่ำเสมอ $g : \{0,1\}^n \to \{0 ,1\}^n$, $g(0)\Vert\cdots\Vert g(N)$ กระจายอย่างสม่ำเสมอ ในที่สุดสิ่งนี้จะนำคุณไปสู่การแจกจ่าย $X_3=R$ สำหรับแต่ละขั้นตอนระหว่างทาง คุณสามารถพิสูจน์ได้ว่าการแจกแจงแยกไม่ออก จากนั้นใช้อสมการรูปสามเหลี่ยมเพื่อให้ได้ข้อความที่คุณต้องการ
Awerde avatar
br flag
ขอบคุณทั้งสอง ฉันไม่แน่ใจว่านี่คือเส้นทางที่ฉันควรทำตาม การพิสูจน์ดูเหมือนจะซับซ้อนเกินไปสำหรับงานประเภทนี้ แต่อย่างไรก็ตาม ขอบคุณ ;)

โพสต์คำตอบ

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