رمزنگاران رویکردی برای حفظ حریم خصوصی جستجوی کل ابداع می کنند | مجله کوانتا

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

این موقعیت‌ها به یک سوال کلیدی در رمزنگاری دامن می‌زند: چگونه می‌توانید اطلاعات را از یک پایگاه داده عمومی بدون فاش کردن چیزی در مورد آنچه به آن دسترسی داشته‌اید بیرون بکشید؟ این معادل چک کردن یک کتاب از کتابخانه است بدون اینکه کتابدار بداند کدام یک.

گفت: ایجاد یک استراتژی که این مشکل را حل کند - معروف به بازیابی اطلاعات خصوصی - "یک بلوک سازنده بسیار مفید در تعدادی از برنامه های کاربردی حفظ حریم خصوصی است." دیوید وو، رمزنگار در دانشگاه تگزاس، آستین. از دهه 1990، محققان این سوال را کنار گذاشتند و استراتژی‌هایی را برای دسترسی خصوصی به پایگاه‌های اطلاعاتی بهبود بخشیدند. یکی از اهداف اصلی که هنوز با پایگاه داده‌های بزرگ غیرممکن است، معادل جستجوی خصوصی گوگل است، که در آن می‌توانید انبوهی از داده‌ها را به صورت ناشناس و بدون انجام هرگونه محاسبات سنگین غربال کنید.

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

گفت: «[این] چیزی در رمزنگاری است که من حدس می‌زنم همه ما آن را می‌خواستیم، اما کاملاً باور نداشتیم که وجود دارد». وینود وایکونتاناتان، یک رمزنگار در موسسه فناوری ماساچوست که در این مقاله دخالتی نداشت. "این یک نتیجه برجسته است."

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

این رویکرد به اندازه کافی در مقیاس های کوچکتر کار می کند، اما با رشد پایگاه داده، زمان مورد نیاز برای اسکن آن حداقل به نسبت افزایش می یابد. همانطور که شما از پایگاه های داده بزرگتر مطالعه می کنید - و اینترنت بسیار بزرگ است - این روند به طرز چشمگیری ناکارآمد می شود.

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

برای دنیل ویچز، یک رمزنگار در دانشگاه نورث ایسترن و یکی از نویسندگان مقاله جدید، به نظر خیلی خوب به نظر می رسید که درست باشد. در حدود سال 2011، او شروع به تلاش برای اثبات غیرممکن بودن این نوع طرح کرد. او گفت: "من متقاعد شده بودم که هیچ راهی برای انجام این کار وجود ندارد."

اما در سال 2017 دو گروه از محققان منتشر شده نتایج که نظرش عوض شد آنها اولین برنامه هایی را ساختند که می توانستند این نوع بازیابی اطلاعات خصوصی را انجام دهند، اما نتوانستند نشان دهند که برنامه ها امن هستند. (کریپتوگراف ها امنیت یک سیستم را با نشان دادن اینکه شکستن آن به اندازه حل یک مشکل سخت دشوار است، نشان می دهند. محققان نتوانستند آن را با یک مشکل سخت متعارف مقایسه کنند.)

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

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

این روش هیچ پیشرفتی ایجاد نکرد، و گروه نزدیک به تسلیم شدن بود - تا زمانی که آنها فکر کردند که آیا این ابزار واقعاً ممکن است در مورد مورد علاقه تک سرور کار کند. آنها دیدند، چند جمله ای را با دقت کافی انتخاب کنید، و یک سرور واحد می تواند آن را بر اساس نتیجه سال 2011 پیش پردازش کند - و طرح جستجوی ایمن و کارآمدی را که Wichs سال ها در آن فکر کرده بود، به دست آورد. ناگهان، آنها مشکل سخت تر را حل کرده بودند.

در ابتدا، نویسندگان آن را باور نکردند. ویچز فکرش را به یاد آورد: «بیایید بفهمیم که چه اشکالی دارد. ما به تلاش ادامه دادیم تا بفهمیم کجا خراب می‌شود.»

اما راه حل ثابت بود: آنها واقعاً یک راه امن برای پیش پردازش یک پایگاه داده تک سرور کشف کرده بودند تا هر کسی بتواند اطلاعات را به صورت مخفیانه استخراج کند. گفت: "این واقعا فراتر از هر چیزی است که ما به آن امیدوار بودیم." یووال ایشایی، یک رمزنگار در Technion در اسرائیل که در این کار دخالتی نداشت. او گفت که این نتیجه "ما حتی آنقدر شجاع نبودیم که درخواست کنیم."

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

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

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

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

Vaikuntanathan گفت خوشبختانه رمزنگاران سابقه طولانی در بهینه سازی نتایج دارند که در ابتدا غیرعملی بود. اگر کار آینده بتواند این رویکرد را ساده کند، او معتقد است که جستجوهای خصوصی از پایگاه های داده غول پیکر ممکن است در دسترس باشد. او گفت: «همه ما فکر می‌کردیم که در آنجا گیر کرده‌ایم. "آنچه نتیجه دانیل می دهد امید است."

کوانتوم در حال انجام یک سری نظرسنجی برای ارائه خدمات بهتر به مخاطبانمان است. ما را بگیر نظرسنجی خواننده علوم کامپیوتر و شما برای برنده شدن رایگان وارد خواهید شد کوانتوم کالا