RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response

در این مقاله می‌خواهیم به سازوکار «پاسخ ترتیبی تصادفی حافظ حریم خصوصی تجمعی» بپردازیم که به منظور خلاصه سازی در سراسر این مقاله آن را RAPPOR می نامیم.

این سازوکار توسط شرکت Google برای پیاده‌سازی «حریم خصوصی تفاضلی محلی» ایجاد شده است.

این روش اصولا روی داده‌های از نوع رشته تمرکز می‌کند اما طبیعی است که می‌توان سایر نوع داده‌ها را نیز به رشته تبدیل کرد و از این رو جامعیت خوبی دارد.

پاسخ تصادفی

بعد از پیدایش حریم خصوصی تفاضلی محلی، راهکارهای متفاوتی برای عملیاتی کردن این تعریف ارائه شد.

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

از «پاسخ تصادفی» در مواردی استفاده می‌شود که یک سوال حساس از شرکت‌کنندگان پرسیده می‌شود. منظور از سوال حساس، سوالی است که شرکت‌کنندگان مایل نیستند سایر افراد پاسخ آن را بدانند به گونه‌ای که حتی ممکن است به آن سوال، پاسخ غلط دهند.

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

باید دقت داشت که «پاسخ تصادفی» تنها برای سوالاتی کاربرد دارد که جواب آنها دودویی است یعنی پاسخ آن‌ها یا مثبت و یا منفی است.

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

البته همچنان برخی افراد ممکن است که باز هم پاسخ‌های غلط ثبت کنند اما تعداد این افراد بسیار اندک می‌شود و نتیجه‌ی آماری را مختل نمی‌کند.

روش‌های قبلی

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

تمام روش‌هایی که قبل از RAPPOR ارائه شده بود این ایراد را داشتند که نمی‌توان از آنها به صورت بلند مدت استفاده کرد.

برای مثال فرض کنید پرسش ما به صورت زیر است:

آیا شما سیگاری هستید؟

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

اما فرض کنید شما ۱۰۰ بار این سوال را به وسیله‌ي «پاسخ تصادفی» از علی می‌پرسید؛ آنگاه اگر تعداد پاسخ‌های مثبت علی ۷۵ عدد باشد شما با قطعیت بیشتری می‌توانید بگویید که علی قطعا سیگاری است.

روش‌های قبل RAPPOR هم همین مشکل را داشتند که اگر چندین بار اطلاعات از کاربران گرفته می‌شد، حریم خصوصی آنها نقض می‌شد.

وجود این مشکل یکی از دلایلی بود که شرکت Google را وا داشت تا سازوکار RAPPOR را پیاده کند.

معرفی کلی

به صورت کلی از RAPPOR می‌توان برای جمع‌آوری داده‌ها در مورد ویژگی‌های دسته‌ای کاربران استفاده کرد.

یک راه برای استفاده از RAPPOR به این صورت است که هر بیت در پاسخ کاربران نمایانگر یک دسته است که مشخص می‌کند که آیا آن کاربر عضو آن دسته‌ی مشخص هست یا خیر. برای مثال اگر بخواهیم کاربران جنسیت خود را اعلام کنند، کاربران یک جواب دو بیتی به ما می‌دهند که مثلا بیت اول جنسیت «مذکر» و بیت دوم جنسیت «مونث» را نشان می‌دهد و برای مثال اگر یک کاربر جواب ۰۱ را ارسال کند یعنی جنسیت او مونث بوده است.

از آنجا که RAPPOR بر روی ویژگی‌های دسته‌ای کاربران تمرکز کرده است، سوالی که پیش می‌آید این است که پس داده‌های عددی را چگونه می‌توان با استفاده از این سازوکار جمع‌آوری نمود. در مورد داده‌های کاربری می‌توان مجموعه مقادیر ممکن را دسته بندی کرد و سپس همانند داده‌های دسته‌ای با آن برخورد کرد؛ برای مثال فرض کنید که ما قصد داریم با استفاده از این سازوکار سن کاربران را به دست آوریم، ابتدا سن را به بازه‌های (دسته‌های) مشخصی تقسیم می‌کنیم مثلا از ۱ تا ۱۰ سال را یک دسته و از ۱۰ تا ۲۰ سال را یک دسته‌ی دیگر و همین طور ادامه می‌دهیم سپس کاربران، با توجه به این که در چه دسته‌ای قرار می‌گیرند، بیت مربوط به آن دسته را برابر با ۱ قرار می‌دهند و سپس این سازوکار را اعمال می‌کنند.

