Off-line electronic cash system based on the representation problem

Tento dokument je částečně zpracován z anglického originálního textu, který v postscriptovém formátu mužete nalézt zde --- digicash.ps Dokument není stylisticky ani formátově příliš upraven.

1. Abstract

Jedná se o systém elektronických peněz. Nový off-line system je založen na reprezenativním problému, který využívá diskrétní logaritmus.
Užitím tohoto reprezenativního problému je možné pomocí některých postupů vytvořit protokoly pro výběr peněz či platbu, které nepoužívají přechozí cut/choose metodologie předchozích systémů. Důsledkem toho je, že tento systém je efektivnější než obě (počítačové i komunikační) složitosti předchozích systémů.

Další silnou stránkou systému je jeho dokazatelnost. Narozdíl od předchozích systémů je jeho správnost matematicky dokazatelná. Speciálně pokud udělám pravděpodobný předpoklad obsahující jednoduchou hašovací funkci, systém je téměř neprorazitelný.

Systém nabízí rozšíření, které bylo v předchozích systémech ztěží dosažitelné. Zajimavá věc je, že celý tento cash-system včetně různých rozšíření může být instalován přímo v taškách zákazníka. Vyhovuje to požadavkům vlastního soukromí uživatele, což se v předchozích systémech zdálo nemožné.

Další předností systému je to, že pokusy do banky mají zanedbatelnou šanci na úspěch.

Zde používáme reprezentační problém s použitím group prvočíselného řádu. --- podobně jako v RSA groupách. Povíme si o tom, jak použít tyto problémy v použitelném cash-systému s odpovídající bezpečností odpovídající bezpečnosti RSA --- podobnou cestou, akorát užitím diskrétního logaritmu.

Nakonec probereme rozhodovací problém --- variantu Diffie-Hellmananového prolému

2. Úvod

Za poslední léta bylo úsilí kryptografických výzkumů věnováné designu off-line elektronického cash-systému, které nemůže garantovat pouze bezpečnost pro banku a obchody, ale i soukromí pro uživatele. Tento systém je první, který je založený na problému (reprezentačním) co do obtížnosti ekvivalentní výpočtu diskrétniho logaritmu. Schopnost faktoru neovlivňuje bezpečnost tohoto systému.

Hlavním cílem bylo vytvořit cash-systém, který je použitelnější než dosavadní systémy s nedokonalými řešeními, s vysokým stupněm dokazatelnosti a rozšiřitelnosti, a který může být instalován do wallets. Těchto cílů bylo dosaženo elektronickou hotovostí či šeky s vazbou na bezpodmínečnou bezpečnost. S tímto závazkem používáme reprezentační problém s grupou prvočíselného řádu.

Podobné problémy jsou v RSA-grupách a téměř všechny nástroje a protokoly, které vyvíjíme pro grupy s prime-order {prvočísly} mohou být přímo přizpůsobeny pro RSA-grupy.

3. Off-line elektronické systémy

Obecně si lidé myslí, že elektronické cash-systémy nemohou současně nabízet soukromí pro uživateli stejně jako bezpečnost pro banku či obchody. Mnoho dnes instalovaných systémů je úplně bez anonymity uživatele a navíc on-line třeba v obchodech, aby byly schopni zjistit spolehlivost plátce. S příchodem veřejných klíčů 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.

Kryptografický model off-line elektronické platby

V tomto modelu jsou 3 vylučující se typy účastníků. Množina uživatelů --- U1, ..., UK, množina obchodů --- S1, ..., Sl, a banka B. k a l musí být polynomiální v délce tajných parametrů systému. Potom to odpovídá pravděpodobnostním algoritmům s polynomiální výpočtovou složitostí. V praktické implementaci takového systému jsou uživatelé reprezentování uživatelským modulem, což může být chytrá karta, nebo osobní počítač či pracovní stanice.

Uživatelský modul, jinak zvaný "wallet", protože přináší peníze, ačkoli v digitální podobě. Nicméně B a všechny S jsou v praxi reprezentovány výkonnějšími výpočetními zařízeními.

Když uživatel U ve vyzvedávací fázi kontaktuje banku B, aby obdržel informace, že si může vybrat jistou částku (zvanou coin), později se odečte odpovídající suma peněz z účtu uživatele U. Když U chce později platiti v obchodě S, prokazuje S-ovi informace, které dokazují oprávněnost zaplatit danou částku. Jelikož je systém off-line, posílá S informace B-cku po nějakých intervalech, B potvrzuje, že informace je platná a převádí peníze S-ku.

