Пост-квантовые доказательства с нулевым разглашением

From CryptoWiki
Jump to: navigation, search

Пост-квантовые доказательства с нулевым разглашением – протоколы доказательства с нулевым разглашением знаний, которые квантово-устойчивы.

Квантово-устойчивыми системами/протоколами, считаются такие системы/протоколы, которые нельзя скомпрометировать, используя мощность вычислений квантового компьютера. Термин квантово-устойчивости вводится в пост-квантовой криптографии.

Contents

Постановка задачи защиты информации

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

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

Теоретические основы решения задачи

Переформулировка определений и перенос понятий на квантовые аналоги во многих случаях затрудняется двумя особенностями квантовой теории:

- квантовая информация не может быть скопирована, то есть каждый процесс уникален и нельзя скопировать состояние системы в середине или откатиться назад, в случае неудачного завершения процесса;

- любое считывание информации о состоянии фотона, несущего информацию, влечет к необратимым изменением его состояний.

Интерактивные пост-квантовые доказательства с нулевым разглашение

John Watrous в своей работе удалось решить трудности и перенести классическую модель доказательства с нулевым разглашением на квантовую теорию. В его работе обсуждались интерактивные системы.

Описание системы

Пусть (V,P) - квантовая или классическая интерактивная система доказательств, как и в классической Р — доказывающий, а V — проверяющий. Измерения P и V не влияют на число, длину и порядок входного сообщения X. Эти параметры будут определяться, как |X|.

V' –– любой квантовый процесс, который взаимодействует с доказывающим P. ать, На вход V' поступает, как общая входная строка, так и вспомогательная. Поскольку V' определен, как квантовый, следовательно, он работает на квантовых регистрах и вспомогательная входная и выходная строка являются квантовыми. У квантовых регистров неопределенное начальное состояние. Для V' существуют функции q и r, определяющих число входящих вспомогательных и выходных кубит. V' является полиномиальным верификатором времени, когда V' описано полиномиально-временным семейством квантовых цепей. Физический процесс взаимодействия P с V' на входе порождает некоторый супер-оператор : [n = q(|x|); m = r(|x|)], где n – вспомогательные кубиты; m – выходные кубиты.

Упрощенное определение:

Квантово-статистической с нулевым разглашением знанием называется такая интерактивная система доказательств (V, P), где для каждого генерируемого полиномиального квантового верификатора V' существует полиномиальным квантовый симулятор SV', удовлетворяющие следующим условиям:

1) r и q согласовываются верификатор V' и симулятор SV'

2) Допустимый супер-оператор Ф(x) (от взаимодействия между V' и P на входе X) и допустимый супер-оператор Ψ(x) (от симулятор SV' на вход X). Тогда существует δ ничтожно малая: |(|Φ(x)-Ψ(x)|)|⋄< δ(|x|) для ∀x∈A_yes

Подтверждение

Интерактивные системы доказательств, имеет совершенную полноту и обоснованность ошибка 1/2; если G0≅G1, то V с уверенностью принимает 1, и если G0≇G1, то P' не сможет убедить V принять решение с вероятностью больше 1/2. Если P обладает знанием изоморфизма σ, то его можно принять за полиномиальное время.

По определению (V, P) является итерактивной системой с доказательством нулевого разглашения знаний относительно любого классического полиномиального верификатора времени V'. Для уменьшения ошибки устойчивости до экспоненциально малого уровня может применено последовательное повторение с последующим единогласным голосованием.

Необходимо рассмотреть ограниченный тип верификатора следующим образом:

1) В дополнение к (G0,G1) верификатор принимает в качестве входных данных квантовый регистр W, представляющий вспомогательный квантовый вход. Верификатор будет использовать два дополнительных квантовых регистра, которые функционируют как рабочее пространство: V, который является произвольным (полиномиальным) регистром, и A, который является одним кубитным регистром. Регистры V и A инициализируются в их нулевое состояние до начала протокола.

