В 1994 году Питер Шор предложил эффективный алгоритм факторизации, то есть разложения числа на простые множители для квантового компьютера. Спустя семь лет работоспособность этого алгоритма продемонстрировала группа специалистов IBM на числах, которые уже тогда могли разложить на множители при помощи классических компьютеров. Используя алгоритм Шора, квантовые компьютеры смогут взломать системы, основанные на алгоритмах с открытым ключом, так что использование таких алгоритмов фактически потеряет смысл.
В 1996 году американский математик Лов Гровер предложил другой квантовый алгоритм, основанный на методе перебора чисел. Этот алгоритм квантовые компьютеры смогут использовать для взлома систем симметричного шифрования. Чтобы сохранить текущий уровень безопасности, потребуется удвоить размер ключей.
Появление квантовых вычислений неизбежно приведет к изменениям в методах шифрования. В противном случае практически все существующие системы будут достаточно быстро взломаны. При этом появление квантовых компьютеров по-разному повлияет на безопасность классических криптографических алгоритмов: в алгоритмах с открытым ключом защита исчезнет полностью, а в симметричных алгоритмах ее эффективность снизится вдвое.
Идея о том, что популярные сегодня алгоритмы шифрования перестанут защищать данные, может прозвучать угрожающе. Но на самом деле алгоритмы, которые в первую очередь нужно исправить,— это цифровые подписи и шифрование с открытым ключом. После исправления этих алгоритмов все самые важные протоколы можно будет сделать квантово-безопасными. Наступит эпоха так называемой постквантовой криптографии.