Score:0

PRG จากฟังก์ชัน OW

ธง jp

กำหนดฟังก์ชัน OW $f:\{0,1\}^n\to\{0,1\}^n$ ด้วยคำกริยาที่ไม่ยอมใครง่ายๆ $h(x)$คุณสามารถสร้าง PRG $G$ โดยการตั้งค่า $$G(s):=f(s)\Vert h(s), \quad s\leftarrow\{0,1\}^n.$$ เงื่อนไขการขยายตัวสำหรับ $G$ พอใจเล็กน้อย (เมล็ด $s$ มีความยาว $n$ในขณะที่สตริง $f(s)\Vert h(s)$ มีความยาว $n+1$). ฉันจะแสดงได้อย่างไร $G$ ยังเป็น pseudorandom อีกด้วย นั่นคือสำหรับตัวแยกความแตกต่างของเวลาหลายตัวที่น่าจะเป็น $\คณิตศาสตร์ D$ $$\mid\Pr[\mathcal D(G(s)=1]-\Pr[\mathcal D(r)=1]\mid\le\epsilon(n), \quad r\leftarrow \{0, 1\}^{n+1} $$ ที่ไหน $\epsilon(n)$ เป็นหน้าที่เล็กน้อยของ $n$?

jp flag
@kelalaka ขออภัยความคิดเห็นของคุณเกี่ยวกับคำถามที่ถูกลบของฉัน (ความจำเป็นของข้อกำหนดแบบครั้งเดียวสำหรับแผ่นแบบครั้งเดียว) หรือไม่ ถ้าเป็นเช่นนั้น ฉันพบคำตอบที่น่าพอใจแล้ว
kelalaka avatar
in flag
ยินดีต้อนรับสู่ Cryptography.SE. มักจะค้นหาก่อนแล้วจึงถาม วิธีการทั่วไปสำหรับคำถามประเภทนี้ถือว่ามีตัวแยกความแตกต่างสำหรับ $G$ จากนั้นมีตัวแยกสำหรับ $f$ เช่นกัน
jp flag
@kelalaka คุณช่วยอธิบายเพิ่มเติมได้ไหม
Chris Peikert avatar
in flag
ไม่เพียงพอที่ $f$ จะเป็น *ฟังก์ชัน* แบบทางเดียว แต่เพียงพอสำหรับการเป็น *การเรียงสับเปลี่ยน* แบบทางเดียว (เช่น Bijection)

โพสต์คำตอบ

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