Cyfrowy podpis kwantowy

Quantum Digital Signature (QDS) odnosi się do kwantowo-mechanicznego odpowiednika klasycznego podpisu cyfrowego lub, bardziej ogólnie, odręcznego podpisu na dokumencie papierowym. Podobnie jak podpis odręczny, podpis cyfrowy służy do ochrony dokumentu, takiego jak umowa cyfrowa, przed sfałszowaniem przez inną stronę lub jedną z uczestniczących stron.

Wraz ze wzrostem znaczenia handlu elektronicznego w społeczeństwie pojawiła się potrzeba poświadczania pochodzenia wymienianych informacji. Nowoczesne podpisy cyfrowe zwiększają bezpieczeństwo w oparciu o trudność rozwiązania problemu matematycznego, takiego jak znajdowanie czynników dużych liczb (stosowanych w algorytmie RSA ). Niestety, zadanie rozwiązania tych problemów staje się wykonalne, gdy dostępny jest komputer kwantowy (patrz algorytm Shora ). Aby stawić czoła temu nowemu problemowi, opracowywane są nowe schematy kwantowych podpisów cyfrowych, które zapewniają ochronę przed manipulacją, nawet ze strony osób posiadających komputery kwantowe i stosujących potężne strategie oszukiwania kwantowego.

Klasyczna metoda klucza publicznego

Metoda kryptografii z kluczem publicznym umożliwia nadawcy podpisanie wiadomości (często tylko kryptograficznego skrótu wiadomości) kluczem podpisu w taki sposób, że każdy odbiorca może, używając odpowiedniego klucza publicznego, sprawdzić autentyczność wiadomości. Aby to umożliwić, klucz publiczny jest szeroko udostępniany wszystkim potencjalnym odbiorcom. Aby upewnić się, że tylko legalny autor wiadomości może prawidłowo podpisać wiadomość, klucz publiczny jest tworzony z losowego, prywatnego klucza podpisu, przy użyciu funkcji jednokierunkowej . Jest to funkcja zaprojektowana w taki sposób, że obliczenie wyniku przy danych wejściowych jest bardzo łatwe, ale obliczenie danych wejściowych przy danym wyniku jest bardzo trudne. Klasycznym przykładem jest mnożenie dwóch bardzo dużych liczb pierwszych: mnożenie jest łatwe, ale rozłożenie iloczynu na czynniki bez znajomości liczb pierwszych jest zwykle uważane za niewykonalne.

{\ Displaystyle x \ mapsto f (x)}

łatwe

{\ Displaystyle f (x) \ mapsto x}

bardzo trudne

Cyfrowy podpis kwantowy

Podobnie jak klasyczne podpisy cyfrowe, kwantowe podpisy cyfrowe wykorzystują klucze asymetryczne. Zatem osoba, która chce podpisać wiadomość, tworzy jedną lub więcej par znaku i odpowiednich kluczy publicznych. Ogólnie schematy kwantowych podpisów cyfrowych możemy podzielić na dwie grupy:

Schemat, który tworzy publiczny klucz kwantowo-bitowy z prywatnego klasycznego ciągu bitów: ${\ Displaystyle k \ mapsto | f_ {k} \ rangle}$
Schemat, który tworzy publiczny klucz kwantowo-bitowy z prywatnego ciągu bitów kwantowych : ${\ Displaystyle | k \ ranga \ mapsto | f_ {k} \ ranga}$

W obu przypadkach f jest jednokierunkową funkcją kwantową, która ma takie same właściwości jak klasyczna funkcja jednokierunkowa. Oznacza to, że wynik jest łatwy do obliczenia, ale w przeciwieństwie do klasycznego schematu funkcji nie można odwrócić , nawet jeśli stosuje się potężne strategie oszukiwania kwantowego.

Najbardziej znany schemat dla pierwszej powyższej metody został przedstawiony przez Gottesmana i Chuanga

Wymagania dotyczące dobrego i użytecznego schematu podpisu

Większość wymagań dotyczących klasycznego schematu podpisu cyfrowego dotyczy również kwantowego schematu podpisu cyfrowego.

Szczegółowo

System musi zapewniać zabezpieczenie przed manipulacją przez
1. Nadawca po podpisaniu wiadomości (patrz zobowiązanie bitowe )
2. Odbiornik
3. Strona trzecia
Tworzenie podpisanej wiadomości musi być łatwe
Każdy odbiorca musi otrzymać tę samą odpowiedź podczas testowania wiadomości pod kątem ważności (ważna, nieprawidłowa)

