Strona główna

Jest to szereg kroków, obejmujących dwie lub więcej stron, podejmowanych w celu realizacji zadania. Jest to inaczej mówiąc sekwencja działań, każde z nich musi być kolejno wykonane i żadne nie może być podjęte


Pobieranie 343.43 Kb.
Strona9/10
Data19.06.2016
Rozmiar343.43 Kb.
1   2   3   4   5   6   7   8   9   10

Hierarchiczna struktura pieniądza



Tablica G odpowiadająca strukturze hierarchicznej pieniądza



Założenia stawiane podzielonym pieniądzom:

  1. wartość pieniądza w gałęzi N jest sumą wartości pieniędzy w gałęziach podrzędnych,

  2. jeśli gałąź (a z nią związana wartość pieniężna) została już użyta, wszystkie podrzędnie gałęzie nie mogą być użyte,

  3. żadna z gałęzi nie może być użyta więcej niż jeden raz.


Jeżeli użytkownik chce wydać np. 75 zł, to musi użyć jednej gałęzi o wartości 50 zł (G00) oraz jednej o wartości 25 zł (G010).
Bank celem wydawania tego typu pieniędzy generuje dla każdej z grup wartości portfela oddzielnie parametry systemu RSA, i tak np.:

dla wartości 10 zł generuje n10, e10, d10,

dla wartości 100 zł generuje n100, e100, d100,

itd.
W zasadzie problem należy do banku z jakim skokiem pomiędzy poszczególnymi wartościami będzie miał do czynienia, czy to stałym, czy też narastającym. Ważne jest by wartości te można było łatwo i naturalnie dzielić.
W każdej trójce parametrów n odpowiada modułowi i jest liczbą złożoną, e jest kluczem jawnym, d jest kluczem tajnym. Parametry te służą do komunikacji użytkownika z bankiem oraz ustalania wartości podstawowego czeku
Szerzej to zagadnienie opisane jest w artykule „Universal elecrtonic cash” Tatsuaki Okamoto, Kazuo Ohta, CRYPTO 91. Podobne zagadnienie tylko innymi metodami zaprezentowali Chan, Frankel i Tsiounis na konferencji EUROCRYPT 98.

DOWODY TWIERDZEŃ O WIEDZY


Służą między innymi do przedstawiania informacji o posiadaniu pewnych danych zarazem nie ujawniając ich osobie sprawdzającej, a także nikomu postronnemu.

Własności dowodów wiedzy:

  • osoba dowodząca twierdzenia nie może oszukiwać sprawdzającego, jeżeli nie zna dowodu, to jej szanse na przekonanie sprawdzającego, że zna ona dowód, są znikome;

  • osoba sprawdzająca nie może oszukiwać osoby udowadniającej, nie uzyskuje ona najmniejszej wskazówki odnośnie do dowodu z wyjątkiem sytuacji, kiedy osoba udowadniająca zna dowód; w szczególności osoba sprawdzająca nie może wykazywać poprawności dowodu komukolwiek innemu bez udowodnienia go samemu sobie na podstawie skrawków informacji;

  • osoba sprawdzająca nie dowiaduje się od osoby dowodzącej niczego, czego nie mogłaby się dowiedzieć samodzielnie bez dowodzącej.


Protokół konwersacyjny udowadniania wiedzy.

Przykładowo użytkownik A zna część informacji i dodatkowo informacja ta jest rozwiązaniem trudnego problemu. W tym przypadku protokół ma postać:


  1. użytkownik A używa swojej informacji i pewnej liczby losowej do przekształcenia trudnego problemu w inny trudny problem, który jest izomorficzny z funkcją pierwotną, następnie używa on swojej informacji i liczby losowej do rozwiązania nowego trudnego problemu;

  2. użytkownik A dokonuje zobowiązania w stosunku do nowego rozwiązania, używając pewnego schematu zobowiązania bitowego;

  3. użytkownik A ujawnia użytkownikowi B nowy problem trudny, użytkownik B nie może użyć tego nowego problemu do uzyskania jakiejkolwiek informacji dotyczącej problemu pierwotnego lub jego rozwiązania;

  4. użytkownik B żąda od użytkownika A wykonania jednej z dwóch czynności:

  1. udowodnienia jemu, że stary i nowy problem są izomorficzne; albo

  2. otwarcia rozwiązania zawartego w zobowiązaniu w kroku 2) i udowodnienia, że jest to rozwiązanie nowego problemu;

  1. użytkownik A wykonuje polecenie;

  2. obydwaj użytkownicy A i B powtarzają powyższe kroki n-krotnie.

Drogi Hamiltona



