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

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

Если это возможно, от каких предположений это будет зависеть? (Факторизация больших чисел, $a^b\pmod d$ $a^c\pmod d$ $a^{bc}\pmod d$ т.д ...)

speedup complexity-theory cryptography MCCCS
источник

Связанный : может ли квантовый компьютер моделировать нормальный компьютер? & Возможно ли существование метода шифрования, который невозможно взломать, даже используя квантовые компьютеры? ,

Санчайан Датта

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

Ниль де Боудрап,

Ответы:

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

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

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

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

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