الرياضيات التي تحتاجها
لماذا هذا مهم تعتمد أدوات الخصوصية في هذه الوحدة، مثل العثور على العملاء المشتركين دون تبادل القوائم أو نشر إحصائيات تحمي كل شخص، على ثلاث قطع صغيرة من الرياضيات. لا تحتاج إلى درجة في الرياضيات. أنت بحاجة إلى حسابات الساعة، وإحساس بالاحتمال، وفكرة أن الضوضاء العشوائية تلغي بعضها البعض في المجموعات الكبيرة. يقدم لك هذا الدرس هذه الأشياء بالضبط، مع Python للتجربة.
1. حسابات الساعة
إن الساعة الآن 22:00. كم تكون الساعة بعد 5 ساعات؟ ليست 27:00 لأن الساعة تعيد ضبط نفسها، لذا تكون 03:00. لقد قمت بحساب 22 + 5 = 27 وأبقيت على الباقي بعد القسمة على 24.
الحساب النمطي: حساب حيث تدور الأرقام بعد الوصول إلى حجم ثابت، وهو المقياس. "27 mod 24" هي 3، وهي الباقي بعد قسمة 27 على 24. في Python عامل الباقي هو %: 27 % 24 هو 3.
يُبقي الالتفاف الأرقام بحجم ثابت مهما جمعت أو ضربت، وهذا ما يجعله مفيداً في التشفير. ولدى Python أيضاً دالة مدمجة سريعة لـ "ارفع إلى قوة، ثم التفّ": pow(base, exponent, modulus).
print((22 + 5) % 24) # 3
print(pow(3, 4, 7)) # 3*3*3*3 = 81, and 81 % 7 = 4
print(pow(5, 200, 23)) # instant, even though 5 to the 200 is huge
2. سهلة في اتجاه واحد، صعبة في الآخر
خلط الطلاء الأصفر والأزرق لإنتاج اللون الأخضر أمر سهل. إعادة فصل الأخضر إلى اللونين الأصفر والأزرق بدقة هو أمر مستحيل عمليا. بعض الرياضيات تعمل بنفس الطريقة.
اختر معامل أولياً كبيراً ورقم P. حساب h لـ pow(h, a, P) سري هو أمر لحظي. لكن عند إعطاء الإجابة فقط، فإن إيجاد a مرة أخرى بطيء جداً للأرقام الكبيرة بما يكفي بحيث لا يمكن لأحد القيام بذلك. تسمى هذه الخاصية أحادية الاتجاه aمشكلة اللوغاريتم المنفصل..
حقيقة أخرى، وهي تدعم المختبرات التالية. الرفع إلى a ثم إلى b يعطي نفس النتيجة مثل الرفع إلى b ثم إلى a، لأن كليهما يساويان h مرفوعا للقوة a ضرب b:
P = 1019 # a small prime: fine for learning, useless for security
h, a, b = 42, 123, 456
print(pow(pow(h, a, P), b, P) == pow(pow(h, b, P), a, P)) # True
مثل قفلين على صندوق واحد، لا يهم الترتيب الذي تضعهما به. يمكن لشخصين إضافة سرهما الخاص وينتهيان إلى نفس النتيجة دون كشف أسرارهما أبدا.
3. الاحتمال في فقرة واحدة
احتماليةA هي رقم من 0 (أبدا) إلى 1 (دائما). عملة عادلة تسقط على وجه العملة باحتمالية 0.5. عندما يكون شيئان مستقلين، فإن فرصة حدوث كليهما هي حاصل الضرب: وجهان للعملة متتاليان هما 0.5 x 0.5 = 0.25. القيمة المتوقعة expected value هي المتوسط على المدى الطويل: ارمِ نردا عادلا مرات عديدة ويقترب المتوسط من 3.5.
4. يختفي الضجيج في الحشد
Noise: كمية عشوائية تضاف إلى قيمة حقيقية عن قصد، بحيث يتم إخفاء القيمة الدقيقة. إذا كانت احتمالية أن تكون الضوضاء للأعلى مساوية لاحتمالية أن تكون للأسفل، فإن متوسطها يصبح صفراً عبر قيم كثيرة.
إليك خدعة استطلاع كلاسيكية تسمى randomised response. تريد معرفة عدد الأشخاص الذين قاموا بشيء محرج. يقوم كل شخص برمي عملة معدنية سريا. وجه العملة للأعلى: أجب بصدق. وجه العملة للأسفل: ارمِ العملة مرة أخرى وأجب بـ "yes" إذا كانت للأعلى و "no" إذا كانت للأسفل. أي إجابة "yes" منفردة قد تكون مجرد نتيجة العملة، لذا لا تثبت إجابة أي شخص أي شيء عنهم.
لكن إجمالي الحشد لا يزال مفيداً. إذا كان الكسر الحقيقي هو p، فإن كسر إجابات "نعم" التي تتوقعها هو 0.5 x p + 0.25. لذا إذا قال 35% نعم، فإن p هو حوالي (0.35 - 0.25) / 0.5 = 0.2، أو 20%. كلما كبر الحشد، اقترب التقدير، لأن الضجيج العشوائي يتقلص بالنسبة للإجمالي مع نمو الحشد.
import random
rng = random.Random(1) # seeded: the same "random" numbers every run
truth = [rng.random() < 0.2 for _ in range(10000)] # 20% really did it
answers = []
for did_it in truth:
if rng.random() < 0.5:
answers.append(did_it) # heads: tell the truth
else:
answers.append(rng.random() < 0.5) # tails: random yes or no
yes = sum(answers) / len(answers)
print(round((yes - 0.25) / 0.5, 3)) # close to 0.2
الضجيج المستخدم في الخصوصية التفاضلية، والذي يسمى Laplace noise، هو نسخة سلسة من الفكرة نفسها: عادة ما يكون صغيراً، وأحياناً أكبر، وباحتمالية متساوية للأعلى أو للأسفل. يحدد scale مدى كبره عادة.
في لغات أخرى
تعمل % في JavaScript بنفس الطريقة للأرقام الموجبة، وتستخدم الأرقام الكبيرة BigInt (المكتوبة بـ n). لا يوجدت أسلوب أس modular مدمج، لذا إليك الحلقة القياسية:
function powMod(base, exp, mod) {
let result = 1n;
base %= mod;
while (exp > 0n) {
if (exp & 1n) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1n;
}
return result;
}
console.log(powMod(3n, 4n, 7n)); // 4nفي لغة Go، يقوم new(big.Int).Exp(base, exp, mod) من math/big بنفس المهمة.
A مفهوم خاطئ شائع
"إضافة الضجيج تجعل البيانات عديمة الفائدة." بالنسبة لقيمة شخص واحد، نعم، وهذا هو الهدف. بالنسبة لمجموعة كبيرة، يتم إلغاء الضجيج إلى حد كبير، لذا تظل الإجماليات والمتوسطات مفيدة. تعيش تقنية الخصوصية في تلك الفجوة: غير واضحة للأفراد، وواضحة للحشود.
ملخص
- الحساب النمطي يلف الأرقام حول مقياس معين؛ تستخدم Python الرموز
%وpow(b, e, m). - الرفع إلى قوة سرية أمر سهل في اتجاه واحد ومن المستحيل عمليا عكسه، ولا يهم ترتيب قوتين سريتين.
- تُضرب الاحتمالات المستقلة؛ والقيمة المتوقعة هي المتوسط على المدى الطويل.
- يخفي الضجيج العشوائي الأفراد لكنه يلغي بعضه البعض في المجموعات الكبيرة، وهذا هوت كيفية عمل الاستجابة العشوائية.
سيفتح هذا التمرين قريبا
أنهِ الدرس السابق ليفتح هذا الدرس. الدورة كاملة مجانية، ولا تحتاج إلى حساب، ويمكنك قراءة هذا الدرس الآن.
يقوم هذا المتصفح بحظر ملفات تعريف الارتباط لـ learn.floati.life، لذا لا يمكن فتح الدروس التي أنهيتها هنا بالترتيب. اسمح بملفات تعريف الارتباط لهذا الموقع وأعد التحميل.