¿Por qué Feige-Fiat-Shamir no es conocimiento cero sin bits de signo?

En el capítulo 10 de HAC (10.4.2) , vemos el conocido protocolo de identificación Feige-Fiat-Shamir basado en una prueba de conocimiento cero que utiliza la (presunta) dificultad de extraer el módulo de raíces cuadradas de un compuesto que es difícil de factorizar. Daré el esquema en mis propias palabras (y con suerte lo haré bien).

Comencemos con un esquema más simple: sea $n$ un número entero de Blum (entonces $n=pq$ y cada una de $p$ y $q$ es 3 mod 4) de tamaño suficientemente grande para que la factorización sea intractible. Como $n$ es un número entero de Blum, la mitad de los elementos de $Z_n^*$ tienen el símbolo de Jacobi +1 y la otra mitad tiene -1. Para los elementos +1, la mitad de ellos tienen raíces cuadradas, y cada elemento que tiene una raíz cuadrada tiene cuatro de ellos, exactamente uno es un cuadrado.

Ahora Peggy selecciona un elemento aleatorio $s$ de $Z_n^*$ y establece $v=s^2$ . Luego envía $v$ a Victor. El siguiente es el protocolo: Victor desea verificar que Peggy conoce una raíz cuadrada de $v$ y Peggy quiere demostrar a él sin revelar nada acerca de $s$ más allá del hecho de que ella sabe Tal $s$ .

1. Peggy elige un aleatorio $r$en $Z_n^*$ y envía $r^2$ a Victor.
2. Víctor equiparobablemente envía $b=0$ o $b=1$ regreso a Peggy.
3. Peggy envía $rs^b$ a Victor.

Victor puede verificar que Peggy ha enviado la respuesta correcta al cuadrar lo que recibe y compararlo con el resultado correcto. Por supuesto, repetimos esta interacción para reducir la posibilidad de que Peggy sea una adivinadora afortunada. Se afirma que este protocolo es ZK; Una prueba se puede encontrar en varios lugares (por ejemplo, las notas de clase de Boaz Barak ).

Cuando ampliamos este protocolo para hacerlo más eficiente, se llama Feige-Fiat-Shamir; Es muy similar a lo anterior. Comenzamos Peggy con valores aleatorios s 1 ⋯ s k y signos aleatorios t 1 = ± 1 , ⋯ t k = ± 1 ella publica sus cuadrados como v 1 = t 1 s 2 1 , ⋯ , v k = t k s 2 k . En otras palabras, negamos aleatoriamente algunas de las $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$ . Ahora$v_i$

1. Peggy elige un aleatorio en Z ∗ n y envía r 2 a Victor.$r$$Z_n^*$$r^2$
2. Victor envía equiparobablemente valores b i desde { 0 , 1 } de regreso a Peggy.$k$$b_i$$\{0,1\}$
3. Peggy envía a Victor.$r\Pi_{i=1}^ks_i^{b_i}$

Mi pregunta: ¿Por qué son la es necesario firmar los bits? Entre paréntesis, HAC señala que están allí como un requisito técnico requerido para demostrar que no se filtró información secreta. La página de Wikipedia para Feige-Fiat-Shamir (que hace que el protocolo sea incorrecto) implica que sin esto se filtró un poco.$t_i$

No puedo encontrar un ataque que extraiga nada de Peggy si omite los signos.

El protocolo de identificación Feige-Fiat-Shamir (FFS) es una prueba de conocimiento (PoK), en el que el probador (Peggy) demuestra su conocimiento de las raíces cuadradas de la entrada dada al verificador (Victor).

FFS quiere discriminar PoK de las pruebas de membresía en el idioma , en el que Peggy demuestra que la entrada tiene alguna propiedad (más formalmente, la entrada pertenece a un determinado idioma).

Si no usamos los signos negativos, es posible que las entradas no posean ninguna raíz cuadrada. Por ejemplo, el número 20 no tiene ninguna raíz cuadrada mod 21. Dado que distinguir cuadrados y no cuadrados es un problema difícil famoso , FFS lo evita permitiendo que la entrada sea el más o menos de algún número al cuadrado. En sus propias palabras (cambiado un poco):

$v_i$$v_i$ s i v $+1 \bmod n$$s_i$$v_i$

Por pruebas de conocimiento de conocimiento cero de entrada sin restricciones , se refieren a un ZK PoK cuya prueba de pertenencia lingüística correspondiente es trivial; es decir, V puede decidir por sí mismo que la entrada es el más o menos de algún cuadrado (simplemente marcando el símbolo de Jacobi).