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

Один из наиболее распространенных алгоритмов шифрования RSA, повсеместно применяемый сегодня для безопасной передачи данных в интернете, использует факторизацию простых чисел. Идея алгоритма основана на том факте, что задачу разложения на множители очень большого числа невозможно быстро решить на компьютере, но если заранее знать один из множителей, то второй можно получить простым делением. Однако доказано, что квантовый компьютер сможет искать разложение на множители за достаточно короткое время, а значит алгоритм RSA более не сможет эффективно защищать данные пользователей в интернете.

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

Новый алгоритм, предложенный американскими учеными, основан на задаче о ранце: как выбрать из предметов с различным весом и “ценностью” оптимальный набор, который имел бы наибольшую суммарную “ценность” при суммарном весе, не превышающем изначально заданную величину. Как и факторизация целых чисел, задача о рюкзаке чрезвычайно трудна для алгоритмического решения, более того, доказано, что она принципиально сложнее задачи о факторизации (задача о рюкзаке является NP-полной, для задачи факторизации это не доказано). Построенную на ее основе криптографическую систему не смогут взломать даже квантовые компьютеры.

Первый алгоритм защиты данных на основе задачи о рюкзаке был предложен еще в 1976 году. Однако систему вскоре удалось взломать. Дальнейшие попытки улучшить алгоритм также не привели к успеху. Из-за этого ученые надолго отказались от использования задачи о рюкзаке в криптографии. Однако Нэйтан Хэмлин и Уильям Уэбб из Вашингтонского государственного университета утверждают, что им наконец удалось переработать алгоритм на фундаментальном уровне и избавить его от всех слабых мест.