Понятие нулевого разглашения в криптографии

Введение

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

На протяжении многих лет доказательства (и аргументы) ZK были неотъемлемой частью разработки многочисленных криптографических протоколов, в первую очередь безопасных вычислений общего назначения [37], а также конкретных задач, таких, например, как задачи о подбрасывании монет.[25]. Даже протоколы, удовлетворяющие более слабым понятиям ZK, таким, например, как сокрытие посредника (witness hiding) [29], обычно строятся только через протокол ZK. В частности, общая сложность ZK определяет общую сложность известных конструкций для этих задач.

Профессора Голдрейх (Goldreich) и Кравицк (Krawcyzk) выявили, that three round ZK arguments for NP with black-box simulation do not exist for languages outside BPP. Кроме того, для всех известных методов моделирования вне «черных ящиков» [3] требуется более трех раундов. Это стало препятствием для реализации протоколов широкого спектра во многих из вышеупомянутых задачах. В этой статье будет изучена возможность преодоления этого препятствия.

Необходимо ли НР (и когда оно необходимо)? Доказательства с нулевым разглашением обычно используются для обеспечения «честного поведения» участников криптографического протокола. Наличие НР дополнительно обеспечивает конфиденциальность водящих данных. Однако многие приложения с НР, описанные выше, сами по себе не гарантируют безопасность на основе моделирования, а только более слабую безопасность на основе неразличимости. Таким образом, сразу не ясно, нужна ли «полная» симуляция и использование НР для таких приложений.

Например, надежное сокрытие посредников требует, чтобы для двух неразличимых распределений операторов X1, X2 доказательство (или аргумент) для утверждения  x1 ← X1 не должно отличаться от доказательства (или аргумента) для утверждения  x2 ← X2. Все известные протоколы с надежным сокрытием посредников полагаются на аргументы НР со стандартным моделированием - и, следовательно, в конечном итоге требуется столько же раундов, сколько и аргументов НР. Подобные проблемы возникают и при скрытых вычислениях, вычислениях с сокрытием посредников и доказательств, а также сложных схем обязательств. Однако, непонятно, действительно ли применение НР необходимо в этих ситуациях.

Это ставит вопрос о том, можно ли разрабатывать «более слабые» стратегии моделирования в три раунда или меньше, что может быть использовано для восстановления нескольких итераций применения НР. В этой статье будет реализована такая ​​стратегия моделирования с использованием «черного ящика» всего за два раунда.

Distinguisher-Dependent Simulation. Наше начальное наблюдение заключается в том, что для любого криптографического протокола, предназначенного для indistinguishability-based security, the security reduction has access to an efficient distinguisher. В таких условиях можно утверждать, что безопасность осуществляется с помощью более слабой стратегии моделирования.

Идея distinguisher-dependent simulation не является новой и ранее изучалась в контексте интерактивных доказательств, где она упоминается как слабое НР (weak ZN, СНР). Применение СНР подразумевает, что любой бит информации, который может быть освоен верификатором путем взаимодействия с программой, можно моделировать, учитывая только исходные данные. Таким образом, СНР применимо для многих протоколов с НР, и, в частности, подразумевает использование более слабых технологий, таких, как WH и WI [29].