Różnice między klasycznymi i kwantowymi funkcjami jednokierunkowymi

Natura funkcji jednokierunkowej

Klasyczna funkcja jednokierunkowa, jak wspomniano powyżej, opiera się na klasycznym niewykonalnym zadaniu matematycznym, podczas gdy kwantowa funkcja jednokierunkowa wykorzystuje zasadę nieoznaczoności, która uniemożliwia nawet komputerowi kwantowemu obliczenie odwrotności. Odbywa się to poprzez zapewnienie kwantowego stanu wyjściowego, z którym nie można dowiedzieć się wystarczająco dużo o ciągu wejściowym, aby go odtworzyć. W przypadku pierwszej grupy schematów pokazuje to twierdzenie Holevo, które mówi, że z danego n-kubitowego stanu kwantowego nie można wydobyć więcej niż n klasycznych bitów informacji. Jedną z możliwości zapewnienia, że schemat używa mniej kubitów dla ciągu bitów o określonej długości, jest użycie stanów prawie ortogonalnych

{\ Displaystyle | \ langle f_ {k} | f_ {k} '\ rangle | <\ delta \ qquad {\ tekst {dla}} k \ neq k '\ ziemia 0\równik \delta \równik 1}

To daje nam możliwość indukowania bazy z więcej niż dwoma stanami. Tak więc, aby opisać informację o długości ${\ displaystyle 2 ^ {n}}$ bitów, możemy użyć mniej niż n kubitów. Przykład z bazą 3 kubitów

${\ Displaystyle | 0 \ rangle}$
${\ Displaystyle | 1 \ rangle}$
${\ Displaystyle {\ Frac {1} {\ sqrt {2}}} (| 0 \ rangle + | 1 \ rangle)}$

$,$ gdy .

Z powodu twierdzenia Holevo i faktu, że m może być znacznie mniejsze od n, możemy wydobyć tylko m bitów z n-bitowej wiadomości. Mówiąc bardziej ogólnie, jeśli ktoś otrzyma T kopii klucza publicznego, może wyodrębnić co najwyżej Tm bitów klucza prywatnego. Jeśli jest duży, $staje$ $duży , co$ klucza znaku

Uwaga: Nie możesz rozróżnić stanów nieortogonalnych, jeśli masz tylko niewielką liczbę identycznych stanów. Tak działają kwantowe funkcje jednokierunkowe. Niemniej ${\ displaystyle | f_ {k} \ rangle}$ wycieka informacje o kluczu prywatnym, w przeciwieństwie do klasycznego klucza publicznego, który zmusza do uzyskania niczego lub wszystkiego o kluczu prywatnym.

Kopiowanie klucza publicznego

W klasycznym przypadku klasyczny klucz publiczny tworzymy z klasycznego klucza znakowego, dzięki czemu łatwo jest udostępnić kopię klucza publicznego każdemu potencjalnemu odbiorcy. Klucz publiczny może być swobodnie dystrybuowany. Staje się to trudniejsze w przypadku kwantowym, ponieważ kopiowanie stanu kwantowego jest zabronione przez twierdzenie o zakazie klonowania, o ile sam stan jest nieznany. Tak więc klucze publiczne mogą być tworzone i dystrybuowane tylko przez osobę, która zna dokładny stan kwantowy, który chce stworzyć, a więc kto zna klucz znaku (może to być nadawca lub bardziej ogólnie zaufana instytucja). Niemniej jednak, w przeciwieństwie do klasycznego klucza publicznego, istnieje górna granica liczby publicznych kluczy kwantowych T , które można utworzyć, nie umożliwiając odgadnięcia klucza znaku, a tym samym zagrażając bezpieczeństwu schematu ( musi być duży ) ${\ displaystyle n-Tm}$

Klucz publiczny powinien być taki sam dla każdego odbiorcy (test zamiany)

Aby mieć pewność, że każdy odbiorca otrzyma identyczne wyniki podczas testowania autentyczności wiadomości, dystrybuowane klucze publiczne muszą być takie same. W klasycznym przypadku jest to proste, ponieważ można łatwo porównać dwa klasyczne łańcuchy bitów i sprawdzić, czy pasują do siebie. Niemniej jednak w stanie kwantowym jest to bardziej skomplikowane. Aby sprawdzić, czy dwa publiczne stany kwantowe są takie same, należy porównać następujące elementy

