Score:0

การก่อสร้างนี้เป็น OWF หรือไม่?

ธง cn

กำหนดฟังก์ชัน OWF $f: \{0,1\}^{2\lambda} \rightarrow \{0,1\}^{2\lambda}$ และ กปปส $G: \{0,1\}^{\lambda} \rightarrow \{0,1\}^{2\lambda}$เป็นฟังก์ชันต่อไปนี้ $ฉ^*$ OWF?

\begin{จัด} f^*: \{0,1\}^{\lambda} &\to \{0,1\}^{2\lambda}\ x &\to f^*(x) = f(G(x)\oplus(0^{\lambda}||x)) \end{จัด}

ความคิดของฉันคือมีความปลอดภัยเป็นหลักเนื่องจากฟังก์ชัน $f$ เป็น OWF เอง แต่ฉันไม่สามารถพิสูจน์ได้ยิ่งกว่านั้น ฉันคิดว่าความน่าจะเป็นของการชนกันของอินพุตอาจเกี่ยวข้องด้วย แต่ก็ไม่มีอะไรมากไปกว่าสัญชาตญาณ

cn flag
คำแนะนำ: ให้ $G'$ เป็น PRG จากนั้น $G$ กำหนดเป็น $G(x_1\|x_2) = G(x_1)||x_2$ นานพอ $x_1$ ก็เป็น PRG เช่นกัน
kelalaka avatar
in flag
@แมร์ นานพอ =?
cn flag
@kelalaka เศษส่วนคงที่ใด ๆ ที่จะทำ พูด 1/2 ของความยาวอินพุตสำหรับการก่อสร้างคอนกรีต
zingiest avatar
cn flag
@Maeher ฉันควรสร้าง counterexample ด้วยคำใบ้ของคุณหรือไม่
cn flag
ที่สามารถทำงานได้
zingiest avatar
cn flag
@Maeher ฉันคิดว่าตามคำใบ้ของคุณ เราสามารถสร้างฟังก์ชันได้ $f^*(x_1||x_2) = f(G'(x_1)||x_2 \oplus (0^{\lambda}||x1||x2 ))$ และถ้าเรามี $|G'(x_1)| = \lambda + |x1|$ เรายังมีส่วนที่สองของอินพุตของ $f$ เป็นศูนย์เสมอ (เพราะ xor) ดังนั้น ความน่าจะเป็นในการค้นหาภาพล่วงหน้าของ $f^*$ จึงถูกจำกัดมากกว่าตัวเลือก $x_1$ ในกรณีนี้ แต่เราต้องการ $x_1$ ที่มากพอที่จะมี PRG... เมื่อพิจารณาจาก $|x_1|=\lambda/2$ เช่นเดียวกับในตัวอย่างของคุณ เรายังมีความเป็นไปได้ที่จะค้นหาภาพล่วงหน้าของ $2^{-\lambda /2}$ ที่ยังคงถือว่าเล็กน้อย
kelalaka avatar
in flag
คุณแน่ใจหรือไม่ว่าพารามิเตอร์ ทำ $f^*$ จาก $2\lambda$ หรือ $\lambda$ ตั้งแต่ $G$ จาก $\lambda$ นอกจากนี้ @Maeher ยังหมายถึงการเขียน $G(x_1\|x_2) = G'(x_1)||x_2$ ซึ่งเป็นโครงสร้างสำหรับตัวอย่างที่น่าสมเพช $PRG$ ถึง ....
zingiest avatar
cn flag
@kelalaka $f*$ รับอินพุตความยาว $\lambda$ ซึ่งสามารถเป็น $x_1||x_2$ แต่ฉันไม่เข้าใจว่า $G(x_1||x_2) = G'(x_1)||x_2 นั้นปลอดภัยสำหรับ $x_1$ ที่มีขนาดใหญ่เพียงพอ
cn flag
คำแนะนำ 2: OWF รับประกันได้ว่าจะกลับรายการได้ยากหากสุ่มตัวอย่างอินพุตตามการกระจายแบบสม่ำเสมอ การแจกแจงที่มีเฉพาะอินพุตที่ลงท้ายด้วยเลขศูนย์จำนวนมากนั้นอยู่ไกลมาก (และแยกแยะได้ง่ายจาก) เครื่องแบบ
zingiest avatar
cn flag
ดังนั้นฉันจึงคิดเกี่ยวกับการสร้าง OWF $f'(x) $ ที่ "โง่" ซึ่งในกรณีที่ $\lambda$ บิตสุดท้ายของอินพุตเป็น null เอาต์พุตจะเป็นเอาต์พุตเอง หรือมิฉะนั้น เอาต์พุตปกติของ $f$ ฟังก์ชันควรยังคงเป็น OWF เนื่องจากความน่าจะเป็นของการสุ่มอินพุตที่ลงท้ายด้วย $0^{\lambda}$ คือ $2^{-\lambda}$ ดังนั้นจึงถือว่าเล็กน้อย แม้ว่าผู้โจมตีจะเห็น $G'(x)\oplus(0^{\lambda}||x)$ เขาจะทำอะไรกับมันได้ เขาจะหัก $x$ ได้อย่างไร (อย่างไรก็ตาม ขอบคุณมากสำหรับความช่วยเหลือ!)
cn flag
มีวิธีอื่นสำหรับ OWF ที่จะทำตัวโง่เขลา จำไว้ว่าคุณไม่จำเป็นต้องหา $x$ คุณเพียงแค่ต้องหา *a* พรีอิมเมจ ไม่ใช่พรีอิมเมจ *เดียวกัน*
zingiest avatar
cn flag
ฉันคิดว่าฉันเข้าใจแล้ว! ฉันสร้าง OWF $f'$ ที่ส่งคืน $1^{2\lambda}$ หาก ${\lambda/2}$ บิตสุดท้ายของอินพุตคือ $0$ และเอาต์พุตของ OWF $f$ ปกติเป็นอย่างอื่น $f'$ เป็น OWF เพราะความน่าจะเป็นของการสุ่มอินพุตที่ลงท้ายด้วย $0^{\lambda/2}$ คือ $2^{-\lambda/2}$ แต่โครงสร้าง $f*$ สามารถแตกหักได้ง่ายเนื่องจาก ผู้โจมตีจะได้รับ $1^{2\lambda}$ เสมอ ดังนั้นเขาเพียงส่งภาพล่วงหน้าที่ลงท้ายด้วย $0^{\lambda/2}$ บิตเพื่อชนะเกม ถูกต้องหรือไม่?
cn flag
ตัวอย่างของคุณควรใช้งานได้ เป็นแนวปฏิบัติที่ดีที่จะเขียนหลักฐานว่า $f$ และ $G$ ที่คุณสร้างนั้นเป็น OWF และ PRG ที่ปลอดภัยตามลำดับ การโจมตีของคุณยังใช้งานได้แต่มีความเฉพาะเจาะจงเกินความจำเป็น $f^*(x_1\|x_2) = f(G(x_1\|x_2)\oplus(0^\lambda\|x_1\|x_2) = f((G'(x_1)\|x_2)\oplus( 0^\lambda\|x_1\|x_2) = f((G'(x_1)\oplus 0^\lambda\|x_1) \|0^{\lambda/2}) = 1^{2\lambda}$ ดังนั้น $f^*$ จึงเป็นฟังก์ชัน *constant* และค่า *any* $2\lambda$ เป็นพรีอิมเมจที่ถูกต้อง

โพสต์คำตอบ

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