Off-line electronic cash system based on the representation problem

Tento dokument je castecne zpracovan z anglickeho originalniho textu, ktery v postscriptovem formatu muzete nalezt zde --- digicash.ps Dokument neni stylisticky ani formatove prilis upraven.

1. Abstract

Jedna se o system elektronickych penez. Novy off-line system je zalozen na reprezenativnim problemu, ktery vyuziva diskretni logaritmus.
Uzitim tohoto reprezenativniho problemu je mozne pomoci nekterych postupu vytvorit protokoly pro vyber penez ci platbu, ktere nepouzivaji prechozi cut/choose metodologie predchozich systemu. Dusledkem toho je, ze tento system je efektivnejsi nez obe (pocitacove i komunikacni) slozitosti predchozich systemu.

Dalsi silnou strankou systemu je jeho dokazatelnost. Narozdil od predchozich systemu je jeho spravnost matematicky dokazatelna. Specialne pokud udelam pravdepodobny predpoklad obsahujici jednoduchou hasovaci funkci, system je temer neprorazitelny.

System nabizi rozsireni, ktere bylo v predchozich systemech ztezi dosazitelne. Zajimava vec je, ze cely tento cash-system vcetne ruznych rozsireni muze byt instalovan primo v taskach zakaznika. Vyhovuje to pozadavkum vlastniho soukromi uzivatele, coz se v predchozich systemech zdalo nemozne.

Dalsi prednosti systemu je to, ze pokusy do banky maji zanedbatelnou sanci na uspech.

Zde pouzivame reprezentacni problem s pouzitim group prvociselneho radu. --- podobne jako v RSA groupach. Povime si o tom, jak pouzit tyto problemy v pouzitelnem cash-systemu s odpovidajici bezpecnosti odpovidajici bezpecnosti RSA --- podobnou cestou, akorat uzitim diskretniho logaritmu.

Nakonec probereme rozhodovaci problem --- variantu Diffie-Hellmananoveho prolemu

2. Uvod

Za posledni leta bylo usili kryptografickych vyzkumu venovane designu off-line elektronickeho cash-systemu, ktere nemuze garantovat pouze bezpecnost pro banku a obchody, ale i soukromi pro uzivatele. Tento system je prvni, ktery je zalozeny na problemu (reprezentacnim) co do obtiznosti ekvivalentni vypoctu diskretniho logaritmu. Schopnost faktoru neovlivnuje bezpecnost tohoto systemu.

Hlavnim cilem bylo vytvorit cash-system, ktery je pouzitelnejsi nez dosavadni systemy s nedokonalymi resenimi, s vysokym stupnem dokazatelnosti a rozsiritelnosti, a ktery muze byt instalovan do wallets. Techto cilu bylo dosazeno elektronickou hotovosti ci seky s vazbou na bezpodminecnou bezpecnost. S timto zavazkem pouzivame reprezentacni problem s grupou prvociselneho radu.

Podobne problemy jsou v RSA-grupach a temer vsechny nastroje a protokoly, ktere vyvijime pro grupy s prime-order {prvocisly} mohou byt primo prizpusobeny pro RSA-grupy.

3. Off-line elektronicke systemy

Obecne si lide mysli, ze elektronicke cash-systemy nemohou soucasne nabizet soukromi pro uzivateli stejne jako bezpecnost pro banku ci obchody. Mnoho dnes instalovanych systemu je uplne bez anonymity uzivatele a navic on-line treba v obchodech, aby byly schopni zjistit spolehlivost platce. S prichodem verejnych klicu do kryptografie byly rozvinuty zpusoby, ktere ukazaly, ze tato duvera je neopravnena. Tyto zpusoby dovoluji vybudovat off-line cash-systemy, ktere jsou bezpecne, pro banku, a pro cestne uzivatele je navic zarucena naprosta anonymita. Tedy bezpecnost banky nejde na ukor uzivatele a obchodu. Fakt, ze systemy jsou offline, usetri spoustu nakladu, drahoty a nepruznosti on-line cache-systemu.

Kryptograficky model off-line elektronicke platby

V tomto modelu jsou 3 vylucujici se typy ucastniku. Mnozina uzivatelu --- U1, ..., UK, mnozina obchodu --- S1, ..., Sl, a banka B. k a l musi byt polynomialni v delce tajnych parametru systemu. Potom to odpovida pravdepodobnostnim algoritmum s polynomialni vypoctovou slozitosti. V prakticke implementaci takoveho systemu jsou uzivatele reprezentovani uzivatelskym modulem, coz muze byt chytra karta, nebo osobni pocitac ci pracovni stanice.

Uzivatelsky modul, jinak zvany "wallet", protoze prinasi penize, ackoli v digitalni podobe. Nicmene B a vsechny S jsou v praxi reprezentovany vykonnejsimi vypocetnimi zarizenimi.

Kdyz uzivatel U ve vyzvedavaci fazi kontaktuje banku B, aby obdrzel informace, ze si muze vybrat jistou castku (zvanou coin), pozdeji se odecte odpovidajici suma penez z uctu uzivatele U. Kdyz U chce pozdeji platiti v obchode S, prokazuje S-ovi informace, ktere dokazuji opravnenost zaplatit danou castku. Jelikoz je system off-line, posila S informace B-cku po nejakych intervalech, B potvrzuje, ze informace je platna a prevadi penize S-ku.

