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:

Symulator może zobaczyć, na jakich wartościach strony pytają o wyrocznię.
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.

— MS Dousti
źródło

Myślę, że możesz mieć na myśli „wyczerpujący” zamiast „wyczerpujący”.

— Dave Clarke,

Pozwolę sobie być innego zdania. Znaczyłem, że znalazłem sposób na „wyczerpanie” symulatora protokołów ZK ... Nie ma czegoś takiego jak „wyczerpujący” symulator.

— MS Dousti,

Mój błąd. Wyczerpuję się jako przymiotnik, a nie czasownik.

— Dave Clarke,

Odpowiedzi:

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, kiedy $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. $poly(time(V*))$ $V*$

— Boaz Barak
źródło

Czy to samo dotyczy „uniwersalnej symulacji” ZK? W końcu czarna skrzynka ZK jest rodzajem uniwersalnej symulacji ZK, której czas działania jest ustalony przed określeniem . (Jednak ZK bez czarnej skrzynki jest rodzajem uniwersalnej symulacji ZK, w której S może patrzeć na „wnętrzności” V *)

V *

$V*$

— MS Dousti

Zobacz edytowane pytanie, aby uzyskać odniesienia.

— MS Dousti,

W przypadku uniwersalnego symulatora (innego niż czarna skrzynka) należy zezwolić na wielomian czasu wykonywania w czasie wykonywania ponieważ w przeciwnym razie symulator nie będzie miał czasu na wywołanie . Ale ogólnie rzecz biorąc, chciałem powiedzieć, że „wiedza z czarnej skrzynki” nie jest definicją kanoniczną, ale raczej narzędziem, i to narzędzie może być używane inaczej w kontekście wyników pozytywnych lub negatywnych, aby wyniki były bardziej znaczące.

V^{*}

$V^{*}$

V^{*}

$V^{*}$

— Boaz Barak,

Odłożyłem odpowiedź na Twój komentarz, ponieważ chciałem przeczytać więcej. W szczególności przeczytałem artykuł Yunga i Zhao (cytowany powyżej) i zauważyłem, że zastosowali czarną skrzynkę ZK w modelu RO, aby uzyskać pozytywny wynik, a ty powiedziałeś „nie ma sensu mówić, że model losowo-wyroczni symulator to „czarna skrzynka”. ” Czy ich wynik jest filozoficznie problematyczny, czy też powinniśmy rozluźnić definicję czarnej skrzynki?

— MS Dousti

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.

— David Cash
źródło

Dziękuję za odpowiedź David. Niezależnie od zdolności symulatora do zaprogramowania RO, powinien być w stanie je „monitorować”. Tak więc każde zapytanie wyroczni z V * marnuje czas M przynajmniej o czas. Twoim wielkim pomysłem jest zmiana modelu na „pozwól, aby symulator działał wielomianem czasowym w | x | i liczbą zapytań RO wydanych przez V *”. To nie jest standardowy model, ale uważam to za rozsądne rozwiązanie. Myślę jednak, że „giganci” w społeczności muszą najpierw uznać autentyczność takiego modelu ...

— MS Dousti

Czy możesz podać źródło, które precyzyjnie definiuje „model standardowy”? (Termin ten jest często używany jako synonim „żadnych przypadkowych wyroczni lub innych takich modyfikacji w modelu obliczeniowym”, ale nie sądzę, że o to ci chodziło). Oczekuję, że naszkicowałem definicję tego, co byłoby uważane za standardowe, a jeśli nie, możemy to odkryć bez żadnych „gigantów” aktywnie potwierdzających nasze rozumowanie.

— David Cash

Oczywiście, przez „model standardowy” miałem na myśli „standardową definicję” ZK w ramach modelu RO. Możesz odnieść się do pracy Rafaela Passa (cytowanej w pytaniu) lub jego pracy magisterskiej (zatytułowanej „Alternatywne warianty dowodów zerowej wiedzy”) lub pracy Wee w AsiaCrypt 2009 („Zero wiedzy w losowym modelu Oracle, ponownie”) . Żadne z nich nie zdefiniowało „czarnej skrzynki” ZK w modelu RO (wszyscy wspominali o wejściu pomocniczym ZK), chociaż żadne nie odnosiło się do „wielomianu uruchomionego w czasie w | x | i liczby zapytań RO wykonanych przez V *”. Dlatego myślę, że proponujesz nową definicję (Google it!)

— MS Dousti

Zobacz edytowane pytanie, aby uzyskać odniesienia.

— MS Dousti,