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

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

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

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

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

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

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

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