اما داده‌ها تنها به دو نوع دسته‌ای و عددی ختم نمی‌شوند و ممکن است داده‌هایی داشته‌ باشیم که به هیچ صورتی نتوان آن‌ها را به داده‌های دسته‌ای تبدیل کرد. برای فائق آمدن بر این مشکل از Bloom filter استفاده شده است.

دقت شود که زمانی که ویژگی‌های دسته‌ای و یا ویژگی‌هایی که قابلیت تبدیل به داده‌های دسته‌ای دارند را مورد بررسی قرار می‌دهیم، برای محاسبه‌ی نتایج تنها کافی است که تعداد بیت‌های ۱ در پاسخ کاربران را بشماریم و سپس تحلیل کنیم و پاسخ نهایی را به دست آوریم اما هنگامی که سایر داده‌ها را مورد بررسی قرار می‌دهیم و از Bloom filter استفاده می‌کنیم، برای به دست آوردن نتایج نهایی مجبور خواهیم بود از روش‌های پیچیده‌‌ی آماری استفاده کنیم تا ابتدا رشته‌های کاندید را شناسایی کنیم و سپس با به دست آوردن فراوانی هر کدام به ادامه‌ی تحلیل بپردازیم.

در ادامه با معرفی کوتاهی از Bloom filter به ادامه‌ی راهکار سوم خواهیم پرداخت.

Bloom filter

از این الگوریتم معمولا بیشتر در شبکه و برای آزمون عضویت یک عنصر در یک مجموعه استفاده می‌شود.

روش کلی به این صورت است که هنگامی که یک عنصر وارد مجموعه می‌شود توسط توابع مختلف، چکیده‌های مختلفی برای آن به دست می‌آید و همه‌ی بیت‌های متناظر با چکیده‌ها را برابر با ۱ قرار می‌دهیم.

هنگامی که بخواهیم بفهمیم آیا عضوی قبلا به مجموعه اضافه شده است یا خیر، کافی است که چکیده‌های مختلف عضو مورد نظر را محاسبه کنیم و اگر همه‌ی بیت‌ها متناظر با چکیده‌ها برابر با ۱ باشد نتیجه می‌گیریم که این عنصر عضو مجموعه‌ی ما است و در غیر این صورت عضو مجموعه‌ی ما نیست.

طبیعی است که این روش دارای False Positive خواهد بود اما False negative ندارد.

علی‌رغم داشتن False Positive این روش به دلیل مصرف کم حافظه و سریع بودن آن در حوزه‌های مختلف مورد استفاده قرار می‌گیرد.

انواع مهاجم

در این مقاله دسته‌بندی زیبایی بر روی مهاجمان انجام داده بود که به نظر نویسنده خالی از لطف نیست اگر در اینجا ذکر شود. این مطلب صرفا جهت بیشتر بدانید در اینجا بیان شده است و اگر صرفا به دنبال فهم روش RAPPOR هستید، می‌توانید این قسمت را مطالعه نکنید.

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

• مهاجم پایه: این مهاجم تنها به یک دور از پاسخ‌ها دسترسی دارد؛ یعنی برای مثال ما تنها یک بار از کاربران سوال خود را می‌پرسیم و کاربران نیز با «پاسخ تصادفی» به سوال ما پاسخ می‌دهند و ما همه‌ی پاسخ‌ها را به مهاجم می‌دهیم و از او می‌خواهیم که پاسخ واقعی یکی از کاربران را به دست آورد.
• مهاجم بازه‌ای: این مهاجم قوی‌تر از مهاجم قبلی است و در این مدل مهاجم به چندین «پاسخ تصادفی» از یک کاربر در طول زمان دسترسی دارد.

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

در RAPPOR برای مقابله با مدل دوم از یک مرحله «به خاطرسپاری» استفاده می‌کند که عملا داشتن چند «پاسخ تصادفی» کمکی به مهاجم نمی‌کند که در ادامه بیشتر با آن آشنا خواهید.

