Существуют ли какие-либо комплекты шифрования, которые могут быть взломаны классическими компьютерами, но не квантовыми компьютерами?

11

Существуют ли какие-либо комплекты шифрования, которые могут быть взломаны обычными компьютерами или суперкомпьютерами, но не квантовыми компьютерами?

Если это возможно, от каких предположений это будет зависеть? (Факторизация больших чисел, ab(modd) ac(modd) abc(modd) т.д ...)

MCCCS
источник
4
Квантовый компьютер теоретически может делать все, что может делать классический компьютер, и в этом случае ваш вопрос имеет смысл только как вопрос о техническом уровне техники. Все, что для этого потребуется, - это криптосистема, которая может быть легко решена с помощью классического компьютера с использованием базовой арифметики (например, простого сложения по модулю N) на достаточно больших числах, чтобы эти числа не могли быть сохранены на сегодняшних относительно незначительных прототипах устройств.
Ниль де Боудрап,

Ответы:

13

Это не очень понятная концепция, потому что наиболее интересные квантовые алгоритмы, такие как алгоритм Шора, также включают в себя некоторые классические вычисления. В то время как вы всегда можете использовать классические вычисления в квантовом компьютере , это будет стоить слишком дорого.

Мы, конечно, еще не знаем, какие именно проблемы будет трудно решить, даже если будет предоставлен квантовый компьютер - сейчас проводится конкурс NIST PQCRYPTO для изучения этого вопроса.

Однако даже в этом случае на него, скорее всего, не будет дан окончательный ответ, равно как и на окончательный ответ о том, какую криптографию мы не можем сломать на классических компьютерах: никто не нашел реально эффективного классического алгоритма для разложения произведения на единообразное случайное 1024-битное простых чисел, чье соотношение взаимно простое с 3, и никто не нашел реально эффективный классический алгоритм для вычисления корней куба по модулю , и никто даже не установил, сложнее ли факторинг, чем вычисление корней куба (хотя, конечно, это не проще ).nϕ(n)n

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

Брезгливый оссифраж
источник