Могут ли квантовые компьютеры взломать любой шифр? [закрыто]

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

Это правда?

Я голосую за то, чтобы закрыть этот вопрос как не по теме, потому что вопрос касается проверки заявления об использовании квантового компьютера, а вовсе не о физике. Возможно , Криптография или Скептики лучше подходят для этого вопроса.
На самом деле, я не думаю, что это тема для нас. На самом деле это вопрос о криптографии — единственная связь с физикой — это знание того, что квантовый компьютер может эффективно решать определенные задачи за менее чем экспоненциальное время.
Я не думаю, что это даже такое большое дело. Недавно я ответил на аналогичный вопрос: как квантовые вычисления изменят криптографию? , и tdlr в том, что мы знаем, как бороться с тем, что компьютеры становятся быстрее: большие пробелы между ключами.
@NathanCooper Если я смогу построить машину, чья способность к факторингу растет быстрее, чем способность вашей машины к шифрованию/дешифрованию, то большие пространства ключей не помогут. Или я что-то упускаю?
@DanielSank, если....
@emory конечно "если". Дело в том, что то, что сказал Натан, не имеет для меня никакого смысла.
Я думаю, что 24 голоса и несколько очень успешных ответов предполагают, что этот вопрос был уместным. Предлагаю заново открыть. Это популярный вопрос, связанный с квантовыми вычислениями — это, безусловно, междисциплинарный вопрос, но тот факт, что он междисциплинарный, не означает, что на него нельзя ответить или что он не является темой для этого форума.

Ответы (7)

Нет.

Квантовые компьютеры могут эффективно факторизовать большие числа, что позволило бы взломать многие широко используемые криптосистемы с открытым ключом, такие как RSA, которые основаны на сложности факторизации.

Однако существуют и другие криптосистемы, такие как криптография на основе решеток, которые не основаны на жесткости факторинга и которые (насколько нам известно) не будут уязвимы для атаки квантового компьютера.

Квантовые вычисления обещают много, но они не безграничны.

Утверждения (преувеличения), которые вы слышали, вероятно, основаны на самом известном алгоритме квантовых вычислений — алгоритме Шора . Это метод использования квантового компьютера для разложения целых чисел на простые числа. Как оказалось, многие схемы шифрования основаны на том факте, что разложение больших чисел на множители очень сложно. Сообщения могут быть довольно легко зашифрованы таким образом, что только тот, кто знает простую факторизацию конкретного числа, может расшифровать их с разумными усилиями. Если бы вы могли быстро разложить на множители большие числа, вы бы взломали многие современные схемы шифрования.

Однако есть и другие технологии, которым квантовые компьютеры не угрожают. Если ничего другого, вы всегда можете использовать одноразовый блокнот , пока само сообщение. Это математически невозможно взломать, поскольку любое сообщение можно «расшифровать» из зашифрованного с помощью соответствующего предположения ключа, поэтому у перехватчика нет возможности узнать настоящее сообщение.

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

Так помогут ли квантовые компьютеры перехватчикам получить преимущество над шифровальщиками или наоборот? Звучит так, будто в некоторых случаях расшифровка становится проще, но хорошее шифрование тоже становится проще.
Для одноразовых блокнотов шифрование становится более дорогим и менее безопасным, поскольку блокнот должен быть физически отправлен шифровальщику, который затем должен гарантировать, что он не будет прочитан «плохими парнями». Для очень больших потоков трафика подушки также становятся большими, так что это требует затрат. Однако пока ключ остается в безопасности, перехватчики беспомощны, а квантовые компьютеры бесполезны.
Но во многих случаях подслушивание не является проблемой. Например, скажем, у меня на жестком диске есть файл, который я не хочу, чтобы кто-либо читал, даже если они украдут машину.
@innisfree Квантовая механика помогает шифровальщикам больше, чем перехватчикам, поскольку квантовое распределение ключей делает одноразовые блокноты жизнеспособными по незащищенному каналу. Современные системы спроектированы таким образом, что любой подслушивающий может вызвать коллапс волновой функции, разрушая при этом OTP. Также обратите внимание, что алгоритм Шора в значительной степени является теоретической уязвимостью (на момент написания статьи максимальное число, которое было учтено, равно 56153), тогда как эти системы QKD используются сегодня.

