أوضح من الصفر: استعادة المعلومات الخاصة والتشفير المتماثل

هذا شرح من البداية لاسترداد المعلومات الخاصة الذي تم إنشاؤه باستخدام تشفير متماثل الشكل. أحاول أن أفترض فقط خلفية عامة في الرياضيات / الكمبيوتر. لتبسيط الأمور ، لا تتوافق تفسيراتي دائمًا مع التعريفات الأكاديمية. يمكنك التحقق من هذا العرض التوضيحي لـ Wikipedia أو مدقق رصيد Bitcoin أو الورقة أو الرمز لمعرفة المزيد. تابعنا علىSpiralPrivacy.

لنفترض أننا نريد جلب مقالة من ويكيبيديا ، ولكن بطريقة ما لا نكشف للخادم أي مقال تم جلبه.

الحل البسيط هو تنزيل ويكيبيديا بالكامل وتخزينها ؛ عندها يمكن أن تكون جميع طلباتك محلية ولا يتعلم الخادم أي شيء أبدًا. لسوء الحظ ، يتطلب هذا قدرًا كبيرًا من النطاق الترددي والتخزين (حوالي 10 غيغابايت) ، لذا فهو ليس عمليًا للغاية.

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

اتضح أنه يمكننا أن نفعل ما هو أفضل بكثير - من الممكن من خلال التشفير أن الخادم لا يمكنه معرفة أي شيء بشأن طلبك. في التشفير ، تسمى هذه المشكلة "استرجاع المعلومات الخاصة" أو "PIR". في PIR ، يريد العميل استرداد العنصر $ i $ -th من قاعدة بيانات $ n $ -elements المستضافة على الخادم ، دون الكشف عن $ i $ للخادم أو تنزيل قاعدة البيانات بأكملها. بشكل أساسي ، يجب الحفاظ على ضمان "سرية الطلب" حتى إذا كان الخادم ضارًا بشكل نشط.

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

في هذه المقالة ، سأشرح كيف يمكننا إنشاء PIR من البداية. بنهاية هذه المقالة ، سيكون لدينا 200 سطر من لغة Python الخالية من التبعية والتي تنفذ مخطط PIR (وإن كان غير فعال). محتويات أنشئ ملف PIR باستخدام تشفير متماثل

لا توفر مجموعة الأدوات القياسية لوظائف التشفير العادي والتجزئة حلاً عمليًا لـ PIR. ومع ذلك ، باستخدام نوع خاص من التشفير يسمى "تشفير متماثل الشكل" ، من الممكن الإجابة على استعلام بشكل خاص دون تنزيل قاعدة البيانات بأكملها. فيما يلي نظرة عامة عالية المستوى حول كيفية قيام العميل باسترداد العنصر $ i $ -th بشكل خاص من قاعدة بيانات $ n $ -elements؛ في مثالنا ، $ i = 3 $ و $ n = 4 $:

يقوم العميل بترميز الفهرس المطلوب $ i = 3 $ في ترميز واحد ساخن. أي أنها تُنشئ متجهًا بقيمة $ n = 4 $ بت ، حيث يكون $ i $ -th هو $ 1 $ والباقي $ 0 $. يقوم العميل بإنشاء مفتاح سري للتشفير متماثل الشكل ويستخدمه لتشفير كل بت ، مما ينتج عنه نصوص مشفرة $ n $ ، حيث يكون النص المشفر $ i $ -th هو التشفير $ 1 $ ، والباقي يتم تشفيره $ 0 $. يرسل العميل متجه البتات المشفرة هذا إلى الخادم. بالنسبة للخادم ، فإن متجه البتات المشفرة هذا عبارة عن ضوضاء عشوائية تمامًا ؛ لا يمكنه معرفة أي شيء عن البتات المشفرة. يأخذ الخادم نصوص التشفير $ n $ (كل منها يشفر قليلاً) ويضربها بشكل متماثل في عنصر قاعدة البيانات نص عادي المقابل. ينتج عن هذا إجمالي نصوص مشفرة $ n $ ، كل منها يشفر إما 0 أو عنصر قاعدة البيانات المطلوب. يقوم الخادم بإلحاق كل هذه النصوص المشفرة بشكل متجانس ، مما يؤدي إلى نص مجفر واحد يشفر عنصر قاعدة البيانات المطلوب. يرسل الخادم هذا النص المشفر الفريد إلى العميل. يفك العميل تشفير هذا النص المشفر ويحصل على عنصر النص العادي المطلوب.

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