Pozadavek na soukromi pro uzivatele je to, ze platba provedena uzivatelem by nemela byt "linkable", tzn., ze pozdejsi pravdepodobnost shody je neskonale vetsi nez predchozi pravdepodobnost, k vyberu, i kdyz banka spolupracuje se vsemi obchody.(untracebility). Untracebility zarucuje, ze uzivatel zustane anonymni, protoze jeho identita je spojena s vyberem. Je nezbytne a vhodne, aby informace, ktere U poskytuje S pomoci protokolu byly statisticky nezavisle na informacich od banky, ktere obdrzi pomoci withdrawal protocol. Jelikoz informace o vyberu nejakym zpusobem musi byt digitalne oznacena tajnym klicem B, ve fazi vyberu musi byt pouzit vhodny podepisovaci protocol. Obykle banky nastavuji tajne parametry a uzivatele je nemohou ovlivnit. Casto jsou kladeny silnejsi pozadavky nez untraceability --- unlinkability, tzn., ze je nemozne pro banku spojiovat nejmene 2 platby provedene 1 uzivatelem. Schopnost spojit 2 platby patri take k naruseni soukromi uzivatele. tzn. Je-li uzivatel identifikovan pri jedne platbe (protoze jej majitel obchodu zna), vsechny platby v retezci jsou rozpoznany, ze byly ucineny jim. Bezpecnost banky se sklada z toho, ze uzivatele nemohou falsovat penize a musi byt stejny zpusob chranit uzivatele od utraceni tychz penez vice nez jednou (double-spending). Double-spending nelze v off-line systemech ciste kryptograficky osetrit. Vypada to, ze je potreba se nezbytne odebrat k odolnym walltes, coz je patrne v konfliktu s pozadavky soukromi. Nicmene lze to vyresit pouzitim kryptograficke techniky, ktera povoluje chytit double-spendera po cinu. Spociva to v kodovani identity platce nejakym zpusobem v informacich, ktere obdrzi pri fazi vybirani. Uzivatel musi pri vybirani nejake castecne informace takove, ze kdyz double-spending je detekovan pri depositni fazi, identita uzivatele muze byt vypoctena ze dvou ruznych casti informace. Nicmene v souladu s pozadavky soukromi, pokud uzivatele jsou cestni, jejich soukromi muze byt nepodminene chraneno. --- Identita nemuze byt zjistena z jedenoho kusu informace. Tento model off-line plateb neni ale vhodne pro vysoke platby, nebot double-spender muze opustit zemi. Velke platby byvaji typicky delany on-line. Nevyhodou tohoto systemu ale je, ze dany uzivatel muze malou castku double-spendovat nekolikrat.

Elektronicky cash-system pouzivajici wallets s pozorovanimi.

Posledni dobou s novymi druhy transakcnich nastaveni, bylo navrhovano, kdy pouzivat k off-line systemu prostredky, ktere mohou zabranit double-spendingu spise nez to detekovat az po cinu. To prinasi prospech zahrnujici soukromi i bezpecnost.

Intuitivne je jasne, ze toto nastaveni nemuze byt zalozeno pouze na uzivatelem kontrolavne wallets. Nove nastaveni pouziva wallets, ktere maji zabudovane pozorovace. Pozorovac je male zarizeni odolone proti poruseni, ktere reprezentuje organizace v systemu (banka v off-line cash model.) Tedy wallets se zabudovanym uzivatelskym modulem budeme nazyvat observer.

Idea pozorovace (observeru) je, ze nemuze byt zaclenen ve walletu tak, ze zadny uzivatelsky modul nemuze delat transakce sam od sebe. Potrebuje pomoc --- nejakou tajnou informaci od pozorovace. V praxi pak pozorovac opravnuje transakci. Pro double-spending problem to muze byt jednoduse znamenat, ze pozorovac vezme cast v platebnim protokolu, a muze registrovat informaci, ktery je pouzita v platbe. Pokud uzivatel chce utratit tutez informaci, pozorovac mu tu transakci neumozni. K double-spendingu by pak bylo potreba prorazit odolnost pozorovace, uzivatel by musel zjistit tajnou informaci z pozorovace a mit user-modul simulujici dil prace pozorovace v platebnim protokolu. Secure off-line cash system proto musi byt takovy, ze dokonce i v tomto pripade pri stejne bezpecnosti jako je v uzivatelskem modulu je garantovano. Zaverem asi je, ze takto navrzeny system se blizi idealnimu elektronickemu cash-systemu.

Zda se to byt slepa ulicka --- jak muze byt zajistena bezpecnost uzivatele, kdyz by si nosil s sebou chraneny modul pred vniknutim, ktery nese cast ve vsech protokolech, a musi informovat napr. obchodnika, zda-li je dana akce legitimni? Vypada to, ze pozorovac muze byt vzdy naprogramovan tak, ze muze poustet informaci, vztahujici se k identite doprovazejiciho uzivatelskeho modulu a nasledne k osoby, ktere wallet patri. Pokud by uzivatele takovy pokus rozpoznali, nebyl by moc problem si stezovat a system by se mohl zastavit. Nicmene nezadouci informace, ktera vychazi z pozorovace napr. k obchodnikovi, ktera neni specifikovana protokolem muze velmi ublizit soukromi uzivatele. Prikladem muze byt nahodna vyzva, kterou obchod vysle walletu. Pokud ji pozorovac rozpozna, obchod muze dekodovat nebezpecnou informaci (kdyz bude pouzivat kodovani rozpoznatelne pozorovacem.) bez uzivatelova vedomi.