RAPPOR

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

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

الگوریتم RAPPOR خود از چهار قسمت مختلف تشکیل شده است:

• قدم اول: این الگوریتم ابتدا با دریافت مقدار واقعی داده‌ی مورد نظر از کاربر، به وسیله‌ی Bloom filter یک آرایه با اندازه‌ي k در خروجی تولید می‌کند که حاصل اعمال Bloom filter بر روی آن داده‌ی مورد نظر است؛ دقت شود که در همین قدم اول، به صورت ناخواسته مقداری حریم خصوصی افزایش می‌یابد زیرا همان‌گونه که در بالاتر گفته شد، Bloom filter دارای False Positive است و از این رو مهاجم با دیدن خروجی Bloom filter نمی‌تواند با قطعیت بگوید که چه داده‌ی ورودی چه چیزی بوده است. البته باید توجه داشت که تابع‌های چکیده برگشت پذیر نیستند و از این رو توانایی محاسباتی مهاجم نیز تضعیف می‌شود.*

• قدم دوم: بعد از به دست آوردن آرایه‌ی kتایی از مرحله قبل، روی هر بیت آن به صورت مستقل یک بار «پاسخ تصادفی» اعمال می‌شود، به این صورت که کاربر با احتمال f/2 مقدار بیت مورد نظر را برابر با ۱ و با همین احتمال برابر با ۰ قرار می‌دهد و در غیر این صورت مقدار واقعی بیت مورد نظر را در خروجی می‌نویسد:قدم

