Существует ли доказательство с нулевым разглашением хешированного секрета?

Алиса хочет поделиться секретом $S$ с Бобом, поэтому она шифрует его закрытым ключом Боба.

Боб сейчас не в сети, поэтому Виктор тем временем позаботится о его безопасности.

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

Алиса делает это

зашифрованный секрет = зашифровать (секрет, bobsPublicKey)

Виктор делает это

Verify(encryptedSecret, hashOfSecret) => true
проверить("что-нибудь еще", hashOfSecret) => false

Разве такое проверять функция существует?

Частная проверка решения судоку, разговор Боу-Максвелла и транзакция биткойнов на семинаре Financial Crypto 2016.

Проблема, решенная с проверкой, была:

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

Было введено и реализовано неинтерактивное доказательство, чтобы убедиться, что:

1. открытый текст является действительным решением судоку для поставленной головоломки;
2. зашифрованный текст создавался с помощью ключа;
3. ключ представляет собой прообраз хеш-значения, которое было отправлено покупателю вместе с зашифрованным текстом.

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

Краткий практический ответ: можно проверить прообраз хэша с помощью доказательства zkSNARK. Другой (общий) ответ: интерактивная система проверки существует для любого языка NP.

Наглая реклама: была разработана альтернативная схема проверки решения судоку, начиная с представления полиномиального набора и решения «игральные карты» Наора, представленного на IEEE ATIT 2019.

https://github.com/vadym-f/Sudoku_solvability_proof/tree/master/IEEE_ATIT_2019

Существует ZK-STARK, который доказывает, что вы знаете прообраз значения. «Утверждение Rescue-Hash, подтвержденное проверкой, приведенной в этом коде, таково:

«Я знаю последовательность из n + 1 входов {w_i} такую, что H(...H(H(w_0, w_1), w_2) ..., w_n) = p»

куда:

H — спасательная хэш-функция.
Каждый w_i представляет собой набор из 4 элементов поля. Это частные входные данные, известные только доказывающему.
p — общедоступный вывод хэша (который также состоит из 4 элементов поля).

" https://github.com/starkware-libs/ethSTARK/дерево/зигги