Рейтинг:2

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

флаг cn

Два человека хотят придумать случайное число. Они не доверяют ни друг другу, ни какой-либо третьей стороне. Какие известны решения этой проблемы?

Я изучаю квантовую криптографию и в настоящее время работаю над генерацией квантовых случайных чисел.Приветствуются любые решения, как классические, так и квантовые.

РЕДАКТИРОВАТЬ

Итак, вот что я понял, прочитав некоторые документы. Предположим, что две недоверчивые стороны хотят получить случайный бит. В классическом сценарии (без учета вычислительной сложности) задача невыполнима. В квантовом сценарии есть два варианта; сильные и слабые версии. Если желаемый результат каждой из сторон нет известно, что это называется сильной версией и наоборот. Сильная версия имеет ненулевую границу смещения, тогда как слабая версия может иметь произвольно маленькое смещение.

https://arxiv.org/pdf/1911.13283.pdf

Frédéric Grosshans avatar
флаг co
Не ответ, а просто помощь в поиске: эта проблема называется подбрасыванием монеты.
Dotman avatar
флаг cn
Спасибо вам за это. Это действительно помогло!
Рейтинг:5
флаг es

Требуемое случайное число представляет собой целое число от 0 до $\ell$. Каждый выбирает случайное число $x_i$ между 0 и $\ell$, и каждый выбирает $n$-битный случайный коэффициент ослепления $b_i$ куда $n\geq 128$ и $n$ должны быть согласованы заранее. Затем каждый объявляет обязательство по хэшированию, рассчитанное как $H(b\mathbin\|x)$. Затем каждый из них открывает свои обязательства, объявляя о своих ценностях. $b$ и $х$, и вычислить их случайное число как $$x_1 + x_2\pmod\ell.$$ Это квантово-безопасно, если хэш и выбор $n$ вместе являются квантово-безопасными.

Как указывает @poncho, человек, который открывает свое обязательство последним, может имитировать отказ от завершения протокола, если он недоволен конкретным общим случайным значением, которое будет сгенерировано во время этого вызова протокола.Это может быть проблемой, особенно если $\ell$ маленький.

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

poncho avatar
флаг my
Одной из атак на этот протокол является атака с имитацией сбоя; предположим, что Алиса выбрала $x_1$, а Боб выбрал $x_2$; они проходят через протокол, и Алиса открывает свое обязательство по $x_1$. Теперь Боб видит, что ему не нравится результат $x_1 + x_2 \bmod \ell$, и поэтому он имитирует сбой (сбой сети, перезагрузка компьютера и т. д.). Это можно решить с помощью метапротокола; может быть важно, чтобы вы это сделали
knaccc avatar
флаг es
@poncho спасибо, отличный момент
kelalaka avatar
флаг in
А если действительно ошибка? Почему честный человек должен терять средства в этом случае?
knaccc avatar
флаг es
@kelalaka Честный человек должен возобновить (а не перезапустить или отказаться) протокол, как только будут устранены технические трудности, и штрафа не будет. Нечестный человек захочет отказаться от протокола и никогда не возобновлять его.
Рейтинг:1
флаг cn

Я думаю Эта бумага решает хотя бы частично вашу проблему.

kelalaka avatar
флаг in
Мы называем это ответом только по ссылке и рассматриваем как комментарий. Не могли бы вы немного объяснить, что делает эта бумага?
Dotman avatar
флаг cn
Это было действительно полезно... @kelalaka Я постараюсь добавить комментарий, как только пойму
Dotman avatar
флаг cn
Итак, вот что я понял, прочитав некоторые документы. Предположим, что две недоверчивые стороны хотят получить случайный бит. В классическом сценарии (без учета вычислительной сложности) задача невыполнима. В квантовом сценарии есть два варианта; сильные и слабые версии. Если желаемый результат каждой стороны **не** известен, это называется сильной версией, и наоборот. Сильная версия имеет ненулевую границу смещения, тогда как слабая версия может иметь произвольно маленькое смещение.
Рейтинг:1
флаг in

Мануэль Блаум смотрел этот номер в 1981 году в Подбрасывание монеты по телефону: протокол решения невозможных проблем

Технические детали указаны на бумаге. Этот протокол гарантирует те (на бумаге жирным шрифтом ум);

  1. Если любой участник следует протоколу не поймает другого обмана, он или она может быть уверен, что каждая монета имеет ровно 50-50 независимых шансов выпадение орла (доказуемо при разумном предположении, что факторинг труден.
  2. Если любой участник ловит другого на мошенничестве, он или она может доказать это судье (это предполагает, что все сообщения отправляются подписанными).
  3. После того, как Боб подбрасывает монеты Алисе, она знает, какие монеты выпали орлом, а какие решкой. Он не должен иметь абсолютно никакого представления о том, как они появились. (даже не догадки).
  4. После серии подбрасываний монеты Алиса должна быть в состоянии доказать Бобу, какие монеты выпали орлом, а какие решкой..

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

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