Nicmene to neni tak hrozne. Pozorova musi byt zabudovan dovnitr do user-modulu takovym zpusobem, ktery bude umoznovat user-modulu overovat zpravy vyslane ven, aa tedy umoznovat user-modulu potvrzovat tyto zpravy. Tedy user-modul muze rozpoznat pokusy pozorovace uvolnit nezadouci informace a naopak. Nicmene by to nebylo mozne moderovat na takove rozsireni, aby to mohlo autorizovat transakce sami o sobe. Uzitim specialnich kryptografickych protokolu, vsechny pozadavky obsahujici bezpecnost mohou byt zajisteny stejne jako soukromi.

Nekdo muze premyslet --- i kdyby kazdy pozorovac shromazdoval informace, ktere prijima v case, kdy je vlozen do user-modulu, je nemozne proniknout od user-modulu a pozorovace a po te se podivat na informaci uvnitr pozorovace a vsechny informace shromazdene od organizaci (To muze byt nazyvano traceability po cinu, nebot napr. banka muze udelat to, ze vsechny platby ucinene walletem mohou byt trasovany). Tato moznost neni vyloucena prevenci prichozich a odchozich dat, nebot napriklad jednoduche nahodne cislo zname pozorovaci i obchodu muze umoznit linkovani; fakt, ze user-modul vezme cast generovani tohoto (takze zadna informace nemuze byt jim kodovana, coz umoznuje chranit oboje --- vstupni i vystupni toky) je nepodstatna. Takovre vzajemne zname informace, ktere umoznuji linkovani, se nazyvaji sdilene informace. Jedna z nutnych veci techniky potrebna k ochrane pred sdilenou informaci je rozptyleni (divertability) protokolu.

Prevence pred sdilenou informaci nemusi byt v praxi vzdy dulezity problem, nebot narozdil od vstupu a vystupu, sdilena informace nemuze ovlivnit soukromi uzivatele v dobe, kdy je s uzivatelem. Pouze, kdyz pozorovace musi byt systematicky podany providerovi z nejakeho duvodu, muze byt pomoci sdilene informace vyextrahovana platebni historie vlastnika. Toto je ale v elektronickych cash-systemech celkem realne predpokladat, takze je v nasem zajmu mit elektronicky cash-system uzivajicim wallets s pozorovaci, ktere zajistuji nesdilene informace.

Takze k predchozimu --- zda se, ze kryptograficke techniky umoznuji vytvorit off-line electronic cash-system, ktery muze zaroven garantovat soukromi i bezpecnost. Pokud si vystaci s detekovanim double-spendingu po cinu, muze byt realizovan uzitim walletu, ktery je uplne pod kontrolou uzivatele (treba bez pozorovace). Pokud ma byt double-spending osetren, pak to muze byt realizovano zpusobem, ze uzivatel ma wallets se zabudovanym pozorovacem.

Je to jeden z prvnich systemu, o kterem je v literature dokazana korektnost (dosavadnim systemum byly davany intuitivni informace). Zbyva tedy z praktickeho hlediska vytvorit system, ktery je vskutku vykonny a ucinny a o kterem lze matematicky dokazat, ze vsechny pozadavky ma. Diky rychlemu rozvoji HW, mohou byt systemy vykonne z hlediska komplexne-teoretickeho, implementovany v soucasnych HW, napr. kartach, zpusobem, ktery zarucuje, ze pozadavky na rychlost a shromazdovani zadosti.

Nekdo by mohl namitnout, ze snad toto je snad nejzajimavejsi problem k reseni. Nicmene problem P vs. NP bude nejspise nevyresen jeste dlouho. Takze je nejlepsi to redukovat nejake zname ne snadno resitelne problemy (jako je faktorizace a extrakce diskretniho logaritmu) na bezpecnost systemu. Nicmene soucasny stav kryptografickych dokazovacich technik je ten, ze neni znama matematicka kostra (ramec, system) obdrzet takovou redukci pro komplexne kryptograficke systemy (napr. systemy skladajici se z vice nez jednoho protokolu, jako jsou off-line cash-systemy).

Dalsi vlastnosti

Dalsi vlastnosti, kterou lze k idealnim off-line cash systemum pridat, je prenosnost a oddelitelnost a elektronicke seky. Transferability --- obchody i uzivatele mohou delat platce i prijemce, a mohou platit penezmi, ktere prijali od ostatnich ucastniku systemu bez zasahu banky. Divisibility --- elektronicke penize mohou byt spojeny nejakym zpusobem --- spoctenim celkove sumy z jednotlivych kousku. Elektronicke seky mohou byt utraceny do jiste omezene castky, o ktery se da snizit platba. Dela se to pomoci vyzvy a odpovedi.

