Несложная криптографическая задача

Правка ru5, от AlexanderBolshakov, 2016-02-02 03:45:09

Пару месяцев назад я придумал одну задачу. Рассказал ее коллеге, и мы вместе нашли некое подобие решения. Теперь мне бы хотелось услышать какие-либо новые идеи.

Условие: Алиса и Боб загадали по однобайтовому числу (пусть эти числа будут называться a и b соответственно). Требуется придумать протокол общения между Алисой и Бобом, позволяющий им понять: равны ли a и b? При этом хочется, чтобы Алиса и Боб выдали друг другу как можно меньше информации о своих числах (в идеале — только сам факт равенства/неравенства). Предполагается, что Алиса и Боб будут строго следовать протоколу. Предполагается, что посторонних участников в задаче нет.

Прошу писать идеи решения в комментариях и прятать их под спойлеры.

UPD. hellman_ предложил решение, которое на первый взгляд удовлетворяет вышеописанному требованию к идеальному решению.

UPD2. OWNAGE от eatmore.

UPD3. Опубликовал неидеальное авторское решение.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru5 Русский AlexanderBolshakov 2016-02-02 03:45:09 123
ru4 Русский AlexanderBolshakov 2016-02-01 00:10:06 117
ru3 Русский AlexanderBolshakov 2016-01-31 22:16:29 215 Мелкая правка: 'йлеры.\n\nUPD. [user:hel' -> 'йлеры.\n\n**UPD.** [user:hel'
ru2 Русский AlexanderBolshakov 2016-01-31 19:16:36 4 Мелкая правка: 'гадали по однобайтовому числу (пу' -> 'гадали по **однобайтовому** числу (пу'
ru1 Русский AlexanderBolshakov 2016-01-31 18:45:07 762 Первая редакция (опубликовано)