\( B^\prime_i = \left\{\begin{array}{c} 1, \qquad \textrm{with probability}\frac{1}{2}f \\ 0, \qquad \textrm{with probability}\frac{1}{2}f \\ B_i, \qquad \textrm{with probability}1-f \end{array} \right. \)

که B همان آرایه‌ی به دست آمده از قدم قبلی است و ‘B نتیجه‌ی نهایی این قدم است. دقت کنید که ‘B همان مقداری است که به وسیله‌ی «به خاطرسپاری» ذخیره می‌شود و در پرسمان‌های بعدی، دیگر به جای اجرای این دو قدم، قدم‌های بعدی صرفا اجرا خواهند شد.

• قدم سوم: در قدم سوم، هدف این است که یک‌بار دیگر «پاسخ تصادفی» را بر روی «پاسخ تصادفی» قبلی اعمال کنیم. این پاسخ تصادفی به شکل ساده‌تری انجام می‌شود اما همچنان ویژگی تصادفی بودن پاسخ را حفظ می‌کند. برای این کار یک آرایه به اندازه‌ی k در نظر گرفته می‌شود و همه‌ی بیت‌های آن را در ابتدا برابر با ۰ قرار می‌دهیم. سپس «پاسخ تصادفی» را روی هر بیت اعمال می‌کنیم به این صورت که با احتمال q پاسخ واقعی را قرار می‌دهیم و با احتمال p پاسخ غلط را در خروجی قرار می‌دهیم:

\( P[S_i = 1] = \left\{\begin{array}{c} q, \qquad \textrm{if} B^\prime_i = 1 \\ p, \qquad \textrm{if} B^\prime_i = 0 \end{array} \right. \)

که در عبارت بالا، S همان نتیجه‌ی نهایی این قدم است.

• قدم چهارم: قدم چهارم صرفا شامل ارسال آرایه‌ی S حاصل از قدم قبلی به سمت سرور است.

انواع RAPPOR

الگوریتمی که در بخش قبل گفته شد، قوی‌ترین حالت RAPPOR است اما ممکن است بنابر نیازمان، نخواهیم تمامی ۴ قدم گفته شده را انجام دهیم. طبیعی است که در هر کدام از سه قدم اول، مقداری نوفه(Noise) به پاسخ اضافه می‌کند و از این رو بهره‌وری را کاهش می‌دهد. بنابراین اگر یکی از این سه قدم برای نیازمان اضافی باشد، می‌توان آن را حذف کرد تا بهره‌وری را افزایش دهیم؛ با در نظر گرفتن این نکته می‌توان سه نوع RAPPOR در نظر گرفت:

• یک بار مصرف: اگر داده‌های کاربران صرفا قرار است یک بار مورد پرس‌وجو قرار گیرد، می‌توان قدم دوم را حذف کرد تا حریم خصوصی تفاضلی بلند مدت را حذف کرد و بهره‌وری را افزایش دهیم.
• پایه: اگر مقادیر ممکن برای ویژگی مورد پرسمان مشخص باشد، می‌توان به جای استفاده از Bloom filter هر مقدار ممکن (یا تعدادی از مقادیر ممکن) را به عنوان یک دسته در نظر بگیریم و معادل با هر دسته یک بیت در نظر بگیریم. در واقع در این نوع از RAPPOR ما قدم اول را حذف می‌کنیم و به دلیل حذف شدن امکان False Positive بهره‌وری افزایش می‌یابد.
• پایه‌ي یک‌ بار مصرف: این نوع از RAPPOR شامل ترکیب دو نوع بالا است.

محاسبه پرسمان

محاسبه‌ی پرسمان از روی نتیجه‌های به دست آمده از طریق RAPPOR نیازمند روش‌های آماری پیچیده و مختلفی است به گونه‌ای که خارج از ظرفیت این مقاله است و همچنین در مقاله‌ی مرجع نیز ذکر نشده است. در اینجا ما به صورت کلی به نحوه‌ی محاسبه‌ی نتایج می‌پردازیم تا صرفا شما را با میزان پیچیدگی آن آشنا کنیم اما اگر قصد دارید که نحوه‌ی محاسبه‌ی پرسمان‌ها را با دقت متوجه شوید توصیه می‌شود که به کد پیاده‌سازی این الگوریتم مراجعه کنید.

به منظور تسریع محاسبه‌ی نتایج پرسمان می‌توان کاربران به دسته‌های مختلف تقسیم کرد و در هر دسته از گروه مختلفی از توابع چکیده‌ساز استفاده کنیم تا تصادم را کاهش دهیم و همچنین محاسبه‌ی پرسمان را ساده‌تر کنیم.

در چهار قدم می‌توان نتایج پرسمان را به دست آورد:

• در هر دسته از کاربران، برای هر بیت i تعداد مقادیر ۱ را می‌شماریم و از طریق «تخمین پاسخ تصادفی» که برای به دست آوردن نتایج حاصل از «پاسخ تصادفی» استفاده می‌شود تعداد ۱های واقعی را تخمین می‌زنیم.
• سپس باید M عدد از مقادیر را به عنوان نماینده انتخاب کنیم تا فراوانی آنها را محاسبه کنیم، دقت شود باید مقادیری انتخاب شوند که حدس می‌زنیم فراوانی بیشتری نسبت به سایر مقادیر دارند. سپس با توجه به مقادیر منتخب و پاسخ‌های دریافت شده از RAPPOR یک ماتریس تشکیل می‌دهیم و با استفاده از Lasso regression یک مدل برای این ماتریس به دست می‌آوریم.
• با استفاده از متغیرهای به دست آمده یک «رگرسیون کم‌ترین مربعات» به دست می‌آوریم و به وسیله‌ی آن فراونی هر نماینده، خطای استاندارد و مقدار p را محاسبه می‌کنیم.
• نهایتا از طریق مقایسه‌ی مقدار p به دست آمده، فراوانی‌های درست را شناسایی می‌کنیم.

نتیجه‌گیری

از RAPPOR به عنوان یک سازوکار موفق یاد می‌شود زیرا سابقه‌ی عملی خوبی دارد به گونه‌ای که شرکت Google از این روش در مرورگر Chrome برای جمع‌آوری داده‌های کاربران مورد استفاده قرار گرفت.

همچنین از این سازوکار می‌توان برای به دست‌ آوردن دسته‌ی کاربران، فراوانی و همچنین نمودارهای مختلف استفاده کرد.

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

Erlingsson, Úlfar, Vasyl Pihur, and Aleksandra Korolova. “Rappor: Randomized aggregatable privacy-preserving ordinal response.” Proceedings of the 2014 ACM SIGSAC conference on computer and communications security. 2014