Požadavek na soukromí pro uživatele je to, že platba provedená uživatelem by neměla být "linkable", tzn., že pozdější pravděpodobnost shody je neskonale větší než předchozí pravděpodobnost, k výběru, i když banka spolupracuje se všemi obchody.(untracebility). Untracebility zaručuje, že uživatel zůstane anonymní, protože jeho identita je spojena s výběrem. Je nezbytné a vhodné, aby informace, které U poskytuje S pomocí protokolu byly statisticky nezávislé na informacích od banky, které obdrží pomocí withdrawal protocol. Jelikož informace o výberu nějakým způsobem musí být digitálně označena tajným klíčem B, ve fázi výběru musí být použit vhodný podepisovací protocol. Obykle banky nastavují tajné parametry a uživatelé je nemohou ovlivnit. Často jsou kladeny silnější požadavky než untraceability --- unlinkability, tzn., že je nemožné pro banku spojiovat nejméně 2 platby provedené 1 uživatelem. Schopnost spojit 2 platby patří také k narušení soukromí uživatele. tzn. Je-li uživatel identifikován při jedné platbě (protože jej majitel obchodu zná), všechny platby v řetězci jsou rozpoznány, že byly učiněny jím. Bezpečnost banky se skládá z toho, že uživatelé nemohou falšovat peníze a musí být stejný způsob chránit uživatele od utrácení týchž peněz více než jednou (double-spending). Double-spending nelze v off-line systémech čistě kryptograficky ošetřit. Vypadá to, že je potřeba se nezbytně odebrat k odolným walltes, což je patrně v konfliktu s požadavky soukromí. Nicméně lze to vyřešit použitím kryptografické techniky, která povoluje chytit double-spendera po činu. Spočívá to v kódování identity plátce nějakým způsobem v informacích, které obdrží při fázi vybírání. Uživatel musí při vybírání nějaké částečné informace takové, že když double-spending je detekován při depositní fázi, identita uživatele může být vypočtena ze dvou různých částí informace. Nicméně v souladu s požadavky soukromí, pokud uživatelé jsou čestní, jejich soukromí může být nepodmíněně chráněno. --- Identita nemůže být zjištěna z jedenoho kusu informace. Tento model off-line plateb není ale vhodné pro vysoké platby, neboť double-spender může opustit zemi. Velké platby bývají typicky dělány on-line. Nevýhodou tohoto systému ale je, že daný uživatel může malou částku double-spendovat několikrát.

Elektronický cash-systém používající wallets s pozorováními.

Poslední dobou s novými druhy transakčních nastavení, bylo navrhováno, kdy používat k off-line systému prostředky, které mohou zabránit double-spendingu spíše než to detekovat až po činu. To přináší prospěch zahrnující soukromí i bezpečnost.

Intuitivně je jasné, že toto nastavení nemůže být založeno pouze na uživatelem kontrolavné wallets. Nové nastavení používá wallets, které mají zabudované pozorovače. Pozorovač je malé zařízení odoloné proti porušení, které reprezentuje organizace v systému (banka v off-line cash model.) Tedy wallets se zabudovaným uživatelským modulem budeme nazývat observer.

Idea pozorovače (observeru) je, že nemůže být začleněn ve walletu tak, že žadný uživatelský modul nemůže dělat transakce sám od sebe. Potřebuje pomoc --- nějakou tajnou informaci od pozorovače. V praxi pak pozorovač opravňuje transakci. Pro double-spending problém to může být jednoduše znamenat, že pozorovač vezme část v platebním protokolu, a může registrovat informaci, který je použita v platbě. Pokud uživatel chce utratit tutéž informaci, pozorovač mu tu transakci neumožní. K double-spendingu by pak bylo potřeba prorazit odolnost pozorovače, uživatel by musel zjistit tajnou informaci z pozorovače a mít user-modul simulující díl práce pozorovače v platebním protokolu. Secure off-line cash system proto musí být takový, že dokonce i v tomto případě při stejné bezpečnosti jako je v uživatelském modulu je garantováno. Závěrem asi je, že takto navržený systém se blíží ideálnímu elektronickému cash-systému.

Zdá se to být slepá ulička --- jak může být zajištěna bezpečnost uživatele, když by si nosil s sebou chráněný modul před vniknutím, který nese část ve všech protokolech, a musí informovat např. obchodníka, zda-li je daná akce legitimní? Vypadá to, že pozorovač může být vždy naprogramován tak, že může pouštět informaci, vztahující se k identitě doprovázejícího uživatelského modulu a následně k osoby, které wallet patří. Pokud by uživatelé takový pokus rozpoznali, nebyl by moc problém si stěžovat a systém by se mohl zastavit. Nicméně nežádoucí informace, která vychází z pozorovače např. k obchodníkovi, která není specifikována protokolem může velmi ublížit soukromí uživatele. Příkladem může být náhodná výzva, kterou obchod vyšle walletu. Pokud ji pozorovač rozpozná, obchod může dekódovat nebezpečnou informaci (když bude používat kódování rozpoznatelné pozorovačem.) bez uživatelova vědomí.

