Wyczerpujący symulator protokołów zerowej wiedzy w losowym modelu Oracle

W artykule zatytułowanym „On Deniability in Common Reference String and Random Oracle Model” Rafael Pass pisze:

Zauważamy, że udowadniając bezpieczeństwo zgodnie ze standardową definicją zerowej wiedzy w modelu RO [Random Oracle], symulator ma dwie zalety w stosunku do zwykłego symulatora modelu, a mianowicie:

1. Symulator może zobaczyć, na jakich wartościach strony pytają o wyrocznię.
2. Symulator może odpowiedzieć na te zapytania w dowolny wybrany przez siebie sposób, o ile odpowiedzi „wyglądają” OK.

Pierwsza technika, mianowicie możliwość „monitorowania” zapytań do RO, jest bardzo powszechna we wszystkich artykułach odnoszących się do koncepcji zerowej wiedzy w modelu RO.

Rozważmy teraz definicję „ czarnej skrzynki” ( PPT oznacza probabilistyczną maszynę Turinga o wielomianowym czasie ):

$\exists$ symulator PPT , taki że (prawdopodobnie oszustwo) PPT weryfikator , wspólne wejście i losowość , następujące są nie do odróżnienia:$S$$\forall$$V^*$$\forall$$x\in L$$\forall$$r$

• widok podczas interakcji z przysłowiem na wejściu i przy użyciu losowości ; $V^*$$P$$x$$r$
• Wyjście na wejściach i , gdy jest podany czarnej skrzynki dostęp do . $S$$x$$r$$S$$V^*$

Tutaj chcę pokazać oszukiwającego weryfikatora , którego zadaniem jest wyczerpanie dowolnego symulatora, który próbuje monitorować zapytania RO:$V'$

Niech będzie symulatorem gwarantowanym przez egzystencjalny kwantyfikator w definicji wiedzy zerowej czarnej skrzynki, i niech będzie wielomianem, który górnie ogranicza czas działania na wejściu . Załóżmy, że próbuje monitorować zapytania do RO.$S$$q(|x|)$$S$$x$$S$$V^*$

Teraz rozważ oszustwo , które najpierw sprawdza RO dla razy (na dowolnie wybranych wejściach), a następnie działa arbitralnie złośliwie.$V'$$q(|x|)+1$

Oczywiście, wyczerpuje symulatora . Prostym sposobem dla jest odrzucenie takiego złośliwego zachowania, ale w ten sposób wyróżnik może łatwo odróżnić rzeczywistą interakcję od symulowanej. (Ponieważ w prawdziwej interakcji, przysłowie nie może monitorować zapytań , a zatem nie odrzuci na podstawie samego faktu, że pyta za dużo.)$V'$$S$$S$$P$$V'$$V'$

Jakie jest obejście powyższego problemu?

Edytować:

Dobrym źródłem do badania ZK w modelu RO jest:

Martin Gagné, A Study of the Random Oracle Model, Ph.D. Teza, University of California, Davis , 2008, 109 stron. Dostępne w ProQuest: http://gradworks.umi.com/33/36/3336254.html

W szczególności podaje definicje czarnej skrzynki ZK w modelu RO w sekcji 3.3 (strona 20), przypisane Yungowi i Zhao:

Moti Yung i Yunlei Zhao. Interaktywna zerowa wiedza z ograniczonymi losowymi wyroczniami. W teorii kryptografii - TCC 2006 , LNCS 3876, s. 21–40, 2006.

Powstaje pytanie, dlaczego chciałoby się zdefiniować czarną skrzynkę ZK w modelu losowej wyroczni. Istnieją co najmniej dwa powody, dla których ludzie sugerowali definicję czarnej skrzynki bez wiedzy:

