تجمیع امن
چرا مهم است یک اپ تناسب اندام میخواهد کل قدمهای پیمودهشده در یک شهر را بداند؛ یک سازندهٔ صفحهکلید میخواهد بداند یک واژه در همهٔ گوشیها چند بار تایپ میشود. در هر مورد، شرکت به یک عدد از دستگاههای بسیار نیاز دارد. تجمیع امن به آن اجازه میدهد آن جمع را بفهمد بیآنکه هرگز مقدار یک فرد را ببیند، و بهطرز شگفتآوری ساده است.
رمزنگاری آموزشی، نه امن: اعداد آزمایشگاههای این ماژول آنقدر کوچکاند که خوانده شوند و تصادفی بودن بذر ثابت دارد تا نمرهدهی تکرارپذیر باشد. سیستمهای واقعی از کتابخانههای بررسیشده و اعداد بسیار بزرگتر استفاده میکنند. هرگز کد آموزشی را در یک محصول کپی نکنید.
ترفند حقوق
سه دوست میخواهند میانگین حقوقشان را بدانند بیآنکه کسی حقوق خودش را فاش کند. اولی یک عدد تصادفی بزرگ به حقوقش اضافه میکند و نتیجه را در گوش دومی زمزمه میکند. او حقوقش را اضافه میکند و زمزمه را ادامه میدهد. سومی حقوقش را اضافه میکند و آن را برمیگرداند. اولی عدد تصادفیاش را کم میکند و جمع کل بیرون میآید. هر زمزمه برای کسی که آن را شنید شبیه یک عدد تصادفی بود.
تجمیع امن: محاسبهٔ جمع (یا میانگین) مقدارهای افراد بسیار بهطوری که هیچ مقدار تکی برای هیچکس فاش نشود، حتی سروری که آنها را جمع میکند.
تسهیم راز جمعی: بریدن یک عدد مخفی به چند سهم که بهتنهایی تصادفی به نظر میرسند اما جمعشان برابر راز است. هر سهم تکی، یا هر گروهی که دستکم یک سهم را نداشته باشد، هیچ چیز دربارهٔ راز فاش نمیکند.
سهمها چگونه کار میکنند
برای تقسیم عدد 7,350 به سه سهم، دو عدد تصادفی انتخاب کنید و سومی را طوری انتخاب کنید که جمع هر سه 7,350 شود. با حساب دورزننده (پیمانهٔ M، اینجا 2 به توان 32، کمی بیش از 4 میلیارد)، هر سهم بهتنهایی عددی تصادفی با توزیع یکنواخت است:
M = 2 ** 32
s1, s2 = 3919211450, 120775123 # random
s3 = (7350 - s1 - s2) % M # whatever makes it add up
print((s1 + s2 + s3) % M) # 7350
چرا دور زدن؟ بدون آن، یک سهم گاهی منفی یا بهطرز مشکوکی نزدیک به راز میشد. با آن، هر مقدار سهم، صرفنظر از اینکه راز چه باشد، به یک اندازه محتمل است، پس یک سهم تکی هیچ اطلاعاتی ندارد.
دستگاههای بسیار، چند سرور
حالا هر گوشی تعداد قدمهایش را به یک سهم برای هر سرور تقسیم میکند و سهم 1 را به سرور 1، سهم 2 را به سرور 2 و به همین ترتیب میفرستد. هر سرور سهمهایی را که دریافت کرده جمع میزند. جمع هر سرور هنوز تصادفی به نظر میرسد. فقط وقتی جمعهای سرورها با هم جمع شوند، جمع واقعی شهر ظاهر میشود. تا وقتی سرورها سهمهای خام یک گوشی را روی هم نگذارند، مقدار هیچ گوشیای هرگز دیده نمیشود.
نسخهٔ دنیای واقعی
سیستمهایی که برای آموزش مدلها روی گوشیهای بسیار به کار میروند (که یادگیری فدرال نامیده میشوند) از نسخهای زیرکانهتر با یک سرور استفاده میکنند: جفتهای دستگاه روی ماسکهای تصادفی توافق میکنند که وقتی همه چیز جمع شود همدیگر را خنثی میکنند، بهعلاوهٔ گامهای اضافه برای کنار آمدن با گوشیهایی که در میانهٔ کار آفلاین میشوند. ایدهٔ اصلی همان است که شما میسازید: تکههایی تصادفینما که فقط با هم معنا پیدا میکنند.
آنچه تجمیع امن انجام نمیدهد
جمع کل دقیقاً فاش میشود. اگر فقط دو نفر مشارکت کرده باشند و یکی مقدار خودش را بداند، میتواند آن را کم کند و مقدار دیگری را بفهمد. اگر خود جمع حساس است، به آن نویز حریم خصوصی تفاضلی هم اضافه کنید. این دو ابزار با هم خوب کار میکنند: تجمیع ورودیها را پنهان میکند، DP اثر هر فرد بر خروجی را پنهان میکند.
در زبانهای دیگر
تقسیم در جاوااسکریپت، با استفاده از دور زدن 32 بیتی با >>> 0 و منبع تصادفی امن مرورگر:
function split(value, n) {
const shares = Array.from(crypto.getRandomValues(new Uint32Array(n - 1)));
const sum = shares.reduce((a, b) => (a + b) >>> 0, 0);
shares.push((value - sum) >>> 0);
return shares;
}و در Rust، جایی که wrapping_sub روی یک u32 دور زدن را برایتان انجام میدهد:
let last = value.wrapping_sub(shares.iter().fold(0u32, |a, &b| a.wrapping_add(b)));خلاصه
- تجمیع امن جمع کل را فاش میکند اما هیچ مشارکت تکی را نه.
- تسهیم راز جمعی یک مقدار را با حساب دورزننده به سهمهایی تصادفینما تقسیم میکند که جمعشان برابر آن است.
- هر سرور فقط سهمهای تصادفینما را میبیند؛ فقط همهٔ جمعهای سرورها با هم پاسخ را میدهند.
- خود جمع کل دقیقاً فاش میشود، پس وقتی جمع ممکن است کسی را افشا کند، آن را با نویز DP همراه کنید.
سه تابع بنویسید، با استفاده از M (2 به توان 32) از دنیای تمرین. split(value, n, rng) فهرستی از n سهم برمیگرداند: n - 1 تای اول از rng.randrange(M)، و آخری برابر (value - sum(shares)) % M. combine(shares) مقدار sum(shares) % M را برمیگرداند. aggregate(values, n_servers, rng) هر مقدار را با split تقسیم میکند، سهم j را به server_totals[j] اضافه میکند (به پیمانهٔ M) و تاپل (total, server_totals) را برمیگرداند که در آن total = combine(server_totals) است.
مشکلی در این درس دیدید؟ گزارشش کنید · دربارهٔ این درس بپرسید
این تمرین بهزودی باز میشود
درس پیش از آن را تمام کنید تا این یکی باز شود. کل دوره رایگان است، حساب کاربری لازم نیست، و میتوانید همین الان این درس را بخوانید.
این مرورگر کوکیهای learn.floati.life را مسدود میکند، پس درسهایی که اینجا تمام کردید نمیتوانند به ترتیب باز شوند. کوکیها را برای این سایت مجاز کنید و صفحه را دوباره بارگذاری کنید.