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.
Odpowiedzi:
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.
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.