ในการเข้ารหัสแบบแลตทิซ ผู้คนมักจะทำงานกับ q-ary lattices เพื่อให้เราสามารถใช้ความแข็งของวิธีแก้ปัญหาจำนวนเต็มสั้น (SIS) และการเรียนรู้ด้วยข้อผิดพลาด (LWE)ฉันเห็นในบันทึกบางอย่างที่บางครั้งเราต้องการ $คิว$ เพื่อเป็นนายกรัฐมนตรีหรืออำนาจสำคัญ อย่างไรก็ตามไม่มีคำอธิบายใด ๆ ว่าเหตุใดจึงเป็นเช่นนั้น ดังนั้นฉันจึงมีคำถามสองสามข้อเกี่ยวกับการเลือก $คิว$:
ไม่ใช่คำตอบที่สมบูรณ์ แต่อาจมีประโยชน์อยู่แล้ว ...
เป็นที่รู้จักกัน ที่มีความยาวเพียงบิตแต่ไม่ใช่รูปแบบของ $คิว$ มีความสำคัญต่อการรักษาความปลอดภัยของปัญหา LWE (และ RLWE)
นอกจากนี้หากเราแก้ได้ $SIS_{n, q, \beta}$ กับ $\beta = O(q / \sigma)$แล้วเราจะแก้ได้ $LWE_{n, q, \sigma}$ (ดูข้อปฏิบัติ 2 ของ [MPS15]).
ดังนั้น อย่างน้อยก็สำหรับขอบเขตเล็กๆ ดังกล่าว $\เบต้า$ ตามบรรทัดฐานของโซลูชัน SIS รูปแบบของ $คิว$ ไม่ควรสำคัญ
ดังที่ Hilder กล่าวถึง โดยใช้เทคนิค "การสลับโมดูลัส" ทางเลือกเฉพาะของ $คิว$ ไม่สำคัญมากนักสำหรับความปลอดภัยของ LWE ดังนั้นรูปแบบเฉพาะของ $คิว$ เป็นส่วนใหญ่เพื่อให้สามารถปรับปรุงประสิทธิภาพได้ ฉันเป็นคนผิดที่เขียนรายการทั้งหมดอย่างละเอียดถี่ถ้วน แต่สามารถชี้ไปที่บางข้อได้ง่ายๆ โดยอ่านข้อเสนอของ NIST PQC KEM
ตัวอย่างเช่น:
การเลือก $q = 2^k$ สำหรับบางคน $k$ อนุญาตให้แทนที่การลดโมดูลาร์โดย $คิว$ ด้วยการเลื่อนบิต การดำเนินการที่ถูกกว่า นี่เป็นส่วนหนึ่งของเหตุผลที่เซเบอร์เลือก $q = 2^{13}$.
การเลือก $คิว$ เป็น "NTT ที่เป็นมิตร" NTT เป็นอะนาล็อกของ FFT "mod $คิว$" (กว่าจะจบ $\mathbb{C}$) ที่สามารถเปิดใช้งานการเร่งความเร็วจำนวนมากในการคูณพหุนาม (โดยประมาณจาก $O(n^2)$ ความซับซ้อนที่ไร้เดียงสา $O(n\log n)$). ขนาดของการเร่งความเร็วนั้นเชื่อมโยงโดยตรงกับการมีอะนาล็อกที่เหมาะสม $i\in\mathbb{C}$. กรณีที่ดีที่สุด (พูดเมื่อทำงานเสร็จ $\mathbb{Z}_q[x]/(x^n+1)$ สำหรับ $n = 2^k$) เกิดขึ้นเมื่อคุณมี "ดั้งเดิม $2n$รากแห่งความสามัคคี" ซึ่งเกิดขึ้นเมื่อ $q\equiv 1\bmod 2n$ (ฉันคิดว่า). โปรดทราบว่าวิธีนี้ใช้ไม่ได้กับการเพิ่มประสิทธิภาพก่อนหน้านี้ KEM Kyber เลือกตัวเลือกนี้ (เกือบจะมีความแตกต่างทางเทคนิคเล็กน้อย)
การเลือก $คิว$ เป็นผลคูณของโคไพรม์ขนาดเล็ก (ขนาดคำ) ดังนั้นใคร ๆ ก็สามารถอุทธรณ์ทฤษฎีบทเศษเหลือของจีนได้ และรักษาขนาดคำตามเลขคณิตไว้ทั้งหมด ฉันไม่รู้จัก KEM ที่ทำสิ่งนี้ แต่สิ่งนี้เป็นที่นิยมในวรรณกรรม FHE (และมักจะใช้ชื่อ "Residue Number System" หรือ RNS arithmetic)
จึงมีข้อโต้แย้งในการเลือก $q \equiv 0 \bmod 2^k$, $q\equiv 1\bmod 2\times 2^k$, และ $คิว$ ผลิตภัณฑ์จากโคไพรม์ขนาดเล็ก ทั้งหมดนี้อาจดูเหมือนเป็นการปรับให้เหมาะสมเฉพาะร่วมกัน แต่อาจค่อนข้างฉลาดและใช้การปรับให้เหมาะสมหลายรายการพร้อมกัน ตัวอย่างเช่นมี งานนี้ ในการฝังตัวดัดแปลงเลขคณิต $2^k$ (เช่น "การลดโมดูลาร์ที่เป็นมิตร") ลงในวงแหวนที่เป็นมิตรต่อ NTT ให้ใช้ทั้งการปรับให้เหมาะสม 1 และ 2
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
