Безопасная оценка схемы - раздел Программирование, Протоколы, алгоритмы и исходные тексты на языке С Вход Алисы - А, А Боба - Ъ. Они Вместе Хотят Вычислить Некотору...
Вход Алисы - а, а Боба - Ъ. Они вместе хотят вычислить некоторую функцию f(a,b) так, чтобы Алиса не смогла ничего узнать о входе Боба, а Боб - о входе Алисы. Главная проблема безопасных вычислений с н е-сколькими участниками также называется безопасной оценкой схемы.Алиса и Боб могут создать произвольную логическую схему. Эта схема получает на вход значения Алисы и Боба и выдает результат. Безопасная оценка схемы является протоколом, который реализует следующие три требования :
1. Алиса может ввести свое значение так, что Боб не сможет его узнать .
2. Боб может ввести свое значение так, что Алиса не сможет его узнать .
3. И Алиса, и Боб могут вычислить результат, причем обе стороны будут убеждены в том, что результат правилен и не подтасован ни одной стороной.
Детали протокола безопасной оценки схемы можно найти в [831].
Вам не удастся пообедать с компанией криптографов и не оказаться среди ожесточенной перепалки . В [321] Дэвид Чаум вводит Проблему обедающих криптографов :
Три криптографа сидят за обедом в своем любимом трехзвездочном ресторане . Их официант сообщает им, что метрдотель принял необходимые меры, чтобы счет можно было бы оплатить анонимно . За обед мог бы заплатить один из криптографов или NSA. Три криптографа очень уважают право каждого из них заплатить анонимно, но им хотелось бы знать, з а-платит ли NSA.
Как криптографам Алисе, Бобу и Кэрол узнать, не заплатил ли за обед кто-нибудь из них, и в то же время не
нарушить анонимность плательщика? Чаум решает проблему:
Каждый криптограф бросает несмещенную монету, прикрывшись своим меню, между ним и криптографом справа от н е-го так, что только они двое могут видеть результат. Затем каждый криптограф громко объявляет, упаали ли две монеты - одна его и одна его левого соседа - на одну или на различные стороны. Если плательщик - один из криптографов, то его утвержд е-ние противоположно тому, что он видит. Нечетное число заявленных различий за столом указывает, что обед оплачивает криптограф; четное число различий - что NSA (при условии, что обед может быть оплачен только один раз). Однако, если обед оплачивает криптограф, никто из двух других не узнает из сделанных заявлений, кто же конкретно опл атил обед.
Чтобы увидеть, как это работает, вообразите, что Алиса пытается понять, кто из двух других криптографов заплатил за обед (при условии, что не она и не NSA). Если она видит две различных монеты, то либо оба других криптографа (Боб и Кэрол) сказали, "одинаковые" или оба сказали, "разные". (Помните, нечетное число кри п-тографов, говорящих "разные" указывает, что оплатил кто-то из них.). Если оба сказали "разные", то плател ь-щик - криптограф, сидящий ближе всего к монете, результат броска которой тот же, что и у скрытой монеты (брошенной между Бобом и Кэрол). Если оба сказали "одинаковые", то плательщик - криптограф, сидящий ближе всего к монете, результат броска которой отличается от результата броска скрытой монеты. Однако, если Алиса видит две одинаковых монеты, то или Боб сказал, "одинаковые", а Кэрол - "разные", или Боб сказал "разные", а Кэрол - "одинаковые". Если ли скрытая монета - такая же как и видимые ей две монеты, то пл а-телыцик - криптограф, который сказал, "разные". Если скрытая монета отлична от видимых ей двух монет, то плательщик - криптограф, который сказал "одинаковые". Чтобы определить, кто платил, во всех этих случаях Алиса должна знать результат броска монеты между Бобом и Кэрол.
Этот протокол может быть обобщен на любое количество криптографов, которые сидят по кругу и бросают монеты между собой. Каждая пара криптографов выполняет протокол. Конечно, они знают, кто платит, но кто-то, наблюдающий за протоколом может сказать только, что заплатил один из криптографов или NSA, но не со-жет указать, какой из криптографов платил.
Применение этого протокола выходит далеко за пределы обеденного стола. Вот пример безусловного отправителя и неотслеживаемого отправителяГруппа пользователей сети может использовать этот протокол для отправления анонимных сообщений.
(1) Пользователи упорядочиваются по кругу.
(2) Через регулярные интервалы времени соседние пары пользователей бросают между собой монету, испол ь-зуя какой-нибудь безопасный от злоумышленников протокол бросания "честной" монеты .
(3) После каждого броска каждый пользователь объявляет либо "одинаковые", либо "разные" .
Если Алиса хочет передать широковещательное сообщение, она просто начинает инвертировать свое утве р-ждение в тех раундах, которые соответствуют 1 в двоичном представлении ее сообщения. Например, если ее сообщение было "1001", она инвертирует ее утверждение, сообщит правду, сообщит правду, и затем инвертир у-ет снова утверждение. При условии, что результатом ее бросков было были "разные", "одинаковые", "одинаковые", "одинаковые", она будет говорить "одинаковые", "одинаковые ", "одинаковые", "разные".
Если Алиса замечает, что полный результат протокола не соответствует сообщению, которое она пробует п о-сылать, она понимает, что в это же время кто-то еще пытается посылать сообщение. Тогда она прекращает п е-редачу сообщения и выжидает случайное количество раундов перед очередной попыткой. Точные параметры должны быть выработаны на основе трафика сообщений в сети, но идея достаточно понятна.
Чтобы сделать дело еще более интересным, эти сообщения могут быть зашифрованы открытым ключом др у-гого пользователя. Затем, когда каждый принимает сообщение (практическая реализация должна включать стандартные заголовки и окончания сообщений), только определенный получатель сможет расшифровать и прочесть сообщение. Никто другой ничего не узнает про автора сообщения и не сможет определить получателя сообщения. Даже если удастся расшифровать сами сообщения, то анализ трафика, отслеживающий и собира тощий формы межпользовательского обмена, бесполезен.
Альтернативой бросанию монет между соседними сторонами могло бы быть использование файла случа й-ных битов. Возможно, стороны могли бы хранить файл на CD-ROM, или один член пары мог бы генерировать пачку битов и посылать их другой стороне (конечно, в зашифрованном виде). Или, они могли бы договориться использовать совместно криптографически безопасный генератор псевдослучайных чисел, и каждый из них смог бы генерировать для протокола ту же самую последовательность псевдослучайных битов.
Проблемой этого протокола является то, что хотя мошенничающий участник и не сможет читать никаких с о-общений, он может незаметно испортить всю систему, постоянно обманывая на этапе (3). Существует модификация предыдущего протокола, позволяющая обнаружить вредительство [1578, 1242]. Эта проблема называется "Обедающие криптографы в дискотеке".
6.4 Электронные наличные
Наличные деньги - это проблема. Раздражает их носить, они способствуют распространению микробов, л годи могут красть их у Вас. Чеки и кредитные карточки уменьшили количество наличных денег, оборачивающи х-ся в обществе, но полное удаление наличных денег фактически невозможно. Этого никогда не произойдет; то р-говцы наркотиками и политические деятели никогда этого не допустят. Чеки и кредитные карточки можно пр о-следить, вы не можете скрыться от того, кому дали деньги.
С другой стороны, чеки и кредитные карточки позволяют людям вторгаться в вашу личную жизнь как ник о-гда прежде. Вы никогда не допустили бы, чтобы полиция всю жизнь ходила за вами по пятам, но полицейские могут проследить ваши финансовые операции. Они могут видеть, где вы покупаете газ, где вы покупаете еду, кому вы звоните по телефону, и все это не отрываясь от своих компьютерных терминалов. Люди должны уметь защитить свою анонимность, чтобы защитить свои личные тайны.
К счастью, существует сложный протокол, который разрешает использование заверенных, но неотслежива е-мых сообщений. Лоббист Алиса может передать электронные деньгиконгрессмену Бобу так, чтобы газетный репортер Ева ничего не узнала бы об Алисе. Боб может затем вносить эти электронные деньги на свой банко в-ский счет, даже если банк не имеет об Алисе никакого представления. Но если Алиса пробует покупать кокаин на ту же самую порцию электронных денег, которую она использовала для подкупа Боба, она будет обнаружена банком. И если Боб пробует вносить порцию электронных денег на два различных счета, это будет обнаружено, но Боб, как и Алиса, останется он анонимным. Иногда это называется анонимными электронными деньгами,чтобы можно было отличить их от отслеживаемых электронных денег, типа креди тных карточек.
В подобных вещах существует большая общественная необходимость. С ростом использования Internet для коммерческих операций растет и потребность в секретности передаваемой по сети информации и анонимности при ведении дел. (Имеется немало причин для того, чтобы люди отказывались посылать номер их кредитной карточки по Internet.) С другой стороны, банки и правительства, по видимому, не пожелают уступить контроль над современными банковскими системами. Хотя им придется это сделать. Все, что потребуется, чтобы эле к-тронные деньги вошли в моду, - это появление некоторого заслуживающего доверия учреждения, желающего преобразовывать цифры в реальные деньги.
Протоколы электронных денег очень сложны. Дальше мы шаг за шагом построим один из них. Более подробно об этом протоколе можно прочитать в [318, 339, 325, 335, 340]. Но помните, это только один из протоколов электронных денег, существуют и другие.
Протокол №1
Первые несколько протоколов представляют собой физические аналоги криптографических протоколов . Следующий протокол является упрощенным физическим протоколом для анонимных денежных чеков :
(1) Алиса готовит 100 анонимных денежных чеков по $1000 каждый.
(2) Алиса вкладывает каждый из них и листок копировальной бумаги в 100 различных конвертов и относит все конверты в банк.
(3) Банк открывает 99 конвертов и убеждается, что каждый чек выписан на $1000.
(4) Банк подписывает единственный оставшийся нераспечатанным конверт . С помощью копировальной бумаги подпись переводится на чек. Банк возвращает нераспечатанный конверт Алисе и списывает $1000 с ее счета.
(5) Алиса вскрывает конверт и отдает денежный чек продавцу.
(8) Банк проверяет свою подпись и начисляет $1000 на счет продавца.
Этот протокол работает. Банк не видит денежный чек, который он подписывает, поэтому, когда продавец принесет чек в банк, банк никогда не узнает, что это чек Алисы. Благодаря подписи банк убежден в законности чека. А из-за протокола "разрезать и выбрать" (см. раздел 5.1) банк уверен, что нераспечатанный денежный чек - на сумму $1000 (а не $100000 или $100000000). Он проверяет остальные 99 конвертов, поэтому вероятность обмана банка Алисой составляет только 1 процент. Конечно, банк назначит за обман достаточно большой штраф, такой, чтобы не стоило мошенничать. Ведь если банк просто откажется подписать последний чек (если Алиса поймана на обмане), не штрафуя Алису, она продолжит свои попытки, пока ей не повезет. Лучшее ере д-ство устрашения - это тюремное заключение.
Протокол №2
Предыдущий протокол не дает Алисе написать чек на сумму, отличную от заявленной, но он не мешает ей отксерокопировать чек и использовать его дважды. Это называется проблемой повторной оплаты;для ее ре-шение придется усложнить протокол:
(1) Алиса готовит 100 анонимных денежных чеков по $1000 каждый. К каждому денежному чеку она добавляет уникальную строку, выбранную случайным образом и достаточно длинную, чтобы вероятность и с-пользования этой строки другим человеком была пренебрежимо мала.
(2) Алиса вкладывает каждый из них и листок копировальной бумаги в 100 различных конвертов и относит все конверты в банк.
(3) Банк открывает 99 конвертов и убеждается, что каждый чек выписан на $1000.
(4) Банк подписывает единственный оставшийся нераспечатанным конверт . С помощью копировальной бума-ги подпись переводится на чек. Банк возвращает нераспечатанный конверт Алисе и списывает $1000 с ее счета.
(5) Алиса вскрывает конверт и отдает денежный чек продавцу.
(8) Банк проверяет свою подпись и по своей базе данных убеждается, что денежный чек с такой уникальной строкой ранее не депонировался. Если это так, банк начисляет $1000 на счет продавца и записывает уни-кальную строку в базу данных.
(9) Если денежный чек уже был депонирован ранее, банк отказывается принять его.
Теперь, если Алиса попытается расплатиться ксерокопией денежного чека или продавец попытается депон и-ровать денежный чек повторно, используя ксерокопию, банк узнает об этом.
Протокол №3
Предыдущий протокол защищает банк от мошенников, но не устанавливает их личность . Банк не знает, по-пытался ли человек, который получил чек (банк ничего не знает об Алисе), обмануть продавца, или продавец пытается обмануть банк. Эта неоднозначность исправляется следующим протоколом :
(1) Алиса готовит 100 анонимных денежных чеков по $1000 каждый. К каждому денежному чеку она добавляет уникальную строку, выбранную случайным образом и достаточно длинную, чтобы вероятность и с-пользования этой строки другим человеком была пренебрежимо мала.
(2) Алиса вкладывает каждый из них и листок копировальной бумаги в 100 различных конвертов и относит все конверты в банк.
(3) Банк открывает 99 конвертов и убеждается, что каждый чек выписан на $1000, и что все случайные стро-ки различны.
(4) Банк подписывает единственный оставшийся нераспечатанным конверт . С помощью копировальной бума-ги подпись переводится на чек. Банк возвращает нераспечатанный конверт Алисе и списывает $1000 с ее счета.
(5) Алиса вскрывает конверт и отдает денежный чек продавцу.
(7) Продавец просит Алису написать случайную идентификационную строку на денежном чеке.
(8) Алиса выполняет это.
(9) Продавец относит денежный чек в банк.
(10) Банк проверяет свою подпись и по своей базе данных убеждается, что денежный чек с такой уникальной строкой ранее не депонировался. Если это так, банк начисляет $1000 на счет продавца и записывает уни-кальную строку в базу данных.
(11) Если уникальная строка уже есть в базе данных, банк отказывается принять денежный чек и сравнивает идентификационную строку на денежном чеке с хранимой в базе данных. Если они совпадают, то банк убеждается, что копия была снята с чека продавцом. Если идентификационные строки различны, то банк знает, что чек был скопирован человеком, который его готовил.
В этом протоколе предполагается, что продавец не может изменить идентификационную строку после того,
как Алиса напишет ее на денежном чеке. На денежном чеке мог бы находиться ряд небольших квадратов, кот о-рые по требованию торговца Алиса должна заполнить крестиками или ноликами. Денежный чек мог бы быть сделан из бумаги, которая рвется при исправлениях.
Так как продавец и банк взаимодействуют после того, как Алиса потратит деньги, продавцу могут всучить плохой денежный чек. Практические реализации этого протокола могли бы потребовать от Алисы подождать у кассового аппарата, пока продавец будет разбираться с банком, точно также, как это происходит сегодня при обработке платежей с использованием кредитных карточек.
Алиса также может приспособиться и к этому. Она может потратить копию денежного чека второй раз, н а-писав ту же самую идентификационную строку на этапе (7). Если продавец не ведет базу данных уже получе н-ных денежных чеков, он будет введен в заблуждение. Эту проблему устраняет следующий протокол.
На сайте allrefs.net читайте: Протоколы, алгоритмы и исходные тексты на языке С...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Безопасная оценка схемы
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Об авторе
БРЮС ШНАЙЕР - президент Counterpane Systems, Оак Парк, Иллинойс, фирма-консультант, специализирующаяся в криптографии и компьютерной безопасности. Брюс также написал E-Mail Security, John W
DKi(EK/M))=M
Безопасность этих алгоритмов полностью основана на ключах, а не на деталях алгоритмов. Это значит, что алгоритм может быть опубликован и проанализирован. Продукты, использующие этот алгоритм, могут
Симметричные алгоритмы
Существует два основных типа алгоритмов, основанных на ключах: симметричные и с открытым ключом . Симметричные алгоритмы,иногда называемые условными алгоритмами, представляют собой
DK(C)=M
Симметричные алгоритмы делятся на две категории . Одни алгоритмы обрабатывают открытый текст побитно (иногда побайтно), они называются потоковыми алгоритмамиили потоковыми
Криптоанализ
Смысл криптографии - в сохранении открытого текста (или ключа, или и того, и другого) в тайне от зл о-умышленников (также называемых взломщиками, соперниками, врагами, перехватчиками). Предполагает
Безопасность алгоритмов
Различные алгоритмы предоставляют различные степени безопасности в зависимости от того, насколько трудно взломать алгоритм. Если стоимость взлома алгоритма выше, чем стоимость зашифрованных данных,
Исторические термины
Исторически термин код относится к криптосистеме, связанной с лингвистическими единицами: словами, фразами, предложениями и так далее. Например, слово "ОЦЕЛОТ" может кодировать целую фраз
Перестановочные шифры
В перестановочном шифременяется не открытый текст, а порядок символов. В простом столбцовом перестановочном шифреоткрытый текст пишется горизонтально на разграфле
Роторные машины
В 1920-х годах для автоматизации процесса шифрования были изобретены различные механические устро й-ства. Большинство использовало понятие ротора,механического колеса, используемог
Элементы протоколов
2.1 Введение в протоколы
Смысл криптографии - в решении проблем. (По сути, в этом состоит и смысл использования компьютеров, о чем многие пытаются забыть.) Криптография решает проблемы сек
Самодостаточные протоколы
Самодостаточный протоколявляется лучшим типом протокола. Он полностью обеспечивает честность сторон (см. 1-й(в)). Для выполнения протокола не нужен ни посредник, не решающий споры
Попытки вскрытия протоколов
Криптографические попытки взлома могут быть направлены против криптографических алгоритмов, и с-пользуемых в протоколах, против криптографических методов, используемых для реализации алгоритмов и п
Коды проверки подлинности сообщения
Код проверки подлинности сообщения(message authentication code, MAC), известный также как код про-
верки подлинности данных (data authentication code, DAG), представл
Смешанные криптосистемы
Первые алгоритмы с открытым ключом стали известны в то же время, когда проходило DES обсуждение как предполагаемого стандарта. Это привело к известной партизанщине в криптографическом сообществе .
Подпись документа с помощью криптографии с открытыми ключами
Существуют алгоритмы с открытыми ключами, которые можно использовать для цифровых подписей. В н е-которых алгоритмах - примером является RSA (см. раздел 19.3) - для шифрования может быть использова
Подпись документа и метки времени
На самом деле, при определенных условиях Боб сможет смошенничать . Он может повторно использовать документ и подпись совместно. Это не имеет значения, если Алиса подписала контракт (одной копией по
Алгоритмы и терминология
Существует множество алгоритмов цифровой подписи. Все они представляют собой алгоритмы с открытыми ключами с закрытой частью для подписи документов и с открытой - для проверки подписи . Иногда проц
Несколько подписей
Как Алисе и Бобу одновременно подписать один и тот же документ? В отсутствие однонаправленных хэш-функций существует две возможности. Алиса и Боб могут подписать различные копии одного и того же до
Невозможность отказаться от цифровой подписи
Алиса может смошенничать с цифровыми подписями, и с этим ничего нельзя поделать. Она может подп и-сать документ и затем утверждать, что она этого не делала. Сначала она, как обычно, подписывает пис
Использование цифровых подписей
Одним из самых ранних предложенных применений цифровых подписей было упрощение проверки собл ю-дения договоров о ядерных испытаниях [1454, 1467]. Соединенные Штаты и Советский Союз (кто-нибудь пом
Обнаружение вскрытия, основанного на возвращении сообщения
Только что описанное вскрытие работает потому, что операция шифрования совпадает с операцией проверки подписи, а операция дешифрирования - с операцией подписи. Операции шифрования и цифровой подпис
Вскрытия криптографии с открытыми ключами
Во всех подобных протоколах криптографии с открытыми ключами я не рассказал , как Алиса получает открытый ключ Боба. Подробно этот вопрос описан в разделе 3.1, но о нем стоит упомянуть и здесь.
Генерация случайных и псевдослучайных последовательностей
Почему даже в книге по криптографии снова эти докучливые рассуждения о генерации случайных чисел? Генератор случайных чисел встроен в каждый компилятор, обычный вызов функции. Почему бы не использ
Псевдослучайные последовательности
Лучшее, что может сделать компьютер - это генератор псевдослучайных последовательностейЧто это такое? Многие пытались дать его формальное определение, но я уклонюсь от этого. Псевд
Криптографически безопасные псевдослучайные последовательности
Криптографические приложения предъявляют к генератору псевдослучайных последовательностей более высокие требования по сравнению с другими приложениями . Криптографическая случайность не ограничивае
Настоящие случайные последовательности
Теперь мы вторгаемся в область, принадлежащую философам . Существует ли такая вещь как случайность? Что такое случайная последовательность? Как узнать, что последовательность случайна? Является ли
Основные протоколы
3.1 Обмен ключами
Общепринятой криптографической техникой является шифрование каждого индивидуального обмена соо б-щениями отдельным ключом. Такой ключ называется сеансовым, так как он исп
Обмен ключами с помощью симметричной криптографии
Этот протокол предполагает, что пользователи сети, Алиса и Боб, получают секретный ключ от Центра ра с-пределения ключей (Key Distribution Center, KDC) [1260] - Трента наших протоколов. Перед начал
Обмен ключами, используя криптографию с открытыми ключами
Базовая смешанная криптосистема обсуждалась в разделе 1.5. Для согласования сеансового ключа Алиса и Боб применяют криптографию с открытыми ключами, а затем используют этот сеансовый ключ для шифро
Обмен ключами с помощью цифровых подписей
Использование цифровой подписи в протоколе обмена сеансовым ключом также позволяет избежать вскр ы-тия "человек-в-середине". Трент подписывает открытые ключи Алисы и Боба. Подписанные клю
Передача ключей и сообщений
Алисе и Бобу не обязательно выполнять протокол обмена ключами перед обменом сообщениями. В этом протоколе Алиса отправляет Бобу сообщение без предварительного протокола обмена ключами :
(1
Широковещательная рассылка ключей и сообщений
Не существует причин, запрещающих Алисе посылать шифрованное сообщение нескольким людям . В следующем примере Алиса посылает шифрованное сообщение Бобу, Кэрол и Дэйву :
(1) Алиса генериру
Удостоверение подлинности с помощью однонаправленных функций
Роджер Неедхэм (Roger Needham) и Майк Гай (Mike Guy) показали, что главному компьютеру не нужно знать сами пароли, вполне достаточно, чтобы главный компьютер мог отличать правильные пароли от непр
Удостоверение подлинности сообщений
Когда Боб получает сообщение от Алисы, как ему узнать, что это сообщение подлинно? Если Алиса подписала свое сообщение, то все просто. Цифровая подпись Алисы достаточна, чтобы подтвердить кому уго
Лягушка с широким ртом
Протокол "Лягушка с широким ртом" (Wide-Mouth Frog) [283,284], возможно, является простейшим симметричным протоколом управления ключами, в котором используется заслуживающий доверия серв
Otway-Rees
Этот протокол также использует симметричную криптографию [1224].
(1) Алиса создает сообщение, состоящее из порядкового номера, ее имени, имени Боба и случайного числа. Сообщение шифруе
Широковещательная передача сообщения
Представьте, что в некоей операции занято 100 ваших тайных агентов . Вы хотите иметь возможность посылать сообщения группам агентов, но вы не знаете заранее состав групп . Можно либо шифровать соо
Совместное использование с мошенниками
Существует множество способов обмануть пороговую схему. Вот только несколько из них. Сценарий 1 : Полковники Алиса, Боб и Кэрол сидят в изолированном бункере где-то глубоко под землей. Однажды они
Совместное использование секрета без раскрытия долей
У этих схем есть одна проблема. Когда участники протокола собираются, чтобы восстановить секрет, они открывают свои части. Но раскрытие секрета не всегда желательно. Если разделяемый секрет являетс
Схемы совместного использования секрета с мерами предохранения
Секрет делится среди 50 человек так, чтобы любые 10 могли собраться вместе и восстановить секрет . Это нетрудно. Но, можем ли мы реализовать ту же схему совместного использования секрета, добавив т
Совместное использование секрета с вычеркиванием из списка
Вы создали систему совместного использования секрета и теперь хотите застрелить одного из владельцев части секрета. Вы могли бы создать новую схему, исключив этого несчастного, но время поджимает.
Промежуточные протоколы
4.1 Службы меток времени
Во многих ситуациях людям нужно убедиться, что определенный документ уже существовал в определенный момент времени. Примером является спор об авторских правах или
Решение с посредником
В этом протоколе участвуют Трент, обладающий надежной службой меток времени, и Алиса, которая хочет задать метку времени для документа.
(1) Алиса передает копию документа Тренту.
Улучшенное решение с посредником
Большинство этих проблем легко снимаются при использовании однонаправленной хэш-функции и цифр о-вых подписей:
(1) Алиса вычисляет значение однонаправленной хэш-функции для документа.
Протокол связи
Одним из путей решения этой проблемы является установление связи между меткой времени Алисы и ме т-ками времени, ранее созданными Трентом. Весьма вероятно, что эти метки были созданы не для Алисы,
Распределенный протокол
Люди умирают, метки времени теряются. Между пометкой документа и его оспариванием может произойти многое, что помешает Алисе получить копию метки времени !„.,. Эта проблема может быть частич
Дальнейшая работа
Дальнейшие улучшения протоколов метки времени описаны в [92]. Авторы используют двоичные деревья для увеличения количества меток времени, зависящих от данной метки, уменьшая вероятность создания це
Применения подсознательного канала
Наиболее очевидным применением подсознательного канала является шпионская сеть. Если кто-то посылает и принимает сообщения, то передача сообщений по подсознательному каналу в подписанных документах
Подписи, свободные от подсознательного канала
Алиса и Боб обмениваются подписанными сообщениями, обговаривая сроки контракта. Они используют протокол цифровой подписи. Однако, эти переговоры на самом деле маскируют шпионскую деятельность Ал и-
Групповые подписи с надежным посредником
Следующий протокол использует заслуживающего посредника:
(1) Трент создает большую кучу пар открытый ключ/закрытый ключ и выдает каждому члену группы инд и-видуальный список уникальных зак
Подписи с обнаружением подделки
Пусть Ева является могучим противником. У нее есть обширные компьютерные сети и залы, набитые ко м-пьютерами Крэй, на много порядков более мощных, чем доступные Алисе . Все эти компьютеры днем и но
Blob-объекты
Строки, которые Алиса посылает Бобу для вручения бита, иногда называют blob-объектами.Blob-объект -это последовательность битов, хотя протоколы этого и не требуют. Как сказал Жиль
Бросок монеты с помощью однонаправленных функций
Если Алиса и Боб договорятся об однонаправленной функции, протокол прост : (1) Алиса выбирает случайное число, х. Она вычисляет y—f(x), где/fx) - однонаправленная функция.
Бросок монеты в колодец
Интересно отметить, что во всех этих протоколах Алиса и Боб узнают результат броска не одновременно . В каждом протоколе есть момент, когда одна из сторон (Алиса в первых двух протоколах и Боб в по
Генерация ключей с помощью броска монеты
Реальным применением этого протокола служит генерация сеансового ключа. Протоколы броска монеты п о-зволяют Алисе и Бобу создать случайный сеансовый ключ так, что никто из них не сможет повлиять на
Мысленный покер с тремя игроками
Покер интереснее, если в игре участвуют несколько человек. Базовый протокол мысленного покера легко может быть распространен на трех и более игроков . В этом случае криптографический алгоритм также
Вскрытия мысленного покера
Криптографы показали, что при использовании этими протоколами покера алгоритма с открытыми ключами RSA происходит небольшая утечка информации [453, 573]. Конкретно, если двоичное представление карт
Анонимное распределение ключей
Хотя непохоже, чтобы кто-нибудь собирался использовать этот протокол для игры в покер по модему , Чарльз Пфлегер (Charles Pfleeger) рассматривает ситуацию, в которой этот тип протокола может оказат
Политика условного вручения ключей
Помимо правительственных планов относительно условного вручения ключей распространяются и комме р-ческие системы с условным вручением ключей. Возникает очевидный вопрос: какое преимущество от услов
Развитые протоколы
5.1 Доказательства с нулевым знанием
А вот другая история:
Алиса: "Я знаю пароль компьютера Федеральной Резервной Системы, компоненты секретного соуса Макдональдс и оде р-жан
Изоморфизм графа
Объяснение этого понятия, пришедшего из теории графов [619, 622], может занять некоторое время. Граф представляет собой сеть линий соединяющих различные точки. Если два графа идентичны во всем, кро
Гамилыпоновы циклы
Вариант этого примера был впервые представлен Мануэлем Блюмом (Manuel Blum) [196]. Пегги знает кружной, продолжительный путь вдоль линий графа, который проходит через каждую точку только один раз .
Параллельные доказательства с нулевым знанием
В базовом протоколе с нулевым знанием используется п обменов информацией между Пегги и Виктором. Почему бы не выполнить их параллельно:
(1) Пегги использует свою информацию и п
Неинтерактивные доказательства с нулевым знанием
Кэрол невозможно убедить, потому что она не участвует в интерактивном процессе протокол. Для убеждения Кэрол и других заинтересованных лиц нам нужен неинтерактивный протокол .
Для неинтера
Общие замечания
Блюм (Blum) доказал, что любая математическая теорема может быть преобразована в граф, такой, что д о-казательство теоремы будет эквивалентно доказательству существования гамильтонова цикла для это
Проблема гроссмейстера
Вот как Алиса, даже не зная правил шахмат, может обыграть гроссмейстера. (Иногда это называется проблемой гроссмейстера.) Она посылает вызов Гарри Каспарову и Анатолию Карпову, предлагая играть в
Обман, выполненный мафией
Обсуждая свой протокол идентификации с нулевым знанием, Ади Шамир сказал [1424]: "Я могу ходить в принадлежащий мафии магазин хоть миллион раз подряд, а они все еще не смогут выдать себя за ме
Обман, выполненный террористами
Если Алиса хочет объединиться с Кэрол, то они также могут провести Дэйва. В этом протоколе Кэрол - и з-вестная террористка. Алиса помогает ей въехать в страну. Дэйв - офицер-пограничник, Алиса и Кэ
Предлагаемые решения
Оба описанных мошенничества возможны, так как заговорщики используют тайный радиоканал. Одним из способов предотвратить мошенничество является проведение процедуры идентификации в клетке Фарадея, б
Обман с несколькими личностями
Существуют и другие способы злоупотребить доказательствами идентичности с нулевым знанием, также рассматриваемые в [485, 120]. В ряде реализаций проверка при регистрации человеком своего ключа не п
Прокат паспортов
Алиса хочет поехать в Заир, но правительство этой страны не дает ей визы. Кэрол предлагает сдать свою личность Алисе "напрокат". (Первым это предложил Боб, но возник ряд очевидных проблем
Доказательство членства
Алиса хочет доказать Бобу, что она является членом суперсекретной организации, но не хочет раскрывать свою личность. Эта проблема, близкая проблеме доказательства личности, но отличающаяся от нее,
Полностью слепые подписи
Боб - государственный нотариус. Алиса хочет, чтобы он подписал документ, не имея ни малейшего пре д-ставления о его содержании. Боб не отвечает за содержание документа, он только заверяет, что нота
Рассеянные подписи
Честно говоря, я не могу придумать, чего их можно использовать, но существует два типа рассеянных по д-писей [346]:
1. У Алисы есть п различных сообщений. Боб может выбрать одно из
Подпись контракта с помощью посредника
Алиса и Боб хотят заключить контракт. Они достигли согласия на словах, но никто не хочет ставить свою подпись, пока не поставлена подпись другого. При личной встрече это не вызывает затруднений - о
Эзотерические протоколы
6.1 Безопасные выборы
Компьютерное голосование никогда не будет использовано для обычных выборов, пока не появится прот о-кол, который одновременно предохраняет от мошенничества и защищает
Упрощенный протокол голосования №1
(1) Каждый голосующий шифрует свой бюллетень открытым ключом Центральной избирательной комиссии (ЦИК).
(2) Каждый голосующий посылает свой бюллетень в ЦИК.
(3) ЦИК расшифровывает
Упрощенный протокол голосования №2
(1) Каждый голосующий подписывает свой бюллетень своим закрытым ключом .
(2) Каждый голосующий шифрует свой бюллетень открытым ключом ЦИК .
(3) Каждый голосующий посылает свой бюл
Голосование со слепыми подписями
Нам нужно как-то отделить бюллетень от голосующего, сохранив процедуру идентификации личности . Именно это можно сделать с помощью протокола слепой подписи .
(1) Каждый избиратель создает
Голосование с двумя Центральными комиссиями
Одним из решений является разделить ЦИК пополам . Ни у одной из них не будет достаточно власти, чтобы смошенничать по своему усмотрению.
В следующем протоколе используется Центральное упра
Голосование с одной Центральной комиссией
Чтобы избежать опасности сговора между ЦУР и ЦИК можно использовать более сложный протокол [1373]. Этот протокол идентичен предыдущему с двумя изменениями :
— ЦУР и ЦИК являются единой орг
Улучшенное голосование с одной Центральной комиссией
В этом протоколе также используется ANDOS [1175]. Он удовлетворяет всем шести требованиям хорошего протокола голосования. Он не удовлетворяет седьмому требованию, но обладает двумя свойствами, допо
Улучшенное голосование с одной Центральной комиссией
В этом протоколе также используется ANDOS [1175]. Он удовлетворяет всем шести требованиям хорошего протокола голосования. Он не удовлетворяет седьмому требованию, но обладает двумя свойствами, допо
Голосование без Центральной избирательной комиссии
В следующем протоколе ЦИК не используется, избиратели следят друг за другом . Этот протокол, созданный Майклом Мерриттом [452, 1076, 453], настолько громоздок, что возможность его реализации больше
Другие схемы голосования
Было предложено много сложных безопасных протоколов выборов . Их можно разделить на два типа. Суще-ствуют протоколы с перемешиванием, как "Голосование без Центральной избирательной комиссии&qu
Протокол №1
Как может группа людей вычислить свою среднюю зарплату без того, чтобы зарплата одного стала известна другому?
(1) Алиса добавляет секретное случайное число к сумме своей зарплаты, шифрует
Протокол №2
Алиса и Боб вместе в ресторане и спорят о том, кто старше. Никто, однако, не хочет сообщить другому свой возраст. Каждый из них мог бы прошептать свой возраст на ушко доверенной нейтральной стороне
Протокол №3
Алиса нравится забавляться с плюшевыми медведями. В эротических фантазиях Боба важное место зан и-мают мраморные столы. Оба весьма стесняются своих привычек, но с удовольствием нашли бы кого-нибудь
Протокол №4
Вот другая проблема для безопасных вычислений со многими участниками [1373]: совет семи регулярно
встречается, чтобы тайно проголосовать по некоторым вопросам. (Все в порядке, они упр
Протокол №4
Если окажется, что человек, выписавший банковский чек, попытался обмануть продавца, то банк может з а-хотеть личность этого человека. Чтобы сделать это, придется вернуться от физических аналогий в
Электронные наличные и идеальное приведение
У электронных наличных есть и своя темная сторона. Иногда людям не нужно так много секретности. Смотрите, как Алиса совершает идеальное преступление [1575]:
(1) Алиса крадет ребенка.
Другие протоколы электронных наличных
Существуют и другие протоколы электронных наличных, см. [707, 1554, 734, 1633, 973]. Ряд из них использует весьма изощренную математику. Различные протоколы электронных наличных можно разделить на
Анонимные кредитные карточки
Этот протокол [988] для защиты личности клиента использует несколько различных банков. Каждый клиент имеет счет в двух различных банках. Первый банк, которому известна личность человека, может зачи
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов