⚡ electrical engineering

Deterministic Johnson--Lindenstrauss Projections from Pisot $\beta$ -Transformations for Zero-Knowledge Private Routing

تقدم هذه الورقة إسقاط جونسون-ليندسترائس حتميًا ومتوافقًا مع تقنيات المعرفة الصفرية، مشتقًا من تحويلات بيتا (Pisot $\beta$ -transformations)، والذي يلغي الحاجة إلى العشوائية المكلفة داخل الدائرة عبر استخدام بذرة عامة واحدة لتحقيق تباين خالٍ من الأبعاد وقابلية إعادة إنتاج دقيقة في الحقل المحدود مع الحفاظ على المسافات الزوجية.

المؤلفون الأصليون: I. Dey, I. Cherkaoui

نُشر 2026-08-14

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: I. Dey, I. Cherkaoui

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل عالماً تكون فيه حياتك الرقمية عبارة عن سلسلة من المصافحات السرية. أنت تريد أن تثبت لـ "حارس بوابة" أنك تنتمي إلى نادٍ متميز دون إظهار هويتك، أو تثبت للبنك أن لديك مالاً كافياً دون الكشف عن رصيدك. هذا هو سحر "براهين المعرفة الصفرية" (Zero-Knowledge Proofs - ZK): وهي طريقة لقول "أنا أعرف السر" دون أن تهمس بالسر نفسه أبداً. ولكن هنا تكمن المشكلة: لكي تثبت أنك تنتمي إلى المجموعة الصحيحة، غالباً ما تكون هويتك الرقمية عبارة عن سحابة ضخمة ومعقدة من الأرقام (متجه عالي الأبعاد). والتحقق مما إذا كانت هذه السحابة تطابق قائمة كبار الشخصيات يشبه محاولة العثور على حبة رمل محددة في جبل؛ فهذا يتطلب الكثير من قوة الحاسوب والوقت لدرجة أنه يبطئ كل شيء.

لحل هذه المشكلة، يستخدم العلماء خدعة تسمى إسقاط "جونسون-ليندسترأس" (Johnson-Lindenstrauss - JL). فكر في الأمر كآلة تصوير سحرية تقوم بضغط منحوتة ثلاثية الأبعاد ضخمة وتحويلها إلى ظل مسطح ثنائي الأبعاد. ومن المذهل أنه إذا قمت بضغطها بشكل صحيح تماماً، فإن المسافات بين النقاط في الظل تظل كما هي تماماً كما كانت في المنحوتة الأصلية. وهذا يجعل مهمة "الحارس" سهلة وسريعة. ومع ذلك، هناك عقبة: الطريقة القياسية لتشغيل آلة الضغط هذه تتضمن رمي نرد رقمي. فالآلة عشوائية، ولكي تثبت أنك لم تحِد عن البروتوكول، عليك أن تثبت أنك رميت النرد بشكل صحيح. وهذا الإثبات ثقيل جداً لدرجة أنه يلغي كل السرعة التي اكتسبتها من ضغط البيانات. نحن بحاجة إلى آلة ضغط ثابتة، عامة، ولا تحتاج إلى رمي نرد لإثبات عدالتها.

يقدم هذا البحث طريقة جديدة لبناء تلك الآلة باستخدام نوع خاص من الرياضيات يسمى "تحويلات بيزوتا $\beta$ " (Pisot $\beta$ -transformations).

التشبيه: فكر في قطعة من العجين. أنت تقوم بمدها (الضرب في رقم $\beta$ ) ثم طيها فوق نفسها (أخذ الباقي). هذه عملية "فوضوية"؛ فإذا بدأت بنقطتين من العجين متشابهتين تقريباً، فستنتهي بهما الحال بسرعة في أماكن مختلفة تماماً. هذه الفوضى رائعة عادةً لتشفير البيانات، لكنها سيئة جداً للحواسيب التي تحتاج إلى الاتفاق على النتيجة.
المشكلة مع الفوضى العادية: إذا حاول حاسوبان محاكاة عملية التمدد والطي هذه، فإن الاختلافات الطفيفة في رياضياتهما (مثل أخطاء التقريب) ستؤدي إلى تباعدهما بسرعة. قد يعتقد أحد الحاسوبين أن العجين في الموقع (أ)، بينما يعتقد الآخر أنه في الموقع (ب). لا يمكنهما الاتفاق على المصفوفة.
سحر "بيزو": يستخدم المؤلفون نوعاً خاصاً من الأعداد يسمى "عدد بيزو" (مثل النسبة الذهبية 1.618، أو العدد البلاستيكي 1.325). لهذه الأعداد خاصية جبرية خاصة: على الرغم من أن العملية فوضوية، إلا أنه يمكن حساب "المدار" (المسار الذي يسلكه العجين) بدقة باستخدام مجموعة محدودة من القواعد.
- النتي نتيجة: يمكن لحاسوبين تشغيل نفس محاكاة "التمدد والطي" والحصول على نفس النتيجة تماماً، بت-بِت (bit-for-bit)، دون أي أخطاء تقريب. إنه مثل امتلاك وصفة تعمل بشكل مثالي سواء استخدمت ملعقة خشبية أو معدنية، طالما اتبعت الخطوات.