{\ Displaystyle | f_ {k} '\ rangle = | f_ {k} \ rangle}

Zamień test dla kubitów

Odbywa się to za pomocą następującego obwodu kwantowego, który wykorzystuje jedną bramkę Fredkina F , jedną bramkę Hadamarda H i kubit ancilla a . Przede wszystkim kubit ancilla jest ustawiony w stan symetryczny ${\ Displaystyle | a \ rangle = {\ Frac {1} {\ sqrt {2}}} (| 0 \ rangle + | 1 \ rangle)}$ .

Zaraz po tym, jak qubit ancilla jest używany jako kontrola celów ${\ Displaystyle | f_ {k} \ rangle \}$ i ${\ Displaystyle \ | f_ {k} '\ rangle}$ w Fredkin Gate.

Ponadto na kubicie ancilla stosowana jest bramka Hadamarda i ostatecznie mierzony jest pierwszy kubit. Jeśli oba stany są takie same, wynik ${\ displaystyle | 0 \ rangle}$ jest mierzona. Jeśli oba stany są prawie ortogonalne, wynikiem może być ${\ Displaystyle | 0 \ rangle \}$ lub ${\ Displaystyle \ | 1 \ rangle}$ .

Bardziej szczegółowe obliczenia testu zamiany:

Ogólny stan

{\ 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} '\ zakres +|1\rangle |f_{k}\rangle |f_{k}'\rangle {\bigg )}}

Po zastosowaniu bramki Fredkina

${\ Displaystyle \ Strzałka w prawo {\ Frac {1} {\ sqrt {2}}} {\ bigg (}|0\rangle |f_{k}\rangle |f_{k}'\rangle +|1\rangle \mathbf {|f_{k}'\rangle |f_{k}\rangle } {\bigg ) }}$

Po zastosowaniu bramki Hadamarda na pierwszym kubicie

${\ 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 ]}}$

Po sortowaniu dla ${\ Displaystyle | 0 \ rangle {\ tekst {i}} | 1 \ rangle}$

${\ Displaystyle \ Strzałka w prawo |\ 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 ]}}$

