Читать «Золотой билет» онлайн - страница 83

Допустим, у Элис имеются конфиденциальные данные, над которыми требуется произвести некие вычисления, а Боб как раз предоставляет сервис облачных вычислений. Элис отправляет Бобу информацию, закодированную его открытым ключом. Боб расшифровывает данные, выполняет вычисления и отправляет Элис результат, закодированный ее открытым ключом. Если система шифрования достаточно надежна, то ни один злоумышленник не сумеет похитить секретную информацию. Схема работает – но лишь до тех пор, пока Элис доверяет Бобу. А что, если она захочет скрыть свои данные даже от него?

В этом случае помогут системы, называемые полностью гомоморфными. Протокол RSA устроен таким образом, что, умножив шифр одного числа (к примеру, числа 28) на шифр другого (к примеру, 45), мы в итоге получим шифр их произведения (т. е. числа 1260). Умножение чисел можно проводить без расшифровки, и исходные данные при этом знать не обязательно. Для сложения, однако, это правило не действует, и по кодам чисел 28 и 45 код числа 73 в системе RSA не получишь.

Умножение соответствует логическому «И», а сложение – логическому «ИЛИ». Вместо логических схем можно строить схемы из операций умножения и сложения, и такими схемами на самом деле реализуются очень многие вычисления. Полностью гомоморфная криптосистема позволяет не только умножать зашифрованные числа, но и складывать; обе операции можно проводить без расшифровки, и никакая дополнительная информация при этом не потребуется.

Допустим, Элис закодировала информацию полностью гомоморфным шифром и отправила ее на сервер Боба. Боб выполняет вычисления, не имея представления об исходных данных. Результат он получает в закодированном виде; расшифровать его он не в состоянии, а вот Элис легко сделает это, когда закачает все на свой компьютер.

С полностью гомоморфными шифрами у криптографов долгое время не ладилось. Многие считали, что создать такой шифр просто невозможно. Наконец, в 2009 году аспиранту Стэнфордского университета Крейгу Гентри удалось разработать полностью гомоморфную криптосистему. На практике схема Гентри работала неприемлемо долго, однако благодаря ей в ближайшем будущем можно ожидать появления чрезвычайно мощных протоколов.

В поисках случайности

Рассмотрим популярную игру «Камень, ножницы, бумага» для двух игроков, в которой нужно выбрать камень, ножницы или бумагу и показать рукой соответствующий знак.

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

Какова оптимальная стратегия в этой игре? Хорошо, если вы можете предсказать выбор противника; но что, если все наоборот, и противник знает ход ваших рассуждений? Неужели вы обречены на вечный проигрыш?

Вовсе нет – при условии, что вы действуете наугад, не размышляя. Когда камень, ножницы и бумага выбираются с одинаковой вероятностью, то независимо от стратегии противника вероятность проигрыша, победы и ничьи тоже будет одинакова – одна треть. Впрочем, человеку на самом деле очень сложно сделать по-настоящему случайный выбор, и знающие люди этим пользуются; вот почему для участия в чемпионатах по игре в «Камень, ножницы, бумагу» необходима не только удача, но и определенное мастерство.