Drogą Hamiltona w grafie nazywamy taką trasę przejścia po drzewie grafu, która zwiera wszystkie wierzchołki grafu i na dodatek przejście przez każdy wierzchołek jest przejściem jednokrotnym. Przy odpowiednio dużych grafach wyznaczenie tej drogi jest problemem bardzo czasochłonnym. Jeżeli użytkownik A zna ta drogę dla grafu G i chce przekonać o tym użytkownika B, to musi wykonać następujące czynności stanowiące protokół dowodu wiedzy z zatrzymaniem samej wiedzy tylko dla siebie:


    1. użytkownik A dokonuje losowej permutacji G, przesuwa ona wierzchołki dookoła i zmienia etykiety, aby utworzyć nowy graf H, ponieważ grafy G i H są w sensie topologicznym izomorficzne (jest to ten sam graf), więc jeżeli zna drogę Hamiltona grafu G, może łatwo znaleźć drogę Hamiltona grafu H, jeżeli nie utworzył on grafu H osobiście, to określenie izomorfizmu między dwoma grafami jest problemem trudnym;

    2. użytkownik A przekazuje użytkownikowi B kopię grafu H;

    3. użytkownik B żąda od użytkownika A wykonania jednej z dwóch rzeczy:

  1. udowodnienia, że G i H są izomorficzne; albo

  2. przekazania drogi Hamiltona dla grafu H;

    1. użytkownik A wykonuje polecenie, realizując jedną z dwóch poniższych czynności:

  1. dowodzi, że graf G i H są izomorficzne, bez pokazywania drogi Hamiltona dla żadnego z grafów; albo

  2. pokazuje drogę Hamiltona dla grafu H, bez dowodzenia, że G i H są w sensie topologicznym izomorficzne;

    1. użytkownicy A i B powtarzają kroki od 1) do 4) n-krotnie.


Izomorfizm grafów
Użytkownik Zna izomorfizm pomiędzy grafami G1 i G2 oraz chce przekonać użytkownika B o tej wiedzy. Protokół ma postać:


      1. użytkownik A dokonuje losowej permutacji wierzchołków grafu G1 aby wytworzyć inny graf H taki, że jest on izomorficzny z G1; ponieważ użytkownik A zna izomorfizm między G1 i H, więc zna także izomorfizm między H i G2; dla każdej innej osoby znalezienie izomorfizmu między grafami G1 i H oraz G2 i H jest równie trudne, jak znalezienie izomorfizmu miedzy G1 i G2;

      2. użytkownik A przekazuje użytkownikowi B kopię grafu H;

      3. użytkownik B żąda od użytkownika A wykonania jednej z dwóch rzeczy:

  1. udowodnienia, że G1 i H są izomorficzne; albo

  2. udowodnienia, że G2 i H są izomorficzne;

      1. użytkownik A wykonuje polecenie realizując jedną z poniższych czynności:

  1. dowodzi, że G1 i H są izomorficzne bez udowodnienia, że G2 i H są izomorficzne; albo

  2. dowodzi, że G2 i H są izomorficzne bez udowodnienia, że G1 i H są izomorficzne;

      1. użytkownicy A i B powtarzają kroki 1) do 4) n-krotnie.


Użytkownik B nie uzyskuje żadnej informacji o samym izomorfizmie grafów G1 i G2.
Równoległe dowody o wiedzy
Są to metody udowodnienia wiedzy pomiędzy użytkownikami ze zmniejszoną ilością wymiany informacji pomiędzy użytkownikami.

Postać protokołu:


    1. użytkownik A wykorzystuje swoją informację i pewne liczby losowe do przekształcenia trudnego problemu w n odmiennych problemów izomorficznych, następnie wykorzystuje swoją informację i liczbę losową do rozwiązania tych n nowych trudnych problemów;

    2. użytkownik A zobowiązuje się do rozwiązania n nowych trudnych problemów;

    3. użytkownik A ujawnia użytkownikowi B n nowych trudnych problemów; użytkownik B nie może wykorzystać tego nowego problemu do uzyskania jakiejkolwiek informacji dotyczącej problemu pierwotnego lub jego rozwiązania;

    4. dla każdego z nowych n trudnych problemów użytkownik B żąda od użytkownika A wykonania jednej z dwóch czynności:

a) udowodnienia, że problemy stary i nowy są izomorficzne; albo

b) ujawnienia rozwiązania zawartego w zobowiązaniu z kroku 2) i udowodnienia, że jest to rozwiązanie tego nowego problemu;

    1. użytkownik A realizuje te czynności dla każdego spośród n nowych trudnych problemów.