Teraz łatwo zobaczyć, czy stany ${\ Displaystyle | f_ {k} \ rangle = | f_ {k} '\ rangle \}$ wtedy ${\ Displaystyle \ |\ psi \ rangle = | 0 \ rangle | f_ {k} \ rangle | f_ {k} \ rangle}$ , co daje nam 0 za każdym razem, gdy jest mierzone.

Przykład procesu sprawdzania poprawności podpisu przy użyciu uproszczonego schematu Gottesmana-Chuanga

Proces podpisywania

Przykład procesu podpisywania dla bitu wiadomości b = 0 przy użyciu schematu Gottesmana-Chuanga

Niech Osoba A (Alicja) chce wysłać wiadomość do Osoby B (Bob). Algorytmy mieszające nie będą brane pod uwagę, więc Alicja musi podpisać każdy bit swojej wiadomości. Message-Bit b ${\ Displaystyle \ in \ {0,1 \}}$ .

Alicja wybiera M par kluczy prywatnych ${\ Displaystyle \ {k_ {0} ^ {i}, k_ {1} ^ {i} \} \ quad 1 \ równoważnik ja \równik M}$

Wszystkie $.$ zostaną użyte do podpisania bitu wiadomości, jeśli b = 0
Wszystkie $podpisania$ bitu wiadomości, jeśli b = 1

Funkcja odwzorowująca ${\ Displaystyle k \ mapsto | f_ {k} \ rangle}$ jest znany wszystkim stronom. Alicja oblicza teraz odpowiednie klucze publiczne ${\ Displaystyle \ {| f_ {k_ {0}} ^ {i} \ rangle, | f_ {k_ {1}} ^ {i} \ rangle \}} i daje je$ wszystkie odbiorcy. Może zrobić tyle kopii, ile potrzebuje, ale musi uważać, aby nie narazić na szwank bezpieczeństwa ${\ Displaystyle \ lewo (n \ gg Tm {\ tekst {musi trzymać}} \ prawo)}$ .

Jej poziom bezpieczeństwa ogranicza liczbę identycznych kluczy publicznych, które może utworzyć

Jeśli

bit wiadomości b = 0 , wysyła wszystkie swoje klucze prywatne wraz z bitem wiadomości b do Boba ${\ displaystyle k_ {0}}$
bit wiadomości b = 1 , wysyła wszystkie swoje klucze prywatne wraz z bitem wiadomości b do Boba ${\ displaystyle k_ {1}}$

Pamiętaj: W tym przykładzie Alicja wybiera tylko jeden bit b i podpisuje go. Musi to zrobić dla każdego bitu w swojej wiadomości

Proces walidacji

Przykład walidacji z wykorzystaniem schematu Gottesmana-Chuanga. Brany jest pod uwagę tylko jeden próg

Bob teraz posiada

Bit wiadomości b
Odpowiednie klucze prywatne ${\ displaystyle k_ {0} {\ tekst {lub}} k_ {1}}$
Wszystkie klucze publiczne ${\ Displaystyle \ {| f_ {k_ {0}} \ ranga, | f_ {k_ {1}} \ ranga \}}$

Teraz Bob oblicza ${\ Displaystyle | f_ {k_ {b}} \ rangle}$ dla wszystkich otrzymanych kluczy prywatnych ( ${\ Displaystyle k_ {0} {\ tekst {lub}} k_ {1}}$ ).

Po wykonaniu tej czynności wykorzystuje test zamiany do porównania obliczonych stanów z otrzymanymi kluczami publicznymi. Ponieważ test zamiany ma pewne prawdopodobieństwo podania błędnej odpowiedzi, musi to zrobić dla wszystkich M i liczy, ile otrzyma błędnych kluczy r . Jest oczywiste, że M jest pewnym parametrem bezpieczeństwa. Jest mniej prawdopodobne, aby sprawdzić trochę źle dla większego M .

Jeśli otrzyma tylko kilka niepoprawnych kluczy, bit najprawdopodobniej jest ważny, ponieważ jego obliczone klucze i klucze publiczne wydają się być takie same.
Jeśli dostanie wiele błędnych kluczy, to z dużym prawdopodobieństwem ktoś sfałszował wiadomość.

Unikaj sprawdzania poprawności wiadomości w inny sposób

Jednym z problemów, który pojawia się szczególnie w przypadku małych M , jest to, że liczba błędnych kluczy mierzonych przez różnych odbiorców różni się z prawdopodobieństwem. Zatem zdefiniowanie tylko jednego progu nie wystarczy, ponieważ spowodowałoby to inną walidację wiadomości, gdy liczba błędnych kluczy r jest bardzo bliska zdefiniowanemu progowi.

Można temu zapobiec, definiując więcej niż jeden próg. Ponieważ liczba błędów rośnie proporcjonalnie do M, progi są zdefiniowane jak

Akceptacja

{\ Displaystyle T_ {a} = c_ {1} M}

Odrzucenie

{\ Displaystyle T_ {r} = c_ {2} M}

Jeśli liczba niepoprawnych kluczy r jest mniejsza niż $\ displaystyle T_ {a}}$ bit jest ważny z dużym prawdopodobieństwem T za
Jeśli liczba niepoprawnych kluczy r jest większa niż , bit jest sfałszowany z dużym prawdopodobieństwem ${\ displaystyle T_ {r}}$
Jeśli liczba błędnych kluczy r mieści się pomiędzy obydwoma progami, to odbiorca nie może być pewien, czy inny odbiorca otrzyma ten sam wynik podczas sprawdzania poprawności bitu. Co więcej, nie może być nawet pewien, czy dobrze zweryfikował wiadomość.

$zero$ założymy doskonałe kanały bez szumów, więc bit nie może zostać zmieniony z powodu przeniesienia, wówczas próg , ponieważ test zamiany przechodzi zawsze, gdy porównywany stany są takie same

Uwierzytelnianie wiadomości

Kody uwierzytelniania wiadomości (MAC) mają na celu głównie uwierzytelnianie pochodzenia danych, ale mogą również zapewniać niezaprzeczalność w pewnych realistycznych scenariuszach, gdy zaangażowana jest zaufana strona trzecia. Zasadniczo ten sam pomysł można wykorzystać w ramach kwantowych MAC. Jednak szeroka klasa kwantowych MAC nie wydaje się oferować żadnej przewagi nad ich klasycznymi odpowiednikami.

Zobacz też

Podpis Lamporta — praktyczna metoda podpisu cyfrowego wynaleziona w latach 70. XX wieku i uważana za bezpieczną nawet przed atakami komputerów kwantowych.
Kryptografia kwantowa
Kwantowe odciski palców