Регистрация Войти
Рейтинг:2
jiedo avatar Crypto

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

флаг de
jiedo

Алиса разбила длинную строку P на два сегмента A и B. A относительно короткая, а B длинная.

Н = sha256 (А + В)

Боб не знает P, но знает H.

Может ли Алиса доказать Бобу, что A является префиксом P, но ей нужно только предоставить дополнительную информацию? намного короче чем Б?

70
1 + 7
kelalaka avatar
флаг in
kelalaka
Добро пожаловать в Cryptography.SE. Каково происхождение этого вопроса? Каковы размеры $A$ и $B$.
1
Ответить
jiedo avatar
флаг de
jiedo
Спасибо, это вопрос, о котором я думаю, когда изучаю доставку Bitcoin tx. Я надеюсь, что, не сообщая всех tx, я смогу доказать другим, какой первый utxo потрачен по этому tx. поэтому A составляет около 40 байт, B может превышать 1000 КБ.
0
Ответить
kelalaka avatar
флаг in
kelalaka
Ну, это ввод SHA256, поэтому, если вы не можете найти коллизию, вам нужно рассказать все.
0
Ответить
jiedo avatar
флаг de
jiedo
Понятно. Если A длинное, а B короткое, то можно доказать, что B — это суффикс P с содержанием короче, чем A. Но обратное кажется действительно невозможным.
0
Ответить
kelalaka avatar
флаг in
kelalaka
Если B короткое, то Боб может переборщить его
0
Ответить
jiedo avatar
флаг de
jiedo
Я имею в виду доказательство того, что B является **суффиксом**, если B короткое. без А. Боба нельзя использовать грубую силу.
0
Ответить
kodlu avatar
флаг sa
kodlu
что значит А+В? конкатенация?
0
Ответить
Рейтинг:3
Richard Thiessen avatar Crypto
флаг mx
Richard Thiessen

Из-за того, как работает SHA2, нет.

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

Хеширование Меркла-Дамгарда

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

Деревья Меркла

Если вы хотите быстро проверить подстроки, стандартным решением является использование Дерево Меркла.

Дерево Меркла

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

Если L1 и L2 были А строка и L3 и L4 были Б строка, Алиса может предоставить А вместе с Хэш 1 и Бобу не нужно знать L3 и L4 блоков для вычисления корневого хэша. Алиса может обрезать дерево, чтобы включить в него только то, что необходимо.

0 + 0
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.