Nicméně to není tak hrozné. Pozorova musí být zabudován dovnitř do user-modulu takovým způsobem, který bude umožňovat user-modulu ověřovat zprávy vyslané ven, aa tedy umožňovat user-modulu potvrzovat tyto zprávy. Tedy user-modul může rozpoznat pokusy pozorovače uvolnit nežádoucí informace a naopak. Nicméně by to nebylo možné moderovat na takové rozšíření, aby to mohlo autorizovat transakce sami o sobě. Užitím speciálních kryptografických protokolu, všechny požadavky obsahující bezpečnost mohou být zajištěny stejně jako soukromí.

Někdo může přemýšlet --- i kdyby každý pozorovač shromažďoval informace, které přijímá v čase, kdy je vložen do user-modulu, je nemožné proniknout od user-modulu a pozorovače a po té se podívat na informaci uvnitř pozorovače a všechny informace shromážděné od organizací (To může být nazýváno traceability po činu, nebot např. banka muže udělat to, že všechny platby učiněné walletem mohou být trasovány). Tato možnost není vyloučena prevencí příchozích a odchozích dat, neboť například jednoduché náhodné číslo známé pozorovači i obchodu může umožnit linkování; fakt, že user-modul vezme část generování tohoto (takže žádná informace nemůže být jím kódována, což umožňuje chránit oboje --- vstupní i výstupní toky) je nepodstatna. Takovré vzájemně známé informace, které umožňují linkování, se nazývají sdílené informace. Jedna z nutných věcí techniky potřebná k ochraně před sdílenou informací je rozptýlení (divertability) protokolu.

Prevence před sdílenou informací nemusí být v praxi vždy důležitý problém, neboť narozdíl od vstupů a výstupů, sdílená informace nemůže ovlivnit soukromí uživatele v době, kdy je s uživatelem. Pouze, když pozorovače musí být systematicky podány providerovi z nějakého důvodu, může být pomocí sdílené informace vyextrahována platební historie vlastníka. Toto je ale v elektronických cash-systémech celkem reálně předpokládat, takže je v našem zájmu mít elektronický cash-systém užívajícím wallets s pozorovači, které zajišťují nesdílené informace.

Takže k předchozímu --- zdá se, že kryptografické techniky umožňují vytvořit off-line electronic cash-system, který může zároveň garantovat soukromí i bezpečnost. Pokud si vystačí s detekováním double-spendingu po činu, může být realizován užitím walletu, který je úplně pod kontrolou uživatele (třeba bez pozorovače). Pokud má být double-spending ošetřen, pak to může být realizováno způsobem, že uživatel má wallets se zabudovaným pozorovačem.

Je to jeden z prvních systémů, o kterém je v literatuře dokázána korektnost (dosavadním systémům byly dávány intuitivní informace). Zbývá tedy z praktického hlediska vytvořit systém, který je vskutku výkonný a účinný a o kterém lze matematicky dokázat, že všechny požadavky má. Díky rychlému rozvoji HW, mohou být systémy výkonné z hlediska komplexně-teoretického, implementovány v současných HW, např. kartách, způsobem, který zaručuje, že požadavky na rychlost a shromažďování žádostí.

Někdo by mohl namítnout, že snad toto je snad nejzajímavější problém k řešení. Nicméně problém P vs. NP bude nejspíše nevyřešen ještě dlouho. Takže je nejlepší to redukovat nějaké známé ne snadno řešitelné problémy (jako je faktorizace a extrakce diskrétního logaritmu) na bezpečnost systému. Nicméně současný stav kryptografických dokazovacích technik je ten, že není známa matematická kostra (rámec, systém) obdržet takovou redukci pro komplexně kryptografické systémy (např. systémy skládající se z více než jednoho protokolu, jako jsou off-line cash-systémy).

Další vlastnosti

Další vlastností, kterou lze k ideálním off-line cash systémům přidat, je přenosnost a oddělitelnost a elektronické šeky. Transferability --- obchody i uživatelé mohou dělat plátce i příjemce, a mohou platit penězmi, které přijali od ostatních účastníků systému bez zásahu banky. Divisibility --- elektronické peníze mohou být spojeny nějakým způsobem --- spočtením celkové sumy z jednotlivých kousků. Elektronické šeky mohou být utraceny do jisté omezené částky, o který se dá snížit platba. Dělá se to pomocí výzvy a odpovědi.

