تقاطع خصوصی مجموعهها
چرا مهم است شرکتها اغلب میخواهند بدانند کدام مشتریان را بهطور مشترک دارند، برای یک پیشنهاد مشترک یا برای سنجیدن اینکه آیا یک تبلیغ اثر داشته است. راه آسان مبادلهٔ فهرست مشتریان است، یعنی ایمیل شما در پایگاهدادهٔ شرکتی دیگر مینشیند. تقاطع خصوصی مجموعهها به آنها اجازه میدهد اشتراک را پیدا کنند بیآنکه هیچکدام فهرست خود را تحویل دهد. دانستن طرز کار آن به شما کمک میکند حریم خصوصی واقعی را از «ما فقط ایمیلهای هششده را به اشتراک گذاشتیم» تشخیص دهید.
رمزنگاری آموزشی، نه امن: اعداد آزمایشگاههای این ماژول آنقدر کوچکاند که خوانده شوند و تصادفی بودن بذر ثابت دارد تا نمرهدهی تکرارپذیر باشد. سیستمهای واقعی از کتابخانههای بررسیشده و اعداد بسیار بزرگتر استفاده میکنند. هرگز کد آموزشی را در یک محصول کپی نکنید.
مسئله
یک فروشگاه و یک اپ هر کدام فهرستی از ایمیلهای مشتریان دارند. آنها ایمیلهایی را میخواهند که در هر دو فهرست هستند و نه چیز دیگری: فروشگاه نباید کاربران دیگر اپ را بفهمد و اپ نباید مشتریان دیگر فروشگاه را بفهمد.
تقاطع مجموعهها: اقلامی که دو فهرست بهطور مشترک دارند. تقاطع خصوصی مجموعهها (PSI): راهی برای اینکه دو طرف آن را محاسبه کنند و هیچ چیز دیگری دربارهٔ فهرستهایشان فاش نکنند.
چرا «فقط هشش کن» شکست میخورد
هش: تابعی که متن را به درهمریختهای با طول ثابت تبدیل میکند (SHA-256 یکی از رایجهاست). ورودی یکسان همیشه خروجی یکسان میدهد و نمیتوانید آن را مستقیماً برعکس اجرا کنید.
«ما ایمیلهای هششده را مبادله میکنیم، پس هیچکس ایمیلهای واقعی را نمیبیند» امن به نظر میرسد. اما ایمیلها قابل حدساند. هر کس فهرستی از ایمیلهای محتمل داشته باشد میتواند همهٔ حدسها را هش کند و دنبال تطابق بگردد، مثل امتحان کردن همهٔ کلیدهای یک دستهکلید بزرگ. تابع naive_reverse شما دقیقاً همین کار را با 200 ایمیل ساختگی دنیای تمرین میکند. هش کردن فقط وقتی داده را پنهان میکند که ورودیها قابل حدس نباشند، و ایمیلها، شمارهتلفنها و نامها قابل حدساند.
ترفند دو قفل
از درس ریاضی به یاد بیاورید: گذاشتن راز a و سپس راز b همان نتیجهٔ b و سپس a را میدهد. هر ایمیل را یک جعبه تصور کنید. آلیس قفل خودش را روی هر یک از جعبههایش میگذارد و آنها را برای باب میفرستد. باب قفل خودش را اضافه میکند و آنها را برمیگرداند. باب جعبههای خودش را هم قفل میکند و برای آلیس میفرستد و آلیس قفلش را اضافه میکند. حالا هر جعبه هر دو قفل را دارد، و دو جعبه با ایمیل یکسان درونشان یکسان به نظر میرسند، فرقی نمیکند کدام قفل اول گذاشته شده.
به زبان اعداد، با گروه تمرینی از watched.leg7a_privacy (P، hash_to_group، random_secret):
- آلیس
blind(alice_items, a)را میفرستد: هر قلم در گروه هش میشود و سپس به توانaمیرسد. - باب آنها را به توان
bمیرساند (reblind) و با همان ترتیب برمیگرداند. - باب
blind(bob_items, b)را میفرستد. - آلیس مقدارهای باب را به توان
aمیرساند. هر یک از مقدارهای دوقفلهٔ او که در مجموعهٔ دوقفلهٔ باب ظاهر شود، قلمی مشترک است. چون او ترتیب را نگه داشته، میداند هر کدام کدام قلم خودش است.
چرا این روش امن است در حالی که هش کردن شکست خورد؟ برای آزمودن یک حدس به هر دو راز نیاز دارید و هر طرف راز خودش را نگه میدارد. باب فقط مقدارهای آلیس را با راز او میبیند که شبیه اعداد تصادفیاند.
PSI دیفی-هلمن: نام این پروتکل، برگرفته از ایدهٔ تبادل کلید 1976 که از آن وام میگیرد (دو طرف که توانهای مخفی را ترکیب میکنند). نسخههای واقعی از خمهای بیضوی (نوع دیگری از گروه، با همان ویژگی «ترتیب مهم نیست» و اعداد بسیار کوتاهتر) و هش کردن دقیق استفاده میکنند.
خود پاسخ یک افشاست
حتی PSI بینقص هم به آلیس میگوید که فرد خاصی مشتری باب است. اگر باب یک درمانگاه یا مشاور بدهی باشد، این حساس است. اغلب یک شرکت فقط لازم دارد بداند چند مشتری مشترکاند. در PSI کاردینالیتی باب پاسخش را در مرحلهٔ 2 به هم میزند، پس آلیس میتواند تطابقها را بشمارد اما نمیتواند بگوید به کدام اقلام او تعلق دارند. کمترین چیزی را بخواهید که به پرسش پاسخ میدهد.
در زبانهای دیگر
مرحلهٔ کور کردن در جاوااسکریپت با 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 ممیزیشده استفاده کنید.
خلاصه
- ایمیلهای هششده را با فهرستی از حدسها بهآسانی میتوان برگرداند، پس «ما فقط هشها را به اشتراک گذاشتیم» حریم خصوصی نیست.
- PSI دیفی-هلمن هر قلم را با دو راز که ترتیبشان مهم نیست دوقفله میکند، پس تطابقها بدون فاش شدن هیچکدام از فهرستها ظاهر میشوند.
- نگه داشتن ترتیب فاش میکند کدام اقلام تطابق دارند؛ به هم زدن (PSI کاردینالیتی) فقط تعداد را فاش میکند.
- خود تقاطع دادهٔ شخصی است، پس کمترین چیزی را بخواهید که به پرسش پاسخ میدهد.
پنج تابع بنویسید. 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) هر مقدار را به پیمانهٔ P به توان secret میرساند و ترتیب را حفظ میکند. psi(alice_items, bob_items, a_secret, b_secret) چهار مرحلهٔ درس را با blind و reblind دنبال میکند و فهرست مرتبشدهٔ اقلامی از آلیس را که باب هم دارد برمیگرداند. psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) همین کار را میکند اما پاسخ باب را با rng.shuffle به هم میزند و فقط تعداد اقلام مشترک را برمیگرداند.
مشکلی در این درس دیدید؟ گزارشش کنید · دربارهٔ این درس بپرسید
این تمرین بهزودی باز میشود
درس پیش از آن را تمام کنید تا این یکی باز شود. کل دوره رایگان است، حساب کاربری لازم نیست، و میتوانید همین الان این درس را بخوانید.
این مرورگر کوکیهای learn.floati.life را مسدود میکند، پس درسهایی که اینجا تمام کردید نمیتوانند به ترتیب باز شوند. کوکیها را برای این سایت مجاز کنید و صفحه را دوباره بارگذاری کنید.