Score:0

พิสูจน์ว่าฟังก์ชัน G ไม่ใช่ตัวสร้างสุ่มหลอก

ธง de

ฟังก์ชัน G(x) = x || x (โดยที่ â||â หมายถึงการต่อข้อมูลสตริง) ระบุว่า G ไม่ใช่ตัวสร้างสุ่มหลอก ใครช่วยอธิบายว่าเราจะพิสูจน์สิ่งนี้ได้อย่างไร ฉันเริ่มสับสนเล็กน้อยในแนวคิดของเครื่องกำเนิดสุ่มหลอก

สิ่งที่ฉันเข้าใจจนถึงตอนนี้ - คำจำกัดความอย่างเป็นทางการของเครื่องกำเนิดสุ่มหลอกจะได้รับเป็น $\Pr[PRG_{A,G(n)} = 1] ⤠1/2 + negl(n)$. ที่นี่เราสามารถสังเกตได้ว่าสำหรับฟังก์ชันนี้ G เอาต์พุตจะมีครึ่งแรกและครึ่งหลังเท่ากัน จะใช้สิ่งนี้กับคำจำกัดความอย่างเป็นทางการเพื่อพิสูจน์ว่า G ไม่ปลอดภัยได้อย่างไร

Maarten Bodewes avatar
in flag
ตามที่ระบุไว้แล้ว ยังคงเป็นงานที่มอบหมายโดยไม่มีข้อบ่งชี้ที่ชัดเจนถึงความพยายาม โปรด [แก้ไข] คำถามเพื่อระบุเหตุผลของคุณ ไม่จำเป็นต้องถูกต้อง แค่ต้องมี *ตรงนั้น*
Marc Ilunga avatar
tr flag
ยินดีต้อนรับสู่ Crypto.SE! วิธีการที่เป็นประโยชน์ในที่นี้คือการเขียนคำจำกัดความของ PRG และการรับประกันความปลอดภัยของวัตถุดังกล่าว จากตรงนั้น คุณอาจเห็นว่าทำไมอินสแตนซ์นี้ใช้ไม่ได้ สิ่งนี้อาจช่วยในการแก้ไขความคิดเห็นในลักษณะที่สอดคล้องกัน (ดูความคิดเห็นแรก)
archie09 avatar
de flag
ขอบคุณที่ทำให้ฉันรู้. ฉันได้แก้ไขคำถามแล้ว ขอขอบคุณสำหรับความช่วยเหลือเกี่ยวกับแนวคิดนี้
fgrieu avatar
ng flag
@archie09: คุณข้ามคำจำกัดความที่เป็นทางการของ PRG ไปมากเช่นเดียวกับโดเมนอินพุตและเอาต์พุต บางทีอาจเป็นคุณสมบัติการขยาย (บางแหล่งข้ามไป) และแน่นอนว่าบริบทของสูตร: บางอย่างที่ปรับแต่งจาก "สำหรับอัลกอริทึม Probabilistic Polynomial-Time ใดๆ $\mathcal A$ มีเล็กน้อย function $\mathrm{negl}$ such that..." ในฐานะที่เป็นผู้เยาว์ ฉันไม่รู้ว่าสูตรนี้เป็นสูตรหนึ่งในคำจำกัดความของ PRG ที่ฉันศึกษา แต่อาจเป็นไปได้ว่าฉันใช้ข้อมูลอ้างอิงอื่น
archie09 avatar
de flag
@fgrieu คุณช่วยบอกแหล่งที่มาที่ดีที่ฉันสามารถอ้างถึงคำจำกัดความนี้ได้ไหม ฉันพยายามค้นหาแต่ไม่สามารถเข้าใจแนวคิดนี้ได้อย่างถูกต้อง
Maarten Bodewes avatar
in flag
ในท้ายที่สุด คุณควรจะสามารถพิสูจน์ได้ว่าบิตในเอาต์พุตไม่มีโอกาส 0.5 + $e$ ที่จะเป็น 0 หรือ 1 ในขณะที่รวมเอาต์พุตก่อนหน้าด้วย ที่ควรจะง่ายใช่มั้ย? อย่างไรก็ตาม ฉันไม่เห็นวิธีการที่จะทำอย่างนั้นในคำจำกัดความ ดังนั้นฉันจะปล่อยให้คุณทำอย่างเป็นทางการ

โพสต์คำตอบ

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