ما وجدوه

أثبت الفريق أن هذه المصفوفة الحتمية تعمل بجودة تضاهي المصفوفات العشوائية، ولكن مع بعض المزايا الرئيسية:

تحافظ على المسافات: لقد أثبتوا رياضياً أن البيانات "المضغوطة" تحتفظ بالمسافات بين النقاط كما هي تقريباً من الأصل. والخطأ (الانحياز) ضئيل ولا يزداد سوءاً حتى لو أصبحت البيانات ضخمة.
سريعة ورخيصة: بما أن المصفوفة ثابتة وعامة، فلا يحتاج الحاسوب لقضاء وقت في إثبات أنه تم إنشاؤها بعدالة. إنه فقط يستخدم الوصفة المتفق عليها مسبقاً.
قابلة لإعادة الإنتاج: لقد أظهروا أنه بينما تتطلب الخريطة الفوضوية العامة (مثل "الخريطة اللوجستية" الشهيرة) كمية هائلة من الذاكرة للحساب بدقة (تنمو بشكل أسي)، فإن خريطة "بيزو" تتطلب فقط كمية صغيرة وثابتة من الذاكرة (تنمو بشكل خطي).
- الاختبار: في عمليات المحاكاة، قارنوا طريقتهم في "بيزو" بست طرق قياسية أخرى، بما في ذلك مصفوفات غاوس العشوائية والخرائط الفوضوية الأخرى.
- النتيجة: طابقت طريقة "بيزو" الجودة الإحصائية للمصفوفات العشوائية تماماً. كان "الضجيج" في القياس هو نفسه، وكانت القدرة على توجيه الرسائل بشكل صحيح متطابقة. في الواقع، وجدوا أن "بذرة" عامة واحدة (نقطة البداية للعجين) يمكن أن تحافظ على المسافات لجميع أزواج المراكز في قائمة كبيرة.

العقبة (والمستقبل)

المؤلفون واضحون جداً بشأن ما حققوه وما لم يحققوه بعد.

ما تم إثباته: لقد أثبتوا رياضياً أن الانحياز صغير وأن التباين (الضجيج) يعمل بشكل جيد. وقد أثبتوا وجود بذرة جيدة ويمكن العثور عليها من خلال البحث.
ما تم قياسه: أجروا عمليات محاكاة تظهر أن الطريقة تعمل بكفاءة مماثلة للطرق العشوائية في الممارسة العملية، دون أي فقدان في الدقة.
ما يزال مفتوحاً: يعترفون بأنه بينما يعتقدون أن الطريقة أفضل مما يوحي به إثباتهم الحالي (تتطلب ذاكرة أقل للقوائم الكبيرة)، إلا أنهم لم يثبتوا تماماً "متباينة التركيز" (concentration inequality) التي من شأنها ضمان ذلك لأي مدخلات ممكنة، بل فقط لمجموعة المراكز المحددة التي يحمونها.

لماذا هذا مهم؟

هذا ليس مجرد لغز رياضي؛ إنه مفتاح لجعل الذكاء الاصطناعي الخاص أمراً عملياً. حالياً، إذا كنت تريد توجيه حالة طبية خاصة إلى متخصص أو التحقق من عملية دفع دون الكشف عن التفاصيل، فإن "الإثبات" يستغرق دقائق وجيغابايت من البيانات. مع هذا الإسقاط الحتمي الجديد، يقترح المؤلفون أنه يمكننا تقليص ذلك الوقت إلى ثوانٍ وحجم البيانات إلى كيلوبايتات، كل ذلك مع الحفاظ على ضمانات الخصوصية صلبة تماماً.

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

ملخص تقني: إسقاطات جونسون-ليندسترأوسس الحتمية من تحويلات بيتا (β) من نوع بيسوت (Pisot) لأجل التوجيه الخاص في المعرفة الصفرية

1. بيان المشكلة

في أنظمة إثبات المعرفة الصفرية (ZK) للتوجيه الخاص، يجب على المبرهن (prover) أن يثبت أن تضمين الرسالة $v \in \mathbb{R}^d$ ينتمي إلى فئة دلالية مسموح بها محددة بمجموعة من المراكز العامة $C = \{c_1, \dots, c_N\}$ . يتم القيام بذلك عادةً عبر اختبار أقرب مركز، وهو ما يتطلب $O(Nd)$ من القيود الحسابية. ونظرًا لأبعاد التضمين الحديثة ( $d \in [768, 4096]$ )، فإن عدد هذه القيود يهيمن على حجم الإثبات ووقت المبرهن.

