A faster way to preserve privacy online/Более быстрый способ сохранить конфиденциальность в Интернете.

A faster way to preserve privacy online

Вычисление сервера в SimplePIR. Каждая ячейка представляет элемент Z𝑞, а × обозначает умножение матрицы. Сервер выполняет основную часть своей работы на единовременном этапе предварительной обработки. После этого сервер может ответить на запрос каждого клиента с помощью облегченной онлайн-фазы. Кредит: Один сервер по цене двух: Простой и быстрый поиск частной информации на одном сервере (2022).

Поиск в Интернете может выявить информацию, которую пользователь предпочел бы сохранить в тайне. Например, когда кто-то ищет медицинские симптомы в Интернете, он может сообщить о своем состоянии здоровья Google, онлайн-медицинской базе данных, такой как WebMD, и, возможно, сотням рекламодателей и деловых партнеров этих компаний.

На протяжении десятилетий исследователи разрабатывали методы, позволяющие пользователям осуществлять поиск и извлекать информацию из базы данных в частном порядке, но эти методы остаются слишком медленными, чтобы эффективно использоваться на практике.

Исследователи Массачусетского технологического института в настоящее время разработали схему для поиска частной информации, которая примерно в 30 раз быстрее, чем другие сопоставимые методы. Их технология позволяет пользователю выполнять поиск в онлайн-базе данных, не раскрывая свой запрос серверу. Более того, он управляется простым алгоритмом, который было бы легче реализовать, чем более сложные подходы из предыдущей работы.

Их технология могла бы обеспечить приватное общение, не позволяя приложению для обмена сообщениями знать, что говорят пользователи или с кем они разговаривают. Его также можно использовать для поиска релевантных онлайн-объявлений без того, чтобы рекламные серверы изучали интересы пользователей.

«Эта работа действительно направлена на то, чтобы вернуть пользователям некоторый контроль над их собственными данными. В долгосрочной перспективе мы бы хотели, чтобы просмотр веб-страниц был таким же приватным, как просмотр библиотеки. Эта работа еще не достигла этого, но она начинает создавать инструменты, позволяющие нам быстро и эффективно выполнять подобные задачи на практике», — говорит Александра Хенцингер, аспирантка по информатике и ведущий автор статьи, представляющей эту технику.

Сохранение конфиденциальности

Первые схемы для частного поиска информации были разработаны в 1990-х годах, частично исследователями Массачусетского технологического института. Эти методы позволяют пользователю взаимодействовать с удаленным сервером, на котором хранится база данных, и считывать записи из этой базы данных так, чтобы сервер не знал, что читает пользователь.

Чтобы сохранить конфиденциальность, эти методы заставляют сервер касаться каждого отдельного элемента в базе данных, поэтому он не может определить, какую запись ищет пользователь. Если одна область останется нетронутой, сервер узнает, что клиент не заинтересован в этом элементе. Но прикосновение к каждому элементу, когда в базе данных могут быть миллионы записей, замедляет процесс запроса.

Чтобы ускорить процесс, исследователи Массачусетского технологического института разработали протокол, известный как Simple PIR, в котором сервер выполняет большую часть базовой криптографической работы заранее, еще до того, как клиент отправит запрос. На этом этапе предварительной обработки создается структура данных, содержащая сжатую информацию о содержимом базы данных, которую клиент загружает перед отправкой запроса.

В некотором смысле эта структура данных подобна подсказке для клиента о том, что находится в базе данных.

«Как только клиент получит эту подсказку, он сможет выполнять неограниченное количество запросов, и эти запросы будут намного меньше как по размеру отправляемых вами сообщений, так и по работе, которую вам нужно выполнить на сервере. Это то, что делает простой PIR намного быстрее», — объясняет Хенцингер.

Но подсказка может быть относительно большой по размеру. Например, чтобы запросить базу данных объемом 1 гигабайт, клиенту потребуется загрузить подсказку объемом 124 мегабайта. Это увеличивает затраты на связь, что может затруднить внедрение технологии на реальных устройствах.

