Большая часть современного шифрования, такого как RSA, основывается на целочисленной факторизации, которая, как полагают, не является сложной задачей NP, но относится к BQP, что делает его уязвимым для квантовых компьютеров. Интересно, почему не было алгоритма шифрования, основанного на известной NP-трудной проблеме. Это звучит (по крайней мере, теоретически) так, как если бы он сделал лучший алгоритм шифрования, чем тот, который не оказался NP-сложным.
109
Там были.
Одним из таких примеров является криптосистема Мак-Элиса, основанная на сложности декодирования линейного кода.
Второй пример - NTRUEncrypt, основанный на кратчайшей векторной проблеме, которая, как я считаю, известна как NP-Hard.
Другой - криптосистема ранца Меркле-Хеллмана, которая была взломана.
Примечание: я понятия не имею, сломаны ли первые два / насколько они хороши. Все, что я знаю, это то, что они существуют, и я получил их от поиска в сети.
источник
Я могу думать о четырех основных препятствиях, которые не являются полностью независимыми:
Обратите внимание, что у меня нет опыта в криптографии; это просто алгоритмические соотв. Теоретические сложности возражения.
источник
Криптография с открытым ключом, как мы ее знаем сегодня, построена на односторонних перестановках ловушек , и эта ловушка имеет важное значение.
Чтобы протокол был общедоступным, вам нужен ключ, доступный любому, и способ шифрования сообщения с использованием этого ключа. Очевидно, что после шифрования будет трудно восстановить исходное сообщение, зная только его шифр и открытый ключ: шифр должен быть дешифруемым только с некоторой дополнительной информацией, а именно с вашим закрытым ключом.
Имея это в виду, легко построить примитивную криптосистему, основанную на любой односторонней перестановке люка.
источник
Просто чтобы дать эвристический аргумент, основанный на практическом опыте.
Почти все случаи, почти все NP-полные проблемы, легко решить. Есть проблемы, когда это не так, но их трудно найти, и трудно быть уверенным, что у вас такой класс.
Это встречалось на практике несколько раз, когда люди пытаются написать генераторы случайных задач для какого-нибудь известного NP-полного класса, такого как Constraint Programming, SAT или Traveling Salesman. Позднее кто-то находит метод решения почти всех случаев, которые генератор случайных чисел производит тривиально. Конечно, если бы это было так для системы шифрования, у нас были бы серьезные проблемы!
источник
Криптосистемы Меркля-Хеллмана основаны на бинарных ранцевых задачах (сумма подмножеств).
источник