سرفصل‌ها درس 133 از 156 · فناوری حریم خصوصی فراتر از مسدودسازی
فناوری حریم خصوصی فراتر از مسدودسازی

ریاضیاتی که لازم دارید

چرا مهم است ابزارهای حریم خصوصی این ماژول، مثل پیدا کردن مشتریان مشترک بدون مبادلهٔ فهرست‌ها یا انتشار آمارهایی که از تک‌تک افراد محافظت می‌کنند، بر سه تکهٔ کوچک ریاضی استوارند. به مدرک ریاضی نیازی ندارید. به حساب ساعتی، درکی از احتمال، و این ایده نیاز دارید که نویز تصادفی در گروه‌های بزرگ همدیگر را خنثی می‌کند. این درس دقیقاً همین‌ها را به شما می‌دهد، همراه با پایتون برای امتحان کردن.

1. حساب ساعتی

ساعت 22:00 است. 5 ساعت بعد ساعت چند است؟ 27:00 نیست: ساعت دور می‌زند، پس 03:00 است. شما 22 + 5 = 27 را حساب کردید و باقی‌ماندهٔ تقسیم بر 24 را نگه داشتید.

حساب پیمانه‌ای: حسابی که در آن اعداد پس از رسیدن به اندازه‌ای ثابت، یعنی پیمانه، دور می‌زنند. «27 mod 24» برابر 3 است، یعنی باقی‌ماندهٔ تقسیم 27 بر 24. در پایتون عملگر باقی‌مانده % است: 27 % 24 برابر 3 است.

دور زدن، اعداد را هر قدر هم که جمع یا ضرب کنید در اندازه‌ای ثابت نگه می‌دارد و همین آن را برای رمزنگاری مفید می‌کند. پایتون یک تابع داخلی سریع هم برای «به توان رساندن و سپس دور زدن» دارد: 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. احتمال در یک پاراگراف

احتمال عددی از 0 (هرگز) تا 1 (همیشه) است. یک سکهٔ سالم با احتمال 0.5 شیر می‌آید. وقتی دو چیز مستقل باشند، احتمال هر دو حاصل‌ضرب آن‌هاست: دو بار شیر پشت سر هم 0.5 x 0.5 = 0.25 است. مقدار مورد انتظار میانگین در بلندمدت است: یک تاس سالم را بارها بیندازید تا میانگین به 3.5 نزدیک شود.

4. نویز در جمعیت خنثی می‌شود

نویز: مقداری تصادفی که عمداً به یک مقدار واقعی افزوده می‌شود تا مقدار دقیق پنهان بماند. اگر احتمال بالا رفتن و پایین آمدن نویز برابر باشد، در میان مقدارهای زیاد میانگین آن به صفر می‌رسد.

این یک ترفند کلاسیک نظرسنجی به نام پاسخ تصادفی‌شده است. می‌خواهید بدانید چند نفر کاری شرم‌آور کرده‌اند. هر نفر پنهانی سکه‌ای می‌اندازد. شیر: راست بگوید. خط: دوباره سکه بیندازد و برای شیر «بله» و برای خط «نه» بگوید. هر «بله» به‌تنهایی ممکن است فقط کار سکه باشد، پس پاسخ هیچ‌کس چیزی را دربارهٔ او ثابت نمی‌کند.

با این حال جمع کل جمعیت هنوز مفید است. اگر نسبت واقعی 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

نویزی که در حریم خصوصی تفاضلی به کار می‌رود، یعنی نویز لاپلاس، نسخهٔ نرم‌تری از همین ایده است: معمولاً کوچک، گاهی بزرگ‌تر، با احتمال برابر به بالا یا پایین. مقیاس آن تعیین می‌کند معمولاً چقدر بزرگ باشد.

در زبان‌های دیگر

عملگر % در جاوااسکریپت برای اعداد مثبت همین‌طور کار می‌کند و اعداد بزرگ از BigInt استفاده می‌کنند (که با یک n نوشته می‌شود). توان پیمانه‌ای داخلی وجود ندارد، پس این حلقهٔ استاندارد است:

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 همین کار را می‌کند.

یک تصور نادرست رایج

«افزودن نویز داده را بی‌فایده می‌کند.» برای مقدار یک نفر، بله، و هدف هم همین است. برای یک گروه بزرگ، نویز تا حد زیادی خنثی می‌شود، پس جمع‌ها و میانگین‌ها مفید می‌مانند. فناوری حریم خصوصی در همین فاصله زندگی می‌کند: تار برای افراد، واضح برای جمعیت‌ها.

خلاصه

  • حساب پیمانه‌ای اعداد را دور یک پیمانه می‌چرخاند؛ پایتون از % و pow(b, e, m) استفاده می‌کند.
  • به توان یک عدد مخفی رساندن از یک سو آسان و برگرداندنش عملاً ناممکن است، و ترتیب دو توان مخفی اهمیتی ندارد.
  • احتمال‌های مستقل در هم ضرب می‌شوند؛ مقدار مورد انتظار میانگین بلندمدت است.
  • نویز تصادفی افراد را پنهان می‌کند اما در گروه‌های بزرگ خنثی می‌شود، و پاسخ تصادفی‌شده همین‌طور کار می‌کند.

مشکلی در این درس دیدید؟ گزارشش کنید · دربارهٔ این درس بپرسید

این تمرین به‌زودی باز می‌شود

درس پیش از آن را تمام کنید تا این یکی باز شود. کل دوره رایگان است، حساب کاربری لازم نیست، و می‌توانید همین الان این درس را بخوانید.