Při používání pouhých uživatelem kontrolovananých modulů, všechny tyto tři další vlastnosti mají své stinné stránky. Nicméně v mnoha situacích transferabilita není potřebována vůbec a dokonce může být spíše neobhrabaná, protože přenesené peníze rostou v rozměru. Podobně je to s divisibility, tak ale může být účinně dosažena bez linkability. Někdo vskutku může používat šeky v systému, což je patrně jediný přídavek, který má velkou šanci na realizaci bez nevýhod. Naproti tomu ve wallets s pozorovači mohou být tyto přídavky bez mnoha nevýhod implementovány, protože pozorovač může ošetřit jisté problémy, které jsou těžko řešitelné s pouhým uživatelským modulem. V podstatě jsou dva způsoby, jak dosáhnout těchto properties. První je dodat korektní systém do jednoho z pozorovačů (pro systém bez pozorovačů). Pokud se nazajímá o sdílenou informaci, může to být uděláne přímo. Ale pokud se musí sdílená informace ošetřit, stává se to velmi obtížnou věcí. Jiný způsob je použít jednotnou možnost wallets s pozorovači ze 3 částí. Např. ačkoli můžeme šekový systém implantovat přes nastavení pozorovače, mohou být šeky dosaženy výkonnějším způsobem, tím, že se pozorovač stará o částku, který může být uživateli proplacena.

3. Vlastnosti tohoto cash-systému

Provedeme diskusi tohoto off-line elektronického systému v několika kategoriích.

Výkonnost --- systém je daleko výkonnější než předchozí navržená řešení. (Jak vybírací, tak platící fáze). Systém je daleko výkonnější ve složitosti komunikace i ve výpočetní složitosti. Zvláště vybírací a platící protokoly se skládají s pouhých tří pohybů a kontroly zůstatku vyžadující jednu akci (pohyb). Použitím standardního zpusobu dávání výzev v obchodech je jediná funkce jisté informace; můžeme zhustit platební protokol do jediného pohybu. Všechna předchozí navržená řešení používají binární protokoly (výzva-odpověď) ve výběrové fázi --- (k potvrzení uživatelské identity je přijímaná informace podepisována) a v platící fázi (k potvrzení, že bude odchycen v případě double-spender), takže potřebují polynomiálně mnoho odpovědí (obvykle probíhajících paralelně) k dosažení vytouženého stupně bezpečnosti. V tomto kontrolním doplňku se vybírací protokol skládá ze 4 pohybů --- platba a proplacení 3 pohybů jeden záložní. Na platbu a proplacení --- podobé označení jako výše. Může být přidán vektor řetězové techniky, dokonce ověřovací vztahy jsou daleko daleko výkonnější k spočítání než u předchozích systémů.

Dokazatelnost --- můžeme dokázat správnost tohoto cash-systému na velmi vysokém stupni, který je patrně velkým problémem předchozích systémů. Bezpečnost tohoto systému se zdá býti ekvivalentní nějakým známým těžkým problémům, jako je Diffi-Hellmanova podmínka.

Rozšiřitelnost --- Tento systém může být rozšířen mnoha způsoby velmi snadno, aniž by to snížilo jeho výkonnost. Například uživatelům lze povolit utratit coins k-krát (k-podpis) místo jednou způsobem, že k+1 útrat odhaluje identitu uživatele, zatímco na k útrat jej bezpodmínečně skryje. Přestože všech těchto k plateb je linkable, celý řetěz k plateb je bezpodmínečně nelinkable pro určitého uživatele. Tato věc způsobí pouze lineární zvýšení délky přenášené informace a výpočetní složitost.

Další rozšíření systémů může být použití šeků (checks --- kontrol?). Lze vytvořit check-system, který je výkonnější než u základního systému s coiny. Mohou být použity šeky s různou maximální hodnotou.

Podobně může být dosaženo divisibility. Téměř všechny popsané systémy toto neumožňují. I toto může být navrženo tak, aby bylo mošno šek utratit vícekrát bez zjevení identity.

Může být přidána přenositelnost. Ovšem silnou stránkou tohoto systému je to, že může být přímo zabudován do wallets s pozorovači, zvyšuje se i bezpečnost ohledně double-spendingu. Uživatelé by mimo silnou kryptografickou podmínku museli zlomit i neotviratelné zařízení. Bezpečnost je tedy velmi silná. Díky reprezenativnímu problému může být většina protokolů snadno převedena. U předchozích systémů šlo velmi zabudovat do walletu tyto požadavky.

Funkcionalita --- systém nabízí extra funkcionalitu. Například sestavení pokusů do banky --- chráněno mechanismem: uživatelé jsou schopni prokázat, že jsou lživě obžalováni, např. v případě double-spendingu. V předchozích systémech, identifikující informace o uživatelích byla úplně známa bance. V tomto systému uživatele identifikující informace se skládá z tajné části, která nemůže být bankou spočítána, bez ohledu na výpočetí sílu.