Pri pouzivani pouhych uzivatelem kontrolovananych modulu, vsechny tyto tri dalsi vlastnosti maji sve stinne stranky. Nicmene v mnoha situacich transferabilita neni potrebovana vubec a dokonce muze byt spise neobhrabana, protoze prenesene penize rostou v rozmeru. Podobne je to s divisibility, tak ale muze byt ucinne dosazena bez linkability. Nekdo vskutku muze pouzivat seky v systemu, coz je patrne jediny pridavek, ktery ma velkou sanci na realizaci bez nevyhod. Naproti tomu ve wallets s pozorovaci mohou byt tyto pridavky bez mnoha nevyhod implementovany, protoze pozorovac muze osetrit jiste problemy, ktere jsou tezko resitelne s pouhym uzivatelskym modulem. V podstate jsou dva zpusoby, jak dosahnout techto properties. Prvni je dodat korektni system do jednoho z pozorovacu (pro system bez pozorovacu). Pokud se nazajima o sdilenou informaci, muze to byt udelane primo. Ale pokud se musi sdilena informace osetrit, stava se to velmi obtiznou veci. Jiny zpusob je pouzit jednotnou moznost wallets s pozorovaci ze 3 casti. Napr. ackoli muzeme sekovy system implantovat pres nastaveni pozorovace, mohou byt seky dosazeny vykonnejsim zpusobem, tim, ze se pozorovac stara o castku, ktery muze byt uzivateli proplacena.

3. Vlastnosti tohoto cash-systemu

Provedeme diskusi tohoto off-line elektronickeho systemu v nekolika kategoriich.

Vykonnost --- system je daleko vykonnejsi nez predchozi navrzena reseni. (Jak vybiraci, tak platici faze). System je daleko vykonnejsi ve slozitosti komunikace i ve vypocetni slozitosti. Zvlaste vybiraci a platici protokoly se skladaji s pouhych tri pohybu a kontroly zustatku vyzadujici jednu akci (pohyb). Pouzitim standardniho zpusobu davani vyzev v obchodech je jedina funkce jiste informace; muzeme zhustit platebni protokol do jedineho pohybu. Vsechna predchozi navrzena reseni pouzivaji binarni protokoly (vyzva-odpoved) ve vyberove fazi --- (k potvrzeni uzivatelske identity je prijimana informace podepisovana) a v platici fazi (k potvrzeni, ze bude odchycen v pripade double-spender), takze potrebuji polynomialne mnoho odpovedi (obvykle probihajicich paralelne) k dosazeni vytouzeneho stupne bezpecnosti. V tomto kontrolnim doplnku se vybiraci protokol sklada ze 4 pohybu --- platba a proplaceni 3 pohybu jeden zalozni. Na platbu a proplaceni --- podobe oznaceni jako vyse. Muze byt pridan vektor retezove techniky, dokonce overovaci vztahy jsou daleko daleko vykonnejsi k spocitani nez u predchozich systemu.

Dokazatelnost --- muzeme dokazat spravnost tohoto cash-systemu na velmi vysokem stupni, ktery je patrne velkym problemem predchozich systemu. Bezpecnost tohoto systemu se zda byti ekvivalentni nejakym znamym tezkym problemum, jako je Diffi-Hellmanova podminka.

Rozsiritelnost --- Tento system muze byt rozsiren mnoha zpusoby velmi snadno, aniz by to snizilo jeho vykonnost. Napriklad uzivatelum lze povolit utratit coins k-krat (k-podpis) misto jednou zpusobem, ze k+1 utrat odhaluje identitu uzivatele, zatimco na k utrat jej bezpodminecne skryje. Prestoze vsech techto k plateb je linkable, cely retez k plateb je bezpodminecne nelinkable pro urciteho uzivatele. Tato vec zpusobi pouze linearni zvyseni delky prenasene informace a vypocetni slozitost.

Dalsi rozsireni systemu muze byt pouziti seku (checks --- kontrol?). Lze vytvorit check-system, ktery je vykonnejsi nez u zakladniho systemu s coiny. Mohou byt pouzity seky s ruznou maximalni hodnotou.

Podobne muze byt dosazeno divisibility. Temer vsechny popsane systemy toto neumoznuji. I toto muze byt navrzeno tak, aby bylo mosno sek utratit vicekrat bez zjeveni identity.

Muze byt pridana prenositelnost. Ovsem silnou strankou tohoto systemu je to, ze muze byt primo zabudovan do wallets s pozorovaci, zvysuje se i bezpecnost ohledne double-spendingu. Uzivatele by mimo silnou kryptografickou podminku museli zlomit i neotviratelne zarizeni. Bezpecnost je tedy velmi silna. Diky reprezenativnimu problemu muze byt vetsina protokolu snadno prevedena. U predchozich systemu slo velmi zabudovat do walletu tyto pozadavky.

Funkcionalita --- system nabizi extra funkcionalitu. Napriklad sestaveni pokusu do banky --- chraneno mechanismem: uzivatele jsou schopni prokazat, ze jsou lzive obzalovani, napr. v pripade double-spendingu. V predchozich systemech, identifikujici informace o uzivatelich byla uplne znama bance. V tomto systemu uzivatele identifikujici informace se sklada z tajne casti, ktera nemuze byt bankou spocitana, bez ohledu na vypoceti silu.

Analogie v ostatnich grupach --- temer vsechny predchozi systemy pouzivali triky, ktere se velmi tezko prizpusobovaly ostatnim grupam. Naproti tomu tento system pouziva mnoho nastroju, ktere se mohou snadno prizpusobit k drzeni se v RSA-grupach (napr. v multiplikativnich grupach modulo dve prvocisla) stejne dobre jako v reprezentacnim problemu. Jediny vec, o ktere se nevi, jak ji prizpusobit RSA-grupam je slepy podpisove schema, ktere je potreba u vyberoveho protokolu.

