Предсказуемость псевдослучайных генераторов квантовыми компьютерами
Могут ли классические псевдослучайные генераторы быть предсказуемыми мощными квантовыми компьютерами в будущем, или доказано, что это невозможно?
Если они предсказуемы, знают ли ученые, существуют ли PRG, которые непредсказуемы квантовыми компьютерами?
1 ответ
Безопасность классического криптографического генератора псевдослучайных чисел (CPRNG) всегда основана на некотором допущении жесткости, таком как "факторинг сложен" или "столкновение функции SHA-256 трудно".
Квантовые компьютеры облегчают некоторые вычислительные проблемы. Это нарушает некоторые старые предположения о твердости. Но не все из них.
Например, blum blum shub, вероятно, сломан квантовыми компьютерами, но никто не знает, как сломать решеточную криптографию с квантовыми компьютерами. Показывать, что вы можете сломать все классические CPRNG с квантовыми компьютерами, равносильно тому, чтобы показать, что BQP= NP, что, как ожидается, не так.
Даже если квантовые компьютеры сломали все классические CPRNG, они также заполняют эту дыру. Они позволяют создавать "Einstein-сертифицированные" случайные числа.