Analogie v ostatních grupách --- téměř všechny předchozí systémy používali triky, které se velmi těžko přizpůsobovaly ostatním grupám. Naproti tomu tento systém používá mnoho nástrojů, které se mohou snadno přizpůsobit k držení se v RSA-grupách (např. v multiplikativních grupách modulo dvě prvočísla) stejně dobře jako v reprezentačním problému. Jediný věc, o které se neví, jak ji přizpůsobit RSA-grupám je slepý podpisové schéma, které je potřeba u výběrového protokolu.

Vedle těchto velmi milých dobrých vlastností je v tomto systému také několik věcí, které by se mohly zdokonalit. To může například výkonnější slepé podpisové schéma z pohledu storage space, neboť v tomto systému se jeden podpis banky skládá ze 4 čísel. Toto schéma příčinou, že výpočetní úsilí k zlomení systému není větší než k zlomení Diffie-Hellmanova problému. Bylo by příjemnější secutirity ekvivalence problému diskrétního logaritmu.

Stručná diskuse techniky, která se k tomuto používá

U dosavadních systémů bylo těžké o nich cokoli matematicky dokázat. Zde nemáme za cíl rigorózní důkaz, ale nějaký rámec, ale částečný důkaz bezpečnosti, který vede k rigoróznímu důkazu. Jeden z hlavních problémů, s nímž se sektáme při dokazování bezpečnosti tohoto systému, je, že se zdá těžké dokázat, že skladba minimálně-znalostního protokolu je minimum-znalostní.

Momentálně nejlepší, co může člověk udělat, je dokázat korektnost tak hluboce, jak je to jen možné. Existují nějaké explicitní podmínky. Nejobvyklejší je např. použít několik nespecifikonavých funkcí v protokolech, jejichž interakci téměř nelze analyzovat. Typicky se takové funkce objevují, neboť manipulují v různých grupách skrze systémové požadavky mapující prvky z jedné grupy do druhé.

Je rozhodující začít s pružným základem problému, z něhož je systém vyvíjen. Takže obvyklé je nemít nespecifikované funkce. Proto v elektronickém cash-systému používáme jeden základní problém --- reprezentační problém, který umožňuje flexibilní manipulaci.

Detekovat double-spending zakódováním identity v elektronické cashi je pravděpodobně jediný nejtěžší problém k řešení v ochraně soukromí off-line cash-systémů nespoléhajících na odolnost proti porušení, a co se jak účtuje pro více nevýkonných a nespecifikovaných funkcí. V tomto systému, zda je identita uživatele ve vybírací informaci (coins, checks) závisí zcela na znalosti tohoto. Proto, jak mnoho je jistá vybírací informace hodnotná, jehož identita je v ní a zda může být utracena závisí zcela na znalosti uživatele, o němž je daná informace.

Cesta ke kódování identity ve spojitosti s reprezentačním problémem nám dovoluje virtuálně všechny manipulace v tomto systému ve dvou isomorfních grupách (G,Z) bez potřeby představovat nespecifikované funkce kromě hašovací funkce. Důležitější: umožňuje aplikovat některé techniky tohoto systému užitečné k dokázání korektnosti a výkonnosti velkých rozměrů. První je aplikována na vybírací protokol a povoluje odstranit cut/choose metodu běžně používanou pro kódování informace uživatele, obsahující jeho identitu. Spíše než dávat vlastní identitu slepému číslu a přesvědčovat banku, že to udělal otevřením všeho, ale trochy (vybrané bankou), používá se to, co se nazývá omezující slepé podpisové schéma, kde je uživatel 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, že banky nepotřebují znát další tajné informace než ostatní účastníci systému, kromě tajného klíče používajícího ke slepému podpisu. To nám umožňuje nahlédnout do celého systému jako na jeden celek, neboť všechny účastníci protokolů mohou být algoritmicky polynomiálně náročné (i když banka nepotřebuje být), může být simulován pravděpodobnostním polynomiálním alegoritmem. Takto můžeme dokázat, že mnoho myslitelných útoků na systém je neproveditelných, protože by to znamenalo, že útočník může určit nějaký relativní diskrétní logaritmus s nejakou pravdepodobnosti. To by znamenalo, že musí existovat uskutecnitelny algoritmus, ktery spocte diskretni logaritmus s nezanedbatelnou pravdepodobností, zvlaste simulujici system (nahodné volby a akce účastníků).

Označení a základní předpoklady

Všechny aritmetické operace provádím v grupe Gq prvočíselného řádu q, takže Gq je Abelova grupa, pro níž polynomiálně-časové algoritmy jsou známy k určení rovnosti prvku, test náležení, spočítání inversu, násobení a náhodné vybrání prvku. Výsledky jsou platné v nějaké grupě. Budeme užívat podgrupu Gq, sice Zp s p=kq+1 prvočíslo pro nějaké k z N. V praktické implementaci systému bude délka p pravděpodobně nejméně 512 bitu a q-čka nejméně 140 bitu. Bezpečnost tohoto systému je spojena s Diskrétním logaritmem a Diffie-Hellmanovou podmínkou, oboje v rámci Gq.