Vedle techto velmi milych dobrych vlastnosti je v tomto systemu take nekolik veci, ktere by se mohly zdokonalit. To muze napriklad vykonnejsi slepe podpisove schema z pohledu storage space, nebot v tomto systemu se jeden podpis banky sklada ze 4 cisel. Toto schema pricinou, ze vypocetni usili k zlomeni systemu neni vetsi nez k zlomeni Diffie-Hellmanova problemu. Bylo by prijemnejsi secutirity ekvivalence problemu diskretniho logaritmu.

Strucna diskuse techniky, ktera se k tomuto pouziva

U dosavadnich systemu bylo tezke o nich cokoli matematicky dokazat. Zde nemame za cil rigorozni dukaz, ale nejaky ramec, ale castecny dukaz bezpecnosti, ktery vede k rigoroznimu dukazu. Jeden z hlavnich problemu, s nimz se sektame pri dokazovani bezpecnosti tohoto systemu, je, ze se zda tezke dokazat, ze skladba minimalne-znalostniho protokolu je minimum-znalostni.

Momentalne nejlepsi, co muze clovek udelat, je dokazat korektnost tak hluboce, jak je to jen mozne. Existuji nejake explicitni podminky. Nejobvyklejsi je napr. pouzit nekolik nespecifikonavych funkci v protokolech, jejichz interakci temer nelze analyzovat. Typicky se takove funkce objevuji, nebot manipuluji v ruznych grupach skrze systemove pozadavky mapujici prvky z jedne grupy do druhe.

Je rozhodujici zacit s pruznym zakladem problemu, z nehoz je system vyvijen. Takze obvykle je nemit nespecifikovane funkce. Proto v elektronickem cash-systemu pouzivame jeden zakladni problem --- reprezentacni problem, ktery umoznuje flexibilni manipulaci.

Detekovat double-spending zakodovanim identity v elektronicke cashi je pravdepodobne jediny nejtezsi problem k reseni v ochrane soukromi off-line cash-systemu nespolehajicich na odolnost proti poruseni, a co se jak uctuje pro vice nevykonnych a nespecifikovanych funkci. V tomto systemu, zda je identita uzivatele ve vybiraci informaci (coins, checks) zavisi zcela na znalosti tohoto. Proto, jak mnoho je jista vybiraci informace hodnotna, jehoz identita je v ni a zda muze byt utracena zavisi zcela na znalosti uzivatele, o nemz je dana informace.

Cesta ke kodovani identity ve spojitosti s reprezentacnim problemem nam dovoluje virtualne vsechny manipulace v tomto systemu ve dvou isomorfnich grupach (G,Z) bez potreby predstavovat nespecifikovane funkce krome hasovaci funkce. Dulezitejsi: umoznuje aplikovat nektere techniky tohoto systemu uzitecne k dokazani korektnosti a vykonnosti velkych rozmeru. Prvni je aplikovana na vybiraci protokol a povoluje odstranit cut/choose metodu bezne pouzivanou pro kodovani informace uzivatele, obsahujici jeho identitu. Spise nez davat vlastni identitu slepemu cislu a presvedcovat banku, ze to udelal otevrenim vseho, ale trochy (vybrane bankou), pouziva se to, co se nazyva omezujici slepe podpisove schema, kde je uzivatel omezen druhem slepou manipulaci toho, co dela, muze zarizovat statistickou nezavislost potrebnou k untraceability a jeste jistou strukturu (kde je jeho identita) ve znalostech, ktere ma o slepe informaci, ktera bude vzdy stejna jako neslepa informace, nedbaje na specifickou slepou manipulaci vybranou uzivatelem. V dusledku toho uzivatel potrebuje pouze slepe jednoduche cislo (misto polynomialne mnoha), ktere otevrou totez. Druha technika je take aplikovana na slepe podpisove schema: Efektivne oddelime ruzne spusteni vybiraciho protokolu, kde kazda signatura se sklada ze dvou novych nahodnych cisel, genereovanych bankou, a nespocitatelnych uzivatelem. Treti technika je aplikovana na platebni protokol a pouziva dobre znamou ideu, ze sklon primky v rovine je jednoznacne urcen dvema ruznmymi body v primce, dokonce jednim, pokud je znam jeden bod. To umoznuje vytvorit velmi rychly platebni protokol, protoze nepotrebuje polynomialne mnoho vyzev a odpovedi.

K dukazu bezpecnosti tohoto systemu se pouzije nekolik dukazovych postupu. Nejdulezitejsi, ktery pouzijeme na vice mistech, prameni z faktu, ze vytvoreni jsou takova, ze banky nepotrebuji znat dalsi tajne informace nez ostatni ucastnici systemu, krome tajneho klice pouzivajiciho ke slepemu podpisu. To nam umoznuje nahlednout do celeho systemu jako na jeden celek, nebot vsechny ucastnici protokolu mohou byt algoritmicky polynomialne narocne (i kdyz banka nepotrebuje byt), muze byt simulovan pravdepodobnostnim polynomialnim alegoritmem. Takto muzeme dokazat, ze mnoho myslitelnych utoku na system je neproveditelnych, protoze by to znamenalo, ze utocnik muze urcit nejaky relativni diskretni logaritmus s nejakou pravdepodobnosti. To by znamenalo, ze musi existovat uskutecnitelny algoritmus, ktery spocte diskretni logaritmus s nezanedbatelnou pravdepodobnosti, zvlaste simulujici system (nahodne volby a akce ucastniku).