На самом деле существует целый класс сложности, посвященный ответу: «Нет, он не может сломать код». Этот класс известен как BQP , или «квантовое полиномиальное время с ограниченной ошибкой». Это класс задач принятия решений, которые могут быть решены квантовым компьютером за полиномиальное время с погрешностью не более 1/3 (эта погрешность учитывается на классическом шаге вычислений, который происходит после того, как большинство квантовых алгоритмов проверяет, что результаты правильные).

Считается, что BQP имеет следующие отношения с другими сложностями:

  • Содержит P (полиномиальное время)
  • Пересекается, но, вероятно, не полностью содержит NP (недетерминированное полиномиальное время)
    • Вероятно, не содержит NP-полных (как следствие)
  • Подмножество PSPACE (задачи, решаемые с полиномиальными требованиями к пространству)

(Главное неизвестное в этом списке заключается в том, что еще неизвестно, является ли P = NP. Список предполагает, что P! = NP, но если P = NP, очевидно, что NP и NP-полные также будут частью BQP. Мы также не не знаю, NP = BQP или нет , так много еще предстоит выяснить! )

RSA можно взломать с помощью квантовых компьютеров, потому что задача факторизации больших составных чисел находится в BQP, как продемонстрировал алгоритм Шора. Алгоритм Шора является NP (но не NP-полным). Существуют и другие алгоритмы NP, которые, как считается, находятся за пределами BQP, которые можно использовать для шифрования (принятый ответ ссылается на криптографию на основе решетки, которая является одним из таких классов алгоритмов).

«Единственное неизвестное в этом списке — это то, что еще неизвестно, является ли P = NP». -- Точное соотношение NP и BQP также неизвестно.

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

Однако шифрование — это нечто большее, чем открытый ключ. Схемы симметричного шифрования, в которых две стороны совместно используют секретный ключ, считаются подверженными не более чем квадратичному ускорению с квантовыми компьютерами (квантовые компьютеры могут достичь квадратичного ускорения для общих задач поиска, но не более). Это соответствует эффективному уменьшению вдвое длины ключа. В отличие от обычных систем с открытым ключом, на эффективное уменьшение длины ключа вдвое очень легко реагировать: вы можете просто удвоить длину ключа и продолжить. Симметричное шифрование чрезвычайно распространено; даже там, где используется шифрование с открытым ключом, оно чаще всего просто используется для замены ключа на симметричное шифрование.

Наиболее распространенная симметричная система, AES, имеет 256-битный вариант ключа, обеспечивающий 128-битную защиту от квантовых компьютеров. Другие разрабатываемые схемы поддерживают 512-битные ключи, которые обеспечивают 256-битную эффективную защиту. И 128, и 256 бит считаются безопасными в обозримом будущем.

Точно так же считается, что криптографические хеш-функции очень хорошо противостоят квантовым компьютерам. Есть та же атака на основе алгоритма Гровера, но, как и в случае с функциями шифрования, ей легко противостоять.

Таким образом, любые заявления о том, что криптография становится бессмысленной, совершенно необоснованны, потому что единственное, что серьезно страдает, — это системы с открытым ключом. Системы с открытым ключом важны, но криптография — гораздо более широкая область.

И именно из-за этого ответа я чувствую, что этот вопрос здесь не по теме: здесь нет ни капли физики (то, что мы ожидаем , есть в каждом ответе).
@KyleKanos: здесь есть капля физики, в алгоритме Гровера, в котором в 1997 году было достаточно физики, чтобы его можно было опубликовать в Phys. Преподобный Летт. ($$) ( версия arXiv ). Я признаю, что это всего лишь капля физики, но знание того, физика это или информатика, является распространенной (и разочаровывающей) проблемой с квантовой информацией.

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

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

Поскольку программы по своей сути работают с логическими вентилями, разумно предположить, что любой существующий код для классических компьютеров может работать на квантовом компьютере.

