Частное извлечение информации
Кратко
- Частное извлечение информации, или PIR, позволяет устройству получать один элемент из базы данных сервера так, чтобы сервер не узнал, какой именно элемент был запрошен
- Zcash нуждается в этом, потому что приватный кошелек не может спрашивать у сервера, какие транзакции принадлежат ему, не выдав себя
- Сегодня кошельки загружают и сканируют гораздо больше данных, чем им нужно, и это одна из главных причин медленной синхронизации
- PIR позволил бы кошельку получать только собственные данные в приватном режиме, устраняя это узкое место и сохраняя конфиденциальность
- Это активная область исследований для Zcash: в теории технология очень мощная, и сейчас ее делают практичной для реальных кошельков
Для кого это
- Для всех, кто задавался вопросом, как приватный кошелек находит свои монеты, не раскрывая, какие именно
- Для новичков, которые постоянно видят упоминания PIR рядом с работой по масштабированию Zcash
- Для читателей, которые сначала хотят понять саму идею, а уже потом лежащую под ней криптографию
Какую проблему PIR решает для Zcash
Zcash скрывает, кому предназначена транзакция. Эта приватность создает неудобный вопрос: если сеть не видит, какие транзакции принадлежат вам, как ваш собственный кошелек их находит?
Сегодня ответ довольно грубый. Кошелек не может спросить у сервера, какие транзакции мои, потому что такой вопрос раскрыл бы именно то, что Zcash пытается скрыть. Поэтому вместо этого кошелек загружает большой объем данных и локально проверяет каждый элемент, чтобы понять, что принадлежит ему. Это работает и сохраняет приватность, но это медленно и тяжеловесно. Такое сканирование является одной из главных причин, почему синхронизация кошелька может казаться вялой.
Идеальным решением был бы способ, при котором кошелек мог бы запросить у сервера точно свои данные и получить их, а сервер при этом так и не узнал бы, что именно было запрошено. Именно это и обеспечивает частное извлечение информации.
Что такое PIR
Частное извлечение информации — это криптографический метод, который позволяет клиенту прочитать одну запись из базы данных сервера, не раскрывая серверу, какую именно запись он прочитал.
Представьте библиотеку, где вы можете получить именно ту книгу, которая вам нужна, но библиотекарь так и не узнает, какую книгу он вам выдал. Вы получаете свой экземпляр, а ваш интерес остается приватным. PIR — это математическая версия этой идеи, примененная к любой базе данных.
Эта концепция изучается в криптографии уже десятилетиями. Впервые она была представлена в 1995 году Chor, Goldreich, Kushilevitz и Sudan, которые описали подход с несколькими серверами, а первая версия для одного сервера появилась в 1997 году у Kushilevitz и Ostrovsky. Это не изобретение Zcash, а уже сложившаяся область, которую Zcash теперь применяет к реальной и устойчивой проблеме.
Как работает PIR на базовом уровне
Существует два широких подхода к построению PIR, и это различие важно.
Первый использует несколько серверов. Клиент отправляет каждому из нескольких серверов часть запроса, а затем локально объединяет их ответы. Ни один отдельный сервер не видит достаточно, чтобы понять, что именно было запрошено. Это эффективно, но зависит от того, что серверы не вступают в сговор друг с другом, а это трудно гарантировать в реальном мире.
Второй использует один сервер и продуманную криптографию вместо нескольких участников. Здесь клиент опирается на специальный инструмент под названием гомоморфное шифрование, и именно это направление наиболее полезно для реального развертывания, потому что ему не нужны несколько не вступающих в сговор серверов.
Механизм: гомоморфное шифрование
Гомоморфное шифрование — это вид шифрования, который позволяет серверу выполнять вычисления над данными, пока они остаются зашифрованными. Сервер получает корректный зашифрованный ответ, так и не увидев исходные значения.
Вот идея PIR с одним сервером, построенного таким образом. Клиенту нужен элемент номер три из списка. Он формирует запрос, который по сути представляет собой зашифрованное «да» для позиции три и зашифрованное «нет» для всех остальных позиций. Для сервера этот запрос — просто бессмысленный шум, он не может определить, в какой позиции находится «да».
Затем сервер объединяет свою базу данных с этим зашифрованным запросом, используя особые свойства гомоморфного шифрования: он умножает каждый сохраненный элемент на соответствующее зашифрованное «да» или «нет» и складывает результаты. На выходе получается один зашифрованный пакет, содержащий ровно тот элемент, который хотел клиент, и ничто не раскрывает, какой именно это был элемент. Клиент расшифровывает этот пакет и читает свой элемент. Сервер ответил на вопрос, так и не узнав сам вопрос.
Более сильная версия, называемая symmetric PIR, добавляет вторую гарантию: клиент узнает только тот элемент, который он запросил, и ничего не узнает о других записях в базе данных. Это защищает не только клиента, но и саму базу данных.
Более пристальный взгляд для технических читателей
Современные схемы для одного сервера строятся на решеточной криптографии, чаще всего на предположении learning with errors. Запрос клиента представляет собой вектор шифротекстов, то есть шифрование единицы в целевом индексе и нуля во всех остальных, а само шифрование аддитивно гомоморфно, поэтому сервер может складывать шифротексты и умножать их на открытые записи базы данных без расшифровки.
Сервер рассматривает базу данных как матрицу, применяет к ней зашифрованный вектор выбора и возвращает один шифротекст, который расшифровывается в нужную строку. Поскольку запрос неотличим от случайного шума, сервер не получает никакой информации об индексе.
Исторически главным препятствием всегда была стоимость. В наивной реализации сервер должен обращаться к каждой записи в базе данных для каждого запроса, что дорого вычислительно, а шифротексты имеют большой размер, что дорого по пропускной способности. Недавние исследования борются с этим с помощью предварительной обработки: схемы вроде SimplePIR и FrodoPIR позволяют серверу заранее подготовить базу данных и выдать каждому клиенту небольшую подсказку, перенося значительную часть работы в офлайн-фазу, чтобы живые запросы стали быстрыми. Полезный побочный эффект состоит в том, что конструкции на основе решеток также считаются устойчивыми к квантовым атакам, что соответствует более широкому движению Zcash в сторону постквантовой приватности.
PIR в Zcash
PIR — часть усилий по тому, чтобы сделать Zcash одновременно приватным и быстрым в масштабе.
Целью является описанное выше узкое место со сканированием кошельком. Работа в Valar Group развивает методы частного извлечения информации, чтобы кошелек мог получать собственные данные с сервера, а сервер при этом не узнавал, какие записи были запрошены. Одно из конкретных применений — приватная проверка nullifier. Nullifier — это уникальная метка, публикуемая при трате note, которая не позволяет потратить одни и те же средства дважды. Кошельку часто нужно проверить, появился ли уже данный nullifier, иными словами, не потрачена ли еще note, а выполнение такой проверки через сервер сегодня может раскрыть, о какой note идет речь. Частное извлечение информации позволяет кошельку задать этот вопрос, не раскрывая, какой nullifier его интересует. Это идет параллельно с другой работой по масштабированию, включая Project Tachyon и новое ПО для узлов, направленной на устранение ограничений производительности, которые сегодня сдерживают приватные кошельки.
Важно честно говорить о текущем этапе. Это активные исследования и инженерная работа, а не завершенная и уже выпущенная функция. Концепция хорошо устоялась, направление определено, но сделать PIR достаточно эффективным для повседневных кошельков на обычных устройствах — это как раз та сложная часть, над которой сейчас и работают.
Распространенные заблуждения
- PIR скрывает, какой именно элемент вы запросили, но не обязательно скрывает сам факт обращения к серверу, метаданные на уровне сети — это отдельная проблема
- PIR не уникален для Zcash, это общий криптографический инструмент, который Zcash применяет к приватности кошельков
- Более быстрая синхронизация благодаря PIR — это цель, над которой еще работают, а не функция, уже присутствующая в кошельках
- Загрузка всего подряд и локальное сканирование, текущий подход, сохраняют приватность, но работают медленно; PIR стремится сохранить приватность и убрать эту медлительность
Связанные страницы