Oznaceni a zakladni predpoklady

Vsechny aritmeticke operace provadim v grupe Gq prvociselneho radu q, takze Gq je Abelova grupa, pro niz polynomialne-casove algoritmy jsou znamy k urceni rovnosti prvku, test nalezeni, spocitani inversu, nasobeni a nahodne vybrani prvku. Vysledky jsou platne v nejake grupe. Budeme uzivat podgrupu Gq, sice Zp s p=kq+1 prvocislo pro nejake k z N. V prakticke implementaci systemu bude delka p pravdepodobne nejmene 512 bitu a q-cka nejmene 140 bitu. Bezpecnost tohoto systemu je spojena s Diskretnim logaritmem a Diffie-Hellmanovou podminkou, oboje v ramci Gq.

Diskretni Log problem nazvu nalezt jedinecny index log h o zakladu g nalezi Zq a h nalezi Gq, g take v Gq bez {1}. Rekneme, ze algoritmus resi problem DisLog, jestlize pro vstup g nerovno 1, h generovane stejne nahodne, dava na vystup log a zakladu g z h s nejmene nezanedbatelnou pravdepodobnost uspechu. Podminka dislog vyjadruje, ze neexsituje polynomalne casove slozity algoritmus, ktery resi problem Dislog s nezanedbatelnou pravdepodobnosti uspechu.

Pokud existuje algoritmus, ktery resi Dislog problem, pak existuje algoritmus resici Dislog problem s nezanedbatelnou pravdepodobnosti uspechu.

Nasledujici tvrzeni jsou ekvivalenstni:
(a) Existuje polynomialni algoritmus A s indexem (a), pro nahodne zvoleny vstup g nerovno 1 a h dava na vystup log h o zakladu g.
(b) Existuje g nerovno 1 a polynomialne casove slozity algoritmus A (b), ktery pro nahodne vybrany vstup h dava vystup log g h.

Nalezeni jedineho Diffie-Hellmanova klice g na ab of g1,g2 je DH problem. Rekneme, ze algoritmus resi DF problem se zakladem g, pro vstup g1, g2 generovany stejne nahodne, dava na vystup DF klic z g1, g2 s ohledem na g nejmene s nezanedbatelnou pravdepodobnosti uspechu. DF podminka vyjadruje, ze pro vsechna g nerovna 1, neni znam takovy polynomialni algoritmus.

Reprezentacni problem

Definice 5 --- viz papir str. 15,pozorovani 6

(Pozorovani 7) Definujeme V jako mnozinu funkci nastavenim vsech fci ve forme q(.)/r(.) takovou, ze q(.) a r(.) jsou polynomialni v oboru celych cisel a celosiselnych koeficientu, a q(k)>r(k)>=1 pro vsechna dostatecne velka K. Pro nejake funkce f1(.),f2(.),f3(.),f4(.) z V, nasledujici 4 tvrzeni jsou ekvivalentni:
(1) Existuje polynomialne casove slozity algoritmus A s ind. (1), ktery na vstupy generatoru k-tic a h nalezi Gq, dava na vystup representujici indexovou t-ici h-cka s pravdepodobnosti uspechu nejmene 1/f1(|p|) pro vsechna dostatecne velka p.
(2) Existuje polymomialne casovy algoritmus A s ind. (2), ktery se vstupem generarem k-tic dava na vystup netrivialni representujici index-tici jednicky s pravdepodobnosti uspechu nejmene 1/f2(|P|) pro vsechna dostatecne velka p.
(3) Existuje nejake h z Gq\{1} a polynomialne casovy algoritmus A s ind. (3), ktery se vstupem generarotu k-tice dava na vystup representuci tici h-cka s pravdepodobnosti uspechu nejmene 1/f3(|p|) pro vsechna dostatecne velka p.
(4) Existuje polynomialne casovy algoritmus A s ind. (4), ktery resi DisLog problem s pravdepodobnosti uspechu nejmene 1/f4(|p|) pro vsechna dostatecne velka p.

Instance: grupa G, prvky g1,...,gk z G (s k polynomialni v mohutnosti G, h z G)
Otazka: Existuje representace h s ohledem na (g1,...,gk) a pokud ano, nalezni jednu.
V tomto cash-systemu pouze pouzivame pouze omezenou formu tohoto problemu, representacni problem pro grupy prvociselneho radu.
Lze dokazat, ze representacni problem pro grupy prvociselneho radu je ekvivalentni co do vypocetni slozitosti Dislog problemu.
Dale, viz dusledek 8.

Vykonnost vypoctu representativniho problemu. Vysledek algoritmu se zda byt vhodny v pocitacich zarizenich male kapacity, jako jsou karty ci off-line elektronicke systemy.

Dukaz znalosti representace Abychom dovolili casove polynomialnimu dokazateli P dokazat znalost representace (a1,...,ak) cisla h s ohledem na (g1,...,gK) overoviteli V, muzeme primo uzit zobecneni identifikacniho protokolu. 1. P generuje k cisel w1,...,wK ze Zq a posila --- viz papir.

