Score:4

ผลกระทบของ dual sublattices ระดับต่ำต่อการโจมตี dual lattice บน LWE คืออะไร

ธง ru

ในการโจมตีตาข่ายคู่ของ Espitau, Joux และ Kharchenko (บนแนวทางแบบคู่/ไฮบริดสู่ LWE ลับเล็กๆ) ผู้เขียนเสนอความแตกต่าง (และกู้คืนค่าความลับในภายหลัง) ของตัวอย่าง LWE $(A,\mathbf ข)=(A,A\mathbf s+\mathbf จ)$ โดยการหาเวกเตอร์คู่ $(\mathbf x^T|\mathbf y^T)$ ในลักษณะที่ส่วนประกอบของเวกเตอร์มีขนาดเล็ก (โดยมีข้อยกเว้นที่เป็นไปได้ของส่วนประกอบย่อยเล็กน้อยของ $\mathbf y$) และ $\mathbf x^TA=\mathbf y^T$. กรณีนี้หาก $\mathbf ข$ มาจากการแจกแจงแบบ LWE $\mathbf x^T\mathbf b=\mathbf y^T\mathbf s+\mathbf x^T\mathbf e$ และการมีส่วนร่วมในการแสดงออกนี้จากองค์ประกอบเล็ก ๆ ของ $\mathbf x$ และ $\mathbf y$ โดยเฉลี่ยแล้วควรมีขนาดเล็กเมื่อเทียบกับเครื่องแบบ $\mathbf ข$ กรณี. ด้วยการหาเวกเตอร์คู่อิสระจำนวนมาก สิ่งนี้ควรทำให้สามารถให้คะแนนตัวอย่างได้ $\mathbf ข$ และไอเสียมากกว่าส่วนประกอบของ $\mathbf s$ เพื่อหาค่าการให้คะแนนที่น้อย

ในเอกสารล่าสุดโดยกลุ่ม MATZOV (รายงานเกี่ยวกับความปลอดภัยของ LWE ปรับปรุงการโจมตีแบบ dual lattice) มีการพิจารณารูปแบบต่างๆ ของการโจมตี EJK ซึ่งอาจมีผลกับความปลอดภัยของแผน KYBER, SABER และ DILITHIUM อนึ่ง. หนึ่งในข้อเสนอของพวกเขาคือการสร้างเวกเตอร์คู่สั้นจำนวนมากในส่วนที่ 4 ของบทความของพวกเขา พวกเขาเสนอการลดส่วนประกอบของพื้นฐานคู่ด้วยวิธี block-Korkine-Zolotarev (BKZ) พร้อมขนาดบล็อก $\beta_1$ จากนั้นใช้ตาข่าย "ร่อน" บนเวกเตอร์พื้นฐานที่ลดลงเพื่อสร้างเวกเตอร์คู่สั้นจำนวนมาก วิธีการกรองของพวกเขา จำกัด ตัวเองไว้ที่วิธีแรก $\beta_2$ เวกเตอร์ตามเกณฑ์ BKZ และแม้ว่าจะระบุว่าเวกเตอร์สามารถผลิตได้จากรีดักชันและตะแกรงหลายตัว แต่ในหมายเหตุ 4.3 พวกเขาสังเกตว่าการลดขนาดและตะแกรงเพียงครั้งเดียวดูเหมาะสมที่สุด

ซึ่งหมายความว่าเวกเตอร์คู่ทั้งหมดที่ใช้เพื่อสร้างคะแนนอยู่ในอันดับ $\beta_2$ ตารางย่อยของปริภูมิคู่ โดยสัญชาตญาณใคร ๆ ก็รู้สึกว่าถ้า $\beta_2$ มีขนาดเล็ก ดังนั้นการมีส่วนร่วมของเวกเตอร์ต่างๆ ต่อคะแนนจะไม่เป็นอิสระต่อกัน นี่จะเป็นการละเมิดสมมติฐาน 4.4 ของพวกเขา มีทฤษฏีบทหรือฮิวริสติกเกี่ยวกับขนาดอันดับย่อยที่สามารถใช้ในลักษณะนี้ในขณะที่ยังคงสร้างคะแนนที่มีประสิทธิภาพเพียงพอที่จะแยกแยะ/กู้คืนตัวอย่าง/ความลับของ LWE หรือไม่

