Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Предположим, что Алиса и Боб хотят разделить друг с другом истинно случайную двоичную последовательность, но опасаются, что некоторые из ее разрядов могут попасть в руки нарушителя. Тогда, задавая только верхнюю границу на количество информации, которую допустимо скомпрометировать, есть возможность повысить секретность посредством открытых обсуждений, с тем чтобы остановиться на более короткой и намного более секретной двоичной последовательности. Это остается возможным, даже если из-за ошибок при передаче и после злонамеренной подделки исходная последовательность вашего друга оказалась бы слегка отличной от вашей. Данный вопрос был исследован независимо Чарльзом Беннеттом, Жилем Брассаром и Жан-Марком Робертом [36], а также Бенни Чором, Одедом Голдрейчем, Йоханом Хастадом, Джоэлем Фридманом, Стевеном Рудичем и Романом Смоленским [118]. Решение этого вопроса, как описано в следующей главе, является основной составной частью для установления квантового канала. См. также [32, 311].
Дополнительные применения 12<f
Полислучайным семейством функций называется набор эффективно вычисляемых функций, которые являются полиномиально неотличимыми от истинно случайных функций. Это понятие было введено Одедом ГолдреЙчем, Шафи Гольдвассер и Сильвио Микэли [193], которые предложили также его многочисленные применения [192]. Одним из таких применений являются вычислительно надежные аутентификационные метки, для которых требуются короткие секретные разделенные ключи. Майком Люби и Чарльзом Раковом в [254] были построены полислучайные семейства перестановок. Довольно странно, что эти перестановки были получены с помощыб некоего процесса, похожего на DES:"" v
Сублиминалъный канал — это канал, который допускает два уровня шифрования. Секретное сообщение может быть восстановлено от криптограммы, используя «регулярный» секретный ключ, но чтобы получить сублиминальное сообщение, необходим некий дополнительный ключ. Это понятие, которое было введено Густавом Симмонсом, позволяет двум сторонам осуществлять конфиденциальную связь, в то время как ничего не подозревающий нарушитель остается в полном убеждении, что он может читать сообщения обеих сторон [328, 331]. См. также [148].
Несмотря на то, что до сих пор никакой практически значимой криптографической схемы для защиты программного обеспечения пока еще не предложено, интересные теоретические идеи в этом отношении были представлены Амиром Херцбергом и Шломитом Пинтером [216] и Одедом ГолдреЙчем [191]: В частности, Голдрейч делает различие между защитой от незаконного копирования и защитой от незаконного воспроизведения дистрибутива. См. также [283].
Проблема о миллионере, которая впервые была поставлена Эндрю Яо, формулируется следующим образом: два миллионера хотят выяснить, кто из них самый богатый, но так, чтобы ни один из них не смог узнать, каково богатство другого [365]. Это — специальный случай секретного распределенного вычисления, с помощью которого Алиса и Боб хотят вычислить значение некоторой согласованной функции f(a,b) с секретным, известным Алисе, входом а и входом Ь, также секретным, но известным Бобу, таким способом, что ни одна из сторон не может получить никакой информации, чтобы узнать значение секретного входа
124 Применения
Глава 6
другой (кроме той, что может быть извлечена из значения f(a, 6) и собственного секрета одной из сторон). Яо в качестве применения такого вычисления показал, что оно позволяет двум сторонам сотрудничать при выборе некоторого целого числа, которое, как им известно, является произведением в точности двух простых чисел так, что ни одна из сторон не сможет вычислить эти сомножители в том случае, когда они перестанут сотрудничать друг с другом [366]. См. также [232, 129, 130, 233].
Секретное распределенное вычисление естественным образом обобщается на произвольное число сторон. Криптографические решения обобщенной проблемы' секретных распределенных вычислений были даны Одедом Голдрейчем, Сильвио Микэли и Эви Вигдерсоном [195], и независимо Дэвидом Чаумом, Иваном Дам-гардом и Йереоном ван де Граафом [112]. Зви Галил, Стюарт Хабер и Моти Юнг изучали секретные устойчивые к ошибкам протоколы в модели системы с открытым ключом [182]. Позднее и независимо Дэвидом Чаумом, Клодом Крепеу и Иваном Дамгардом в [111], а также Майклом Бен-Ором, Шафи Гольд-вассер и Эви Вигдерсоном в [38] было показано, что безусловно секретные распределенные вычисления могут быть выполнены при одном-единственном предположении, что нечестными являются не более, чем одна треть от общего числа участников. См. также [301, 106].
Схема выборов является специальным случаем предыдущей проблемы. Как могут несколько сторон участвовать в голосовании по компьютерной сети таким образом, что будут в состоянии вычислить результат голосования, но при этом все индивидуальные бюллетени сохранятся в тайне? Этот вопрос изучался многими исследователями, включая Джоша Беналоха [Коэна] и Майкла Фишера [119], Майкла Бен-Ора и Натана Линиэла [39], а также и Беналоха и Моти Юнга [23].