Diskrétní Log problém nazvu nalézt jedinečný index log h o základu g náleží Zq a h náleží Gq, g take v Gq bez {1}. Řekneme, že algoritmus řeší problém DisLog, jestliže pro vstup g nerovno 1, h generované stejně náhodně, dává na výstup log a základu g z h s nejméně nezanedbatelnou pravděpodobnost úspěchu. Podmínka dislog vyjadřuje, že neexsituje polynomálně časově složitý algoritmus, který řeší problém Dislog s nezanedbatelnou pravděpodobností úspěchu.

Pokud existuje algoritmus, který řeší Dislog problém, pak existuje algoritmus řešící Dislog problém s nezanedbatelnou pravděpodobností úspěchu.

Následující tvrzení jsou ekvivalenstní:
(a) Existuje polynomiální algoritmus A s indexem (a), pro náhodně zvolený vstup g nerovno 1 a h dává na výstup log h o základu g.
(b) Existuje g nerovno 1 a polynomiálně časově složitý algoritmus A (b), který pro náhodně vybraný vstup h dává výstup log g h.

Nalezení jediného Diffie-Hellmanova klíče g na ab of g1,g2 je DH problém. Řekneme, že algoritmus řeší DF problém se základem g, pro vstup g1, g2 generovaný stejně náhodně, dává na výstup DF klíč z g1, g2 s ohledem na g nejméně s nezanedbatelnou pravděpodobností úspěchu. DF podmínka vyjadřuje, že pro všechna g nerovna 1, není znám takový polynomiální algoritmus.

Reprezentační problém

Definice 5 --- viz papír str. 15,pozorování 6

(Pozorování 7) Definujeme V jako množinu funkcí nastavením všech fcí ve formě q(.)/r(.) takovou, že q(.) a r(.) jsou polynomiální v oboru celých čísel a celošíselných koeficientu, a q(k)>r(k)>=1 pro všechna dostatečně velká K. Pro nějaké funkce f1(.),f2(.),f3(.),f4(.) z V, následující 4 tvrzení jsou ekvivalentní:
(1) Existuje polynomiálně časově složitý algoritmus A s ind. (1), který na vstupy generátoru k-tic a h náleží Gq, dává na výstup representující indexovou t-ici h-čka s pravděpodobností úspěchu nejméně 1/f1(|p|) pro všechna dostatečně velká p.
(2) Existuje polymomiálně časový algoritmus A s ind. (2), který se vstupem generárem k-tic dává na výstup netriviální representující index-tici jedničky s pravděpodobností úspěchu nejméně 1/f2(|P|) pro všechna dostatečně velká p.
(3) Existuje nějaké h z Gq\{1} a polynomiálně časový algoritmus A s ind. (3), který se vstupem generárotu k-tice dává na výstup representucí tici h-čka s pravděpodobností úspěchu nejméně 1/f3(|p|) pro všechna dostatečně velká p.
(4) Existuje polynomiálně časový algoritmus A s ind. (4), který řeší DisLog problém s pravděpodobností úspěchu nejméně 1/f4(|p|) pro všechna dostatečně velká 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-systému pouze používáme pouze omezenou formu tohoto problému, representační problém pro grupy prvočíselného řádu.
Lze dokázat, že representační problém pro grupy prvočíselného řádu je ekvivalentní co do výpočetní složitosti Dislog problému.
Dále, viz dusledek 8.

Výkonnost výpočtu representativního problému. Výsledek algoritmu se zdá být vhodný v počítacích zařízeních malé kapacity, jako jsou karty či off-line elektronické systémy.

Dukaz znalosti representace Abychom dovolili časově polynomiálnímu dokazateli P dokázát znalost representace (a1,...,ak) čísla h s ohledem na (g1,...,gK) ověřoviteli V, mužeme přímo užít zobecnění identifikačního protokolu. 1. P generuje k čísel w1,...,wK ze Zq a posílá --- viz papír.

Věta 9
1. Úplnost --- Pokud P je čestný --- zná representaci a drží se protokolu, potom V akceptuje.
2. Bezchybnost. --- Pokud P rezná reprezentanta h s ohledem na (g1,...,gk), pak neexistuje strategie, pro níž by mu V potvrdil s významnější pravděpodobností úspěchu.
3. Hledání svědka --- Dokonce se všemi shromážděnými předchozími výkonáváními protokolu a neomezené vkýpočetní síly, V nemže nalézt nějakou informaci o správné reprezentaci, kterou P zná, pokud P dodržuje protokol těchto činností.

