Dlaczego Feige-Fiat-Shamir nie jest zerową wiedzą bez znaków?

W rozdziale 10 HAC (10.4.2) widzimy dobrze znany protokół identyfikacyjny Feige-Fiat-Shamir oparty na dowodzie zerowej wiedzy przy użyciu (przypuszczalnej) trudności w wyodrębnieniu modulo pierwiastków kwadratowych z kompozytu, który jest trudny do uwzględnienia. Podam schemat własnymi słowami (i mam nadzieję, że dobrze to zrobię).

Zacznijmy od prostszego schematu: niech $n$ będzie liczbą całkowitą Bluma (więc $n=pq$ a każdy $p$ i $q$ to 3 mod 4) o wystarczająco dużych rozmiarach, że faktoring jest trudny do rozwiązania. Ponieważ $n$ jest liczbą całkowitą Bluma, połowa elementów $Z_n^*$ ma symbol Jacobiego +1, a druga połowa ma -1. W przypadku elementów +1 połowa z nich ma pierwiastki kwadratowe, a każdy element mający pierwiastek kwadratowy ma cztery z nich, dokładnie jeden sam jest kwadratem.

Teraz Peggy wybiera losowy element $s$ z $Z_n^*$ i ustawia $v=s^2$ . Następnie wysyła $v$ do Victora. Dalej jest protokół: Victor chce sprawdzić, czy Peggy zna pierwiastek kwadratowy z $v$ i Peggy chce udowodnić mu ją bez ujawniania coś o $s$ poza faktem, że zna takie $s$ .

1. Peggy wybiera losowy $r$ w $Z_n^*$ i wysyła $r^2$ do Victor.
2. Victor może wysłać $b=0$ lub $b=1$ powrotem do Peggy.
3. Peggy wysyła do Victor.$rs^b$

Victor może sprawdzić, czy Peggy wysłała prawidłową odpowiedź, podnosząc do kwadratu otrzymane wyniki i porównując z poprawnym wynikiem. Oczywiście powtarzamy tę interakcję, aby zmniejszyć prawdopodobieństwo, że Peggy jest po prostu szczęśliwym zgadywaczem. Ten protokół jest nazywany ZK; dowód można znaleźć w różnych miejscach (np. notatki z wykładu Boaza Baraka ).

Kiedy rozszerzymy ten protokół, aby uczynić go bardziej wydajnym, nazywa się Feige-Fiat-Shamir; jest bardzo podobny do powyższego. Zaczynamy Peggy od losowych wartości s 1 ⋯ s k i losowych znaków t 1 = ± 1 , ⋯ t k = ± 1, ona publikuje ich kwadraty jako v 1 = t 1 s 2 1 , ⋯ , v k = t k s 2 k . Innymi słowy, losowo negujemy niektóre z $k$$s_1\cdots s_k$$t_1 = \pm 1, \cdots t_k = \pm 1$$v_1=t_1s_1^2, \cdots, v_k = t_ks_k^2$ . Teraz$v_i$

1. Peggy wybiera losowy w Z * n i wysyła R 2 do Victor.$r$$Z_n^*$$r^2$
2. Victor equiprobably wysyła wartości b I z { 0 , 1 } tyłu Peggy.$k$$b_i$$\{0,1\}$
3. Peggy wysyła do Victora.$r\Pi_{i=1}^ks_i^{b_i}$

Moje pytanie: Dlaczego są podpisać bity konieczne? W nawiasach HAC zauważa, że ​​istnieją one jako wymóg techniczny wymagany do udowodnienia, że ​​nie ujawniono żadnych tajnych informacji. Strona Wikipedii dla Feige-Fiat-Shamir (która nie zgadza się z protokołem) sugeruje, że bez tego wyciekło trochę.$t_i$

Nie mogę znaleźć ataku, który wyciągnąłby coś z Peggy, gdyby pominęła znaki.

Protokół identyfikacyjny Feige-Fiat-Shamir (FFS) jest dowodem wiedzy (PoK), w którym przysłowie (Peggy) dowodzi swojej wiedzy pierwiastkami kwadratowymi podanych danych wejściowych weryfikatorowi (Victor).

FFS chce odróżnić PoK od dowodów członkostwa w języku , w których Peggy udowadnia, że ​​dane wejściowe mają jakąś właściwość (bardziej formalnie, dane wejściowe należą do określonego języka).

Jeśli nie użyjemy znaków ujemnych, możliwe, że dane wejściowe nie mają pierwiastka kwadratowego. Na przykład liczba 20 nie ma pierwiastka kwadratowego mod 21. Ponieważ rozróżnianie kwadratów i elementów niebędących kwadratami jest znanym trudnym problemem , FFS unika go, pozwalając, aby wartość wejściowa była plusem lub minusem pewnej liczby podniesionej do kwadratu. W ich własnych słów (zmienił się ani trochę):

Umożliwiając być dodatnim lub ujemnym modułem kwadratowym liczby całkowitej Blum , upewniamy się, że v i może rozciągać się na wszystkie liczby z symbolem Jacobiego + 1 mod n, a zatem s i istnienie (z punktu widzenia V) niezależnie od o charakterze v i , jak jest to wymagane w nieograniczonych wejściowych dowodach wiedzy o zerowej wiedzy.$v_i$$v_i$ $+1 \bmod n$$s_i$$v_i$

Przez nieograniczone wejściowe dowody wiedzy o zerowej wiedzy , rozumieją ZK PoK, którego odpowiedni dowód przynależności do języka jest trywialny; tzn. V może sam zdecydować, że wejście jest plusem lub minusem jakiegoś kwadratu (po prostu sprawdzając symbol Jacobiego).