sa flag
TMM
อาจถามคำถามที่ "ง่ายกว่า": เห็นได้ชัดว่าถ้า $\beta_2$ เป็นค่าคงที่เล็กน้อย ตัวแยกความแตกต่างจะไม่ทรงพลังอีกต่อไปเหมือนกับเมื่อเวกเตอร์ทั้งหมดถูกดึงมาจากโครงตาข่ายทั้งหมด
Score:1
ธง ru

นี่ไม่ใช่คำตอบ

ด้วยความหวังที่จะช่วยเหลือใครก็ตามที่คิดเกี่ยวกับเรื่องนี้ และในแง่ของความคิดเห็นของ @TMM ต่อไปนี้เป็นเนื้อหาเพิ่มเติมเล็กน้อยเกี่ยวกับข้อความ "โดยสัญชาตญาณ เราจะรู้สึกว่าถ้า $\beta_2$ มีขนาดเล็ก ดังนั้นการมีส่วนร่วมของเวกเตอร์ต่างๆ ต่อคะแนนจะไม่เป็นอิสระต่อกัน"

พิจารณากรณี $\beta_2=1$. ในกรณีนี้ทั้งหมดของเรา $(\mathbf x^T,\mathbf y^T)$ เวกเตอร์จะเป็นจำนวนทวีคูณของเวกเตอร์กำเนิดเดียว เช่น $\alpha(\mathbf x_0^T,\mathbf y_0^T)$ กับ $\alpha$ บางที Gaussian ที่ไม่ต่อเนื่องขึ้นอยู่กับจำนวนเวกเตอร์ ตอนนี้มี $q^{n-1}$ เวกเตอร์ $\mathbf v$ ดังนั้น $\mathbf x_0^T\cdot\mathbf v=0$. พิจารณาเวกเตอร์ของแบบฟอร์ม $\mathbf v+\mathbf e$ ที่ไหน $\mathbf อี$ มาจากการแจกแจงแบบเดียวกับตัวอย่าง LWE เราคาดว่าบางที $O(\sigma^nq^{n-1})$ เวกเตอร์ดังกล่าว (เวกเตอร์ที่มีการแสดงสองตัวดังกล่าวควรหายาก) และสำหรับขนาดใหญ่ $n$ เราอาจคาดหวังว่าสิ่งเหล่านี้จะครอบคลุมพื้นที่ส่วนใหญ่ คะแนนของเวกเตอร์ดังกล่าวกำหนดโดย $\alpha\mathbf x_0^T\mathbf e$ และให้คะแนนของการแก้ปัญหาเชิงสาเหตุโดย $\alpha(\mathbf x_0^T\mathbf e+\mathbf y_0^T\mathbf s)$. ช่องว่างของเวกเตอร์เชิงสาเหตุจะแยกไม่ออก

โดยทั่วไปสำหรับ $\beta_2=k$ คงจะมีพื้นฐานของ $k$ $(\mathbf x_i^T,\mathbf y_i^T)$ เวกเตอร์ที่มีชุดทดสอบของเราเกิดจากการรวมเชิงเส้นของเวกเตอร์พื้นฐานโดยที่ค่าสัมประสิทธิ์คือ Gaussian (?) อีกครั้งจะมีชุดของ $q^{n-k}$ เวกเตอร์ $\mathbf v$ ตั้งฉากกับทั้งหมด $\mathbf x_i^T$ และอาจจะเป็นย่านของ $O(\sigma^nq^{n-k})$ ของเวกเตอร์ที่ไม่เป็นสาเหตุของการให้คะแนนต่ำ

นี่ดูเหมือนจะแนะนำว่า $\beta_2$ ควรเป็นอย่างน้อย $n\log \sigma/(\log q)$แต่อาจมีชุดเชิงโครงสร้างอื่นๆ ที่ไม่ใช่เชิงสาเหตุ เช่นเดียวกับคะแนนต่ำที่ไม่ใช่เชิงโครงสร้าง ในทำนองเดียวกัน ข้อโต้แย้งสำหรับการขาดการทับซ้อนกันในละแวกใกล้เคียงและระหว่างชุดเชิงสาเหตุถือเป็นแนวทางที่ดีที่สุด

โพสต์คำตอบ

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