Veta 9
1. Uplnost --- Pokud P je cestny --- zna representaci a drzi se protokolu, potom V akceptuje.
2. Bezchybnost. --- Pokud P rezna reprezentanta h s ohledem na (g1,...,gk), pak neexistuje strategie, pro niz by mu V potvrdil s vyznamnejsi pravdepodobnosti uspechu.
3. Hledani svedka --- Dokonce se vsemi shromazdenymi predchozimi vykonavanimi protokolu a neomezene vkypocetni sily, V nemze nalezt nejakou informaci o spravne reprezentaci, kterou P zna, pokud P dodrzuje protokol techto cinnosti.

Zakladni nastroje pro vybiraci protokol

V tomto systemu, identita uzivatele je zakodovana cela v representaci, kterou uzivatele zna s ohledem na generator tice. Proto, muzeme pouzit techniky povolujici se nam zbavit metodologie cut/choose v drivejsich systemech, coz vyrazne zvysuje vykonnost. Uzivatel je bance znam pod synonymem m=g1 na u1 krat g2 na u2, ... gk na uk, ktera je spojena s jeho uctem a identitou. Podpisove schema banky, jejiz verejny klic je (g,h(=g na x)), je takove, ze uzivatel muze delat vlastni blinding pseudonymu, ... 9. kapitola. Uzivatel skonci s novym cislem, ktere je pro banku nezname, psolecne s platnym podpisem banky.

Ukazeme drobny priklad. Uzivatelbude zacne pri vybirani oresne jednou representaci (a1,...,aK) cisla m s ohledem na generator (g1,...,gk). V nasem systemu, toho dosahneme tim, ze uzivatel si vybere sve ai s carkou krat s a spocte m. Podle 8 nemuze skoncit znalosti vice nez jedne representace. str. 23,...

Inspirovani touto myslenkou, muzeme kodovat identitu uzivatele, napr. ai, aj. Pri platbe uzivatel pote uvolni radek ai + aj * c v Zq, c vyzvou c obchodu. Otevre nejakou castecnou informaci o sve reprezentaci a pak presvedci obchod (s podpisem), ktery je cestny. Pokud uzivatel double-spenduje, s nezanedbatelnou pravdepodobnosti se spocte ai, aj, a tudiz i identita uzivatele.

Omezene slepe podpisove schema

Zamer slepych podpisovych protokolu je pro prijemce obrzet podpis sign(m) ve zprave m nerovno 1 tak, ze nejenom (m,sign(m)) zustava pro podpisovatele nezname, ale dokonce s neomezenou vypocetni silou nebude mozne nalety nejaky par (m,sign(m)) specificky ke spusteni protokolu. Pouzivame slepe podpisove schema (prizpusobeni z 3-pohyboveho identifikacniho ) schematu.

Aby tomu bylo rozumet, provedeme urcite zjednoduseni. Necht g... str. 24
1. Podepisovac vygeneruje nahodne cislo w ze Zq a posle z=m na x, a=g na w, b=m na w prijemci.
2. Prijemce vygeneruje nahodne 4 cisla: s, t, a u, v vse ze Zq. pouzitim prvni dvojice cisel spocte m s carkou = m na s * g na t. s ostatnimi dvema spocte --- viz str. 24 dole
3. Podepisovatel odpovi s r=w+cx mod q.

Zakladni nastroje pro platebni protokol

Abychom zabranili double-spendingu coin, musi uzivatel obchodu zjevit nejake informace o svem majetku, jako kus informace, ktera nezjevuje jeho identitu, zatimco dva kusy informace umozni zjistit identitu v polynomialnim case. Uzivame jednoducheho faktu, ze sklon primky je jednoznacne urcen dvem body, a neurcen jednim! str. 30

Randomizace reprezentaci

V tomto nastavenem cash-systemu, uzivatel [P, polynomialne omezen]. musi zarizovat ucet s bankou. To se sklada z cisla h=g1 na a1 * g2 na a a2, takze (a1,a2) jsou bezpodminecne skryte v mnozine vsech reprezetantu h s ohledem na (g1,g2). V nekterych situacich, banka (V neohranicena) muze chtit kazdy prvek representace nechat poznat P aby byly vzajemne nahodne. Obecne, V muze chtit zjednat spolupraci s P a cislem h a representaci h s ohledem na generator ktici (g1,...,gk) takovou, ze kazdy prvek representace je vzajemne nahodny.
Je uzit nasledujici protokol:
1. P generuje stejne nahodne indexovou k-tici (x1,...,x_k+1) a posila V-cku h s carkou = soucin pres i od 1 do k+1 gi na xi.
2. V posila nahodne vybranou indexovou k-tici (y1,...,yk) P-cku.
3. P posila x_k+1 V-cku. Pokud P je v kroku 3 cestny, (x1+y1 mod q,... xk+yk mod q) je reprezentantem h-cka = (soucin pres i=1 az k cisel gi na yi)*h'/(g_k+1)^(x_k+1) s ohledem na (g1,...,gk), coz zarucuje vyse uvedene pozadavky.
Snadne ukazat, ze jedina moznost, jak P muze znat representaci h-cka je, pokud nasleduje protokol.

Zakladni cash-system

--- str. 37