العلاج القياسي هو استخدام إسقاط جونسون-ليندسترأوسس (JL) لتقليل البعد إلى $m \ll d$ . ومع ذلك، فإن مصفوفات JL الكلاسيكية عشوائية. وفي سياق المعرفة الصفرية، فإن استخدام مصفوفة عشوائية يجبر الدائرة (circuit) على الالتزام بالمصفوفة وإثبات عملية أخذ العينات الخاصة بها، مما يعيد تقديم التكلفة الحسابية التي كان الهدف من الإسقاط التخلص منها. علاوة على ذلك، تتطلب المصفوفات العشوائية إثبات عملية أخذ العينات، مما يخلق خطر تسريب المعلومات. التحدي يكمن في بناء مصفوفة إسقاط عامة، وحتمية، وثابتة تحقق:

الحفاظ على المسافات الزوجية بشكل مثبت.
أن تكون متوافقة أصلياً مع الحقل المحدود (finite field) الخاص بالدائرة.
لا تتطلب أي عشوائية داخل الدائرة أو إثباتات لأخذ العينات.

2. المنهجية

يقترح المؤلفون بناء مصفوفة الإسقاط $A$ من المدار المعياري لتحويل بيتا ( $\beta$ -transformation) من نوع "بيسوت" (Pisot).

الخريطة: خريطة تحويل $\beta$ هي $T_\beta x = \beta x - \lfloor \beta x \rfloor$ على الفترة الوحدة، حيث $\beta > 1$ هو عدد بيسوت (وهو عدد صحيح جبري تكون مرافقه الجالوا تقع تماماً داخل قرص الوحدة، مثل النسبة الذهبية).
الديناميكيات: الخريطة هي نظام فوضوي حتمي من نوع "التمدد والطي" (stretch-and-fold) يمتلك مقياس باري (Parry measure) فريد $\mu$ . والأهم من ذلك، نظرًا لأن $\beta$ هو عدد بيسوت، فإن مؤثر النقل (transfer operator) للخريطة يمتلك فجوة طيفية (spectral gap)، مما يؤدي إلى اضمحلال الارتباطات بين الملحوظات هندسياً ( $|r_k| \le C\theta^k$ ).
بناء المصفوفة:
- يتم اختيار بذرة عامة $x_0$ .
- يتم تثبيت فجوة أخذ عينات $g$ لضمان أخذ العينات بعد زمن الارتباط.
- يتم ملء مدخلات المصفوفة $A_{ij}$ بالتتابع بقيم المدار المعيرة $z_p = \psi(T_\beta^{pg} x_0)$ .
- الإسقاط هو $\Phi(v) = Av/\sqrt{m}$ .
قابلية التكرار في الحقل المحدود: على عكس الخرائط الفوضوية العامة، تضمن خاصية "بيسوت" إمكانية إعادة إنتاج المدار بدقة في حقل محدود ثابت. وتكلفة توليد $k$ خطوة هي خطية في $k$ (تحديداً $O(k \log_2 \beta)$ بت)، بينما تتطلب الخرائط الفوضوية العامة (مثل خريطة لوجستية) نمواً أسياً في عدد البتات ( $O(2^k)$ ) للحفاظ على الحسابات الدقيقة.

3. المساهمات الرئيسية

يقدم البحث أربع مساهمات نظرية وعملية رئيسية:

