Score:0

อัตราส่วนโมดูลัสต่อสัญญาณรบกวนที่น้อยลงหมายถึงความปลอดภัยที่มากขึ้นใน LWE

ธง in

อนุญาต $\text{Adv}^{\text{DLWE}}_{n,m,q,\sigma}$ เป็นข้อได้เปรียบของผู้โจมตีในการแยกแยะตัวอย่าง LWE ออกจากเครื่องแบบ โดยที่ $m$ คือจำนวนตัวอย่าง $คิว$ โมดูลัสและ $\sigma$ ส่วนเบี่ยงเบนมาตรฐานของการแจกแจงข้อผิดพลาด

ฉันไม่พบนิพจน์ที่ชัดเจนสำหรับข้อได้เปรียบนี้

ลด $คิว$ และเพิ่มมากขึ้น $\sigma$ แสดงถึงข้อได้เปรียบที่น้อยกว่า (และความปลอดภัยที่ดีกว่า)

Score:1
ธง ng

ฉันไม่พบนิพจน์ที่ชัดเจนสำหรับข้อได้เปรียบนี้

ไม่มีเลย ทั้งนี้เพราะสอดคล้องกับสภาวะของทฤษฎีความซับซ้อนที่ว่า $\mathsf{P} = \mathsf{NP}$, และดังนั้นจึง $\mathsf{Adv}_{n,m,q,\sigma}^{\mathsf{DLWE}}$ เป็นพหุนามบางส่วนในขนาดของพารามิเตอร์ที่เกี่ยวข้อง มันคือ อีกด้วย สอดคล้องกับความคิดเกี่ยวกับการเข้ารหัสในปัจจุบันว่าไม่เป็นเช่นนั้น และสิ่งที่ก้าวร้าวกว่านั้นก็เป็นความจริง กล่าวคือ $\mathsf{Adv}^{\mathsf{DLWE}}_{n,m,q,\sigma}$ ถูกควบคุมเกือบทั้งหมดโดย $n\log คิว$และโดยเฉพาะอย่างยิ่ง:

  1. $m$ สามารถมีขนาดค่อนข้างใหญ่ได้โดยไม่กระทบต่อความปลอดภัย และ
  2. $\sigma$ ได้ค่อนข้างน้อย (ในทางทฤษฎี $\sigma = \Omega(\sqrt{n})$ เป็นสิ่งที่จำเป็นโดยทั่วไป แม้ว่าในทางปฏิบัติแล้ว $\sigma = O(1) \ประมาณ 8$ เป็นเรื่องธรรมดา)

ดังนั้นเราจะประเมินข้อได้เปรียบนี้อย่างเป็นรูปธรรมได้อย่างไร โดยทั่วไปโดย (อย่างเป็นรูปธรรม) ประเมินความทันสมัยของการโจมตีที่รู้จัก ด้วยเหตุนี้จึงมีแหล่งข้อมูลหลักสองแห่ง:

  1. ``LWE Estimator'' ของ Albrecth และคณะ เป็นที่นิยมอย่างไม่น่าเชื่อ คุณสามารถดูกระดาษเริ่มต้น ที่นี่และโมดูล sage (ล่าสุด) ที่นี่.

  2. ข้อเสนอที่เป็นรูปธรรมที่มีอยู่ของวัตถุดั้งเดิมแบบขัดแตะ ตัวอย่างเช่น ผู้เข้ารอบสุดท้ายของ NIST PQC ได้แก่ Kyber, Saber และ NTRUPrime ล้วนมีการวิเคราะห์ (ที่เป็นรูปธรรม) เพื่อพิสูจน์ตัวเลือกพารามิเตอร์ของตน สำหรับวัตถุดั้งเดิมที่หนักกว่านั้น มาตรฐานการเข้ารหัส Homomorphic มีตารางของพารามิเตอร์ที่แนะนำ ตลอดจนบทสรุปของการโจมตีที่เป็นแนวทางในการสร้างตารางเหล่านี้

ที่พูดมาทั้งหมด...

ไม่ลด $คิว$ และเพิ่มมากขึ้น $\sigma$ แสดงถึงข้อได้เปรียบที่น้อยกว่า (และความปลอดภัยที่ดีกว่า)

อย่างอื่นเท่ากันหมด คำตอบคือใช่ รับตัวอย่าง LWE $(\mathbf{A}, \vec ข)$หนึ่งโมดูลัสสามารถเปลี่ยนจาก $q\mapsto q'$ (สำหรับ $q' < q$การวิเคราะห์จะสะอาดกว่าถ้า $q' \กลาง q$ แม้ว่า). สิ่งนี้แมปค่าเบี่ยงเบนมาตรฐานของข้อผิดพลาดอย่างคร่าว ๆ จาก $\sigma \mapsto \frac{q'}{q}\sigma < \sigma$. จากนั้นสามารถเพิ่มข้อผิดพลาดนี้ให้มีค่าเบี่ยงเบนมาตรฐานได้ $\sigma' > \sigma > \frac{q'}{q}\sigma$ โดยการเพิ่ม Gaussian ที่เหมาะสม

นี่คือการบอกว่ามีการลดลงค่อนข้างง่ายจาก $\mathsf{DLWE}_{n, m, q, \sigma}\leq \mathsf{DLWE}_{n, m, q', \sigma'}$ สำหรับ $\sigma' > \sigma$ และ $q' \กลาง q$ (กรณีของ $q' < q$ ไม่ยากกว่ามาก แต่คุณต้องจัดการกับ "ข้อผิดพลาดในการปัดเศษ") ดังนั้นข้อได้เปรียบจะน้อยลง

C.S. avatar
in flag
ขอบคุณ @มาร์ค มีบทความใดบ้างที่ฉันสามารถค้นหาการลดขนาดระหว่าง DLWE สำหรับพารามิเตอร์ต่างๆ
Mark avatar
ng flag
พวกเขากระจายอยู่ระหว่างกระดาษสองสามแผ่น แนวคิดพื้นฐานสองประการคือ เมื่อกำหนดจำนวนตัวอย่าง LWE (คงที่) หนึ่งตัวอย่างสามารถสร้างได้มากขึ้น (จากข้อผิดพลาดที่ใหญ่กว่าเล็กน้อย) ในราคาถูก สิ่งนี้แสดงให้เห็นถึงขอบเขต $m$ ที่ไม่ส่งผลกระทบต่อ $\mathsf{Adv}$ มากนัก ดูส่วนที่ 5 ของ [สิ่งนี้](https://eprint.iacr.org/2020/337.pdf) สำหรับรายละเอียดบางอย่าง (แต่ผลลัพธ์มาจากก่อนหน้าบทความนี้) อีกส่วนหลักคือการวิเคราะห์การสลับโมดูลัสใน[นี้](https://web.eecs.umich.edu/~cpeikert/pubs/lwehard-old.pdf)

โพสต์คำตอบ

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