- Дом.
Квантовые вычисления как идея существуют уже давно – теоретическая возможность была представлена в 1982 году. В последние несколько лет эта область все ближе подбирается к практической реализации
Квантовые вычисления – одна из тех технологий, которые настолько заумны, что герои телепередач упоминают ее, когда хотят показаться умными
Квантовые вычисления как идея существуют уже давно – теоретическая возможность была первоначально представлена Юрием Маниным и Ричардом Фейнманом в 1982 году. Однако за последние несколько лет эта область стала тревожно приближаться к практической реализации
Такие компании, как Google и Microsoft, а также правительственные агентства, такие как АНБ, уже несколько лет лихорадочно работают над созданием квантовых компьютеров. Компания D-Wave производит и продает устройства, которые (хотя они и не являются полноценными компьютерами и могут выполнять только несколько алгоритмов) используют квантовые свойства и являются еще одним шагом на пути к созданию полностью законченной по Тьюрингу квантовой машины
Не кажется необоснованным утверждение, что могут произойти прорывы, которые позволят построить первый крупномасштабный квантовый компьютер в течение десятилетия
https://www.youtube.com/watch?v=6VIAL8gQRTI
Так почему же такой интерес? Почему это должно вас волновать? Компьютеры все время становятся быстрее – что такого особенного в квантовых компьютерах?
Для того чтобы объяснить, почему эти машины так важны, нам придется сделать шаг назад и изучить, что именно представляют собой квантовые компьютеры и почему они работают. Для начала давайте поговорим о понятии, которое называется ‘сложность времени выполнения’
Что такое сложность времени выполнения?
Одним из больших сюрпризов на заре компьютерной науки было открытие того, что если у вас есть компьютер, который решает задачу определенного размера за определенное время, то удвоение скорости компьютера не обязательно позволит ему решать задачи вдвое больше
Общее время выполнения некоторых алгоритмов увеличивается очень и очень быстро по мере роста размера проблемы – некоторые алгоритмы могут быть быстро завершены при 100 точках данных, но для завершения алгоритма при 1000 точках данных потребуется компьютер размером с Землю, работающий миллиард лет. Сложность выполнения является формализацией этой идеи: она рассматривает кривую того, как быстро растет сложность задачи, и использует форму этой кривой для классификации алгоритма
Как правило, эти классы сложности выражаются в виде функций. Алгоритм, который становится пропорционально сложнее при увеличении набора данных, над которым он работает (например, простая счетная функция), считается функцией со сложностью выполнения ‘ n’ (то есть, для обработки n точек данных требуется n единиц времени)
В качестве альтернативы ее можно назвать ‘линейной’, потому что при построении графика получается прямая линия. Другие функции могут быть n^2 или 2^n или n! (факториал n). Это полиномиальные и экспоненциальные функции. В последних двух случаях экспоненциальные растут так быстро, что почти во всех случаях их нельзя решить ни для чего, кроме очень тривиальных примеров
Сложность времени выполнения и криптография
Если вы слышите об этом впервые и это звучит бессмысленно и заумно, давайте попробуем обосновать это обсуждение. Сложность выполнения криптографической схемы очень важна для криптографии, которая основана на том, чтобы сделать расшифровку намного проще для людей, знающих секретный ключ, чем для тех, кто его не знает. В идеальной криптографической схеме расшифровка должна быть линейной, если у вас есть ключ, и 2^k (где k – количество битов в ключе), если нет
Другими словами, лучшим алгоритмом расшифровки сообщения без ключа должно быть простое угадывание возможных ключей, что неразрешимо для ключей длиной всего в несколько сотен бит
Для криптографии с симметричным ключом (в которой две стороны имеют возможность безопасно обменяться секретом до начала общения) это довольно просто. Для асимметричной криптографии это сложнее
Асимметричная криптография, в которой ключи шифрования и дешифрования различны и не могут быть легко вычислены друг из друга, является гораздо более сложной для реализации математической структурой, чем симметричная криптография, но она также гораздо более мощная: асимметричная криптография позволяет вести частные разговоры даже по прослушиваемым линиям! Она также позволяет создавать ‘цифровые подписи’, позволяющие проверить, от кого пришло сообщение и не было ли оно подделано
Это мощные инструменты, составляющие основу современной приватности: без асимметричной криптографии пользователи электронных устройств не имели бы надежной защиты от посторонних глаз
Поскольку асимметричную криптографию сложнее построить, чем симметричную, стандартные схемы шифрования, используемые сегодня, не так сильны, как могли бы быть: самый распространенный стандарт шифрования, RSA, может быть взломан, если вы сможете эффективно найти простые коэффициенты очень большого числа. Хорошая новость заключается в том, что это очень трудная задача
Самый известный алгоритм разложения больших чисел на составляющие их простые называется ситом общего числового поля и имеет сложность выполнения, которая растет немного медленнее, чем 2^n. Как следствие, ключи должны быть примерно в десять раз длиннее, чтобы обеспечить аналогичную безопасность, и это то, с чем люди обычно мирятся как со стоимостью ведения бизнеса. Плохая новость заключается в том, что все игровое поле меняется, когда в дело вступают квантовые компьютеры
Квантовые компьютеры: Изменение криптовалютной игры
Квантовые компьютеры работают потому, что они могут иметь несколько внутренних состояний одновременно, благодаря квантовому явлению, называемому ‘суперпозицией’. Это означает, что они могут одновременно атаковать различные части проблемы, разделенные между возможными версиями вселенной. Они также могут быть настроены таким образом, что ветви, которые решают проблему, имеют наибольшую амплитуду, так что когда вы открываете коробку с котом Шредингера, версия внутреннего состояния, которую вы, скорее всего, получите, – это самодовольный кот, держащий расшифрованное сообщение
Для получения дополнительной информации о квантовых компьютерах ознакомьтесь с нашей недавней статьей на эту тему!
В итоге квантовые компьютеры не просто линейно быстрее, как обычные компьютеры: ускорение в два, десять или сто раз не сильно помогает, когда речь идет об обычной криптографии, которую вы обрабатываете в сотни миллиардов раз медленнее. Квантовые компьютеры поддерживают алгоритмы, которые имеют меньшую сложность во времени выполнения, чем это возможно в других случаях. Именно это делает квантовые компьютеры принципиально отличными от других вычислительных технологий будущего, таких как графен и мемристорные вычисления
В качестве конкретного примера можно привести алгоритм Шора, который может быть выполнен только на квантовом компьютере, который может выполнять факторизацию больших чисел за время log(n)^3 , что значительно лучше, чем лучшая классическая атака. Использование сита общего числового поля для факторизации числа с 2048 битами занимает около 10^41 единиц времени, что составляет более триллиона триллионов триллионов триллионов. При использовании алгоритма Шора для решения той же задачи требуется около 1000 единиц времени
Эффект становится тем более выраженным, чем длиннее ключи. В этом и заключается сила квантовых компьютеров
Не поймите меня неправильно – у квантовых компьютеров есть много потенциальных незлых применений. Квантовые компьютеры могут эффективно решать проблему странствующего продавца, что позволяет исследователям строить более эффективные транспортные сети и разрабатывать более совершенные электрические схемы. Квантовые компьютеры уже находят мощное применение в искусственном интеллекте
При этом их роль в криптографии будет катастрофической. Технологии шифрования, которые позволяют нашему миру продолжать функционировать, зависят от того, насколько трудно решить проблему факторизации целых чисел. RSA и родственные схемы шифрования – это то, что позволяет вам быть уверенным в том, что вы находитесь на правильном сайте, что файлы, которые вы скачиваете, не заражены вредоносным ПО, и что люди не шпионят за вашей работой в Интернете (если вы используете Tor)
Криптография обеспечивает безопасность вашего банковского счета и охрану мировой ядерной инфраструктуры. Когда квантовые компьютеры станут практичными, вся эта технология перестанет работать. Первая организация, которая разработает квантовый компьютер, если мир все еще работает на тех технологиях, которые мы используем сегодня, окажется в пугающе мощном положении
Итак, неизбежен ли квантовый апокалипсис? Можем ли мы что-нибудь с этим поделать? Как выяснилось.да
Пост-квантовая криптография
Существует несколько классов алгоритмов шифрования, которые, насколько нам известно, не могут быть значительно быстрее решены на квантовом компьютере. Они известны под общим названием ‘постквантовая криптография’ и дают некоторую надежду на то, что мир сможет перейти к криптосистемам, которые останутся безопасными в мире квантового шифрования
Перспективные кандидаты включают в себя шифрование на основе решетки, например, Ring-Learning With Error, безопасность которого обусловлена очевидной сложностью проблемы машинного обучения, и многомерную криптографию, безопасность которой обусловлена сложностью решения очень больших систем простых уравнений. Подробнее об этой теме можно прочитать в статье Википедии. Остерегайтесь: многие из этих вещей сложны, и вы можете обнаружить, что ваша математическая подготовка должна быть значительно усилена, прежде чем вы сможете действительно вникнуть в детали
Из всего этого можно сделать вывод, что постквантовые криптосхемы очень круты, но также очень молоды. Над ними нужно еще поработать, чтобы сделать их эффективными и практичными, а также продемонстрировать, что они безопасны. Причина, по которой мы можем доверять криптосистемам, заключается в том, что мы бросали в них достаточно много клинически параноидальных гениев в течение достаточно долгого времени, чтобы любые очевидные недостатки уже были обнаружены, и исследователи доказали различные характеристики, которые делают их сильными
Современная криптография зависит от света как дезинфицирующего средства, и большинство пост-квантовых криптографических схем просто слишком новы, чтобы доверять им мировую безопасность. Однако они уже на подходе, и если им повезет и они немного подготовятся, эксперты по безопасности смогут завершить переключение до того, как первый квантовый компьютер будет запущен в эксплуатацию
Однако если они потерпят неудачу, последствия могут быть ужасными. Мысль о том, что кто-то обладает такой силой, вызывает тревогу, даже если вы оптимистично настроены относительно его намерений. Вопрос о том, кто первым разработает работающий квантовый компьютер, – это вопрос, за которым все должны очень внимательно следить в следующем десятилетии
Беспокоит ли вас небезопасность криптографии для квантовых компьютеров? Каково ваше мнение? Поделитесь своими мыслями в комментариях ниже!
Image Credits: Binary orb Via Shutterstock
Комментировать