Почему пространство случайности должно быть значительно больше, чем пространство обязательств |R|>>|C| для создания строки обязательства?

Sheldon

26.06.2023, 11:05

Почему пространство случайностей должно быть значительно больше, чем пространство обязательств |R|>|C|? картина из https://youtu.be/IkNZWJFcfcU?t=236

0 + 0

случайность

устойчивость к столкновениям

обязательства

Рейтинг:1

Crypto

Daniel S

26.06.2023, 12:09

Для свойства скрытия мы требуем, чтобы значение фиксации не предоставляло никакой информации о сообщении. В частности, мы надеемся, что для любого заданного сообщения $м$ это возможно для $Ч(м,р)$ принять все возможные значения в $С$ (иначе можно было бы исключить некоторые сообщения как соответствующие некоторым обязательствам). Если $Ч$ ведет себя как случайная функция, то маловероятно, что она будет обладать этим сюръективным свойством, если только $|R|>|C|\log|C|$.

Более сильно мы, вероятно, хотим, чтобы значения $Ч(м,р)$ для любого фиксированного $м$ быть распределены равномерно по значениям $С$.

Обратите внимание, что это требования теоретико-информационного «нулевого знания», а не требования, ограничивающие сложность/вычисления.

0 + 0

Daniel S

26.06.2023, 14:05

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

Ответить

poncho

26.06.2023, 17:26

"В частности, мы надеемся, что для любого заданного сообщения $m$ $H(m,r)$ может принимать все возможные значения в $C$"; хотя этого было бы достаточно, на самом деле это не обязательно. Что необходимо, так это то, что любой вероятный противник не сможет получить какую-либо информацию о $m$ из обязательства; однако, поскольку вычислительно неограниченные противники неправдоподобны, мы можем рассматривать меньшие цели (такие как вывод информации о $m$ вычислительно невыполнимой..)

Ответить

Daniel S

26.06.2023, 17:47

@poncho: Существует три уровня сокрытия в схемах обязательств [идеальный, статистический и вычислительный] (https://en.wikipedia.org/wiki/Commitment_scheme#Perfect,_statistical,_and_computational_hiding). Лектор молчаливо требует статистического сокрытия (отсюда моя ссылка на теорию информации), и для этого необходимо требование $|R|\gg |C|$.

Ответить

Admin

Этот вопрос на других языках:

EN: Why randomness space must be significantly larger than the commitment space |R|>>|C| in order to generate a commitment string?

TH: เหตุใดพื้นที่สุ่มจึงต้องใหญ่กว่าพื้นที่ผูกมัด |R|>>|C| อย่างมาก เพื่อสร้างสายผูกมัด?

RO: De ce spațiul aleatoriu trebuie să fie semnificativ mai mare decât spațiul de angajament |R|>>|C| pentru a genera un șir de angajament?

RU: Почему пространство случайности должно быть значительно больше, чем пространство обязательств |R|>>|C| для создания строки обязательства?

VI: Tại sao không gian ngẫu nhiên phải lớn hơn đáng kể so với không gian cam kết |R|>>|C| để tạo ra một chuỗi cam kết?

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

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