تقاطع المجموعات الخاصة
لماذا هذا مهم غالبا ما ترغب الشركات في معرفة العملاء المشتركين بينها، لتقديم عرض مشترك أو لقياس مدى نجاح إعلان ما. الطريقة السهلة هي تبادل قوائم العملاء، وهذا يعني وصول بريدك الإلكتروني إلى قاعدة بيانات شركة أخرى. تتيح تقنية Private Set Intersection لهم العثور على التقاطع دون أن يقدم أي طرف قائمته. معرفة كيفية عملها تتيح لك التمييز بين الخصوصية الحقيقية وبين عبارة "لقد شاركنا رسائل البريد الإلكتروني المشفرة فقط".
تعليم التشفير، ليس للأمن: الأرقام في مختبرات هذه الوحدة صغيرة بما يكفي للقراءة والعشوائية مزروعة بحيث يكون التقييم قابلا للتكرار. تستخدم الأنظمة الحقيقية مكتبات معتمدة وأرقاما أكبر بكثير. لا تنسخ كود التعليم أبدا في منتج.
المشكلة
يحتوي كل من متجرA وتطبيق على قائمة من رسائل البريد الإلكتروني للعملاء. يريدان الحصول على رسائل البريد الإلكتروني الموجودة في كلتا القائمتين both فقط، ولا شيء آخر: يجب ألا يعرف المتجر مستخدمي التطبيق الآخرين، ويجب ألا يعرف التطبيق عملاء المتجر الآخرين.
تقاطع المجموعات: العناصر المشتركة بين قائمتين. تقاطع المجموعات الخاصة (PSI): طريقة تمكن طرفين من حسابه دون كشف أي معلومات أخرى عن قوائمهما.
لماذا تفشل طريقة "فقط قم بعمل hash"
Hash: دالة تحول النص إلى تشفير بطول ثابت (SHA-256 هو أحد الأنواع الشائعة). نفس المدخلات تعطي دائما نفس المخرجات، ولا يمكنك تشغيلها بشكل عكسي مباشرة.
"نحن نقوم بتبديل رسائل البريد الإلكتروني المشفرة، لذا لا يرى أحد الرسائل الحقيقية" يبدو أمراً آمناً. لكن رسائل البريد الإلكتروني يمكن تخمينها. يمكن لأي شخص يمتلك قائمة من رسائل البريد الإلكتروني المحتملة أن يقوم بتشفير كل تخمين والبحث عن التطابقات، مثل تجربة كل مفتاح على حلقة مفاتيح كبيرة. ستقوم وظيفة naive_reverse الخاصة بك بالضبط بذلك مع الـ 200 رسالة بريد إلكتروني الاصطناعية في عالم الممارسة. إخفاء البيانات بالتشفير ينجح فقط عندما لا يمكن تخمين المدخلات، ورسائل البريد الإلكتروني وأرقام الهواتف والأسماء يمكن تخمينها.
خدعة القفلين
تذكر من درس الرياضيات: وضع a السري، ثم b السري، يعطي نفس نتيجة b ثم a. تخيل كل بريد إلكتروني كصندوق. تضع Alice قفلها الخاص على كل من صناديقها وترسلها إلى Bob. يضيف Bob قفله ويرسلها مرة أخرى. يقوم Bob أيضا بقفل صناديقه الخاصة ويرسلها إلى Alice، التي تضيف قفلها. الآن كل صندوق يحتوي على القفلين، ويبدو الصندوقان اللذان يحتويان على نفس البريد الإلكتروني متطابقين، بغض النظر عن أي قفل وُضع أولا.
في الأرقام، مع مجموعة الممارسة من watched.leg7a_privacy (P، hash_to_group، random_secret):
- Alice ترسل
blind(alice_items, a): كل عنصر يتم تشفيره إلى المجموعة ثم رفعه إلىa.
يقوم - Bob برفع تلك القيم إلى
b(reblind) ويرسلها مرة أخرى بنفس الترتيب.
يرسل - Bob
blind(bob_items, b). - ترفع Alice قيم Bob إلى
a. أي من قيمها ذات القفل المزدوج التي تظهر في مجموعة Bob ذات القفل المزدوج هي عنصر مشترك. لأنها حافظت على الترتيب، فهي تعرف أي عنصر من عناصرها يمثله كل واحد منها.
لماذا هذا آمن حيث فشل hashing؟ لاختبار تخمين، تحتاج إلى كلا الأسرار، وكل جانب يحتفظ بسره الخاص. يرى Bob فقط قيم Alice مع وجود سرها، والتي تبدو كأرقام عشوائية.
Diffie-Hellman PSI: اسم هذا البروتوكول، بعد فكرة تبادل المفاتيح لعام 1976 التي يستعيرها (طرفان يدمجان أسسًا سرية). تستخدم الإصدارات الحقيقية المنحنيات الإهليلجية (نوع مختلف من المجموعات، مع نفس خاصية "الترتيب لا يهم" وأرقام أقصر بكثير) وتجزئة دقيقة.
الإجابة هي في حد ذاتها كشف
تخبر PSI المثالية تماما أليس بأن شخصا معينا هو عميل لبوب. إذا كان بوب عيادة أو مستشار ديون، فهذا أمر حساس. غالبا تحتاج الشركة فقط إلى كم عدد العملاء المشتركين. في PSI cardinality يقوم بوب بخلط رده في الخطوة 2، لذا يمكن لأليس عد المطابقات ولكن لا يمكنها معرفة لأي من عناصرها تنتمي. اطلب الحد الأدنى الذي يجيب على السؤال.
في لغات أخرى
الخطوة المبهرة في JavaScript باستخدام BigInt (باستخدام مساعد powMod مثل الذي في درس الرياضيات):
const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));وفي لغة Go مع math/big:
func reblind(values []*big.Int, secret, p *big.Int) []*big.Int {
out := make([]*big.Int, len(values))
for i, v := range values {
out[i] = new(big.Int).Exp(v, secret, p)
}
return out
}للمنتجات الحقيقية، استخدم مكتبة PSI مدققة بدلا من كتابة مكتبتك الخاصة.
ملخص
- من السهل عكس رسائل البريد الإلكتروني المشفرة باستخدام قائمة من التخمينات، لذا فإن عبارة "لقد شاركنا فقط الهاشات" لا تعني الخصوصية.
- يقوم Diffie-Hellman PSI بقفل كل عنصر مرتين باستخدام سرين لا يهم ترتيبهما، لذا تظهر المطابقات دون الكشف عن أي قائمة.
- الحفاظ على الترتيب يكشف عن العناصر المطابقة؛ أما العشوائية (PSI cardinality) فتكشف فقط عن العدد.
- تعتبر نقطة التقاطع بيانات شخصية بحد ذاتها، لذا اطلب الحد الأدنى الذي يجيب على السؤال.
اكتب خمس دوال. تعيد naive_reverse(hashes, candidates) القائمة المرتبة للمرشحين الذين يقع ملخص SHA-256 السداسي (hashlib.sha256(c.encode()).hexdigest()) الخاص بهم في hashes. تعيد blind(items, secret) القيمة [pow(hash_to_group(x), secret, P) for x in items]. تقوم reblind(values, secret) برفع كل قيمة إلى secret بمقياس P مع الحفاظ على الترتيب. تتبع psi(alice_items, bob_items, a_secret, b_secret) الخطوات الأربع للدرس باستخدام blind و reblind، وتعيد القائمة المرتبة لعناصر Alice التي يملكها Bob أيضاً. تقوم psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) بنفس الشيء ولكنها تخلط رد Bob باستخدام rng.shuffle وتعيد فقط عدد العناصر المشتركة.
سيفتح هذا التمرين قريبا
أنهِ الدرس السابق ليفتح هذا الدرس. الدورة كاملة مجانية، ولا تحتاج إلى حساب، ويمكنك قراءة هذا الدرس الآن.
يقوم هذا المتصفح بحظر ملفات تعريف الارتباط لـ learn.floati.life، لذا لا يمكن فتح الدروس التي أنهيتها هنا بالترتيب. اسمح بملفات تعريف الارتباط لهذا الموقع وأعد التحميل.