Возможно ли существование метода шифрования, который невозможно взломать, даже используя квантовые компьютеры?

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

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

Исследователи разработали компьютерный алгоритм, который не решает проблемы, а создает их для оценки квантовых компьютеров.

Можем ли мы ожидать новый криптографический алгоритм, который будет сложно взломать даже на квантовом компьютере ? Для наглядности: речь идет конкретно о разработке новых алгоритмов .

В заголовке вашего вопроса запрашиваются методы, которые невозможно взломать, на которые One Time Pad (OTP) является правильным ответом, как указано в других ответах. OTP теоретически защищен информацией, что означает, что вычислительные способности противника неприменимы, когда дело доходит до поиска сообщения.

Однако, несмотря на абсолютную безопасность в теории , OTP имеет ограниченное применение в современной криптографии. Это чрезвычайно трудно успешно использовать на практике .

Важный вопрос действительно таков:

Можем ли мы ожидать новый криптографический алгоритм, который будет сложно взломать даже на квантовом компьютере?

Асимметричная криптография

Асимметричная криптография включает в себя схемы шифрования с открытым ключом (PKE), цифровые подписи и схемы согласования ключей. Эти методы жизненно необходимы для решения проблем распределения ключей и управления ключами. Распределение ключей и управление ключами - это немаловажные проблемы, они в значительной степени препятствуют практическому использованию OTP. Интернет, каким мы его знаем сегодня, не будет функционировать без возможности создания защищенного канала связи из небезопасного канала связи, что является одной из функций, предлагаемых асимметричными алгоритмами.

Алгоритм Шора

Алгоритм Шора полезен для решения задач целочисленной факторизации и дискретных логарифмов. Эти две проблемы являются основой безопасности широко используемых схем, таких как RSA и Diffie-Hellman .

В настоящее время NIST оценивает материалы для постквантовых алгоритмов - алгоритмов, основанных на проблемах, которые считаются устойчивыми к квантовым компьютерам. Эти проблемы включают в себя:

• Решения на основе задач
  • Кратчайшая векторная задача (СВП)
  • Ближайшая векторная задача (CVP)
• Многомерные уравнения
  • Многомерные полиномиальные уравнения
• Схемы на основе кода
  • На основе сложности декодирования линейных кодов
• Суперсингулярная Изогения Диффи-Хеллмана (SIDH)

Следует отметить, что классические алгоритмы для решения вышеуказанных проблем могут существовать , просто время выполнения / точность этих алгоритмов является препятствующей для решения больших случаев на практике. Эти проблемы, по-видимому, не решаемы, если им предоставляется возможность решить проблему нахождения порядка , что и делает квантовая часть алгоритма Шора.

Симметричная криптография

Алгоритм Гровера обеспечивает квадратичное ускорение при поиске в несортированном списке. По сути, это проблема перебора симметричного ключа шифрования.

Обойти алгоритм Гровера относительно легко по сравнению с алгоритмом Шора: просто удвойте размер симметричного ключа . 256-битный ключ обеспечивает противнику, использующему алгоритм Гровера, 128-битное сопротивление против грубой силы.

Алгоритм Гровера также можно использовать против хеш-функций . Решение снова простое: удвойте размер выходного хэша (и емкость, если вы используете хеш на основе губчатой ​​конструкции ).

Я полагаю, что существует тип шифрования, который невозможно взломать с помощью квантовых компьютеров: одноразовый блокнот, такой как шифр Vigenère . Это шифр с клавиатурой, который имеет по крайней мере длину закодированной строки и будет использоваться только один раз. Этот шифр невозможно взломать даже с помощью квантового компьютера.

Я объясню почему:

Давайте предположим, что наш открытый текст ABCD. Соответствующий ключ может быть 1234. Если вы закодируете это, то получите XYZW. Теперь вы можете использовать, 1234чтобы получить ABCDили 4678получить EFGHто, что может быть правильным предложением тоже.

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

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

Да, есть много предложений по постквантовой криптографии алгоритмов, которые предоставляют криптографические примитивы, к которым мы привыкли (включая асимметричное шифрование с закрытыми и открытыми ключами).

В продолжение ответа Эллы Роуз: большинство практических схем шифрования, используемых сегодня (например, Диффи-Хеллмана, RSA, эллиптическая кривая, на основе решетки), сосредоточены вокруг сложности решения проблемы скрытой подгруппы (HSP). Тем не менее, первые три сосредоточены вокруг HSP для абелевых групп. HSP для абелевых групп может быть эффективно решена с помощью квантового преобразования Фурье , которое реализуется, например, алгоритмом Шора. Поэтому они уязвимы для атаки квантовым компьютером. С другой стороны, большинство методов, основанных на решетке, вращаются вокруг HSP для диэдрагруппы, которые неабелевы. Считается, что квантовые компьютеры не способны эффективно решать неабелеву HSP, поэтому эти алгоритмы должны быть в состоянии реализовать постквантовую криптографию.