เหตุใดพารามิเตอร์ (เช่น โมดูลัสและมิติข้อมูล) ของการเข้ารหัสแบบโฮโมมอร์ฟิกจึงมีขนาดใหญ่มาก

โมดูลัส $คิว$ และมิติ $n$ ของการเข้ารหัสแบบโฮโมมอร์ฟิกนั้นมีขนาดใหญ่มาก ตัวอย่างเช่น ใน Kyber $n=256, n \คูณ k = \{512,768,1024\}$, $q = 12289$ หรือ $3329$ในขณะที่อยู่ในแผน FV หรือ HE อื่นๆ $n$ อาจจะเป็น $2^{14}$, และ $คิว$ อาจถึง $2^{744}$. ทั้งคู่ขึ้นอยู่กับปัญหาขัดแตะ ทำไมพารามิเตอร์จึงแตกต่างกันมาก

โครงร่างที่ใช้ (R)LWE ทั้งหมดมีไซเฟอร์เท็กซ์ที่มีสัญญาณรบกวน โดยทั่วไป ถ้าสัญญาณรบกวนมีขนาดเล็กกว่าเศษส่วนของ q (เช่น น้อยกว่า q/2) การถอดรหัสจะทำงาน

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

แต่สำหรับโครงร่างโฮโมมอร์ฟิค คุณต้องการดำเนินการกับไซเฟอร์เท็กซ์ด้วย และการดำเนินการเหล่านี้จะเพิ่มสัญญาณรบกวน ดังนั้นคุณต้องเริ่มต้นด้วยสัญญาณรบกวนเล็กน้อย (เช่น หากข้อความรหัสใหม่มีสัญญาณรบกวนใกล้เคียงกับ q/4 ดังนั้นการเพิ่มเพียงครั้งเดียวจะทำให้เกิดสัญญาณรบกวน ถึง q/2 และไม่สามารถดำเนินการโฮโมมอร์ฟิคได้อีก) โดยปกติแล้ว แบบแผนจะเลือกเสียงเริ่มต้นที่จะล้อมรอบด้วยค่าคงที่เล็กๆ และเพิ่ม q เพื่อให้มีที่ว่างมากขึ้นสำหรับการเติบโตของเสียงที่เกิดจากการดำเนินการแบบโฮโมมอร์ฟิค แต่แล้วปัญหา LWE ก็ง่ายขึ้น ดังนั้นเพื่อให้ถึงระดับความปลอดภัยที่ต้องการ พวกเขาจึงต้องเพิ่มมิติ $n$.

คุณจะสังเกตเห็นว่าโครงร่างที่มีการเติบโตของสัญญาณรบกวนน้อยกว่าจะสามารถเลือกพารามิเตอร์ที่เล็กกว่ามากได้ (เช่น TFHE ใช้ $n = 2^{10}$ และ $q = 2^{32}$).