ทำไม RLWE ถึงยากหรือมีวิธีแก้ปัญหา?

ฉันกำลังคิดว่าเหตุใดและปัญหา RLWE จึงยากเพียงใด ฉันรู้ว่ามันยากเพราะมันสามารถลดให้เป็นปัญหาเวกเตอร์ที่สั้นที่สุดได้ แต่ฉันกำลังคิดว่ามันมีวิธีแก้ปัญหายังไง

ปัญหาคือ:

$a_{i}(x)$ เป็นชุดของพหุนามแบบสุ่ม แต่รู้จักจาก $F_q [ x ] / Φ ( x )$ ด้วยค่าสัมประสิทธิ์จากทั้งหมด $F_q$.

$e_i ( x ) $ เป็นชุดของพหุนามแบบสุ่มขนาดเล็กและไม่รู้จักสัมพัทธ์ เพื่อผูกพัน $ข$ ในวงแหวน $F_q [ x ] / Φ ( x )$.

$s(x)$ เป็นพหุนามขนาดเล็กที่ไม่รู้จักเมื่อเทียบกับขอบเขต $ข$ ใน แหวน $F_q [ x ] / Φ ( x )$.

$b_i ( x ) = ( a_i ( x ) â s ( x ) ) + e_i ( x )$

โจทย์ RLWE ประกอบด้วยการหาพหุนาม $s$ ที่ให้ไว้ $ข$ และ $a$. แต่ฉันจะทราบได้อย่างไรว่าฉันพบข้อผิดพลาด $e$ อาจเป็นอะไรก็ได้? ตัวอย่างเช่น ฉันสามารถเลือกระดับปานกลางได้ $s$ เพื่อให้ผลลัพธ์ใกล้เคียงกับ $ข$ และประดิษฐ์ใดๆ $e$ ดังนั้น $b = a.s + e$. เนื่องจาก $e$ เป็นแบบสุ่มและไม่รู้จัก อาจเป็นอะไรก็ได้ ฉันไม่มีวิธีตรวจสอบด้วยซ้ำว่าฉันพบอันที่ถูกต้องเพราะฉันไม่รู้ $e$.

มีสองประเด็นสำคัญที่คุณกำลังพูดถึง (ประเด็นหนึ่งที่ Poncho กล่าวถึงในความคิดเห็น --- ฉันพูดซ้ำที่นี่เพื่อจุดประสงค์ในการอธิบาย)

1. ข้อผิดพลาด RLWE $e_i(x)$ เป็น เล็ก, และ
2. ความลับ $s(x)$ เป็น สม่ำเสมอ ในทุกตัวอย่าง

นี่เป็นวิธีที่ค่อนข้างง่ายในการยืนยันว่าคุณได้กู้คืนข้อมูลที่ถูกต้องแล้ว $s(x)$ --- แบ่งชุดตัวอย่างของคุณออกเป็นสองส่วน กู้คืน $s(x)$ จากตัวอย่างครึ่งหนึ่งและตรวจสอบว่าเหมือนกัน $s(x)$ เป็นเช่นนั้น $a(x)s(x)\ประมาณ b(x)$ (มากถึงข้อผิดพลาด "เล็กน้อย") ในอีกครึ่งหนึ่งของตัวอย่าง ในตัวอย่างทั้งหมดคุณควรตรวจสอบว่ากู้คืนได้ $e(x) = b(x)-a(x)s(x)$ เล็ก. ฉันเชื่อว่าเทคนิคนี้เรียกว่า การตรวจสอบข้าม ในสถิติ แต่ไม่ว่าจะเรียกว่าอะไรมันก็ใช้ได้ดีเช่นกัน

มีอีกประเด็นหนึ่งที่ต้องทำ โดยขึ้นอยู่กับพารามิเตอร์ที่เลือก ซึ่งมีความเป็นไปได้สูงที่คุณจะพบว่าความลับของ RLWE นั้นไม่ซ้ำใคร (ดังนั้นคุณสามารถพิสูจน์ได้ว่าความกังวลของคุณไม่สามารถเกิดขึ้นได้ตั้งแต่แรก เมื่อมีการกำหนดพารามิเตอร์ที่เหมาะสม) ดูตัวอย่าง คำถามนี้ สำหรับรายละเอียด