DOI: https://doi.org/10.62056/av7t7ta5v
تاريخ النشر: 2026-01-08
المؤلف: Qi Wei
الموضوع الرئيسي: قابلية الحوسبة، المنطق، خوارزميات الذكاء الاصطناعي
نظرة عامة
في هذه الورقة، يقوم المؤلفون بالتحقيق في المجمعات الإيجابية المضافة، والتي تم تصميمها للحفاظ على ملخص مضغوط لمجموعة متزايدة مع السماح بإثبات العضوية من خلال الشهود المتولدين. إنهم يثبتون وجود مقايضة كبيرة بين طول بت المجمع وتكرار تحديثات الشهود. على وجه التحديد، يظهرون أنه إذا كان طول بت المجمع في حدود $\text{poly}(\log n)$، حيث يمثل $n$ عدد القيم المجمعة، فإن بعض القيم ستتطلب $\Omega\left(\frac{\log n}{\log \log n}\right)$ تحديثات للشهود. هذه النتيجة تحسن من الحد الأدنى السابق البالغ $\omega(1)$ الذي تم تأسيسه في [BCCK25] وتتوافق مع الحد الأعلى المقدم في [MQ23].
علاوة على ذلك، يبني المؤلفون على إطار العمل الخاص بـ [MQR22] لتقديم هيكل تركيبي جديد يلغي الحاجة إلى فرضية زمن التحديث الثابت. تمتد منهجيتهم أيضًا إلى التشفير القائم على التسجيل [GHMR18]، مما يعالج بشكل فعال مشكلة مفتوحة من [MQR22] من خلال تأكيد أن الحد الأدنى الضيق على تكرار تحديث فك التشفير يستمر دون قيود زمن التحديث الثابت. في الختام، يتحقق المؤلفون من الادعاء 4 من خلال بناء تسلسلات خطوات متساقطة معيارية على الرسوم البيانية الأمامية الناتجة عن دالة التحديث $\text{NeedUpd}_\lambda$، مما يكشف عن مجموعة فرعية كبيرة $C \subseteq \text{List}_n(X)$ ذات خصائص هيكلية موحدة ضرورية لضمان اتساق البادئة في تحليلهم.
مقدمة
تناقش مقدمة هذه الورقة البحثية مخطط مجمع تشفيري يولد ملخصًا مضغوطًا، يُشار إليه بقيمة المجمع، لمجموعة من القيم \( S = \{x_1, \ldots, x_n\} \). التركيز هو على المجمعات الإيجابية، التي تسمح لأعضاء المجموعة بإثبات إدراجهم باستخدام الشهود. تفحص الورقة بشكل خاص المجمعات الإيجابية المضافة الديناميكية، حيث يمكن أن تنمو المجموعة \( S \) مع مرور الوقت، مما يتطلب تحديثات لقيمة المجمع وشهود العضوية مع إضافة عناصر جديدة. يؤكد المؤلفون على أهمية الحفاظ على الكثافة في قيمة المجمع، مما يضمن أن يبقى طول بتها أصغر بكثير من عدد القيم المجمعة، أي \( |acc_n| = o(n) \).
تقدم هذه الفقرة أيضًا نظرية رئيسية بشأن صحة مخطط المجمع، والتي تنص على أنه إذا كانت دالة الدرجة \( d(n) \) للمجمع تلبي \( d(n) = o(n) \)، فهناك خصم قادر على كسر الصحة باحتمالية غير ضئيلة. يستنتج من هذه النظرية حد أدنى على درجة التحديثات المطلوبة للصحة، مما يشير إلى أنه إذا كانت دالة الطول \( \ell(\lambda, n) \) متعددة الحدود في \( \log n \)، فإن \( d(n) \) يجب أن تنمو على الأقل بنفس سرعة \( \Omega\left(\frac{\log n}{\log \log n}\right) \). يشير المؤلفون إلى أنه بينما توفر تحليلاتهم رؤى كبيرة حول صحة المجمعات الإيجابية المضافة، فإن النتائج تسلط الضوء أيضًا على القيود في استبعاد بعض الحالات الحدودية لدالة الدرجة.
نقاش
تتوسع فقرة النقاش في الورقة حول بناء وكفاءة المجمعات التشفيرية، مع التركيز بشكل خاص على أشجار ميركل وقابليتها للتوسع من خلال مجموعة من الأشجار. تواجه أشجار ميركل التقليدية، على الرغم من فعاليتها للمجموعات الثابتة، تحديات مع الإضافات الديناميكية، مما يتطلب إعادة بناء كاملة لكل عنصر جديد. تتضمن الحل المقترح الحفاظ على عدة أشجار فردية يتم دمجها عندما تكون بنفس الارتفاع، مما يؤدي إلى قيمة مجمع مضغوطة بطول بت قدره $\text{poly}(\log n)$ ويتطلب في أقصى حد $O(\log n)$ تحديثات للشهود لكل عنصر عبر $n$ إضافة.
تناقش الورقة أيضًا آثار هذا الهيكل في سياق التشفير القائم على التسجيل (RBE)، حيث يتم تحديث المعلمات العامة مع تسجيل المستخدمين. تعتبر المساهمة الكبيرة هي إنشاء حدود ضيقة على تكرار تحديثات فك التشفير، والتي يتم إظهار أنها صحيحة حتى عندما تعتمد أوقات التحديث على هويات ومفاتيح المستخدمين المسجلين. يقدم المؤلفون هيكل تركيبي جديد، وهو تسلسل الخطوات المتساقطة، والذي يسمح بإزالة فرضية زمن التحديث الثابت مع الحفاظ على نفس الحدود الدنيا الأسيمتوتية كما في الأعمال السابقة. لا تحل هذه التقدمات فقط المشكلات المفتوحة في هذا المجال، بل توفر أيضًا إطارًا قويًا قابلًا للتطبيق على كل من المجمعات الإيجابية المضافة وRBE، مما يظهر مقايضة بين طول المجمع وتحديثات الشهود تكون ضيقة وذات أهمية للبناءات التشفيرية المستقبلية.
DOI: https://doi.org/10.62056/av7t7ta5v
Publication Date: 2026-01-08
Author(s): Qi Wei
Primary Topic: Computability, Logic, AI Algorithms
Overview
In this paper, the authors investigate additive positive accumulators, which are designed to maintain a compact digest of an expanding set while allowing for the proof of membership through generated witnesses. They establish a significant trade-off between the bit-length of the accumulator and the frequency of witness updates. Specifically, they demonstrate that if the accumulator’s bit-length is on the order of $\text{poly}(\log n)$, where $n$ represents the number of accumulated values, then certain values will necessitate $\Omega\left(\frac{\log n}{\log \log n}\right)$ witness updates. This finding improves upon the previous lower bound of $\omega(1)$ established in [BCCK25] and aligns with the upper bound presented in [MQ23].
Furthermore, the authors build on the framework of [MQR22] to introduce a novel combinatorial structure that eliminates the need for a fixed-update-time assumption. Their methodology also extends to Registration-based Encryption [GHMR18], effectively addressing an open problem from [MQR22] by confirming that the tight lower bound on decryption-update frequency persists without the fixed-update-time constraint. In conclusion, the authors validate Claim 4 by constructing canonical falling-step sequences on forward graphs induced by the update function $\text{NeedUpd}_\lambda$, revealing a significant subset $C \subseteq \text{List}_n(X)$ with uniform structural properties that are essential for ensuring prefix-consistency in their analysis.
Introduction
The introduction of this research paper discusses a cryptographic accumulator scheme that generates a compact digest, referred to as the accumulator value, for a set of values \( S = \{x_1, \ldots, x_n\} \). The focus is on positive accumulators, which allow members of the set to prove their inclusion using witnesses. The paper specifically examines dynamic additive positive accumulators, where the set \( S \) can grow over time, necessitating updates to the accumulator value and membership witnesses as new elements are added. The authors emphasize the importance of maintaining compactness in the accumulator value, ensuring that its bit-length remains significantly smaller than the number of accumulated values, i.e., \( |acc_n| = o(n) \).
The section also introduces a key theorem regarding the soundness of the accumulator scheme, which states that if the degree function \( d(n) \) of the accumulator satisfies \( d(n) = o(n) \), then there exists a polynomial-time adversary capable of breaking the soundness with a non-negligible probability. A corollary derived from this theorem establishes a lower bound on the degree of updates required for soundness, indicating that if the length function \( \ell(\lambda, n) \) is polynomial in \( \log n \), then \( d(n) \) must grow at least as fast as \( \Omega\left(\frac{\log n}{\log \log n}\right) \). The authors note that while their analysis provides significant insights into the soundness of additive positive accumulators, the results also highlight limitations in ruling out certain boundary cases of the degree function.
Discussion
The discussion section of the paper elaborates on the construction and efficiency of cryptographic accumulators, particularly focusing on Merkle trees and their scalability through a collection of trees. Traditional Merkle trees, while effective for static sets, face challenges with dynamic additions, necessitating a complete rebuild for each new element. The proposed solution involves maintaining multiple singleton trees that are merged when of equal height, resulting in a compact accumulator value with a bit-length of $\text{poly}(\log n)$ and requiring at most $O(\log n)$ witness updates for each element across $n$ additions.
The paper also addresses the implications of this structure in the context of Registration-based Encryption (RBE), where public parameters are updated as users register. A significant contribution is the establishment of tight bounds on the frequency of decryption updates, which are shown to hold even when update times depend on the identities and keys of registered users. The authors introduce a new combinatorial structure, the falling-step sequence, which allows for the removal of the fixed-update-time assumption while maintaining the same asymptotic lower bounds as previous works. This advancement not only resolves open problems in the field but also provides a robust framework applicable to both additive positive accumulators and RBE, demonstrating a trade-off between accumulator length and witness updates that is both tight and significant for future cryptographic constructions.