Kvantový digitální podpis

A Kvantový digitální podpis (QDS) odkazuje na kvantově mechanický ekvivalent buď klasického digitální podpis nebo obecněji vlastnoruční podpis na papírovém dokumentu. Stejně jako vlastnoruční podpis se digitální podpis používá k ochraně dokumentu, například digitální smlouvy, proti padělání jinou stranou nebo jednou ze zúčastněných stran.

S tím, jak se elektronický obchod ve společnosti stává stále důležitějším, vyvstala potřeba potvrdit původ vyměňovaných informací. Moderní digitální podpisy zvyšují bezpečnost na základě obtížnosti řešení matematického problému, jako je hledání faktorů velkého počtu (jak se používá v Algoritmus RSA ). Úkol vyřešit tyto problémy se bohužel stane proveditelným, až bude k dispozici kvantový počítač (viz Shorův algoritmus ). Abychom čelili tomuto novému problému, vyvíjejí se nová schémata kvantového digitálního podpisu, která poskytují ochranu proti neoprávněné manipulaci, a to i před stranami, které vlastní kvantové počítače a používají silné strategie kvantového podvádění.

Klasická metoda veřejného klíče

The metoda veřejného klíče kryptografie umožňuje odesílateli podepsat zprávu (často pouze kryptografický hash zprávy) znakovým klíčem takovým způsobem, aby kterýkoli příjemce mohl pomocí odpovídajícího veřejného klíče ověřit pravost zprávy. Aby to bylo možné, je veřejný klíč zpřístupněn všem potenciálním příjemcům. Aby se zajistilo, že zprávu může platně podepsat pouze legální autor zprávy, vytvoří se veřejný klíč z náhodného klíče soukromého podpisu pomocí jednosměrná funkce. Jedná se o funkci, která je navržena tak, že výpočet výsledku daného vstupu je velmi snadný, ale výpočet vstupu daného výsledku je velmi obtížný. Klasickým příkladem je znásobení dvou velmi velkých prvočísel: Násobení je snadné, ale faktorování produktu bez znalosti prvočísel je obvykle považováno za neproveditelné.

{ displaystyle x mapsto f (x)}

snadný

{ displaystyle f (x) mapsto x}

velmi obtížné

Stejně jako klasické digitální podpisy i kvantové digitální podpisy využívají asymetrické klíče. Osoba, která chce podepsat zprávu, tedy vytvoří jeden nebo více párů znamení a odpovídajících veřejných klíčů. Obecně můžeme kvantová schémata digitálního podpisu rozdělit do dvou skupin:

Schéma, které ze soukromého vytvoří veřejný kvantový bitový klíč klasický bitový řetězec: ${ displaystyle k mapsto | f_ {k} rangle}$
Schéma, které vytváří soukromý kvantový bitový klíč kvantová bitový řetězec: ${ displaystyle | k rangle mapsto | f_ {k} rangle}$

V obou případech je f jednosměrná kvantová funkce, která má stejné vlastnosti jako klasická jednosměrná funkce. Výsledek je tedy snadno vypočítatelný, ale na rozdíl od klasického schématu je funkce nemožné invertovat, i když člověk používá silné strategie kvantového podvádění.

Nejslavnější schéma pro první výše uvedenou metodu poskytují Gottesman a Chuang ^[1]

Požadavky na dobré a použitelné schéma podpisu

Většina požadavků na klasické schéma digitálního podpisu platí také pro schéma kvantového digitálního podpisu.

Podrobně

Schéma musí poskytovat zabezpečení proti neoprávněné manipulaci
1. Odesílatel po podepsání zprávy (viz trochu závazku )
2. Příjemce
3. Třetí strana
Vytvoření podepsané zprávy musí být snadné
Každý příjemce musí dostat stejnou odpověď při testování platnosti zprávy (platná, neplatná)

^[1]^[2]

Rozdíly mezi klasickými a kvantovými jednosměrnými funkcemi

Povaha jednosměrné funkce