2) При первой перессылке сообщений P посылает n-вершинный граф. Каждому графу H соответствует унитарный оператор V'_H, которым действуют на регистры (W, V, A).

3) V' измеряет полученный по воздействием регистр и отправляет полученный бит a проверяющему.

4) P в ответ посылает перестановку τ ∈ S(n)

5) V' выводит регистр (W, V, A), граф H и перестановку τ, полученными во время протокола.

Произвольное квантовый верификатор полиномиального времени может быть смоделирован как верификатор этой ограниченной форм. К выходу симулятора, который построен для соответствующего верификатора, может быть применена такая же постобработка. {V', H} однозначно определяет верификатор, а соответственно и симулятор.

Пусть G0≅G1

Отправляемое сообщение ничем не отличается от сообщения отправляемого при классическом варианте протокола. Такая схема во многом упрощает просмотр используемых квантовых регистров Y и Z. Множество всех простых неориентированных графов обозначим Gnс множеством вершин {1,…,n}. Для каждого H ∈ Gn и a ∈ Σ определено линейное отображение

ПКНР1.JPG

Если начальное состояние регистра W – это чистое состояние |ψ> ∈ W, то состояние регистров (W, V, A) после воздействия верификатора:

ПКНР2.JPG

Состояния регистров (W, V, A) в стандартном базисе после воздействия верификатора и А в стандартном базисе:

ПКНР3.JPG

Супер-оператор Ф(х), который является результатом взаимодействия:

ПКНР4.JPG

В частном случае, когда вероятность получения нулевого значения равна 1/2, устанавливается, что результаты процедуры моделирования выливается в оператор Φ(|ψ><ψ|) в случае, если начальное состояние W = |ψ>. Такой вариант является улучшение классического варианта, так как сложность в наихудшем случае будет полиномиальной.

Неитрекативные доказательства с нулевым разглашение

В работе Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives исследуются неинтерактивные доказательства с нулевым разглашением для возможности их применения для реализации пост-квантовых цифровых подписей.

Авторы статьи за основу берут неитерактивную версию ZKBoo.

ZKBoo

ZKBoo опирается на протокол конфиденциального вычисления (MPC). В ZKBoo идей является замена MPC на (2,3)-разложение цепи.

Построения доказательства происходит по следующей схеме:

1) P вычисляет f с использованием декомпозиции и фиксирует 3 состояния;

2) P отправляет обязательства и выходные данные каждого состояния предварительно использовав эвристику FS;

3) В ответ приходит какие 2 из 3 состояний открываются для каждого N запуска;

4) V выполняет проверку выходных данных на полноту восстановления; проверяет, что каждое из 2 открытых состояний вычислено корректно и вычисляет корректность вычисления вызова.

Количество запусков, выбирается так что бы ошибка была незначительной, так что бы возможность попадания злоумышленника во все запуски была минимальной.

ZKB++

ZKB++ является модифицированной версией ZKBoo.

1) Разложение: в View1 и View2, P должен включать k(i), поскольку x(i) может быть детерминистически вычислен V;

2) Не включение входных данных: входные доли, генерирующиеся псевдослучайно, используя k(i), не нужно включать их в представление, когда e = 1. Данные нужно отправлять, только в случае, если e = 2 или e = 3, поскольку для третьего состояния, входные данные не могут быть получены из начального, так как генерируются псевдослучайно, используя k(i);

3) Без отправки обязательств;

4) Отсутствие дополнительно случайной последовательности для обязательств;

5) Без учета выходных данных: выходные данные могут быть вычислены из остальной части доказательств;

6) Не включение состояния-представления: V может пересчитывать состояние, учитывая только случайные k(e) и k(e+1).

Полная схема ZKB++ представлена на рисунке 1.

Рисунок 1 - Схема ZKB++

Улучшения предпринятые для оптимизации ZKBoo уменьшает размер доказательств в 2 раза для ZKB++.

Глоссарий

Библиографический указатель

Перейти к списку литературы

Вернуться к оглавлению

Андрианова В.К., 2018