Základní nástroje pro vybírací protokol

V tomto systému, identita uživatele je zakódována celá v representaci, kterou uživatele zná s ohledem na generátor tice. Proto, mužeme použít techniky povolující se nám zbavit metodologie cut/choose v dřívějších systémech, což výrazně zvyšuje výkonnost. Uživatel je bance znám pod synonymem m=g1 na u1 krát g2 na u2, ... gk na uk, která je spojena s jeho účtem a identitou. Podpisové schéma banky, jejíž veřejný klíč je (g,h(=g na x)), je takové, že uživatel muže dělat vlastní blinding pseudonymu, ... 9. kapitola. Uživatel skončí s novým číslem, které je pro banku neznámé, psolečně s platným podpisem banky.

Ukážeme drobný příklad. Uživatelbude začne při vybírání ořesně jednou representací (a1,...,aK) čísla m s ohledem na generátor (g1,...,gk). V našem systému, toho dosáhneme tím, že uživatel si vybere své ai s čárkou krát s a spočte m. Podle 8 nemuže skončit znalostí více než jedné representace. str. 23,...

Inspirováni touto myšlenkou, mužeme kódovat identitu uživatele, např. ai, aj. Při platbě uživatel poté uvolní řádek ai + aj * c v Zq, c výzvou c obchodu. Otevře nějakou částečnou informaci o své reprezentaci a pak přesvědčí obchod (s podpisem), který je čestný. Pokud uživatel double-spenduje, s nezanedbatelnou pravděpodobností se spočte ai, aj, a tudíž i identita uživatele.

Omezené slepé podpisové schéma

Záměr slepých podpisových protokolu je pro příjemce obržet podpis sign(m) ve zprávě m nerovno 1 tak, že nejenom (m,sign(m)) zustává pro podpisovatele neznámé, ale dokonce s neomezenou výpočetní silou nebude možné naléty nějaký pár (m,sign(m)) specifický ke spuštění protokolu. Používáme slepé podpisové schéma (přizpusobení z 3-pohybového identifikačního ) schématu.

Aby tomu bylo rozumět, provedeme určité zjednodušení. Nechť g... str. 24
1. Podepisovač vygeneruje náhodně číslo w ze Zq a pošle z=m na x, a=g na w, b=m na w příjemci.
2. Příjemce vygeneruje náhodně 4 čísla: s, t, a u, v vše ze Zq. použitím první dvojice čísel spočte m s čárkou = m na s * g na t. s ostatními dvěma spočte --- viz str. 24 dole
3. Podepisovatel odpoví s r=w+cx mod q.

Základní nástroje pro platební protokol

Abychom zabránili double-spendingu coin, musí uživatel obchodu zjevit nějaké informace o svém majetku, jako kus informace, která nezjevuje jeho identitu, zatímco dva kusy informace umožní zjistit identitu v polynomiálním čase. Užíváme jednoduchého faktu, že sklon přímky je jednoznačně určen dvěm body, a neurčen jedním! str. 30

Randomizace reprezentací

V tomto nastaveném cash-systému, uživatel [P, polynomiálně omezen]. musí zařizovat účet s bankou. To se skládá z čísla h=g1 na a1 * g2 na a a2, takže (a1,a2) jsou bezpodmínečně skryté v množině všech reprezetantu h s ohledem na (g1,g2). V některých situacích, banka (V neohraničená) muže chtít každý prvek representace nechat poznat P aby byly vzájemně náhodné. Obecně, V muže chtít zjednat spolupráci s P a číslem h a representací h s ohledem na generátor ktici (g1,...,gk) takovou, že každý prvek representace je vzájemně náhodný.
Je užit následující protokol:
1. P generuje stejně náhodně indexovou k-tici (x1,...,x_k+1) a posílá V-čku h s čárkou = součin přes i od 1 do k+1 gi na xi.
2. V posílá náhodně vybranou indexovou k-tici (y1,...,yk) P-čku.
3. P posílá x_k+1 V-čku. Pokud P je v kroku 3 čestný, (x1+y1 mod q,... xk+yk mod q) je reprezentantem h-čka = (soucin pres i=1 az k cisel gi na yi)*h'/(g_k+1)^(x_k+1) s ohledem na (g1,...,gk), což zaručuje výše uvedené požadavky.
Snadné ukázat, že jediná možnost, jak P muže znát representaci h-čka je, pokud následuje protokol.

Základní cash-system

--- str. 37

Pouze coins. Budeme užívat identitu uživatele ve formě ... a banka zná ...takze je s bankou uzivatele obeznamen. Pokud se někdo spokojí se systémem, ve kterém je obeznámění pouze výpočtově chráněné, mužeme mu dát dokonce uspokojivé schéma, dáme-li mu identitu jednoduše u, banka zný g na u.