Klasická jednosměrná funkce, jak je uvedeno výše, je založena na klasickém neproveditelném matematickém úkolu, zatímco kvantová jednosměrná funkce využívá princip neurčitosti, který znemožňuje výpočet inverze dokonce i kvantovému počítači. To se provádí poskytnutím kvantové výstupní stav, s nímž se člověk nemůže dostatečně naučit o vstupním řetězci, aby jej mohl reprodukovat. V případě první skupiny schémat to ukazuje Holevova věta, která říká, že z daného kvantového stavu n-qubit nelze extrahovat více než n klasické informace.^[3]Jednou z možností, jak zajistit, aby schéma používalo méně qubitů pro bitový řetězec určité délky, je použití téměř ortogonálních stavů

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

To nám dává možnost vyvolat základnu s více než dvěma státy.^[1]Takže popsat informace o ${ displaystyle 2 ^ {n}}$ bitů, můžeme použít méně než n qubitů. Příklad na bázi 3 qubitů

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

K popisu n klasických bitů je zapotřebí pouze m qubitů ${ displaystyle 3 ^ {m} = 2 ^ {n}}$ drží.

Kvůli Holevově teorému a skutečnosti, že m může být mnohem menší než n, můžeme ze zprávy n-bitů získat pouze m bitů. Obecněji řečeno, pokud někdo získá T kopie veřejného klíče, může extrahovat nejvíce Tm bitů soukromého klíče ${ displaystyle delta}$ je velký ${ displaystyle n-Tm}$ stane se velmi velkým, což znemožňuje nepoctivé osobě uhodnout klíč podepsat.

Poznámka: Nelze rozlišovat mezi neortogonálními stavy, pokud máte jen malé množství stejných stavů. Takto fungují kvantové jednosměrné funkce.
Nicméně ${ displaystyle | f_ {k} rangle}$ uniká informace o soukromém klíči, na rozdíl od klasického veřejného klíče, který nutí člověka, aby o soukromém klíči nedostal nic nebo vše.

Kopírování veřejného klíče

V klasickém případě vytvoříme klasický veřejný klíč z klasického znakového klíče, takže je snadné poskytnout každému potenciálnímu příjemci kopii veřejného klíče. Veřejný klíč lze volně distribuovat. To se v kvantovém případě stává obtížnějším, protože kopírování kvantového stavu je zakázáno teorémem bez klonování, pokud není znám samotný stát.^[4]Veřejné klíče tedy může vytvářet a distribuovat pouze osoba, která zná přesný kvantový stav, který chce vytvořit, tedy kdo zná znakový klíč (může to být odesílatel nebo obecněji důvěryhodná instituce). Nicméně na rozdíl od klasický veřejný klíč existuje horní hranice počtu veřejných kvantových klíčů T které lze vytvořit, aniž by bylo možné uhodnout klíč znaménka, a tím ohrozit bezpečnost schématu ( ${ displaystyle n-Tm}$ musí být velký)

Veřejný klíč by měl být stejný pro každého příjemce (Swap Test)

Aby se zajistilo, že každý příjemce získá stejné výsledky při testování autenticity zprávy, musí být distribuované veřejné klíče stejné. To je v klasickém případě jednoduché, protože lze snadno porovnat dva klasické bitové řetězce a zjistit, zda se shodují. , v kvantovém stavu je to složitější. Chcete-li otestovat, zda jsou dva veřejné kvantové stavy stejné, musíte porovnat následující

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

Vyměňte test za qubits

To se provádí pomocí následujícího kvantového obvodu, který používá jeden Fredkinova brána F, jeden Hadamardova brána H a ancilla qubit ANejprve je anbitový qubit nastaven na symetrický stav ${ displaystyle | a rangle = { frac {1} { sqrt {2}}} (| 0 rangle + | 1 rangle)}$ .

Hned po ancilla qubit se používá jako kontrola na cílech ${ displaystyle | f_ {k} rangle }$ a ${ displaystyle | f_ {k} ' rangle}$ ve Fredkinově bráně.

Dále se na anbitový qubit použije Hadamardova brána a nakonec se změří první qubit. Jsou-li oba státy stejné, výsledek ${ displaystyle | 0 rangle}$ Pokud jsou oba stavy téměř kolmé, výsledkem může být buď ${ displaystyle | 0 rangle }$ nebo ${ displaystyle | 1 rangle}$ .^[1]

Výpočet swapového testu podrobněji:

Celkový stav

{ 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)}}

