DOI: https://doi.org/10.62056/a3n56chdj
تاريخ النشر: 2026-01-08
المؤلف: Robin Geelen وآخرون
الموضوع الرئيسي: التشفير وأمان البيانات
نظرة عامة
في هذا القسم، يقدم المؤلفون طريقة تكرارية جديدة لتحويل النصوص المشفرة من نظام BFV المعمم (GBFV) إلى نظام BFV القياسي. تبدأ الطريقة المقترحة بنص مشفر في حلقة سيكلوتومية كبيرة modulo متعددة الحدود ذات النطاق الصغير \( t(x) \) وتنتقل بشكل منهجي إلى حلقة سيكلوتومية أصغر modulo عدد صحيح أكبر بكثير \( p \). هذه التطور يتغلب على قيود طريقة التحويل التافهة المعروفة سابقًا، والتي لم تغير الحلقة السيكلوتومية الأساسية. تتيح الخوارزمية الجديدة تقريبًا بدء التشغيل الأصلي لنظام GBFV، مما يقلل بشكل كبير من العمليات المنفذة ضمن إطار BFV العادي.
يظهر المؤلفون أن نهجهم يسمح بتنفيذ تحويل الفتحة إلى معامل بالكامل ضمن نظام GBFV، على عكس الطرق السابقة التي اعتمدت على نظام BFV لهذا التحويل. تؤدي هذه الابتكار إلى تقليل نمو الضوضاء وأوقات المعالجة الأسرع مقارنة بالتقنيات الموجودة. تحقق تنفيذهم في Microsoft SEAL وقت بدء تشغيل يبلغ 800 مللي ثانية فقط للنصوص المشفرة التي تحتوي على 1024 فتحة على \( F_p \) مع \( p = 2^{16} + 1 \)، مما يمثل تحسينًا بمقدار 1.6× مقارنة بأحدث التقنيات. علاوة على ذلك، يبرز المؤلفون كفاءة بدء التشغيل في GBFV في حساب المسافات المعدلة المشفرة، مما يظهر أنها أسرع تقريبًا بمقدار مرتين من خوارزمية ليفنشتاين المعتمدة على TFHE. يُقترح العمل المستقبلي لدمج هذه الطريقة في مكتبات البرمجيات الأخرى واستكشاف تطبيقها في سيناريوهات التشفير المتجانس بالكامل (FHE) إضافية.
مقدمة
تناقش المقدمة أهمية التشفير المتجانس بالكامل (FHE) في معالجة البيانات المتوازية، مع تسليط الضوء على أنظمة مختلفة مثل BGV و BFV و CKKS التي تستخدم عمليات “تعليمات واحدة، بيانات متعددة” (SIMD) للتعامل بكفاءة مع مجموعات البيانات الكبيرة. بينما يمكن لهذه الأنظمة تعبئة الآلاف من عناصر البيانات، فإن نظام BFV المعمم (GBFV) المقترح مؤخرًا يقدم بديلاً أكثر كفاءة من خلال تقليل حجم متجه SIMD بعامل صحيح صغير $\alpha$. يسمح هذا التعديل إما بتقليل زمن الانتظار أو زيادة القدرة الحسابية، مما يجعل GBFV مفيدًا بشكل خاص في السيناريوهات التي يكون فيها التعبئة المعتدلة كافية.
يتضمن نظام GBFV إجراء بدء تشغيل لتقييم الدوائر ذات الحجم التعسفي، مع استخدام نهج هجين يجمع بين خطوات من كل من GBFV و BFV. ومع ذلك، فإن هذا التهجين يقدم عنق زجاجة في الأداء، حيث تستهلك خطوة التوسع الضوضائي، المنفذة في مجال BFV، موارد حسابية أكثر بكثير من خطوة GBFV. وبالتالي، فإن التكلفة الإجمالية لبدء التشغيل تتأثر بشدة بهذه الخطوة الأولية، مما يشير إلى الحاجة إلى تحسينات إضافية لتحسين الأداء وتقليل النفقات الحسابية.
نقاش
في هذا القسم، يناقش المؤلفون عدم كفاءة التوسع الضوضائي في مجال BFV، حيث تحتوي فقط نسبة صغيرة من الفتحات على معلومات مفيدة. يقترحون خوارزمية بدء تشغيل مبتكرة تعمل بشكل أساسي ضمن مجال GBFV، مما يحسن بشكل كبير من استخدام مساحة النصوص العادية المتاحة. تتضمن الخوارزمية الجديدة روتينًا فرعيًا للتحويل المتجانس بين الحلقات المتشابهة، مما يعزز الكفاءة الحسابية. يظهر المؤلفون أن تنفيذهم يمكنه بدء تشغيل نص مشفر يحتوي على 4096 فتحة في ثانية واحدة فقط مع الاحتفاظ بستة مستويات مضاعفة، متفوقين على الطرق السابقة.
بالإضافة إلى ذلك، يقدم المؤلفون خوارزمية خاصة بـ GBFV لحساب مسافة ليفنشتاين بين سلسلتين مشفرتين، محققين تحسينًا في الأداء يبلغ حوالي مرتين من الحل الحالي الأفضل. يوضح القسم أيضًا الجوانب الأساسية لنظام GBFV، بما في ذلك عملياته المتجانسة وترميز الفتحات العادية، مما يسهل الحساب الفعال وتحويل البيانات المشفرة. بشكل عام، تمثل الطرق المقترحة تقدمًا كبيرًا في مجال التشفير المتجانس، لا سيما في تحسين عمليات بدء التشغيل وتعزيز القدرات الحسابية.
DOI: https://doi.org/10.62056/a3n56chdj
Publication Date: 2026-01-08
Author(s): Robin Geelen et al.
Primary Topic: Cryptography and Data Security
Overview
In this section, the authors introduce a novel iterative method for converting ciphertexts from the Generalized BFV (GBFV) scheme to the standard BFV scheme. The proposed method initiates with an encrypted plaintext in a large cyclotomic ring modulo a small-norm polynomial \( t(x) \) and systematically transitions to a smaller cyclotomic ring modulo a significantly larger integer \( p \). This advancement overcomes the limitations of the previously known trivial conversion method, which did not alter the underlying cyclotomic ring. The new algorithm enables nearly native bootstrapping of the GBFV scheme, significantly reducing the operations performed within the regular BFV framework.
The authors demonstrate that their approach allows for the slot-to-coefficient transformation to be executed entirely within the GBFV scheme, contrasting with prior methods that relied on the BFV scheme for this transformation. This innovation results in reduced noise growth and faster processing times compared to existing techniques. Their implementation in Microsoft SEAL achieves a bootstrapping time of only 800 ms for ciphertexts containing 1024 slots over \( F_p \) with \( p = 2^{16} + 1 \), marking a 1.6× improvement over the state-of-the-art. Furthermore, the authors highlight the efficiency of their GBFV bootstrapping in computing encrypted edit distances, showing it to be nearly two orders of magnitude faster than the TFHE-based Levenshtein algorithm. Future work is suggested to integrate this bootstrapping method into other software libraries and explore its application in additional fully homomorphic encryption (FHE) scenarios.
Introduction
The introduction discusses the significance of fully homomorphic encryption (FHE) in parallel data processing, highlighting various schemes such as BGV, BFV, and CKKS that utilize “single instruction, multiple data” (SIMD) operations to efficiently handle large data sets. While these schemes can pack thousands of data elements, the recently proposed Generalized BFV (GBFV) scheme offers a more efficient alternative by reducing the SIMD vector size by a small integer factor $\alpha$. This adjustment allows for either reduced latency or increased computational capacity, making GBFV particularly advantageous in scenarios where moderate packing is sufficient.
The GBFV scheme incorporates a bootstrapping procedure for evaluating circuits of arbitrary size, employing a hybrid approach that combines steps from both GBFV and BFV. However, this hybridization introduces a performance bottleneck, as the noisy expansion step, executed in the BFV domain, consumes significantly more computational resources than the GBFV step. Consequently, the overall bootstrapping cost is heavily influenced by this initial step, indicating a need for further enhancements to optimize performance and reduce computational expenses.
Discussion
In this section, the authors discuss the inefficiencies of noisy expansion in the BFV domain, where only a fraction of slots contain useful information. They propose an innovative bootstrapping algorithm that operates primarily within the GBFV domain, significantly improving the use of available plaintext space. The new algorithm includes a subroutine for homomorphic conversion between isomorphic rings, which enhances computational efficiency. The authors demonstrate that their implementation can bootstrap a ciphertext of 4096 slots in just one second while retaining six multiplicative levels, outperforming previous methods.
Additionally, the authors introduce a GBFV-specific algorithm for computing the Levenshtein distance between two encrypted strings, achieving a performance improvement of approximately two orders of magnitude over the existing state-of-the-art solution. The section also outlines the foundational aspects of the GBFV scheme, including its homomorphic operations and the encoding of plaintext slots, which facilitate efficient computation and transformation of encrypted data. Overall, the proposed methods represent a significant advancement in the field of homomorphic encryption, particularly in optimizing bootstrapping processes and enhancing computational capabilities.