مخططا BGV وBFV للعمليات على الأعداد الصحيحة

يُعد BGV ‏(Brakerski-Gentry-Vaikuntanathan، 2012) نظام FHE متعدد المستويات قائمًا على RLWE. وهو يدعم عمليات الجمع والضرب الاعتباطية على النصوص الصريحة الصحيحة المجمعة. ويعني وصفه بأنه متعدد المستويات أنه يتعامل مع دوائر يصل عمقها إلى مستوى ثابت L من دون عملية Bootstrapping.

يشفّر 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 مكونات. تستخدم إعادة التخطية مفاتيح التقييم (مفاتيح relin) للتحويل مجددًا إلى الدرجة 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، أي مفاتيح التدوير المحسوبة مسبقًا.

مع n=8192 في BFV: تستغرق عملية الجمع نحو 10 µs، وتستغرق عملية الضرب نحو 5 ms مع إعادة التخطية. وتستغرق عملية Bootstrapping، عند الحاجة، من 30 إلى 60 ثانية. وبالنسبة إلى دفعة من 4096 عددًا صحيحًا، يبلغ المتوسط نحو 1 µs لكل عدد صحيح في كل عملية ضرب. وهذا غير عملي للعمليات في الوقت الفعلي، لكنه مناسب للتحليلات غير المتصلة.

عند اختيار n وq، توصي SEAL باستخدام n=4096 لأمان بمقدار 128 بتًا مع Q < 2^109، واستخدام n=8192 للدوائر الأكبر. يوفر معيار HE، على الموقع homomorphicencryption.org، جداول للمعلمات. استخدم دائمًا المعلمات الموصى بها، إذ يمكن أن تؤدي الاختيارات المخصصة بسهولة إلى تقويض الأمان.

استعلامات قواعد البيانات المشفرة، مثل البحث في السجلات المشفرة من دون فك تشفيرها. التحليل الجيني الخاص، مثل حساب الإحصاءات على DNA المشفر. التجميعات المالية المشفرة، مثل جمع أرصدة الحسابات المشفرة من دون الاطلاع على أرصدة الأفراد. التقييم الآمن للنماذج.

ما التقنية التي يستخدمها BGV لإدارة نمو الضوضاء بعد عمليات الضرب؟

يجري BGV وBFV حسابات صحيحة مشفرة باستخدام RLWE. ويوفر الترميز الدفعي التوازي باستخدام SIMD. ويستخدم BGV تبديل المعامل، بينما يستخدم BFV ثبات القياس. وتعيد إعادة التخطية الدرجة إلى حالتها السابقة بعد الضرب. التالي: CKKS لإجراء العمليات التقريبية وتطبيقات تعلّم الآلة.