Po Fredkin brána je použita

${ 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)}}$

Po Hadamard brána je aplikována na první qubit

${ 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 třídění pro ${ 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]}}$

Nyní je snadné zjistit, zda státy ${ displaystyle | f_ {k} rangle = | f_ {k} ' rangle }$ pak ${ displaystyle | psi rangle = | 0 rangle | f_ {k} rangle | f_ {k} rangle}$ , což nám dává 0, kdykoli je měřeno.

Příklad procesu podepisování a ověřování pomocí zjednodušeného Gottesman-Chuangova schématu

Proces podepisování

Příklad procesu podepisování pro bit zprávy b = 0 pomocí schématu Gottesman-Chuang

Nechte osobu A (Alice), aby chtěla poslat zprávu osobě B (Bob). Algoritmy hash nebudou brány v úvahu, takže Alice musí podepsat každý bit své zprávy. Bit zprávy b ${ displaystyle in {0,1 }}$ .

Alice si vybere M páry soukromých klíčů ${ displaystyle {k_ {0} ^ {i}, k_ {1} ^ {i} } quad 1 leq i leq M}$

Všechny ${ displaystyle k_ {0}}$ klíče se použijí k podpisu bitů zpráv, pokud b = 0.
Všechny ${ displaystyle k_ {1}}$ klíče se použijí k podpisu bitů zpráv, pokud b = 1.

Funkce, která mapuje ${ displaystyle k mapsto | f_ {k} rangle}$ je známa všem stranám. Alice nyní počítá odpovídající veřejné klíče ${ displaystyle {| f_ {k_ {0}} ^ {i} rangle, | f_ {k_ {1}} ^ {i} rangle }}$ a dává je všem příjemcům. Může pořídit tolik kopií, kolik potřebuje, ale musí dbát na to, aby neohrozila bezpečnost ${ displaystyle left (n gg Tm { text {musí držet}} vpravo)}$ .

Její úroveň zabezpečení omezuje počet identických veřejných klíčů, které může vytvořit

Li

bit zprávy b = 0, pošle všechny své soukromé klíče ${ displaystyle k_ {0}}$ spolu s bitem zprávy b Bobovi
bit zprávy b = 1, pošle všechny své soukromé klíče ${ displaystyle k_ {1}}$ spolu s bitem zprávy b Bobovi

Pamatujte: V tomto příkladu Alice vybere pouze jeden bit b a podepíše to. Musí to udělat pro každý kousek ve své zprávě

Proces ověřování

Příklad ověření pomocí schématu Gottesman-Chuang. Zvažuje se pouze jedna prahová hodnota

Bob nyní vlastní

Bit zprávy b
Odpovídající soukromé klíče ${ displaystyle k_ {0} { text {or}} k_ {1}}$
Všechny veřejné klíče ${ displaystyle {| f_ {k_ {0}} rangle, | f_ {k_ {1}} rangle }}$

Nyní Bob počítá ${ displaystyle | f_ {k_ {b}} rangle}$ pro všechny přijaté soukromé klíče (buď ${ displaystyle k_ {0} { text {or}} k_ {1}}$ ).

Poté, co tak učiní, použije swapový test k porovnání vypočtených stavů s přijatými veřejnými klíči. Protože má swapový test určitou pravděpodobnost, že dá špatnou odpověď, musí to udělat pro všechny M klíče a spočítá, kolik nesprávných klíčů dostane r. Je zřejmé, že M je nějaký druh bezpečnostního parametru. Je více nepravděpodobné, že by se ověřovalo trochu špatně pro větší M.

Pokud dostane jen pár nesprávných klíčů, pak je bit pravděpodobně platný, protože jeho vypočítané klíče a veřejné klíče se zdají být stejné.
Pokud dostane mnoho nesprávných klíčů, pak někdo zprávu sfalšoval s vysokou pravděpodobností.

Vyhněte se tomu, aby byla zpráva ověřována jinak

Jeden problém, který vzniká zejména u malých M je, že počet nesprávných klíčů, které různí příjemci měří, se liší s pravděpodobností. Nestačí tedy definovat pouze jednu prahovou hodnotu, protože by to způsobilo, že by byla zpráva ověřena odlišně, když počet nesprávných klíčů r je velmi blízko definované hranici.

Tomu lze zabránit definováním více než jedné prahové hodnoty. Protože počet chyb roste úměrně s M, prahové hodnoty jsou definovány jako

Přijetí

{ displaystyle T_ {a} = c_ {1} M}

Odmítnutí

{ displaystyle T_ {r} = c_ {2} M}

Pokud je počet nesprávných klíčů r je níže ${ displaystyle T_ {a}}$ , pak je bit platný s vysokou pravděpodobností
Pokud je počet nesprávných klíčů r je výše ${ displaystyle T_ {r}}$ , pak je bit s velkou pravděpodobností fingovaný
Pokud je počet nesprávných klíčů r je mezi oběma prahovými hodnotami, pak si příjemce nemůže být při ověřování bitu jistý, pokud jiný příjemce získá stejný výsledek. Kromě toho si nemůže být ani jistý, zda zprávu potvrdil správně.

^[1]

Pokud předpokládáme perfektní kanály bez šumu, takže bit nelze změnit kvůli přenosu, pak prahová hodnota ${ displaystyle T_ {a}}$ lze nastavit na nulu, protože swapový test prochází vždy, když jsou porovnávané stavy stejné

Ověřování zpráv

Kódy ověřování zpráv (MAC) se zaměřují hlavně na ověřování původu dat, ale v určitých realistických scénářích mohou také poskytnout nepopiratelnost, pokud je zapojena důvěryhodná třetí strana. V zásadě lze stejnou myšlenku využít v rámci kvantových MAC. Zdá se však, že široká třída kvantových MAC adres nenabízí oproti svým klasickým protějškům žádnou výhodu. ^[5]

Viz také

Lamportův podpis - Praktická metoda digitálního podpisu vynalezená v 70. letech 20. století a považovaná za bezpečnou i proti útokům kvantových počítačů.
Kvantová kryptografie
Kvantové otisky prstů

Reference

^ ^A ^b ^C ^d ^E Daniel Gottesman, Isaac L. Chuang. Kvantové digitální podpisy, arXiv: quant-ph / 0105032 v2 (, 15. listopadu 2001)
^ Xin Lü, Deng-Guo Feng. Kvantový digitální podpis založený na kvantových jednosměrných funkcích, arxiv: quant-ph / 04030462 v2 (, 24. června 2004)
^ Michael A. Nielsen, Isaac L. Chuang. Kvantové výpočty a kvantové informace 1. vyd., Cambridge University Press, str. 531-536
^ Michael A. Nielsen, Isaac L. Chuang. Kvantové výpočty a kvantové informace 1. vyd., Cambridge University Press, 532
^ Nikolopoulos, Georgios M .; Fischlin, Marc (2020). „Informace - teoreticky zabezpečené ověřování původu dat pomocí kvantových a klasických zdrojů“. Kryptografie. 4 (4): 31. doi:10,3390 / kryptografie4040031.

[Chuang-1] A ^b ^C ^d ^E Daniel Gottesman, Isaac L. Chuang. Kvantové digitální podpisy, arXiv: quant-ph / 0105032 v2 (, 15. listopadu 2001)

[Feng-2] Xin Lü, Deng-Guo Feng. Kvantový digitální podpis založený na kvantových jednosměrných funkcích, arxiv: quant-ph / 04030462 v2 (, 24. června 2004)

[Holevo-3] Michael A. Nielsen, Isaac L. Chuang. Kvantové výpočty a kvantové informace 1. vyd., Cambridge University Press, str. 531-536

[Cloning-4] Michael A. Nielsen, Isaac L. Chuang. Kvantové výpočty a kvantové informace 1. vyd., Cambridge University Press, 532

[5] Nikolopoulos, Georgios M .; Fischlin, Marc (2020). „Informace - teoreticky zabezpečené ověřování původu dat pomocí kvantových a klasických zdrojů“. Kryptografie. 4 (4): 31. doi:10,3390 / kryptografie4040031.

[1]

[2]

[3]

[4]

[5]