Квантовая цифровая подпись - Quantum digital signature - Wikipedia

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

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

Классический метод открытого ключа

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

${\displaystyle x\mapsto f(x)}$ легко

${\displaystyle f(x)\mapsto x}$ очень сложно

Квантовая цифровая подпись

Как и классические цифровые подписи, квантовые цифровые подписи используют асимметричные ключи. Таким образом, человек, который хочет подписать сообщение, создает одну или несколько пар подписи и соответствующих открытых ключей. В целом схемы квантовой цифровой подписи можно разделить на две группы:

1. Схема, которая создает открытый квантово-битовый ключ из частного классический битовая строка: ${\displaystyle k\mapsto |f_{k}\rangle }$
2. Схема, которая создает открытый квантово-битовый ключ из частного квант битовая строка: ${\displaystyle |k\rangle \mapsto |f_{k}\rangle }$

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

Самая известная схема для первого метода, описанного выше, предложена Готтесманом и Чуангом. ^[1]

Требования к хорошей и удобной схеме подписи

Большинство требований к классической схеме цифровой подписи также применимо к схеме квантовой цифровой подписи.

В деталях

1. Схема должна обеспечивать защиту от взлома
   1. Отправитель после подписания сообщения (см. немного обязательств )
   2. Получатель
   3. Третья сторона
2. Создание подписанного сообщения должно быть простым
3. Каждый получатель должен получить один и тот же ответ при проверке сообщения на достоверность (Действительный, Недействительный)

^[1][2]

Различия между классическими и квантовыми односторонними функциями

Природа односторонней функции

Классическая односторонняя функция, как было сказано выше, основана на классической невыполнимой математической задаче, тогда как квантовая односторонняя функция использует принцип неопределенности, который делает невозможным вычисление обратного даже для квантового компьютера. выходное состояние, с которым нельзя узнать достаточно о входной строке, чтобы воспроизвести ее. В случае первой группы схем это показано теоремой Холево, которая гласит, что из данного квантового состояния n-кубитов нельзя извлечь больше, чем n классические биты информации.^[3]Одна из возможностей гарантировать, что схема использует меньше кубитов для битовой строки определенной длины, заключается в использовании почти ортогональных состояний

${\displaystyle |\langle f_{k}|f_{k}'\rangle |<\delta \qquad {\text{ for }}k\neq k'\land 0\leq \delta \leq 1}$

Это дает нам возможность вызвать базис с более чем двумя состояниями.^[1]Итак, чтобы описать информацию о ${\displaystyle 2^{n}}$ бит, мы можем использовать менее n кубитов.Пример с базисом 3 кубита

• ${\displaystyle |0\rangle }$
• ${\displaystyle |1\rangle }$
• ${\displaystyle {\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )}$

Только m кубитов нужно для описания n классических битов, когда ${\displaystyle 3^{m}=2^{n}}$ держит.

Из-за теоремы Холево и того факта, что m может быть намного меньше n, мы можем получить только m бит из n-битного сообщения. В более общем смысле, если кто-то получает T копий открытого ключа, он может извлечь не более Tm бит закрытого ключа. ${\displaystyle \delta }$ большой ${\displaystyle n-Tm}$ становится очень большим, что делает невозможным угадать ключ знака нечестным человеком.

Примечание: вы не можете различить неортогональные состояния, если у вас есть только небольшое количество идентичных состояний. Так работают квантовые односторонние функции.
тем не менее ${\displaystyle |f_{k}\rangle }$ утечка информации о закрытом ключе, в отличие от классического открытого ключа, который заставляет ничего или все о закрытом ключе.

Копирование открытого ключа

В классическом случае мы создаем классический открытый ключ из классического знакового ключа, поэтому каждому потенциальному получателю легко предоставить копию открытого ключа. Открытый ключ может свободно распространяться. Это становится более трудным в квантовом случае, потому что копирование квантового состояния запрещено теоремой о запрете клонирования, пока само состояние неизвестно.^[4]Таким образом, открытые ключи могут быть созданы и распространены только человеком, который знает точное квантовое состояние, которое он хочет создать, таким образом, кто знает ключ подписи (это может быть отправитель или, в более общем смысле, доверенное учреждение). Тем не менее, в отличие от классический открытый ключ есть верхняя граница количества открытых квантовых ключей Т который может быть создан, не позволяя угадать ключ знака и, таким образом, ставя под угрозу безопасность схемы (${\displaystyle n-Tm}$ должен быть большим)

