Создание квантового компьютера, способного взломать одну из ключевых криптосистем — эллиптические кривые — требует значительно меньше ресурсов, чем предполагалось всего пару лет назад. К такому выводу пришли авторы двух независимо написанных белых бумаг. В первой работе исследователи показали, как использовать нейтральные атомы в качестве перенастраиваемых кубитов с прямым доступом друг к другу. Такой подход позволяет взломать 256-битное шифрование на эллиптических кривых (ECC) за 10 дней, сократив накладные расходы в 100 раз по сравнению с прежними оценками.

Прорыв от Google: взлом за девять минут

Во второй статье специалисты из Google продемонстрировали, что могут взломать ECC-защиту блокчейнов, используемых в биткоине и других криптовалютах, менее чем за девять минут. При этом они достигли 20-кратного сокращения ресурсов. Обе работы ещё не прошли рецензирование, но уже вызывают серьёзное внимание.

Квантовые архитектуры и алгоритмы меняют правила игры

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

Во-вторых, появляются всё более эффективные алгоритмы, усиливающие алгоритм Шора — математическую основу квантового взлома. Этот метод, предложенный ещё в 1994 году, доказывает, что квантовые компьютеры могут взламывать ECC и RSA за полиномиальное время, а именно — кубическое. Это невероятно быстрее, чем экспоненциальное время, требуемое современным классическим машинам.

«Научное сообщество продолжает стабильно продвигаться вперёд — как в создании физических кубитов, так и в разработке квантовых алгоритмов для эффективного и практического CRQC», — отметил Брайан ЛаМаккия, криптографический инженер, руководивший переходом Microsoft на постквантовую криптографию с 2015 по 2022 год, а ныне работающий в Farcaster Consulting Group.

«Я не думаю, что эти работы дают нам новую чёткую дату появления практического CRQC (чего, разумеется, у нас никогда и не было), но они подтверждают: мы неуклонно движемся к его созданию, и прогресс не замедляется».

Building a utility-scale quantum computer that can crack one of the most vital cryptosystems—elliptic curves—doesn’t require nearly the resources anticipated just a year or two ago, two independently written whitepapers have concluded. In one, researchers demonstrated the use of neutral atoms as reconfigurable qubits that have free access to each other. They went on to show this approach could allow a quantum computer to break 256-bit elliptic-curve cryptography (ECC) in 10 days while using 100 times less overhead than previously estimated. In a second paper, Google researchers demonstrated how to break ECC-securing blockchains for bitcoin and other cryptocurrencies in less than nine minutes while achieving a 20-fold resource reduction.

Taken together, the papers are the latest sign that cryptographically relevant quantum computing (CRQC) at utility-scale is making meaningful progress. The advances are largely being driven by new quantum architectures developed by physicists and computer scientists in a push to create quantum computers that operate correctly even in the presence of errors that occur whenever qubits—the quantum analog to classical computing bits—interact with their environment. The other key drivers are ever-more efficient algorithms to supercharge Shor’s algorithm, the 1994 series of equations proving that quantum computing could break the ECC and RSA cryptosystems in polynomial time, specificallycubic time, far faster than the exponential time provided by today’s classical computers.

Neither paper has been peer-reviewed.

“The research community continues to make steady progress on both the physical qubits and the quantum algorithms necessary to realize an efficient and practical CRQC,” said Brian LaMacchia, a cryptography engineer who oversaw Microsoft’s post-quantum transition from 2015 to 2022 and now works at Farcaster Consulting Group. “I don’t think either paper gives us a new, hard date for when we’re going to have a practical CRQC (which of course we’ve never had), but they both provide evidence that we are continuing to march down the road to a realizable CRQC and progress toward that goal is not slowing down.”