на множители вашего главного ключа. Если вы храните его взаперти только в своем офисе, то подвергаетесь риску утратить его при пожаре; если же вы храните несколько копий этого разложения в различных местах, то увеличивается риск того, что одна из них попадет еше в чьи-то руки. {N, к)-пороговая схема позволяет вам распределить вашу тайну по п ее дубликатам таким образом, что для вас будет достаточно иметь доступ к любым к из них, чтобы восстановить весь секрет целиком, тогда как никакие к - I из этих п дубликатов не предоставят вам абсолютно никакой информации относительно этого секрета (в смысле теории информации Шеннона). Конструкция этой схемы была разработана независимо Эди Шамиром и Бобом Блэкли [315, 46]. О дальнейших исследованиях на эту тему см. в [243, 22, 92, и т.д.], а также [335].

Пусть Алиса и Боб знают различные секреты, допустим, разложение на множители их соответствуюших RSA модулей. Предположим также, что они хотят ими обменяться. Как можно осу-шествить этот обмен секретами так, чтобы ни одна из сторон не подвергалась никакому риску выяснить в конце протокола, что ею только что было получено совсем не то, о чем она договаривалась с другой стороной, в обмен на свой подлинный секрет? Первоначально этот вопрос был изучен Мануэлем Блюмом и Майклом Рабином [50, 299, 52], а затем он привлек внимание многих других исследователей [58, 253, 342, 343, 211]. См. также [366].

Почта с удостоверением (о получении) является усложненной версией цифровой подписи. В этой задаче Алиса хочет послать сообшение Бобу таким способом, чтобы Боб получил это сообшение, если и только если Алисе будет предъявлено подписанное им подтверждение о его получении. Над этой проблемой, поставленной Уитфилдом Диффи, работали Мануэль Блюм и Майкл Рабин [50, 52, 58, 349]. Решающий ее протокол реализует экстремальную (all-or-nothing) удостоверяющую почту - понятие, также введенное Блюмом, которое означает, что получатель не может узнать абсолютно ничего о содержании сообщения до тех пор, пока отправитель не получит подтверждения о его получении, и наоборот [53].

Подписание контрактов еще сложнее (хотя и является достаточно легким для реализации, если использовать в качестве

примитива протокол конкретной почты с удостоверением). Оно позволяет Алисе и Бобу подписывать контракты по компьютерной сети таким образом, что ни один из них не сможет прервать протокол подписывания (за исключением, которое возможно разве что с очень малой вероятностью) и поставить подписи другой стороны под контрактом до тех пор, пока она не будет с ним согласна [52, 300, 58, 168].

Предположим, что вы располагаете некоторым количеством секретов и хотите продать один из них. Раскрывающий протокол позволяет вам сделать это таким способом, что его покупателю будет предоставлена возможность выбора того секрета, который он получит, но не предоставится никакой информации о том, каков именно этот секрет. Такой протокол является экстремальным (all-or-nothing), если у покупателя нет никакой возможности заполучить отдельные биты или целые части нескольких секретов. Эта проблема была сформулирована и решена Жилем Брассаром, Клодом Крепеу и Жан-Марком Робертом [83, 84], а также, независимо, Дэвидом Чаумом. Ее решение полезно, в частности, при реализации протокола для многостороннего покера без карт, такого как протокол Крепеу [127], и может служить примитивом для более сложных криптографических протоколов. См. также [131].

Предположим, что Алиса и Боб хотят разделить друг с другом истинно случайную двоичную последовательность, но опасаются, что некоторые из ее разрядов могут попасть в руки нарушителя. Тогда, задавая только верхнюю границу на количество информации, которую допустимо скомпрометировать, есть возможность повысить секретность посредством открытых обсуждений, с тем чтобы остановиться на более короткой и намного более секретной двоичной последовательности. Это остается возможным, даже если из-за ошибок при передаче и после злонамеренной подделки исходная последовательность вашего друга оказалась бы слегка отличной от вашей. Данный вопрос был исследован независимо Чарльзом Беннеттом, Жилем Брассаром и Жан-Марком Робертом [36], а также Бенни Чором, Одедом Голдрейчем, Йоханом Хастадом, Джоэлем Фридманом, Стевеном Рудичем и Романом Смоленским [118]. Решение этого вопроса, как описано в следующей главе, является основной составной частью для установления квантового канала. См. также [32, 311].

Полислучайным семейством функций называется набор эффективно вычисляемых функций, которые являются полиномиально неотличимыми от иЬнно случайных функций. Это понятие было введено Одедом Голдрейчем, Шафи Гольдвассер и Сильвио Микэли [193], которые предложили также его многочисленные применения [192]. Одним из таких применений являются вычислительно надежные аутентификационные метки, для которых требуются короткие секретные разделенные ключи. Майком Люби и Чарльзом Раковом в [254] были построены полислучайные семейства перестановок. Довольно странно, что эти перестановки были получены с помощью некоего процесса, похожего на DES:""

Сублиминальный канал - это канал, который допускает два уровня шифрования. Секретное сообщение может быть восстановлено от криптограммы, используя «регулярный» секретный ключ, но чтобы получить сублиминальное сообщение, необходим некий дополнительный ключ. Это понятие, которое было введено Густавом Симмонсом, позволяет двум сторонам осуществлять конфиденциальную связь, в то время как ничего не подозревающий нарушитель остается в полном убеждении, что он может читать сообщения обеих сторон [328, 331]. См. также [148].

Несмотря на то, что до сих пор никакой практически значимой криптографической схемы для защиты программного обеспечения пока еще не предложено, интересные теоретические идеи в этом отношении были представлены Амиром Херцбергом и Шломитом Пинтером [216] и Одедом Голдрейчем [191]; В частности, Голдрейч делает различие между защитой от незаконного копирования и защитой от незаконного воспроизведения дистрибутива. См. также [283].

Проблема о миллионере, которая впервые была поставлена Эндрю Яо, формулируется следующим образом: два миллионера хотят выяснить, кто из них самый богатый, но так, чтобы ни один из них не смог узнать, каково богатство другого [365]. Это - специальный случай секретного распределенного вычисления, с помощью которого Алиса и Боб хотят вычислить значение некоторой согласованной функция f(a, b) с секретным, известным Алисе, входом а и входом 6, также секретным, но известным Бобу, таким способом, что ни одна из сторон не может получить никакой информации, чтобы узнать значение секретного входа