Открытый ключ должен быть одинаковым для всех получателей (тест подкачки)

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

${\displaystyle |f_{k}'\rangle =|f_{k}\rangle }$

Тест подкачки кубитов

Это делается с помощью следующей квантовой схемы, в которой используется один Фредкин ворота F, один Ворота Адамара ЧАС и вспомогательный кубит а.Прежде всего вспомогательный кубит устанавливается в симметричное состояние. ${\displaystyle |a\rangle ={\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )}$.

Сразу после того, как вспомогательный кубит используется как элемент управления для целей ${\displaystyle |f_{k}\rangle \ }$ и ${\displaystyle \ |f_{k}'\rangle }$ в воротах Фредкина.

Кроме того, к вспомогательному кубиту применяется вентиль Адамара, и, наконец, измеряется первый кубит. Если оба состояния совпадают, результат ${\displaystyle |0\rangle }$ Если оба состояния почти ортогональны, результат может быть либо ${\displaystyle |0\rangle \ }$ или же ${\displaystyle \ |1\rangle }$.^[1]

Подробнее о расчете своп-теста:

Общее состояние

${\displaystyle |\psi _{0}\rangle =|a\rangle |f_{k}\rangle |f_{k}'\rangle }$

${\displaystyle |\psi _{0}\rangle ={\frac {1}{\sqrt {2}}}{\bigg (}|0\rangle +|1\rangle {\bigg )}|f_{k}\rangle |f_{k}'\rangle }$

${\displaystyle |\psi _{0}\rangle ={\frac {1}{\sqrt {2}}}{\bigg (}|0\rangle |f_{k}\rangle |f_{k}'\rangle +|1\rangle |f_{k}\rangle |f_{k}'\rangle {\bigg )}}$

После Фредкин ворота применяются

${\displaystyle \Rightarrow {\frac {1}{\sqrt {2}}}{\bigg (}|0\rangle |f_{k}\rangle |f_{k}'\rangle +|1\rangle \mathbf {|f_{k}'\rangle |f_{k}\rangle } {\bigg )}}$

После Адамар вентиль применяется к первому кубиту

${\displaystyle \Rightarrow {\frac {1}{2}}{\bigg [}{\bigg (}|0\rangle +|1\rangle {\bigg )}|f_{k}\rangle |f_{k}'\rangle +{\bigg (}|0\rangle -|1\rangle {\bigg )}|f_{k}'\rangle |f_{k}\rangle {\bigg ]}}$

После сортировка за ${\displaystyle |0\rangle {\text{ and }}|1\rangle }$

${\displaystyle \Rightarrow |\psi \rangle ={\frac {1}{2}}{\bigg [}|0\rangle {\bigg (}|f_{k}\rangle |f_{k}'\rangle +|f_{k}'\rangle |f_{k}\rangle {\bigg )}+|1\rangle {\bigg (}|f_{k}\rangle |f_{k}'\rangle -|f_{k}'\rangle |f_{k}\rangle {\bigg )}{\bigg ]}}$

Теперь легко увидеть, если состояния ${\displaystyle |f_{k}\rangle =|f_{k}'\rangle \ }$ тогда ${\displaystyle \ |\psi \rangle =|0\rangle |f_{k}\rangle |f_{k}\rangle }$, что дает нам 0 при каждом измерении.

Пример процесса подписи-проверки с использованием упрощенной схемы Готтесмана-Чуанга

Процесс подписания

Пример процесса подписи для бита сообщения b = 0 с использованием схемы Готтесмана-Чуанга

Пусть человек A (Алиса) хочет отправить сообщение человеку B (Бобу). Алгоритмы хеширования не будут рассматриваться, поэтому Алиса должна подписать каждый бит своего сообщения. Бит сообщения б ${\displaystyle \in \{0,1\}}$.

Алиса выбирает M пары приватных ключей ${\displaystyle \{k_{0}^{i},k_{1}^{i}\}\quad 1\leq i\leq M}$

• Все ${\displaystyle k_{0}}$ ключи будут использоваться для подписи бита сообщения, если b = 0.
• Все ${\displaystyle k_{1}}$ ключи будут использоваться для подписи бита сообщения, если b = 1.

Функция, отображающая ${\displaystyle k\mapsto |f_{k}\rangle }$ известно всем сторонам. Теперь Алиса вычисляет соответствующие открытые ключи ${\displaystyle \{|f_{k_{0}}^{i}\rangle ,|f_{k_{1}}^{i}\rangle \}}$ и раздает их получателям. Она может сделать столько копий, сколько ей нужно, но должна быть осторожна, чтобы не поставить под угрозу безопасность ${\displaystyle \left(n\gg Tm{\text{ has to hold }}\right)}$.

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

Если

• бит сообщения б = 0, она отправляет все свои закрытые ключи ${\displaystyle k_{0}}$ вместе с битом сообщения б Бобу
• бит сообщения b = 1, она отправляет все свои закрытые ключи ${\displaystyle k_{1}}$ вместе с битом сообщения б Бобу

Помните: в этом примере Алиса выбирает только один бит б и подписывает это. Она должна делать это для каждого бита в своем сообщении.

Процесс валидации

Пример проверки с использованием схемы Готтесмана-Чуанга. Учитывается только один порог

Боб теперь обладает

• Бит сообщения б
• Соответствующие приватные ключи ${\displaystyle k_{0}{\text{ or }}k_{1}}$
• Все открытые ключи ${\displaystyle \{|f_{k_{0}}\rangle ,|f_{k_{1}}\rangle \}}$

Теперь Боб вычисляет ${\displaystyle |f_{k_{b}}\rangle }$ для всех полученных приватных ключей (либо ${\displaystyle k_{0}{\text{ or }}k_{1}}$).

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

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

Избегайте другой проверки сообщения

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

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

Принятие ${\displaystyle T_{a}=c_{1}M}$

Отказ ${\displaystyle T_{r}=c_{2}M}$

• Если количество неверных ключей р ниже ${\displaystyle T_{a}}$, то бит действителен с большой вероятностью
• Если количество неверных ключей р выше ${\displaystyle T_{r}}$, то бит подделан с большой вероятностью
• Если количество неверных ключей р находится между обоими пороговыми значениями, то получатель не может быть уверен, что другой получатель получит такой же результат при проверке бита. Более того, он не может быть даже уверен, правильно ли он подтвердил сообщение.

^[1]

Если мы предполагаем идеальные каналы без шума, поэтому бит не может быть изменен из-за передачи, то порог ${\displaystyle T_{a}}$ может быть установлен в ноль, потому что проверка подкачки проходит всегда, когда сравниваемые состояния совпадают

Аутентификация сообщения

Коды аутентификации сообщений (MAC) в основном предназначены для аутентификации источника данных, но они также могут обеспечить неотказуемость в определенных реалистичных сценариях, когда задействована доверенная третья сторона. В принципе, та же идея может быть использована в рамках квантовых MAC. Тем не менее, широкий класс квантовых MAC не дает никаких преимуществ перед своими классическими аналогами. ^[5]

Смотрите также

• Подпись Лэмпорта - Практический метод цифровой подписи, изобретенный в 1970-х годах и считающийся безопасным даже против атак квантовых вычислений.
• Квантовая криптография
• Квантовый отпечаток пальца

Рекомендации

1. Даниэль Готтесман, Исаак Л. Чуанг. Квантовые цифровые подписи, arXiv: Quant-ph / 0105032 v2, (15 ноября 2001 г.)
2. Синь Люй, Дэн-Го Фэн. Квантовая цифровая подпись на основе квантовых односторонних функций, arxiv: Quant-ph / 04030462 v2, (24 июня 2004 г.)
3. Майкл А. Нильсен, Исаак Л. Чуанг. Квантовые вычисления и квантовая информация 1-е изд., Издательство Кембриджского университета, стр.531-536
4. Майкл А. Нильсен, Исаак Л. Чуанг. Квантовые вычисления и квантовая информация 1-е изд., Издательство Кембриджского университета, стр.532
5. Николопулос, Георгиос М .; Фишлин, Марк (2020). "Информационно-безопасная аутентификация источника данных с использованием квантовых и классических ресурсов". Криптография. 4 (4): 31. Дои:10.3390 / криптография4040031.