Весь интернет держится на вере в нерешаемую задачку. Решат — и мы снова в каменном веке
NewsMakerСпасти нас могут… только кубиты?
В классической криптографии стойкость большинства схем основана на сложности определённых математических задач . Но несмотря на десятилетия исследований, их неразрешимость так и не была строго доказана. Любое открытие, позволяющее эффективно решать хотя бы одну из них, может обрушить всю существующую систему защиты данных. Поэтому криптографы давно ищут другие пути — в том числе за счёт принципов квантовой физики.
В 2021 году аспирант Уильям Кречмер предложил оригинальную схему , использующую квантовые эффекты в качестве основы для новой криптографии — независимой от NP-задач. По замыслу автора, подход мог применяться для множества задач: от шифрования и цифровых подписей до защищённых голосований. Но теория Кречмера была завязана на «оракулы» — абстрактные конструкции, не реализуемые в физическом мире. Это делало его схему теоретически интересной, но непрактичной.
Год спустя Дакшита Курана из Университета Иллинойса в Урбана-Шампейн вместе со своим аспирантом Кабиром Томером решила адаптировать идею под реальные вычисления. Они начали с квантового аналога односторонней функции — генератора состояний, который можно быстро вычислить, но трудно обратить. В отличие от классической версии, такой генератор работает с кубитами, а не с битами, что задаёт принципиально другой уровень сложности.
На практике всё оказалось куда сложнее, чем на уровне формул. После нескольких месяцев безуспешной работы исследователи поняли, что для завершения схемы им нужен промежуточный компонент, связывающий генератор с криптографическими протоколами. Так появилась идея «односторонней головоломки» (one-way puzzle).
Эта структура устроена необычно: ключ и замок создаются квантовыми методами, но сами данные — обычные биты. При этом даже при наличии ключа замок расшифровать сложно. Такая схема практически бесполезна для реального шифрования, но вполне пригодна как строительный блок для моделирования криптографических систем. Как объяснил Кречмер: «Достаточно того, что существует алгоритм, пусть даже крайне медленный, который в принципе может справиться с задачей — это уже даёт основание считать систему рабочей».
Вскоре после завершения этой теоретической части у Кураны родилась дочь. Через три месяца она вернулась к проекту и вместе с Томером начала следующий этап — попытку привязать построенную схему к конкретной математической задаче, способной заменить классические криптоосновы.
Первоначально они хотели снова использовать генераторы квантовых состояний, но позже решили связать головоломки напрямую с вычислением перманента матрицы. Это не просто сложная задача — она относится к классу, где затруднена даже проверка решения, и значительно превосходит NP-проблемы по трудности. При этом она тесно связана с теми задачами, которые квантовые компьютеры решают эффективно, в отличие от классических машин.
Если удастся строго подтвердить это квантовое преимущество, то, как показали Курана и Томер, на его основе можно будет строить надёжные односторонние головоломки — а дальше и всю архитектуру криптографической защиты. Это решает главную проблему классической модели — её зависимость от предположительно труднорешаемых задач.
Сегодня уровень развития квантовой техники ещё не позволяет реализовать предложенные схемы на практике. Но сама возможность построить теоретически обоснованную альтернативу классической криптографии — уже значительный шаг вперёд. Как отметил исследователь Зандри из NTT Research: «Мы только начинаем понимать ландшафт, который всё это время существовал, но оставался неразведанным».
В классической криптографии стойкость большинства схем основана на сложности определённых математических задач . Но несмотря на десятилетия исследований, их неразрешимость так и не была строго доказана. Любое открытие, позволяющее эффективно решать хотя бы одну из них, может обрушить всю существующую систему защиты данных. Поэтому криптографы давно ищут другие пути — в том числе за счёт принципов квантовой физики.
В 2021 году аспирант Уильям Кречмер предложил оригинальную схему , использующую квантовые эффекты в качестве основы для новой криптографии — независимой от NP-задач. По замыслу автора, подход мог применяться для множества задач: от шифрования и цифровых подписей до защищённых голосований. Но теория Кречмера была завязана на «оракулы» — абстрактные конструкции, не реализуемые в физическом мире. Это делало его схему теоретически интересной, но непрактичной.
Год спустя Дакшита Курана из Университета Иллинойса в Урбана-Шампейн вместе со своим аспирантом Кабиром Томером решила адаптировать идею под реальные вычисления. Они начали с квантового аналога односторонней функции — генератора состояний, который можно быстро вычислить, но трудно обратить. В отличие от классической версии, такой генератор работает с кубитами, а не с битами, что задаёт принципиально другой уровень сложности.
На практике всё оказалось куда сложнее, чем на уровне формул. После нескольких месяцев безуспешной работы исследователи поняли, что для завершения схемы им нужен промежуточный компонент, связывающий генератор с криптографическими протоколами. Так появилась идея «односторонней головоломки» (one-way puzzle).
Эта структура устроена необычно: ключ и замок создаются квантовыми методами, но сами данные — обычные биты. При этом даже при наличии ключа замок расшифровать сложно. Такая схема практически бесполезна для реального шифрования, но вполне пригодна как строительный блок для моделирования криптографических систем. Как объяснил Кречмер: «Достаточно того, что существует алгоритм, пусть даже крайне медленный, который в принципе может справиться с задачей — это уже даёт основание считать систему рабочей».
Вскоре после завершения этой теоретической части у Кураны родилась дочь. Через три месяца она вернулась к проекту и вместе с Томером начала следующий этап — попытку привязать построенную схему к конкретной математической задаче, способной заменить классические криптоосновы.
Первоначально они хотели снова использовать генераторы квантовых состояний, но позже решили связать головоломки напрямую с вычислением перманента матрицы. Это не просто сложная задача — она относится к классу, где затруднена даже проверка решения, и значительно превосходит NP-проблемы по трудности. При этом она тесно связана с теми задачами, которые квантовые компьютеры решают эффективно, в отличие от классических машин.
Если удастся строго подтвердить это квантовое преимущество, то, как показали Курана и Томер, на его основе можно будет строить надёжные односторонние головоломки — а дальше и всю архитектуру криптографической защиты. Это решает главную проблему классической модели — её зависимость от предположительно труднорешаемых задач.
Сегодня уровень развития квантовой техники ещё не позволяет реализовать предложенные схемы на практике. Но сама возможность построить теоретически обоснованную альтернативу классической криптографии — уже значительный шаг вперёд. Как отметил исследователь Зандри из NTT Research: «Мы только начинаем понимать ландшафт, который всё это время существовал, но оставался неразведанным».