Чтобы уменьшить размер подсказки, исследователи разработали вторую технику, известную как Double PIR, которая в основном включает в себя повторное выполнение простой схемы PIR. Это создает гораздо более компактную подсказку, размер которой фиксирован для любой базы данных.

Используя Double PIR, подсказка для базы данных объемом 1 гигабайт будет составлять всего 16 мегабайт.

«Наша схема двойного PIR работает немного медленнее, но при этом затраты на связь будут намного ниже. Для некоторых приложений это будет желательным компромиссом», — говорит Хенцингер.

Превышение предельной скорости

Они протестировали схемы Simple PIR и Double PIR, применив их к задаче, в которой клиент стремится провести аудит определенной части информации о веб-сайте, чтобы убедиться, что веб-сайт безопасен для посещения. Чтобы сохранить конфиденциальность, клиент не может раскрывать веб-сайт, который он проверяет.

Самый быстрый метод исследователей смог успешно сохранить конфиденциальность при работе со скоростью около 10 гигабайт в секунду. Предыдущие схемы могли обеспечить пропускную способность только около 300 мегабайт в секунду.

Они показывают, что их метод приближается к теоретическому пределу скорости для поиска частной информации — это почти самая быстрая из возможных схем, которую можно построить, в которой сервер касается каждой записи в базе данных, добавляет Корриган-Гиббс.

Кроме того, их метод требует только одного сервера, что делает его намного проще, чем многие высокопроизводительные методы, требующие двух отдельных серверов с идентичными базами данных. Их метод превзошел эти более сложные протоколы.

«Я думал об этих схемах в течение некоторого времени, и я никогда не думал, что это может быть возможно с такой скоростью. Фольклор заключался в том, что любая схема с одним сервером будет очень медленной. Эта работа переворачивает все это представление с ног на голову», — говорит Корриган-Гиббс.

Хотя исследователи показали, что они могут создавать схемы PIR намного быстрее, все еще предстоит проделать большую работу, прежде чем они смогут применить свои методы в реальных сценариях, говорит Хенцингер. Они хотели бы сократить расходы на связь в своих схемах, сохраняя при этом возможность достижения высоких скоростей. Кроме того, они хотят адаптировать свои методы для обработки более сложных запросов, таких как общие запросы SQL, и более требовательных приложений, таких как общий поиск в Википедии. И в долгосрочной перспективе они надеются разработать более совершенные методы, которые смогут сохранить конфиденциальность, не требуя, чтобы сервер касался каждого элемента базы данных.

«Я слышал, как люди решительно заявляли, что PIR никогда не будет практичным. Но я бы никогда не поставил против технологии. Это оптимистичный урок, который можно извлечь из этой работы. Всегда есть способы внедрять инновации», — говорит старший автор Винод Вайкунтанатан, профессор EECS и главный исследователь CSAIL.

«Эта работа значительно повышает практическую стоимость поиска частной информации. Хотя было известно, что схемы PIR с низкой пропускной способностью подразумевают криптографию с открытым ключом, которая обычно на порядки медленнее, чем криптография с закрытым ключом, в этой работе разрабатывается оригинальный метод преодоления разрыва. Это достигается за счет разумного использования специальных свойств схемы шифрования с открытым ключом благодаря Regev, чтобы перенести подавляющую часть вычислительной работы на этап предварительного вычисления, на котором сервер вычисляет короткую «подсказку» о базе данных», — говорит Юваль Ишай, профессор компьютерных наук в Технион (Израильский технологический институт), который не принимал участия в исследовании.

«Что делает их подход особенно привлекательным, так это то, что одна и та же подсказка может быть использована неограниченное количество раз любым количеством клиентов. Это делает (умеренную) стоимость вычисления подсказки незначительной в типичном сценарии, когда к одной и той же базе данных обращаются много раз.»

Источник: https://techxplore.com/news/2022-12-faster-privacy-online.html?utm_source=nwletter&utm_medium=email&utm_campaign=daily-nwletter