symulacja w linii prostej

11

Czy jakieś ciało zna jakieś dobre odniesienie do znaczenia symulacji liniowej? Obecnie jestem głęboko w strukturze Universal Composability (UC) Canetti, ale nie mogę znaleźć żadnego dobrego odniesienia do znaczenia symulacji w linii prostej. Każda pomoc jest mile widziana.

Yasser Sobhdel
źródło

Odpowiedzi:

10

Tutaj „linia prosta” kontrastuje z „przewijaniem”. Symulator jest „liniowy”, jeśli nie „przewija” strony, dla której wykonuje symulację.

Na przykład w protokole zerowej wiedzy symulator zwykle przewija „weryfikator”. W sensie „linii prostej” przewijanie nie występuje.

Po raz pierwszy zobaczyłem termin „symulator liniowy” w pracy Rafaela Passa ( O Deniabililty w Common Reference String i Random Oracle Models. (CRYPTO'03) ) i mgr inż. praca dyplomowa ( Alternatywne warianty dowodów zerowej wiedzy ).

Edycja: Znalazłem wcześniejszy artykuł: Współbieżna zerowa wiedza: Ograniczanie potrzeby ograniczeń czasowych autorstwa Cynthii Dwork i Amit Sahai, który pochodzi z 1998 r. Więcej wskazówek można znaleźć w komentarzu Alona Rosen poniżej.

MS Dousti
źródło
Nie znam terminu „symulator linii prostej”, ale dla mnie to, że „linia prosta” kontrastuje z „rozgałęzieniem”, analogicznym do logiki czasowej w funkcji czasu rozgałęzienia i równoważnością śledzenia w porównaniu z równoważnością bisimulacji (rozgałęzienia). Czy coś w tym jest?
Dave Clarke
Nie wydaje mi się. Znalazłem inne odniesienie, które jest zgodne z moją definicją.
MS Dousti
Wyjaśnienie Sadeqa jest takie samo, jak w jakimkolwiek kontekście, w którym słyszałem te terminy. Oto kilka notatek z wykładu z zajęć z Adv Crypto z zeszłego roku, które omawiają ten temat; w szczególności patrz roszczenie 8.
Daniel Apon
Deterministyczny brzmi jak możliwy synonim.
Dave Clarke
5
Wcześniejsze zastosowania koncepcji symulowalności linii prostych (choć być może nie w ramach tej terminologii) można znaleźć w: (1) Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali: Resetowalna zerowa wiedza (streszczenie rozszerzone). STOC 2000: 235–244 i (2) Ran Canetti, Marc Fischlin: Zobowiązania uniwersalne. CRYPTO 2001: 19–40. Pojęcie pojawia się w definicji UC, ponieważ nie można przewinąć „środowiska”. Pojawił się wcześniej w innym kontekście w równoległej wiedzy zerowej, gdzie symulator przewijania może mieć kłopoty.
Alon Rosen
3

Nie ma formalnej definicji tego, co to znaczy być symulatorem linii prostej. To tylko intuicyjny pomysł, który można wykorzystać do opisania rzeczy w nieformalny sposób. Jestem bardzo sceptycznie nastawiony do tego, czy można nawet zdefiniować, co oznacza brak przewijania maszyny. Rzeczywiście, przewijanie maszyny samo w sobie jest nieformalnym terminem! Naprawdę rozumiemy przez przewijanie maszyny, że możemy zbadać wiele możliwych ścieżek wykonania maszyny z danego stanu. Formalne argumenty opierają się następnie na liczbie takich egzekucji, które musimy zbadać, zanim będziemy mogli uzyskać zapadnię lub inne informacje, których potrzebujemy, aby kontynuować nasz dowód.


źródło