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

Определите, равны ли два числа, не раскрывая дополнительной информации

флаг ma
Matteo Monti

Рассмотрим следующий сценарий. Алиса выбирает номер А; Боб выбирает число B. И A, и B принадлежат относительно небольшому набору X (под малым я подразумеваю, что X можно легко пройти циклом: для интуиции представьте X размером с колоду карт). Я хотел бы, чтобы Алиса и Боб участвовали в протоколе, который сообщает обоим, если A = B. Если A != B, то у Алисы не должно быть никакой дополнительной информации о B, а у Боба не должно быть никакой дополнительной информации об A.

Интересно, возможно ли это? Если бы X было очень большим, и если предположить без ограничения общности, что A — простое число, Алиса могла бы выбрать произвольное простое число P, большее, чем наибольшее значение в X, и послать Бобу A * P. Затем Боб мог бы попытаться разложить A * P на B: если это сработает, то A = B. Однако это, очевидно, предполагает, что Боб не может попробовать все элементы X. Если X мало, это предположение немедленно отпадает.

62
1 + 1
Perseids avatar
флаг na
Perseids
Кстати, это называется [проблема социалистических миллионеров](https://en.wikipedia.org/wiki/Socialist_millionaire_problem).
0
Ответить
Рейтинг:3
poncho avatar Crypto
флаг my
poncho

Да, это вполне возможно.

Очевидный подход состоял бы в том, чтобы Алиса и Боб выполнили протокол сбалансированного обмена ключами с проверкой подлинности пароля (PAKE) с $А$ и $В$ быть их «паролями». Если они придумают один и тот же общий секрет, $А=В$, а если придумают $А\не Б$ и они больше ничего не узнают о $А$ и $В$

Существует несколько протоколов PAKE; см. статья в википедии для некоторых из наиболее распространенных.

Один из таких способов (упрощенный CPACE) для сравнения значений $а$ известен Алисе и $b$ известный Бобу, будет выбирать несвязанные значения $G$ и $N$ (Я написал это, предполагая эллиптические кривые; его можно напрямую перевести в группу modp, за исключением того, что вычитание становится модульной инверсией) и:

  • Алиса выбирает случайное значение $г$ и вычисляет $C = г G + N$; она посылает $С$

  • Боб выбирает случайное значение $s$ и вычисляет $D = s G + b N$; он посылает $Д$

  • Алиса вычисляет $S = r (D - N)$; Боб вычисляет $T = s (C - b N)$; если $а=б$, тогда $С=Т$; иначе они не связаны.

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

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

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

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