Nastavení systému Banka vygeneruje náhodně následujících pět prvku:
1. generátor tice (g,h). To je public key banky, který používrá k vytvoření signatury ve výběrovém protokolu. Index x=..., obvykle držen v tajemství.
2. generátor sloupce g1,g2, který je používán skrz systém.
3. Tzv. falešný generátor d nerovnajícící se g1 a g2, který je k zajištění, že identita čestného uživatele bude vypočtena ze spuštění platebního protokolu {nezávisle na výpočetní síle}.
Máme jenom coins. v systému. Bezpečnost tohoto schématu závisí na tom, že nikdo není schopen vyjádřit g,h,g1,g2,d jako kombinaci ostatních prvku. Toto je těžké nejméně tak jako problém nalezení reprezentanta 1 s ohledem na generátor tice (g,h,g1,g2,d), je zaučeno podle pozorování 7, že je to nedostupné {podmínka DisLog}. Dokonce banka nepotřebuje znát diskrétní logaritmus kromě x.
Když uživatel U otevře účet v nace, vygeneruje náhodně {možno ve spolupráci s bankou B} čísla u1,u2 --- viz Randomizace reprezentantu,ze Zq a spočte I... Banka nezná u1,u2, uloží si I s uživatelovou skutečnou identitou a číslem účtu. V případě, že uživatel double-spenduje tutéž cash, banka je schopna zjistit u1,u2. Spočtením I... muže určit jeho účet a tedy identitu. Výběrový protokol Uživatel chce vybírat peníze z účtu {jakoby řekl I}, nejprve přesvědší banku B, že peníze vskutku jsou vybírány z jeho vlastního účtu. U dokazuje B-čku znalost reprezentace (např. použitím schématu v sekci 8). Porozujeme, že uživatel to muže ukazat čistě, i když to nebude nejchytřejší, protože bnka muže potom ho rámcovat nebo muze dát naslouchaci, ktery muze nesprávně mezi ně se prezentovat. Pokud B akceptuje dukaz U pro každou hotovost, kterou U chce vybrat, je spuštěn vybírací protokol (viz obr. 5 --- str. 39):
1. B odečte požadovanou sumu peněz z účtu a zformuje číslo m=Id (U si muže) spočíst toto číslo sám a nepotřebuje Bm tedy není potřeba pro Banku posílat to U. B pošle m na x, g na w a m na w uživateli, s w náhodně vzbraným ze Zq.
2. a dále viz text str.38 viz poznámky. Platba Pokud uživatel chce utratit peníze v obchodě S, je spuštěn následující protokol --- viz obrázek 6 + test dále viz str. 40 Zustatek Po nějaké jednotce času, všechny obchody shromáždí informace a platbách bance --- viz Obr. 7, který ihned zjistí dvakrát-utracené peníze, neboť A,B,sign(A,B) bylo použito. Y odpovědí na výzvy muže vypočítat ... a pak identifikovat informaci o uživatelích, kteří dvakrát utratili. u1... Pak spočte I... a nalezne záznam o účtu k identifikaci double-spendera. Pro pozdější porovnání zpusobu, kterým banka identifikuje double-spendery s wallety s pozorovači, zde odvozujeme přesné formule, které banky potřebují k zjištění u1,u2. viz papír.... Pokračuje to featurami. Dále korektnost cash-systému, ..., checks, divisibility, ..., pozorovače, převedení protokolu,...

Korektnost tohoto základního systému

viz text

Off-line cache-systémy ve wallets s pozorovači

Tento systém je rpvní s možností prevence proti sdílené informaci. Díky pružné struktuře repr. problému, který dovoluje převádět. Muže být ochráněno před double-spendingem. Rádi bychom měli systém podobajícímu se našemu základnímu systému, který by byl nejlépe takový, že jestliže je pozorovač prolomen před tím, než byl učet vlastníka banky otevřen, zachovame korektnost základního cash-systému.

K dosažení prevence před double-spendingem, informace, že uživatel vybírá, musí být rozdělena mezi user-modul a pozorovač tak, že uživatel nemuže utratit dvakrát sám od sebe. V základním systému, k zajištění tohoto nezmáme reprezencai m s čárkou, už pozorovač a uživatel však dohromady ano.

Některé otevřené problémy

Existují vhodné omezovací slepá podpisová schémata v RSA-groupách? Pak bychom byly schopni vybudovat cash-systém v RSA-groupách podobně, jako zde bylo popsáno. Existují výkonné slepé podpisové schéma v Gq? Mohou být rozšíření dosažena v nastavení wallets s pozorovači efektivněji zp;sobem, pod požaadavkem nesdílené informace? V našich rozšířeních --- multishow cash a divisibility, je plná linkability. Múže být jedno z rozšíření dosaženo bez linkability?