Проблема Yaos Millionaires - Википедия - Yaos Millionaires problem
Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) (Узнайте, как и когда удалить этот шаблон сообщения)
|
Проблема миллионеров Яо это безопасные многосторонние вычисления проблема, представленная в 1982 году компьютерным ученым и теоретиком вычислений Эндрю Яо. В задаче обсуждаются два миллионера, Алиса и Боб, которые заинтересованы в том, чтобы узнать, кто из них богаче, не раскрывая при этом их фактического богатства.
Эта проблема аналогична более общей задаче, где есть два числа и и цель - определить, выполняется ли неравенство верно или неверно без раскрытия фактических значений и .
Проблема миллионеров - важная проблема в криптография, раствор которого используется в электронная коммерция и сбор данных. Коммерческим приложениям иногда приходится сравнивать конфиденциальные числа, безопасность которых важна.
Для этой проблемы было предложено множество решений, среди которых первое решение, представленное самим Яо, было экспоненциальным во времени и пространстве.[1]
Протоколы и доказательства
Протокол Сяо-Ин Линь и Вэнь-Гэй Цзэн
Позволять быть двоичной строкой длины п.
Обозначим 0-кодировку s в качестве и 1-кодирование s в качестве
Тогда протокол[2] основано на следующем утверждении:
- Предположить, что а и б двоичные строки длины п биты.
- потом если наборы и имеют общий элемент (где а и б являются двоичными кодировками соответствующих целых чисел).
Протокол использует эту идею для практического решения проблемы миллионеров Яо, выполняя частный пересечение множества между и .
Протокол Иоаннидиса и Ананта
Протокол[3] использует вариант не обращая внимания на передачу Называется 1-2 незаметной передачи. В этой передаче один кусочек передается следующим образом: у отправителя два бита и . Получатель выбирает , а отправитель отправляет с протоколом передачи не обращая внимания, так что
- получатель не получает никакой информации о ,
- значение не передается отправителю.
Для описания протокола номер Алисы обозначается как , Номер Боба как , и предполагается, что длина их двоичного представления меньше, чем для некоторых . Протокол включает следующие шаги.
- Алиса создает матрицу размера из -битовые числа, где это длина ключа в протоколе передачи без внимания. Кроме того, она выбирает два случайных числа и , куда и .
- будет -й бит числа, которое появляется в ячейке (куда указывает на младший бит ). Кроме того, обозначается как -й бит числа Алисы . Для каждого , Алиса выполняет следующие действия.
- Для каждого бита она устанавливает и в случайные биты.
- Если , позволять , иначе пусть и для каждого набор на случайный бит.
- За набор и к .
- Для каждого , будет случайным -битовое число, и будет другое количество биты, где все биты, кроме последних двух, случайны, а последние два вычисляются как и , куда это побитовый XOR операция.
- За набор . Где указывает на побитовое вращение из слева от биты.
- Для каждого , Боб переводы с протоколом незаметной передачи, где , и это -й бит .
- Алиса отправляет Бобу .
- Боб вычисляет побитовое исключающее ИЛИ всех чисел, полученных на шаге 3, и начиная с шага 4. Боб просматривает результат слева направо, пока не найдет большую последовательность нулевых битов. Позволять быть битом справа от этой последовательности ( не равно нулю). Если бит справа от равно 1, то , иначе .
Доказательство
Правильность
Боб вычисляет окончательный результат из , а результат зависит от .K, и поэтому c также можно разделить на 3 части. Левая часть не влияет на результат. Правая часть содержит всю важную информацию, а в середине - последовательность нулей, разделяющих эти две части. Длина каждого раздела c связан со схемой безопасности.
Для каждого я, только один из имеет ненулевую правую часть, и это если , и иначе. Кроме того, если , и имеет ненулевую правую часть, то также имеет ненулевую правую часть, и два крайних левых бита этой правой части будут такими же, как и один из . В результате правая часть c является функцией переданных Бобом записей, соответствующих уникальным битам в а и б, и единственные биты в правой части в c которые не являются случайными, - это два крайних левых бита, которые определяют результат , куда я бит самого высокого порядка, в котором а и б отличаются. В конце концов, если , то два крайних левых бита будут 11, и Боб ответит, что . Если биты равны 10, то , и он ответит . Если , то в нем не будет правой части c, и в этом случае два крайних левых бита в c будет 11, и укажет результат.
Безопасность
Информация, которую Боб отправляет Алисе, защищена, потому что она отправляется через скрытую передачу, которая является безопасной.
Боб получает от Алисы 3 числа:
- . Для каждого Боб получает один такой номер, и является случайным, поэтому никакая защищенная информация не преобразуется.
- N. Это XOR случайных чисел, поэтому не раскрывает никакой информации. Актуальная информация раскрывается только после расчета c.
- c. То же самое касается c. Левая часть c является случайным, и правая часть также случайна, за исключением двух крайних левых битов. Выведение любой информации из этих битов требует угадывания некоторых других значений, и вероятность их правильного угадывания очень мала.
Сложность
В сложность из протокол является . Алиса конструирует dчисло длины для каждого бита а, а Боб вычисляет XOR d времена d-длины чисел. Сложность этих операций . Коммуникационная часть также занимает . Следовательно, сложность протокола составляет
Смотрите также
- Криптография
- ЮАР
- Безопасные многосторонние вычисления
- Социалистический миллионер - вариант, при котором миллионеры хотят определить, равны ли их состояния.
внешняя ссылка
Рекомендации
- ^ Яо, Эндрю С. (ноябрь 1982 г.). «Протоколы для безопасных вычислений». FOCS. 23-й ежегодный симпозиум по основам компьютерных наук (FOCS 1982): 160–164. Дои:10.1109 / SFCS.1982.88.
- ^ Линь Сяо-Инь; Цзэн, Вен-Гэй (07.06.2005). Эффективное решение проблемы миллионеров на основе гомоморфного шифрования. Прикладная криптография и сетевая безопасность. Конспект лекций по информатике. 3531. С. 456–466. CiteSeerX 10.1.1.75.4917. Дои:10.1007/11496137_31. ISBN 978-3-540-26223-7.
- ^ Ioannidis, I .; Грама, А. (2003). Эффективный протокол для проблемы миллионеров Яо. 36-я Ежегодная Гавайская международная конференция по системным наукам, 2003 г. Труды. IEEE. CiteSeerX 10.1.1.110.8816. Дои:10.1109 / hicss.2003.1174464. ISBN 978-0769518749.