ใช้การดำเนินการ homomorphic กับข้อมูลเข้ารหัสขนาดใหญ่
ปัจจุบันทดลองกับการเข้ารหัส homomorphic ใช้ห้องสมุด PALISADE
ฉันต้องการใช้การดำเนินการง่ายๆของเขาเช่นการเพิ่มและการคูณกับอินพุตที่เข้ารหัสขนาดใหญ่ ตัวอย่างเช่นอินพุตA[3200]และอินพุตB[4096]ทั้งเวกเตอร์ / อาร์เรย์ของค่า int จะได้รับการเข้ารหัส ด้วยอินพุตทั้งสองนี้Enc(A)และEnc(B)ฉันต้องการใช้การคูณ:
EvalMult(Enc(A[0]), Enc(B[42]))
*0 and 42 denoting the indexes of the corresponding inputs
** no SIMD needed
เท่าที่ฉันกังวลว่าการดำเนินการตามข้อกำหนดที่อธิบายไว้ข้างต้นสามารถแก้ไขได้สองวิธี:
บรรจุอินพุตในไซเฟอร์เท็กซ์เดียว (เช่น SIMD) และสำหรับการดำเนินการของเขาฉันสามารถใช้
EvalIndexAt()เพื่อให้ได้ค่าที่ถูกต้องจากอินพุตที่เข้ารหัสเข้ารหัสแต่ละค่าจาก A และ B แยกกัน
ผมไม่แน่ใจว่าสิ่งที่ค่อนข้างของการแก้ปัญหาที่อธิบายไว้จะดีที่สุดในแง่ของประสิทธิภาพ แนวทางแรกมีความได้เปรียบที่สำคัญนี้ว่ามีเพียงหนึ่งขั้นตอนการเข้ารหัสสำหรับการป้อนข้อมูลทั้งหมดเป็นสิ่งจำเป็น แต่นี้มาพร้อมกับข้อเสียที่ฉันมักจะมีการเข้าถึงองค์ประกอบที่ถูกต้องโดยใช้EvalAtIndex()วิธีการและที่ใหญ่กว่าปัจจัยการผลิตได้รับช้ากว่าการคำนวณของEvalAtIndexKeyGen()ได้รับ (อย่างน้อยก็ในเครื่องของฉัน)
แนวทางที่สองดูเหมือนจะเหมาะสมกว่าเนื่องจากEvalAtIndex()ไม่จำเป็น แต่มาพร้อมกับค่าใช้จ่ายในการเข้ารหัสแต่ละค่าแยกกันซึ่งใช้เวลาพอสมควร
ข้อเสนอแนะความคิดใด ๆ ?
คำตอบ
ขอบคุณสำหรับคำถาม
ประโยชน์หลักของแนวทาง # 1 (SIMD) คือคุณสามารถทำการบวกและคูณเวกเตอร์ (จำนวนเต็ม / จำนวนจริงตั้งแต่ 4096 ขึ้นไป) โดยใช้การบวกหรือการคูณโฮโมมอร์ฟิกเพียงครั้งเดียว (มีประสิทธิภาพมาก) การหมุน (เรียกEvalAtIndexในภาษา PALISADE) เป็นการดำเนินการเพิ่มเติมที่อนุญาตให้หนึ่งเข้าถึงดัชนีแต่ละตัวหรือทำการสรุปที่มีประสิทธิภาพ (เช่นเดียวกับผลิตภัณฑ์ภายใน) การคูณเมทริกซ์ ฯลฯ วิธีนี้ยังมีปัจจัยการขยายตัวของไซเฟอร์เท็กซ์ที่น้อยกว่ามาก แนวทาง # 2. โดยทั่วไปตัวเลือก # 1 เป็นที่ต้องการในทางปฏิบัติ (และฉันไม่สามารถนึกถึงกรณีการใช้งานจริงใด ๆ ที่ฉันต้องการใช้ตัวเลือก # 2)
เพื่อลดต้นทุนในการคูณให้น้อยที่สุดบางทีคุณอาจบรรจุเวกเตอร์ในบล็อกที่อยู่ติดกันเพื่อที่คุณจะต้องมีการหมุนครั้งเดียวสำหรับหนึ่งบล็อก ตัวอย่างเช่น,
EvalMult(Enc(A[0:5]),Enc(B[42:47))
อีกเทคนิคหนึ่งที่คุณสามารถEvalFastRotationใช้ได้คือ(ใช้ได้เฉพาะกับ CKKS และ BGVrns ใน PALISADE v1.10.x) หากคุณต้องการการหมุนหลายรอบของการเข้ารหัสเดียวกันคุณสามารถคำนวณบางอย่างไว้ล่วงหน้าสำหรับการเข้ารหัสแล้วใช้การหมุนที่ถูกกว่า (ประโยชน์สูงสุดสำหรับการสลับคีย์ BV) - ดูhttps://gitlab.com/palisade/palisade-development/-/blob/master/src/pke/examples/advanced-real-numbers.cpp สำหรับตัวอย่าง
นอกจากนี้ยังมีวิธีลดจำนวนคีย์ที่จะสร้างหากคุณต้องการการหมุนหลายครั้ง (คำนวณเฉพาะรากที่สองของจำนวนการหมุนที่ต้องการโดยประมาณเท่านั้น) เช่นการใช้เทคนิคขั้นตอนทารก - ขั้นตอนยักษ์ที่อธิบายไว้ใน https://eprint.iacr.org/2018/244 (เทคนิคเหล่านี้สามารถนำไปใช้ในแอปพลิเคชันที่ใช้ PALISADE ของคุณ)
คุณยังสามารถใช้ลำดับพิเศษในการบรรจุเวกเตอร์ได้หากทราบรูปแบบการคูณ (วิธีนี้การหมุนของคุณจะเตรียมบล็อกหลาย ๆ บล็อกในเวกเตอร์โดยใช้การหมุนครั้งเดียว) การหมุนเป็นวัฏจักร (ล้อมรอบ) ทั้งใน CKKS และ BGVrns เมื่อสล็อต # plaintext (ขนาดแบทช์) เท่ากับring dimension/ 2 หากคุณมีเวกเตอร์ที่เล็กกว่านั้นคุณสามารถโคลน / ทำซ้ำเวกเตอร์ขนาดเล็กได้หลายครั้งตามต้องการ เติมring dimension/ 2.
โดยสรุปแล้วการปรับปรุงประสิทธิภาพครั้งใหญ่ที่สุดสามารถทำได้หากคุณคิดถึงปัญหาของคุณในแง่ของเวกเตอร์ที่เหมือน SIMD จากนั้นคุณสามารถจัดรูปแบบปัญหา / แบบจำลองของคุณใหม่เพื่อใช้ประโยชน์จากชุดเครื่องมือที่ HE มีให้อย่างเต็มที่ ในทางหนึ่งสิ่งนี้คล้ายกับการเขียนโปรแกรมโดยใช้คำสั่งแบบเวกเตอร์เช่น AVX หรือการเขียนโปรแกรมเชิงเมทริกซ์ (เช่นเดียวกับใน MATLAB)