Pouze coins. Budeme uzivat identitu uzivatele ve forme ... a banka zna ...takze je s bankou uzivatele obeznamen. Pokud se nekdo spokoji se systemem, ve kterem je obeznameni pouze vypoctove chranene, muzeme mu dat dokonce uspokojive schema, dame-li mu identitu jednoduse u, banka zny g na u.

Nastaveni systemu Banka vygeneruje nahodne nasledujicich pet prvku:
1. generator tice (g,h). To je public key banky, ktery pouzivra k vytvoreni signatury ve vyberovem protokolu. Index x=..., obvykle drzen v tajemstvi.
2. generator sloupce g1,g2, ktery je pouzivan skrz system.
3. Tzv. falesny generator d nerovnajicici se g1 a g2, ktery je k zajisteni, ze identita cestneho uzivatele bude vypoctena ze spusteni platebniho protokolu {nezavisle na vypocetni sile}.
Mame jenom coins. v systemu. Bezpecnost tohoto schematu zavisi na tom, ze nikdo neni schopen vyjadrit g,h,g1,g2,d jako kombinaci ostatnich prvku. Toto je tezke nejmene tak jako problem nalezeni reprezentanta 1 s ohledem na generator tice (g,h,g1,g2,d), je zauceno podle pozorovani 7, ze je to nedostupne {podminka DisLog}. Dokonce banka nepotrebuje znat diskretni logaritmus krome x.
Kdyz uzivatel U otevre ucet v nace, vygeneruje nahodne {mozno ve spolupraci s bankou B} cisla u1,u2 --- viz Randomizace reprezentantu,ze Zq a spocte I... Banka nezna u1,u2, ulozi si I s uzivatelovou skutecnou identitou a cislem uctu. V pripade, ze uzivatel double-spenduje tutez cash, banka je schopna zjistit u1,u2. Spoctenim I... muze urcit jeho ucet a tedy identitu. Vyberovy protokol Uzivatel chce vybirat penize z uctu {jakoby rekl I}, nejprve presvedsi banku B, ze penize vskutku jsou vybirany z jeho vlastniho uctu. U dokazuje B-cku znalost reprezentace (napr. pouzitim schematu v sekci 8). Porozujeme, ze uzivatel to muze ukazat ciste, i kdyz to nebude nejchytrejsi, protoze bnka muze potom ho ramcovat nebo muze dat naslouchaci, ktery muze nespravne mezi ne se prezentovat. Pokud B akceptuje dukaz U pro kazdou hotovost, kterou U chce vybrat, je spusten vybiraci protokol (viz obr. 5 --- str. 39):
1. B odecte pozadovanou sumu penez z uctu a zformuje cislo m=Id (U si muze) spocist toto cislo sam a nepotrebuje Bm tedy neni potreba pro Banku posilat to U. B posle m na x, g na w a m na w uzivateli, s w nahodne vzbranym ze Zq.
2. a dale viz text str.38 viz poznamky. Platba Pokud uzivatel chce utratit penize v obchode S, je spusten nasledujici protokol --- viz obrazek 6 + test dale viz str. 40 Zustatek Po nejake jednotce casu, vsechny obchody shromazdi informace a platbach bance --- viz Obr. 7, ktery ihned zjisti dvakrat-utracene penize, nebot A,B,sign(A,B) bylo pouzito. Y odpovedi na vyzvy muze vypocitat ... a pak identifikovat informaci o uzivatelich, kteri dvakrat utratili. u1... Pak spocte I... a nalezne zaznam o uctu k identifikaci double-spendera. Pro pozdejsi porovnani zpusobu, kterym banka identifikuje double-spendery s wallety s pozorovaci, zde odvozujeme presne formule, ktere banky potrebuji k zjisteni u1,u2. viz papir.... Pokracuje to featurami. Dale korektnost cash-systemu, ..., checks, divisibility, ..., pozorovace, prevedeni protokolu,...

Korektnost tohoto zakladniho systemu

viz text

Off-line cache-systemy ve wallets s pozorovaci

Tento system je rpvni s moznosti prevence proti sdilene informaci. Diky pruzne strukture repr. problemu, ktery dovoluje prevadet. Muze byt ochraneno pred double-spendingem. Radi bychom meli system podobajicimu se nasemu zakladnimu systemu, ktery by byl nejlepe takovy, ze jestlize je pozorovac prolomen pred tim, nez byl ucet vlastnika banky otevren, zachovame korektnost zakladniho cash-systemu.

K dosazeni prevence pred double-spendingem, informace, ze uzivatel vybira, musi byt rozdelena mezi user-modul a pozorovac tak, ze uzivatel nemuze utratit dvakrat sam od sebe. V zakladnim systemu, k zajisteni tohoto nezmame reprezencai m s carkou, uz pozorovac a uzivatel vsak dohromady ano.

Nektere otevrene problemy

Existuji vhodne omezovaci slepa podpisova schemata v RSA-groupach? Pak bychom byly schopni vybudovat cash-system v RSA-groupach podobne, jako zde bylo popsano. Existuji vykonne slepe podpisove schema v Gq? Mohou byt rozsireni dosazena v nastaveni wallets s pozorovaci efektivneji zp;sobem, pod pozaadavkem nesdilene informace? V nasich rozsirenich --- multishow cash a divisibility, je plna linkability. Muze byt jedno z rozsireni dosazeno bez linkability?