Предположим, что кто-то построил Криптографический квантовый компьютер (CQC) который специально может запускать алгоритм Гровера.Алгоритм Гровера асимптотически оптимален, т.е. $\mathcal{O}(\sqrt{n})$-время для $n$ бит безопасности для атаки по предварительному изображению или поиска ключа. То есть иметь 128-битную защиту из 256-битного пространства ключей. Это реклама алгоритма Гровера, да $\mathcal{O}(\log{n})$-space, однако, этого недостаточно.
Чего обычно не хватает, так это $\mathcal{O}(\sqrt{n})$ вызов алгоритма Гровера, считайте, что вы хотите сломать 128-бит, тогда вам нужно запустить алгоритм Гровера $2^{64}$-время. Если мы предположим, что вы можете выполнить один алгоритм Гровера на машине за одну нону секунду, тогда вам нужно $\около 585$ лет, чтобы найти ключ. Это довольно оптимистично в том смысле, что можно подготовить QCQ за одну наносекунду.
Алгоритм Гровера, как классический алгоритм можно распараллелить, тоже. Ну и интересно, для $к$ параллельно Гроверу у нас нет квадратичного увеличения, у нас есть $\sqrt{к}$ ускорить. Это плохо масштабируется.
На этом все про Гровера, теперь еще одна работа от Брассард и др. для хеш-функций для обнаружение столкновения, имеет $\mathcal{O}(\sqrt[3]{2^{256}})$-время и $\приблизительно \mathcal{O}(2^{85})$-пространство. Это все еще асимптотически оптимально, и на этот раз у нас есть 128-битная защита от 384-битной хэш-функции с $2^{128}$-пространственные требования.
С этим мы можем утверждать, что даже 256-битные хэш-функции и даже 128-битные блочные шифры безопасны для CQC. Более реалистичный расчет, сделанный из
Сохраняя детали статьи, давайте придерживаться НИСТ и предположим, что нам нужно $384$-битная хеш-функция против CQC, чтобы иметь 128-битную устойчивость к коллизиям, сопротивление предварительного изображения $192$-кусочек .
Если мы используем 256-битный HKDF, он будет иметь 128-битное сопротивление предварительного изображения CQC. Это означает, что 256-битного хеша будет достаточно.
Начиная с TLS 1.3 упростил почти все;
Хеш-функция, используемая Transcript-Hash и HKDF, представляет собой хеш-алгоритм набора шифров.
Значимое объяснение заключается в том, что SHA-384 выбран из-за 128-битной устойчивости к коллизиям, которая соответствует 128-битной стойкости AES-256. Упрощенно можно сказать, что AES_256_GCM_SHA384 имеет 128-битную защиту от противников Quantum.
