Криптографи винайшли підхід до повної конфіденційності пошуку | Журнал Quanta

Ми всі знаємо, що потрібно бути обережними з деталями, які ми публікуємо в Інтернеті, але інформація, яку ми шукаємо, також може бути розкриваючою. Шукайте маршрути проїзду, і наше місцезнаходження стане набагато легше вгадати. Перевірте пароль у сховищі скомпрометованих даних, і ми ризикуємо розкрити його самі.

Ці ситуації підживлюють ключове питання в криптографії: як ви можете отримати інформацію з публічної бази даних, не розкриваючи нічого про те, до чого ви отримали доступ? Це еквівалентно тому, щоб взяти книгу в бібліотеці, а бібліотекар не знає, яку саме.

Розробка стратегії, яка вирішує цю проблему — відома як пошук приватної інформації — є «дуже корисним будівельним блоком у ряді додатків, що зберігають конфіденційність». Девід Ву, криптограф Техаського університету в Остіні. Починаючи з 1990-х років, дослідники почали розглядати це питання, покращуючи стратегії приватного доступу до баз даних. Однією з головних цілей, яка все ще неможлива з великими базами даних, є еквівалент приватного пошуку в Google, де ви можете анонімно переглядати купу даних, не виконуючи важких обчислювальних робіт.

Тепер це зробили троє дослідників створений давно шукану версію пошуку приватної інформації та розширив її для створення більш загальної стратегії конфіденційності. Робота, яку отримав а Нагорода за найкращу роботу у червні на річній Симпозіум з теорії обчислювальної техніки, долає головний теоретичний бар’єр на шляху до справді приватного пошуку.

«[Це] те, що в криптографії, я думаю, ми всі хотіли, але не дуже вірили, що воно існує», — сказав Вінод Вайкунтанатан, криптограф з Массачусетського технологічного інституту, який не брав участі в роботі. «Це знаковий результат».

Проблема доступу до приватних баз даних оформилася в 1990-х роках. Спочатку дослідники припустили, що єдиним рішенням буде сканувати всю базу даних під час кожного пошуку, що було б схоже на те, що бібліотекар очищує кожну полицю, перш ніж повернутися з вашою книгою. Зрештою, якби пошук пропустив якийсь розділ, бібліотекар знав би, що вашої книги немає в цій частині бібліотеки.

Цей підхід досить добре працює в менших масштабах, але в міру зростання бази даних час, необхідний для її сканування, зростає принаймні пропорційно. Коли ви читаєте дані з більших баз даних — а Інтернет є досить великим — процес стає надзвичайно неефективним.

На початку 2000-х років дослідники почали підозрювати, що вони можуть уникнути бар’єру повного сканування шляхом «попередньої обробки» бази даних. Грубо кажучи, це означало б кодування всієї бази даних як спеціальної структури, щоб сервер міг відповісти на запит, прочитавши лише невелику частину цієї структури. Досить ретельна попередня обробка теоретично може означати, що єдиний сервер, на якому розміщена інформація, проходить цей процес лише один раз, що дозволяє всім майбутнім користувачам отримувати інформацію конфіденційно без додаткових зусиль.

для Даніель Вікс, криптографа з Північно-східного університету та співавтора нової статті, це здавалося занадто гарним, щоб бути правдою. Приблизно в 2011 році він почав намагатися довести, що така схема неможлива. «Я був переконаний, що це неможливо зробити», — сказав він.

Але в 2017 році дві групи дослідників опублікований результати це змінило його думку. Вони створили перші програми, які могли здійснювати такий вид приватного пошуку інформації, але вони не змогли показати, що програми безпечні. (Криптографи демонструють безпеку системи, показуючи, що зламати її так само складно, як вирішити якусь складну проблему. Дослідники не змогли порівняти її з канонічною складною проблемою.)

Тож навіть з відновленням надії Вікс припустив, що будь-яка безпечна версія цих програм ще далека. Натомість він та його співавтори — Вей-Кай Лінь, зараз в Університеті Вірджинії, і Ітан Мук, також у Northeastern — працювали над проблемами, які, на їхню думку, були б легшими, які включали випадки, коли база даних розміщена на кількох серверах.

