aatatuzov

Квантовые компьютеры дают принципиальное ускорение только для конкретного класса задач (см. алгоритм Шора), важных для криптографии с открытым ключом. Для современных средств шифрования с секретным ключом квантовый компьютер [насколько известно сейчас] не представляет угрозы, надо только увеличить длину ключа раза в два, чтобы добиться того же уровня надежности (это из-за квантового алгоритма Гровера, который способен ограниченно ускорить перебор).

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

Тут надо пояснить, что такое шифрование с открытым ключом: кто угодно может зашифровать сообщение (с помощью открытого ключа), но расшифровать сможет только обладатель секретного ключа. Нужна схема для конфиденциальной передачи сообщений между ранее незнакомыми участниками (т. е. у них нет заранее согласованного секретного ключа для использования шифрования с секретным ключом). Вариация этого подхода лежит в основе https: там отрабатывает похожий протокол генерации общего секретного ключа, основанный на тех же задачах (см. протокол Диффи-Хеллмана).

Так вот, задачи, на трудности которых основаны текущие схемы для криптографии с открытым ключом - Диффи-Хеллман, RSA, Эль-Гамаль - могут быть эффективно решены с помощью алгоритма Шора, поэтому не годятся для постквантовой криптографии (повторюсь, именно для цифровой подписи ситуация другая, т.к. там есть более универсальная схема Лэмпорта). Активно идет поиск и проверка других задач (задачи на решетках - хороший кандидат), на основе которых можно реализовать те же протоколы. Это сейчас одно из основных направлений исследований в криптографии.

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

(Что-то я увлекся и слишком много написал, но не стирать же теперь)

FOCS 2021

1. Современные криптосистемы основаны на задачах из теории чисел, теории групп и тп. Нарушение стойкости таких криптосистем напрямую завязано на решение математических проблем, исследование которых невозможно ограничить.  2. Открытость и доступность - это сложившийся факт, результат долгой работы, которую проводили и продолжают вести те самые математики со всего мира. Самый известный пример - работа Диффи и Хеллмана New Directions in Cryptography 76 года, в которой, кстати, и была предложена та самая цифровая подпись. В NSA были не в восторге от происходящего, однако, статья все же вышла.

Над задачей работают математики со всего мира, в открытом режиме. Если будут хоть малейшие подвижки в направлении вскрытия шифра - то в первую очередь появятся математические статьи, которые "большим дядям" не понятны и не интересны от слова вообще. Посмотрите, к примеру, статьи на FOCS 2020 или STOC 2021. Вот типичное название работы: "Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups".

До середины XX века так и было. Теперь ситуация совсем другая. Шифры, которые используют в качестве стандартов, до сих пор никто не умеет взламывать существенно быстрее, чем полным перебором. Если стандарт 77 года DES сейчас можно взломать из-за короткого ключа (56 бит), то его модификацию Triple DES (использует три ключа DES вместо 1) - нет, и никакой рост производительности не поможет, там цифры превосходят возраст вселенной. Про текущий стандарт AES можно сказать все то же, но ключи там заранее предполагают немного больше. И, естественно, никто не мешает брать ключ размером в мегабайт, с запасом. Никаких алгоритмических идей, которые позволили бы взломать эти шифры, нет и близко. Только немного сокращают перебор, но цифры остаются астрономическими. Про связь между подписью и шифром - это отдельное направление в математике, теоретическая криптография, активно развивается с 80-х годов прошлого века.

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

С удовольствие читаю Игры Хаоса. Это такая особая реалРПГ серия на АТ. Очень спокойные, литературные книги. Уже выходит восьмая (вторая часть седьмой), а в мир ещё привносятся новые принципиальные детали (элементы пошаговой стратегии, к примеру); непрерывный рост персонажей при этом ровный, без присущей жанру сингулярности. 

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

Жаль, что закончился Гардар. Раиду Опила!