คุณสามารถ. มีข้อแม้บางประการที่ควรกล่าวถึงที่นี่ --- ความแข็งของปัญหา LWE ถูกควบคุม (บางส่วน) โดยขนาดของโมดูลัส $คิว$.
ระบอบพารามิเตอร์ที่สำคัญสองประการคือ $คิว$ สิ่งมีชีวิต พหุนามขนาดใหญ่ ในพารามิเตอร์ความปลอดภัยและ โพลิโนเมียลขนาดใหญ่.
โมดูลัสที่เล็กกว่านั้นดีกว่าสำหรับทั้งประสิทธิภาพและความปลอดภัย
ฉันคิดว่าเมื่อเร็ว ๆ นี้เรามี PRF โมดูลัสพหุนามจาก LWE ดูตัวอย่าง นี้.
จนกระทั่งกระดาษนั้น สิ่งนี้นำไปสู่สถานการณ์ตลกที่เราสามารถสร้างสิ่งต่าง ๆ เช่น FHE ที่ปรับระดับจากสมมติฐานโครงตาข่ายที่อ่อนแอกว่าสิ่งที่เราต้องการในการสร้าง PRF
สำหรับซุปเปอร์โพลี $คิว$ แม้ว่าจะมีโครงสร้างที่เรียบง่าย
กระดาษแผ่นนี้ เป็นข้อมูลอ้างอิงที่ดี
แนวคิดหลักคือตัวอย่าง LWE $(a, \langle a,s\rangle + e)$ เป็นการสุ่มหลอก ดังนั้นจึงน่าจะเป็นพื้นฐานสำหรับ PRF
หากมีใครพยายามเขียนผู้สมัครตามธรรมชาติ เช่น:
$$F_s(a) = \langle a,s\rangle + e\bmod q$$
มีสองปัญหาที่ชัดเจน:
นี่เป็นเพียง pseudorandom ถ้า $a$ เป็นแบบสุ่ม (ดังนั้นนี่คือ "PRF ที่อ่อนแอ" แทนที่จะเป็น PRF --- เป็นเพียงการเข้ารหัสแบบดั้งเดิมที่แตกต่างกันเล็กน้อย)
$F_s(ก)$ เป็นฟังก์ชันสุ่ม --- ข้อผิดพลาด $e$ จะต้องสุ่มเลือก
คุณสามารถแก้ไขปัญหาที่สองนี้ได้โดยการปัดเศษให้เป็นค่าทวีคูณที่ใกล้ที่สุด $p$เช่น การเขียน $F_s'(a) = \lfloor \langle a,s\rangle + e\rceil_p$.
โดยมีเงื่อนไขว่า $q/p$ มีขนาดใหญ่พอ สุ่มเลือกของ $e$ จะส่งผลกระทบต่อผลลัพธ์สุดท้ายเพียงเล็กน้อยเท่านั้น ดังนั้นเราอาจเขียนฟังก์ชัน (กำหนด) ได้เช่นกัน $F_s'(a) = \lfloor \langle a,s\rangle\rceil_p$.
หรืออีกทางหนึ่ง สามารถเห็นได้ว่าเป็น PRF ที่อ่อนแอซึ่งสร้างขึ้นจาก เรียนรู้ด้วยการปัดเศษ ข้อสันนิษฐาน
หากต้องการ "อัปเกรด" PRF ที่อ่อนแอเป็น PRF มาตรฐาน เราสามารถทำให้คีย์เป็นได้ $(A, S_1, \จุด, S_k)$และกำหนด
$$F_{A, S_1,\dots, S_k}(x_1,\dots,x_k) = \left\lfloor A\prod_{i =1}^k S_i^{x_i}\right\rceil_p.$$
ที่ไหน $x_i\in\{0,1\}$, และ $A, S_1,\จุด, S_k$ เป็นองค์ประกอบแบบวงแหวนหรือเมทริกซ์ที่มีขนาดเหมาะสมเพื่อให้นิพจน์เหมาะสม
นี่คือการก่อสร้างที่ทำในกระดาษแผ่นที่สองในส่วนที่ 5
สรุป:
- ใช่ เราสามารถสร้าง PRF จากปัญหา LWE/lattice
- การทำอย่างมีประสิทธิภาพ (จากโมดูลัสขนาดเล็ก) นั้นยากอย่างน่าประหลาดใจ แต่ตอนนี้รู้แล้วว่าต้องทำอย่างไร (ดูบทความแรก)
- การดำเนินการจากปัญหา LWR นั้นง่ายตามแนวคิด แต่เราสามารถยึดความปลอดภัยของปัญหา LWR จากปัญหา LWE สำหรับโมดูลัสขนาดใหญ่เท่านั้น