1) Aby uzyskać pozytywny wynik, gdy powiesz, że symulator to „wiedza z zerowej skrzynki”, automatycznie daje ci przyjemne ograniczenie czasu jego działania (tj. Czas w przeciwieństwie do do ), a przydać się może również fakt, że symulator nie „patrzy na wnętrzności i nie dba o to, czy jest implementowane przy użyciu pamięci RAM, obwodu itp. .. Chociaż symulator modelu z losową wyrocznią może być wydajny, to oczywiście nie jest czarną skrzynką, ponieważ powinien w jakiś sposób spojrzeć na wykonanie i zrozumieć z niego, kiedyp o l y ( t i m e ( V ∗ ) ) V ∗ V ∗ V ∗ V $poly(|x|) \cdot time(V*)$$poly(time(V*))$$V*$$V*$$V*$$V*$ocenia funkcję skrótu. Z tego powodu istnieje sens, w którym nie ma sensu mówić, że symulator modelu z losową wyrocznią to „czarna skrzynka”.

2) Aby uzyskać wynik ujemny, ludzie używają „symulatora czarnej skrzynki”, aby uchwycić dużą klasę technik dowodowych. W tym przypadku możesz zdefiniować symulator czarnej skrzynki również w modelu losowej wyroczni, a definicją, która ma sens, jest to, co powiedział David. W rzeczywistości, dla wyniku ujemnego, nawet nie w przypadku modelu losowej wyroczni, najlepiej jest, jeśli wynik zostanie zachowany, nawet jeśli zezwolisz na symulatora . Rzeczywiście, chociaż nie zawsze jest to stwierdzone, negatywne wyniki, o których wiem, że mają tę właściwość, ponieważ weryfikator oszustwa jest zwykle stałym algorytmem wielomianowym, który uruchamia niektóre funkcje pseudolosowe, podczas gdy symulator może mieć dowolny wielomianowy czas działania.V $poly(time(V*))$$V*$

Oto moje podejście do problemu. Ostatnio nie czytałem żadnych artykułów dotyczących wiedzy o zerowej czarnej skrzynce w modelu losowej wyroczni (RO), więc zgaduję, co one oznaczają, a nie co tam jest napisane. Krótka odpowiedź (zgadnij) jest taka, że ​​BB-ZK w modelu RO powinien pozwolić symulatorowi działać w czasie wielomianowym w | x | oraz liczbę zapytań RO wydanych przez V *, weryfikatora oszustwa.

Spróbujmy uzasadnić to przypuszczenie. Początkowa obserwacja jest taka, że ​​termin „dowody zerowej wiedzy w czarnej skrzynce w modelu losowej wyroczni” wymaga dokładniejszego przyjrzenia się, aby właściwie zdefiniować. Symulatory czarnej skrzynki są zdefiniowane do pracy z dowolną wyrocznią (tj. Oszustem weryfikującym jako czarna skrzynka), a ich jedynym interfejsem jest wejście / wyjście wyroczni. Jeśli tylko ulepszymy ten model, aby dać RO wszystkim stronom (być może poprzez umożliwienie ich obwodom posiadania bramek RO), otrzymamy model, w którym symulator nie może zaprogramować RO - na zapytanie Oracle, wszystko (w tym zapytania RO) po prostu dzieje się „wewnątrz” wyroczni V *, a następnie zwraca następną wiadomość. Jeśli chcemy zezwolić na programowanie RO, musimy zmodyfikować interfejsy: Symulator otrzymuje teraz wyrocznię wejścia / wyjścia dla V * i żadnej losowej wyroczni. Przy każdym połączeniu z wyrocznią V * zamiast generować następny komunikat, wyrocznia może zamiast tego wygenerować następne zapytanie do RO, a symulator może udzielić odpowiedzi RO poprzez ponowne wywołanie wyroczni. Teraz pozwala to na programowanie RO, a także możemy pozwolić, aby czas działania symulatora zależał od liczby zapytań do RO.

Wszelkie dalsze badania znaczenia tych definicji pozostawia się czytelnikowi. Myślę syntaktycznie.