حدود الانحياز والتباين المستقلة عن البعد:
- الانحياز (Bias): يثبت المؤلفون أن انحياز مُقدّر التربيع المعياري محكوم بحد يتضاءل هندسياً مع فجوة أخذ العينات $g$ ، وبشكل مستقل عن البعد المحيط $d$ (التمهيدية 1). وقد استُمد ذلك من الفجوة الطيفية لخريطة $\beta$ ، مما يوفر ضماناً أقوى من حجج التوزيع المتساوي القياسية.
- التباين (Variance): يظهرون أن تباين المُقدّر يتناسب مع $V_0/m$ . ومن الأهمية بمكان أنه تحت فرضية التركيز المعلنة، فإن الثابت $V_0$ هو مستقل عن البعد (لا ينمو مع $d^2$ )، على عكس الحدود الفجة التي تشير إلى $O(d^2)$ . وهذا يعني أن بُعد الإسقاط $m$ الثابت يكفي بغض النظر عن مدى كبر $d$ .
وجود بذرة عامة واحدة:
- يثبت المنظر 1 وجود بذرة عامة واحدة $x_0$ تحافظ على جميع المسافات الزوجية لـ $\binom{N}{2}$ من المراكز ضمن نطاق $(1 \pm \varepsilon)$ .
- يمكن العثور على هذه البذرة عبر بحث خارجي (offline) فعال. وبمجرد العثور عليها، تصبح المصفوفة ثابتة، عامة، ولا تتطلب التزاماً بالعشوائية أثناء إثبات المعرفة الصفرية.
قابلية التكرار الدقيقة عبر خاصية بيسوت:
- يحدد البحث أن خاصية بيسوت (وليس مجرد الفوضى العامة) هي الأساسية للنشر في المعرفة الصفرية. فهي تضمن إمكانية إعادة إنتاج المدار بدقة في حقل محدود ثابت بتكلفة لكل خطوة تبلغ $\log_2 \beta$ ، بينما تفشل الخرائط الفوضوية العامة بسبب النمو الأسي المطلوب للدقة (المقامات) لتجنب التباعد في الحسابات.
المتانة والبحث:
- تم توفير نصف قطر متانة مغلق وصالح للتحقق (التمهيدية 1)، والذي يحدد أقصى اضطراب يمكن أن تتحمله الاستعلامات دون تغيير أقرب مركز مسقط لها.
- البحث عن البذرة غير مشروط (مضمون بحدود التباين) ولكن يمكن تحسينه ليعتمد لوغاريتمياً على $N$ إذا تحقق تباين محدد لمتراجحة التركيز لخريطة الفجوة الطيفية.

4. النتائج التجريبية

تم تقييم البناء مقابل ستة عمليات إسقاط قياسية: Gaussian، وRademacher، وAchlioptas sparse، وSubsampled Randomized Hadamard Transform (SRHT)، ومصفوفة متسلسلة فوضوية (Yu et al.).

الجودة الإحصائية: يطابق إسقاط "بيسوت" الجودة الإحصائية لعمليات الإسقاط العشوائية.
- معدل التباين: يتبع تباين المُقدّر قانون $1/m$ ويتداخل مع مرجع $2/m$ الخاص بـ Gaussian JL.
- الاستقلال عن البعد: يظل ثابت التباين $V_0$ مسطحاً بالقرب من 2 مع زيادة $d$ من 64 إلى 1024، مما يؤكد التنبؤ النظري المستقل عن البعد.
- التشويه (Distortion): يتتبع أسوأ تشويه نسبي للمسافات بين أزواج المراكز خط الأساس لـ Gaussian JL.
أداء المهام: في مهمة توجيه أقرب مركز مكونة من 24 فئة مع $d=256$ ، استعاد إسقاط "بيسوت" دقة بنسبة 100% عند $m=32$ (ضغط بمقدار 8 أضعاف)، وهو ما يماثل الطرق الأخرى.
قابلية التكرار: أكدت المحاكاة أن التنفيذات ذات الفاصلة العائمة تتباعد عن المدارات الدقيقة بعد حوالي 50-70 خطوة (مطابق لتوقعات ليابونوف)، بينما يظل التمثيل $\beta$ -adic لـ "بيسوت" دقيقاً ومدمجاً (139 بت لـ 200 خطوة مقابل $1.66 \times 10^6$ بت لخريطة لوجستية).

5. الأهمية والادعاءات

يدعي البحث أن هذا البناء هو الطريقة الوحيدة التي تلبي في آن واحد ثلاثة متطلبات حرجة للتوجيه الخاص في المعرفة الصفرية:

خالٍ من العشوائية داخل الدائرة: لا حاجة للالتزام بالمصفوفة العشوائية أو إثبات أخذ العينات منها.
قابل لإعادة الإنتاج بدقة في حقل محدود ثابت: تم تحقيق ذلك عبر خاصية "بيسوت" بتكلفة لكل خطوة تبلغ $\log_2 \beta$ ، مما يتجنب تكلفة $O(2^k)$ للخرائط الفوضوية العامة.
متكافئ إحصائياً مع الإسقاطات العشوائية: يطابق معدل التباين وخصائص التشويه لمصفوفات JL العشوائية.

يشير المؤلفون إلى أنه بينما تم إثبات الجودة الإحصائية، فإن الخطوة النظرية لترقية حد البحث $O(N^2)$ غير المشروط إلى حد $O(\log N)$ المشروط تعتمد على متراجحة تركيز محددة للمؤثر الناقل، والتي تظل خطوة نظرية مفتوحة. عملياً، يتيح هذا الأسلوب الانتقال من دقائق/جيجابايت من توليد الإثبات إلى ثوانٍ، مما يجعل التوجيه الخاص القابل للتحقق أمراً ممكناً للمتجهات عالية الأبعاد.