У методах, які вони вивчали, інформація в базі даних може бути перетворена в математичний вираз, який сервери можуть оцінити, щоб отримати інформацію. Автори припустили, що можна зробити процес оцінки ефективнішим. Вони гралися з ідеєю 2011 року, коли інші дослідники знайшли спосіб швидко оцінити такий вираз, попередньо обробивши його, створивши спеціальні компактні таблиці значень, які дозволяють пропускати звичайні кроки оцінки.

Цей метод не приніс жодних покращень, і група була ледь не відмовилася — поки вони не задумалися, чи може цей інструмент справді працювати в бажаному випадку з одним сервером. Вибираючи поліном досить ретельно, вони побачили, і єдиний сервер міг попередньо обробити його на основі результату 2011 року, що дало безпечну та ефективну схему пошуку, над якою Вікс роздумував роками. Раптом вони все-таки вирішили складнішу проблему.

Спочатку автори не повірили. «Давайте розберемося, що з цим не так», — згадав думку Вікс. «Ми постійно намагалися з’ясувати, де він ламається».

Але рішення витримало: вони справді знайшли безпечний спосіб попередньої обробки односерверної бази даних, щоб будь-хто міг отримати інформацію таємно. «Це справді перевищує все, на що ми сподівалися», — сказав Юваль Ішай, криптограф із Техніону в Ізраїлі, який не брав участі в цій роботі. Це результат, «ми не вистачило сміливості навіть попросити», — сказав він.

Побудувавши свою таємну схему пошуку, автори звернулися до реальної мети приватного пошуку в Інтернеті, що є більш складним, ніж витягування фрагментів інформації з бази даних, сказав Вікс. Сама по собі схема приватного пошуку дозволяє використовувати версію приватного пошуку, подібного до Google, але вона надзвичайно трудомістка: ви самостійно запускаєте алгоритм Google і таємно отримуєте дані з Інтернету, коли це необхідно. Вічс сказав, що справжній пошук, коли ви надсилаєте запит і сидите, поки сервер збирає результати, насправді є ціллю для ширшого підходу, відомого як гомоморфне шифрування, яке маскує дані, щоб хтось інший міг ними маніпулювати, навіть нічого про них не знаючи. .

Типові гомоморфні стратегії шифрування натрапили б на ту саму заковику, що й пошук приватної інформації, перебираючи весь вміст Інтернету для кожного пошуку. Але використовуючи свій приватний метод пошуку як основу, автори створили нову схему, яка запускає обчислення, які більше схожі на програми, якими ми користуємося щодня, збираючи інформацію таємно, не охоплюючи весь Інтернет. Це підвищить ефективність пошуку в Інтернеті та будь-яких програм, яким потрібен швидкий доступ до даних.

Хоча гомоморфне шифрування є корисним розширенням схеми приватного пошуку, сказав Ішай, він вважає пошук приватної інформації більш фундаментальною проблемою. Рішення авторів є «магічним будівельним блоком», і їхня стратегія гомоморфного шифрування є природним продовженням.

Наразі жодна схема не є практично корисною: попередня обробка наразі допомагає в крайніх випадках, коли розмір бази даних зростає до нескінченності. Але фактичне розгортання означає, що ці заощадження не можуть матеріалізуватися, і процес з’їсть забагато часу та місця для зберігання.

На щастя, сказав Вайкуннатан, криптографи мають довгу історію оптимізації результатів, які спочатку були непрактичними. Якщо майбутні роботи зможуть спростити цей підхід, він вважає, що приватні пошуки з гігантських баз даних можуть бути доступні. «Ми всі думали, що застрягли там», — сказав він. «Результат Деніела дає надію».

Quanta проводить серію опитувань, щоб краще обслуговувати нашу аудиторію. Візьміть наші опитування читачів інформатики і ви будете введені, щоб виграти безкоштовно Quanta товар