См. также квантовые ворота в Википедии.

Это не имеет никакого смысла. Каким образом заявление о том, что квантовый компьютер может делать все то же, что и классический компьютер, исключает возможность того, что квантовые компьютеры могут взламывать коды? Особенно с учетом того, что классические компьютеры могут взламывать коды, просто не обязательно за разумное время. Ваш аргумент похож на высказывание: «Вилочные погрузчики не могут поднять 20 кг, потому что они могут поднять все, что может поднять человек». Это неправильно дважды: люди могут поднять 20 кг, а если и не могут, то погрузчик может больше.

Хорошо, теоретически квантовый компьютер может работать так:

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

Сложная часть (где одноразовый блокнот выделяется) заключается в том, как узнать, действительно ли полученное в результате расшифровки сообщение является правильным текстом. Например, я отправляю OKвам сообщение, зашифрованное с помощью AES 256 бит. Теперь есть 2^256 возможных ключей для расшифровки этого сообщения, и все они приведут к некоторому результату. Многие могут быть в чем-то вроде #§или других загадочных байтовых символах, но некоторые ключи могут привести к двум буквам «WB», а некоторые комбинации могут даже привести к «НЕТ».

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

--

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

Это не то, как работают квантовые компьютеры. Вера в то, что они могут, настолько распространена, что д-р Ааронсон посвятил этому заблуждению целый раздел своего блога: « Говорить правду о параллелизме » . Они дают ускорение для некоторых задач, но не так сильно, как можно было бы предположить. (В принципе, мы не думаем, что BQP = PSPACE.)
В этой категории есть много статей, хотя верно, что мемрезисторы или подобные технологии страдают от нескольких проблем (таких как кодирование вывода), квантовый компьютер может фундаментально решить сложную проблему с высокой вероятностью. И если вы можете настроить вероятность достаточно высоко, чтобы вы были точны на 99,99% с несколькими прогонами, это практически достаточно хорошо и могло бы решить упомянутые проблемы, если бы кто-то мог построить такой контроль качества.
Фундаментальная проблема заключается в том, что квантовые компьютеры не позволяют вам параллельно вычислять все возможные входные данные: квантовые вычисления не являются недетерманизмом.
Даже если цифра 99,99% была правильной (что, как объяснялось, это не так), 0,01% от 2 ^ 256 по-прежнему составляет около 1e73, а это довольно много ключей, которые еще предстоит проверить. На самом деле около 242 бит. (2 ^ 242 ~ 7.07e72) Таким образом , сокращение на 99,99% дает вам 14-15 бит оптимизации из 256-битного ключа. Впечатляет, да (многие другие атаки имеют тенденцию откусывать несколько битов из пространства поиска за раз, самое большее , часто с вариантами с уменьшенным количеством раундов), но очень далеко от полного взлома. Я предполагаю, что многие PRNG хуже, особенно если они плохо заполнены во время генерации ключа.
Помните высказывание Сноудена «предположим, что ваш противник способен угадывать триллион раз в секунду» (по общему признанию, о парольных фразах PGP, но тем не менее; это дает разумную основу для сравнения, и разница может составлять, возможно, несколько порядков или около того). Триллион равен 1e12. Это оставляет нам 1e61 секунду или около того. Возраст Вселенной оценивается примерно в 1e17 секунд. Грубо говоря, вы смотрите на 1e40 раз больше возраста Вселенной .
То, что вы описываете, — это недетерминированный компьютер («N» в «NP»). Хотя мы не знаем наверняка, что квантовые компьютеры не эквивалентны недетерминированным (мы даже не знаем, что п ≠ Н п ), мы почти уверены, что это не так.
-1 В этом ответе говорится, что BQP = NP , что считается ложным. Используя алгоритм Гровера , квантовые компьютеры могут ускорить поиск методом грубой силы с коэффициентом квадратного корня, что означает, что вы можете подобрать 256-битный ключ AES всего за 2^128 операций. Но это все равно экспоненциальная сложность.
Могут ли квантовые компьютеры взломать любой шифр? [закрыто]
СпросиСетьПолитика конфиденциальности1y, 0v