รูปแบบ BGV และ BFV สำหรับการดำเนินการกับจำนวนเต็ม

BGV (Brakerski-Gentry-Vaikuntanathan, 2012) เป็นรูปแบบ FHE แบบมีระดับชั้นที่สร้างบน RLWE รองรับการบวกและการคูณโดยพลการบนข้อความธรรมดาจำนวนเต็มที่จัดแพ็ก คำว่า «แบบมีระดับชั้น» หมายถึงรองรับวงจรที่มีความลึกสูงสุดคงที่ L โดยไม่ต้องใช้การบูตสแตรป

BGV และ BFV เข้ารหัสข้อความธรรมดาเป็นพหุนามใน Z_t[x]/(x^n+1) โดยที่ t เป็นมอดูลัสข้อความธรรมดาขนาดเล็ก (เช่น t=65537) พหุนามแต่ละตัวเข้ารหัสค่าจำนวนเต็ม n ค่า โดยมีหนึ่งค่าต่อสัมประสิทธิ์ การคำนวณบนข้อความเข้ารหัสจะดำเนินการกับค่าทั้ง n ค่าพร้อมกัน ซึ่งเป็นการประมวลผลแบบขนานด้วย SIMD

BGV ลดสัญญาณรบกวนด้วยการเปลี่ยนมอดูลัส: หลังการคูณแต่ละครั้ง มอดูลัสข้อความเข้ารหัส q จะลดจาก Q_L เป็น Q_{L-1} การดำเนินการนี้แบ่งสัญญาณรบกวนด้วย Q_L/Q_{L-1} ทำให้สัญญาณรบกวนยังอยู่ในขอบเขตที่ถอดรหัสได้ ความลึกของวงจร L สอดคล้องกับระดับมอดูลัสจำนวน L ระดับ

BFV (Brakerski/Fan-Vercauteren, 2012) คล้ายกับ BGV แต่ใช้กลยุทธ์จัดการสัญญาณรบกวนที่ต่างกัน คือไม่ขึ้นกับมาตราส่วน BFV ไม่จำเป็นต้องเปลี่ยนมอดูลัส แต่จะปรับมาตราส่วนข้อความเข้ารหัสใหม่หลังการคูณ ซึ่งทำให้การนำไปใช้เรียบง่ายกว่า และมีการใช้งานใน Microsoft SEAL

ด้วยทฤษฎีบทเศษเหลือจีนบนวงแหวนข้อความธรรมดา ข้อความเข้ารหัสแต่ละชุดสามารถเก็บค่าจำนวนเต็มอิสระได้ n/2 ค่า (ช่อง) การดำเนินการบวกข้อความเข้ารหัสจะบวกค่าทั้ง n/2 คู่แบบขนาน การคูณจะคูณค่าทุกคู่ ปริมาณงาน: การดำเนินการจำนวนเต็ม n/2 ครั้งต่อการดำเนินการข้อความเข้ารหัสหนึ่งครั้ง

หลังจากคูณข้อความเข้ารหัสดีกรี 1 สองชุด ผลลัพธ์จะเป็นดีกรี 2 (มี 3 องค์ประกอบ) การทำให้เป็นเชิงเส้นใหม่ใช้กุญแจประเมินผล (กุญแจทำให้เป็นเชิงเส้นใหม่) เพื่อแปลงกลับเป็นดีกรี 1 โดยแลกกับสัญญาณรบกวนที่เพิ่มขึ้น ขั้นตอนนี้จำเป็นต้องทำหลังการคูณทุกครั้ง

from seal import EncryptionParameters, scheme_type, SEALContext, KeyGenerator, Encryptor, Evaluator, Decryptor parms = EncryptionParameters(scheme_type.bfv) parms.set_poly_modulus_degree(4096) parms.set_coeff_modulus(CoeffModulus.BFVDefault(4096)) parms.set_plain_modulus(PlainModulus.Batching(4096, 20))

การหมุนข้อความเข้ารหัสจะเลื่อนช่องข้อความธรรมดา n/2 ช่องแบบวนรอบ มีประโยชน์สำหรับ: การลดรูปด้วยการหาผลรวม (สะสมค่าทุกช่องให้เหลือช่องเดียว) การคูณเมทริกซ์กับเวกเตอร์ (หมุนและสะสม) และการคอนโวลูชัน (เลื่อนและคูณ) จำเป็นต้องใช้กุญแจ Galois (กุญแจการหมุนที่คำนวณไว้ล่วงหน้า)

BFV ที่มี n=8192: การบวกประมาณ 10 µs การคูณประมาณ 5 ms (พร้อมการทำให้เป็นเชิงเส้นใหม่) การบูตสแตรป (หากจำเป็น): 30-60 วินาที กลุ่มจำนวนเต็ม 4096 ค่า: เฉลี่ยแล้วประมาณ 1 µs ต่อจำนวนเต็มต่อการคูณหนึ่งครั้ง ไม่เหมาะสำหรับการทำงานแบบเวลาจริง แต่ใช้ได้กับการวิเคราะห์แบบออฟไลน์

การเลือก n และ q: SEAL แนะนำ n=4096 สำหรับความปลอดภัย 128 บิต โดยมี Q < 2^109 และ n=8192 สำหรับวงจรขนาดใหญ่ มาตรฐาน HE (homomorphicencryption.org) มีตารางพารามิเตอร์ให้ใช้งาน ควรใช้พารามิเตอร์ที่แนะนำเสมอ — การเลือกค่าเองอาจบั่นทอนความปลอดภัยได้ง่าย

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

BGV และ BFV ดำเนินการเลขคณิตจำนวนเต็มที่เข้ารหัสโดยใช้ RLWE การเข้ารหัสแบบกลุ่มช่วยให้ประมวลผลแบบขนานด้วย SIMD BGV ใช้การเปลี่ยนมอดูลัส ส่วน BFV ใช้การไม่ขึ้นกับมาตราส่วน การทำให้เป็นเชิงเส้นใหม่จะคืนค่าดีกรีหลังการคูณ ถัดไป: CKKS สำหรับเลขคณิตโดยประมาณและการเรียนรู้ของเครื่อง