Niekonwersacyjne dowody o wiedzy
Stosuje się gdy trzeba przekonać stronę trzecią o swojej wiedzy nie prowadząc akurat z nią konwersacji. Wykorzystuje się tu protokół postaci:


    1. użytkownik A wykorzystuje swoją informację i pewne liczby losowe do przekształcenia trudnego problemu w n odmiennych problemów izomorficznych, następnie wykorzystuje swoją informację i liczbę losową do rozwiązania tych n nowych trudnych problemów;

    2. użytkownik A zobowiązuje się do rozwiązania n nowych trudnych problemów;

    3. użytkownik A wykorzystuje wszystkie zobowiązania jako wejścia do jednokierunkowej funkcji skrótu, następnie zachowuje on pierwsze n bitów wyniku działania tej funkcji jednokierunkowej:

    4. użytkownik A pobiera n bitów utworzonych w kroku 3), w zależności od tego, czy n-ty bit ma wartość 0 czy 1, pobiera on n-ty nowy trudny problem i wykonuje jedną z dwóch czynności;

a) udowodnienia, że problemy stary i nowy są izomorficzne; albo

b) ujawnia rozwiązanie zawarte w zobowiązaniu z kroku 2) i udowadnia, że jest to rozwiązanie tego nowego problemu;

    1. użytkownik A publikuje wszystkie zobowiązania z kroku 2) jak również rozwiązania z kroku 4);

    2. jakikolwiek inny użytkownik, który jest zainteresowany, sprawdza, czy wykonano właściwie kroki protokołu od 1) do 5).


PROBLEMY DOTYCZĄCE TOŻSAMOŚCI WYKORZYSTUJĄCE DOWODY WIEDZY


Problem arcymistrza szachowego
Problem oszustwa mafijnego
Problem oszustwa terrorysty
Oszustwo wielokrotnej tożsamości
Problem wypożyczania paszportów
Dowód o wiedzy zerowej logarytmu dyskretnego
Użytkownik A chce udowodnić użytkownikowi B, że zna on x spełniające zależność
ax b (mod p)
gdzie p jest liczbą pierwszą, a x jest względnie pierwsze z p-1. Liczby a, b i p są jawne, a liczba x jest tajna. Protokół udowodnienia znajomości liczby x bez jej ujawnienia ma postać:


      1. użytkownik A wytwarza t liczb losowych r1, r2, . . . , rt, przy czym wszystkie ri są mniejsze niż p-1;

      2. użytkownik A oblicza hi = ari (mod p) dla wszystkich wartości i i przesyła je użytkownikowi B

      3. użytkownicy A i B realizują wspólnie protokół rzutu monetą w celu wygenerowania t bitów: b1, b2 , . . . , bt;

      4. dla wszystkich t bitów użytkownik A wykonuje jedną z dwóch operacji:

a) jeżeli bi = 0, to przesyła użytkownikowi ri;

b) jeżeli bi = 1, to przesyła użytkownikowi B
si = ri – rj (mod p-1), gdzie j jest najmniejszą wartością, dla której bi = 1;


      1. dla wszystkich t bitów użytkownik B potwierdza jedną z dwóch następujących zależności:

a) jeżeli bi = 0, to ari = hi

b) jeżeli bi = 1, to ari = hi hj-1

      1. użytkownik A przesyła uzytkownikowi B Z, przy czym


Z = x – rj (mod p-1)


      1. użytkownik B potwierdza, że


aZ = b hj-1
Prawdopodobieństwo oszustwa wynosi 2-t.
Ulepszona postać protokołu o wiedzy zerowej logarytmu dyskretnego ma postać:


  1. użytkownik A wybiera liczbę losową r taką, że r jest mniejsze od p-1, oblicza

h = ar
i przesyła je użytkownikowi B;

  1. użytkownik B przesyła użytkownikowi A losowy bit b;

  2. użytkownik A oblicza


s = r + bx (mod p-1)
i przesyła wynik użytkownikowi B;

  1. użytkownik B potwierdza, że


as = h bb


  1. powtarzane są kroki 1) do 4) t razy.


Dowód o wiedzy niezbędnej do złamania protokołu RSA
Użytkownik A pragnie przekonać użytkownika B o tym, że posiada klucz prywatny użytkownika C bez ujawniania go.

Protokół ma postać:


  1. użytkownicy A i B uzgadniają liczby losowe k i m takie, że


k m = e
Muszą oni wybrać te liczby losowo, stosując protokół rzutu monetą do wytworzenia k, a następnie wyliczenia m; jeżeli obie liczby k i m są większe od 3 to protokół jest kontynuowany; w przeciwnym razie należy ponowić wybór;

  1. użytkownicy A i B tworzą losowy szyfrogram C, wykorzystując protokół rzutu monetą;

  2. użytkownik A, stosując klucz prywatny użytkownika C, oblicza


M = Cd mod n

1   2   3   4   5   6   7   8   9   10


©snauka.pl 2016
wyślij wiadomość