Demostraciones en conocimiento cero
Miguel Angel Marco Buzunariz
Seminario Rubio de Francia, Zaragoza, 17/12/2022
Antes de empezar
- No soy experto en el tema.
- Hay algunas imprecisiones y/o incorrecciones por claridad.
- ¡Preguntad!
Ejemplo
Problema: Demostrar que conozco un isomorfismo entre estos dos grafos:
Ejemplo
Solución:
Ejemplo
Solución:
Desafío
Problema:
Demostrar que conozco un isomorfismo entre estos dos grafos sin revelarlo:
Desafío
Problema:
Demostrar que conozco un isomorfismo entre el grafo central y cada uno de los laterales:
Desafío
Problema:
Demostrar que conozco un isomorfismo entre el grafo central y cada uno de los laterales:
Desafío
Problema:
Demostrar que conozco un isomorfismo entre el grafo central y cada uno de los laterales:
Desafío
Problema:
Demostrar que conozco un isomorfismo entre el grafo central y cada uno de los laterales:
Desafío
Problema:
Demostrar que conozco un isomorfismo entre el grafo central y cada uno de los laterales:
Desafío
Problema:
Demostrar que conozco un isomorfismo entre el grafo central y cada uno de los laterales:
Desafío
Si realmente conozco el isomorfismo entre los dos grafos, puedo repetir este protocolo con tantos grafos como quiera,y pasar la prueba siempre.
Si no conozco el isomorfismo, y repetimos el proceso 100 veces, sólo tengo una probabilidad entre 1267650600228229401496703205376 de pasar todas las pruebas.
1606938044258990275541962092341162602522202993782792835301376 si lo hacemos 200 veces.
Pero la información que he dado no permite descubrir el isomorfismo que conozco.
Definiciones básicas
Sea \Sigma un conjunto finito de símbolos. Denotamos por \Sigma^* al conjunto de secuencias finitas de elementos de \Sigma.
Definición:
Un lenguaje \mathcal{L} es un subconjunto de \Sigma ^*.
Un lenguaje \mathcal{L} es de tipo NP si existe una máquina de Turing polinomial en la primera variable f: \Sigma ^*\times \Sigma^* \longrightarrow \{0,1\} tal que \mathcal{L}= \{x \in \Sigma ^* \mid \exists w \in \Sigma^*, f(x,w) = 1\}
Ejemplos:
- Problema del isomorfismo de grafos: \Sigma=\{0,1,2,3,4,5,6,7,8,9,(,)\}, X es el conjunto de parejas de grafos isomorfos, y w sería un isomorfismo de grafos.
- Problema del número compuesto: \Sigma=\{0,1,2,3,4,5,6,7,8,9\}, X es el conjunto de números naturales compuestos, y w sería un factor no trivial de un número.
- Problema de demostrabilidad: \Sigma=\{\forall,\exists,\rightarrow,\wedge,\vee,\cdots\}, X es el conjunto de frases bien formadas ciertas, y w es una demostración de una afirmación dada.
Demostraciones interactivas de conocimiento cero
P
r_p\leftarrow \$ \qquad x \qquad w
C_0
R_0(x,w,r_p,C_0)
C_1
…
\underrightarrow{\qquad x\qquad }
\underleftarrow{\qquad C_0\qquad }
\underrightarrow{\qquad R_0\qquad }
\underleftarrow{\qquad C_1\qquad }
…
V
x
r_v\leftarrow \$\quad C_0(x,r_v)
R_0
C_1(x,r_v,R_0)
…
M_v(x,r_v,R_0,\ldots ,R_n) \in \{0,1\}
Oráculo aleatorio
Definición:
Un oráculo aleatorio es una función O: X \to Y donde el valor de cada x\in X es elegido mediante un muestreo aleatorio uniforme en Y.
Es decir, calcular O(x) es realmente tomar un valor aleatorio de Y, con la única condición de que para el mismo valor, siempre obtenemos el mismo resultado.
Las funciones computables con máquinas Turing no son oráculos aleatorios, pero algunas funciones hash se pueden usar en la práctica como si lo fueran.
Heurística de Fiat-Shamir
P
r_p\leftarrow \$ \qquad x \qquad w
C_0(x,H(x))
R_0(x,w,r_p,C_0)
C_1(x,H(x||R_0),R_0)
R_1(x,w,r_p,C_0,C_1)
…
\underrightarrow{\qquad x,R_0,\ldots,R_n\qquad }
V
x,R_0,\ldots,R_n
M_v(x,R_0,\ldots ,R_n) \in \{0,1\}
Demostraciones no interactivas en conocimiento cero
Definición:
Dado un lenguaje NP \mathcal{L}\subseteq \Sigma^* dado por una función f, un par de máquinas Turing P, V que corren en tiempo polinomial se dice:
- Completo si \forall (x,w) \in \mathcal{L} \times \Sigma^* tal que f(x,w)=1, V(x,P(x,w))=1 (toda afirmación cierta se puede probar)
- Sólido si para toda máquina Turing P' existe un extractor polinomial E, tal que \forall x \in \Sigma^*, V(x,P'(x))=1 \Rightarrow f(x,E(Tr(P',x)))=1 (si alguien es capaz de dar una demostración convincente de una afirmación, puede también extraer un testigo).
- Conocimiento Cero si existe una máquina Turing S tal que para toda \mathcal{A}, Pr(\mathcal{A}(\pi) = 1\mid \pi = P(x,w))= Pr(\mathcal{A}(\pi)=1 \mid \pi = S(x)) (no se puede distinguir entre una prueba generada con un testigo y una prueba generada sin él).
Teorema:
No pueden existir esquemas de demostración perfectamente completos, sólidos y en conocimiento cero.
¡Pero sí que existen si relajamos la condición de solidez exigiendo sólo “con probabilidad arbitrariamente pequeña”!
Protocolo Pinocho
Curvas elípticas
Sea p un primo, y a,b \in \mathbb{F}_p tales que 4a^3+27b^2\neq 0.
El conjunto
G = \{(x,y)\in \mathbb{F}_p \mid y^2=x^3+ax+b\} \cup \{\infty\}
es una curva elíptica.
Admite una estructura de grupo
Problema del logaritmo discreto.
Tomar p un primo grande, G una curva elíptica sobre \mathbb{F}_p de orden primo q, y g\in G un generador.
Tenemos un isomorfismo de grupos:
\begin{array}{rcl} \mathfrak{h}:\mathbb{F}_q & \longrightarrow & G \\ n & \mapsto & n\cdot g \end{array}
Denotaremos \mathfrak{h}(n) como [n] . . .
Dado n\in \mathbb{F}_q, [n] se puede calcular con a lo sumo 2\lceil\log_2(q)\rceil operaciones en el grupo.
Hipótesis:
No hay algoritmo polinomial en q que calcule \mathfrak{h}^{-1}.
Emparejamientos de grupos
Los emparejamientos de Weil y Tate nos dan el siguiente diagrama conmutativo
\begin{CD} \mathbb{F}_q \times \mathbb{F}_q @>\cdot>> \mathbb{F}_q \\ @V{\mathfrak{h}\times \mathfrak{h}}VV @VV{\mathfrak{h}_T}V \\ G\times G @>p>> G_T \end{CD}
donde G_T es el grupo multiplicativo de raíces q-ésimas de la unidad en \overline{\mathbb{F}_p}.
Hipótesis del conocimiento del exponente.
Definición:
Dos elementos (\mathfrak{x},\mathfrak{y}) del grupo G forman un \alpha-par si \mathfrak{y}=\alpha\cdot \mathfrak{x}.
Dado (\mathfrak{x},\mathfrak{y}) un \alpha-par, se puede obtener un nuevo \alpha-par tomando \beta\in \mathbb{F}_q y calculando (\beta\cdot \mathfrak{x} ,\beta \cdot \mathfrak{y}).
Notar que se puede comprobar si el par generado es un \alpha-par usando el emparejamiento.
Dados (\mathfrak{x}_1,\mathfrak{y}_1),\ldots(\mathfrak{x}_l,\mathfrak{y}_l) una lista de \alpha-pares, se puede obtener un nuevo \alpha-par tomando
({\beta_1}\cdot \mathfrak{x}_1+\cdots +{\beta_l}\cdot \mathfrak{x}_l,{\beta_1}\cdot \mathfrak{y}_1 +\cdots +{\beta_l}\cdot \mathfrak{y}_l) con \beta_i\in \mathbb{F}_q.
Hipótesis:
Para cualquier algoritmo que tome como inputs una lista de \alpha-pares (\mathfrak{x}_1,\mathfrak{y}_1),\ldots(\mathfrak{x}_l,\mathfrak{y}_l) (sin conocer el valor de \alpha) de como respuesta un nuevo \alpha-par (\mathfrak{x}',\mathfrak{y}') existe un extractor en tiempo polinomial que devuelve valores (\beta_1,\ldots,\beta_l) tales que (\mathfrak{x}',\mathfrak{y}')=({\beta_1}\cdot \mathfrak{x}_1+\cdots +{\beta_l}\cdot \mathfrak{x}_l,{\beta_1}\cdot \mathfrak{y}_1 +\cdots +{\beta_l}\cdot \mathfrak{y}_l).
Es decir, si alguien ha generado un \alpha-par a partir de otros dados, conoce los exponentes usados para construirlo.
Evaluación ciega de polinomios
Situación:
- A conoce un valor n\in \mathbb{F}_q.
- B conoce un polinomio f\in \mathbb{F}_q[x] de grado d.
- Queremos calcular [f(n)]
\in G,
- De forma que ambos estén de acuerdo en la correción del resultado,
- Sin que B conozca n,
- Sin que A conozca f.
Evaluación ciega de polinomios
A
n
\alpha\leftarrow \$
\{([n^i],[\alpha n^i])\}_{0\leq i\leq d}
([p(n)], [\alpha p(n)])
\underrightarrow{\quad \{([n^i],[\alpha n^i])\}_{0\leq i\leq d} \quad}
\underleftarrow{\quad [p(n)], [\alpha p(n)] \quad }
B
f=c_0+c_1 x+\cdots + c_d x^d
\{([n^i],[\alpha n^i])\}_{0\leq i\leq d}
c_0\cdot [1] +\cdots + c_d\cdot [n^d]
c_0\cdot [\alpha ]+ \cdots+ c_d\cdot [\alpha n^d]
Evaluación ciega de polinomios
- B puede comprobar que los ([n^i],[\alpha n^i]) son todos \alpha-pares para el mismo \alpha usando el emparejamiento.
- Además, B puede
usar el emparejamiento y ([1],[n]) para
comprobar que ([n^i],[n^{i+1}]) es un
n-par.
- Luego sabe que está evaluando el polinomio en algún valor.
- A podría comprobar
que la respuesta de B es un \alpha-par usando el emparejamiento (incluso
si hubiera olvidado el valor de \alpha).
- Por la hipótesis de conocimiento del exponente, A puede concluir que B conoce los coeficientes del polinomio.
Comprobando relaciones entre polinomios
Ahora P quiere convencer a V de que conoce tres polinomios f_1,f_2,f_3 de grado d, tales que f_1(x) f_2(x) = f_3(x) para x=0,1,\ldots, d.
Equivalentemente, P conoce un polinomio R de grado d-1 tal que f_1 f_2-f_3\cdot 1 = R\cdot Z con Z = x(x-1)\cdots (x-d)
V elige n\in\mathbb{F}_q al azar y realizan el protocolo anterior para que P genere [f_1(n)],[f_2(n)],[f_3(n)],[R(n)].
V calcula [T(n)] y comprueba que p([f_1(n)],[f_2(n)])=p([f_3(n)],[1])+p([R(n)],[Z(n)]).
Si los polinomios que conoce P cumplen la relación, el resultado cumplirá la relación.
Si no la cumplen, f_1(n) f_2(n)-f_3(n)-R(n) T(n) sólo se anulará con probabilidad \frac{1}{q}.
Programas aritméticos cuadráticos
Considerar S el conjunto de soluciones del sistema de ecuaciones sobre \mathbb{F}_q: (x_0 a_0^0+\cdots+x_m a_m^0)(x_0 b_0^0+\cdots+x_m b_m^0)=(x_0 c_0^0+\cdots+x_m c_m^0) \\ (x_0 a_0^1+\cdots+x_m a_m^1)(x_0 b_0^1+\cdots+x_m b_m^1)=(x_0 c_0^1+\cdots+x_m c_m^1) \\ \vdots \\ (x_0 a_0^d+\cdots+x_m a_m^d)(x_0 b_0^d+\cdots+x_m b_m^d)=(x_0 c_0^d+\cdots+x_m c_m^d)
Tomando l<m, tenemos un lenguaje \mathcal{L}_{S,l}:=\{(x_1,\ldots,x_l) \mid (x_1,\ldots,x_l,x_{l+1},\ldots,x_m) \in S \}
Teorema:
Para todo lenguaje de tipo NP se puede reducir polinomialmente a \mathcal{L}_{S,l} para algún (S,l).
Ecuaciones polinomiales
Sea A_i(T) el interpolador de Lagrange de \{(0,a_i^0),\ldots,(d,a_i^d)\}. Análogamente B_i(T) y C_i(T).
El sistema anterior se expresa como
(x_0 A_0(t)+\cdots +x_m A_m(t))(x_0 B_0(t)+\cdots +x_m B_m(t)) = (x_0 C_0(t)+\cdots +x_m C_m(t))
para t=0,\ldots, d.
Equivalentemente, existe R(T) tal que
(x_0 A_0(T)+\cdots +x_m A_m(T))(x_0 B_0(T)+\cdots +x_m B_m(T)) =\\ =` (x_0 C_0(T)+\cdots +x_m C_m(T)) + R(T) Z(T)
con
Z(T) = T\cdot (T-1)\cdots (T-d)
Trusted Setup
- Elegir al azar r_a,r_b,n,\alpha_a,\alpha_b,\alpha_c, \alpha_d,\beta\in \mathbb{F_q}. Calcular r_c=r_a r_b.
- Calcular y revelar:
- Para cada k\in\{1,\ldots,m\}
- [r_a A_k(n)], [r_b B_k(n)], [r_c C_k(n)]
- Para cada k\in\{l+1,\ldots,m\}:
- [\alpha_a r_a A_k(n)], [\alpha_b r_b B_k(n)], [\alpha_c r_c C_k(n)]
- [\beta (r_a A_k(n)+r_b B_k(n)+r_c C_k(n))]
- \{[n^i]\}_{i=0,\ldots,d-1}, \{[\alpha_d n^i]\}_{i=0,\ldots,d-1}
- [r_c Z(n)]
- Para cada k\in\{1,\ldots,m\}
- Destruir el resto de la información.
Prueba y verificación
Prueba
- P calcula R(T), [A(n)] = \sum_{i=l+1}^m x_i \cdot [A_i(n)], [B(n)] = \sum_{i=l+1}^m x_i \cdot [B_i(n)] y [C(n)] = \sum_{i=l+1}^m x_i \cdot[C_i(n)]
- P calcula los pares ([r_a A(n)],[\alpha_a r_a A(n)]), ([r_b B(n)],[\alpha_b r_b B(n)]) y ([r_c C(n)],[\alpha_c r_c C(n)]).
- P calcula [\beta(r_aA(n) +r_b B(n) +r_c C(n)))] y ([R(n)],[\alpha_d R(n)]).
- Envía lo anterior a V, junto con x_1,\ldots,x_l.
Verificación
- Comprueba que ([R(n)],[\alpha_d R(n)]) es un \alpha_d-par.
- Comprueba que ([r_a A(n)],[\alpha_a r_a A(n)]) es un \alpha_a-par. Análogamente para ([r_b B(n)],[\alpha_b r_b B(n)]) y ([r_c C(n)],[\alpha_c r_c C(n)]).
- Comprueba que ([r_aA(n)+r_bB(n)+r_cC(n)],[\beta(r_aA(n)+r_bB(n)+r_cC(n))]) es un \beta-par.
- Calcula [r_a A_v(n)] = \sum_{i=0}^l x_i\cdot [r_a A_i(n)] + [r_aA(n)], análogamente [r_b B_v(n)] y [r_b C_v(n)] y comprueba que p([r_a A_v(n)],[r_b B_v(n)])-p([r_c C_v(n)],[1]) = p([R(n)],[r_c Z(n)])
Resumen
- El protocolo Pinocho permite dar demostraciones de cualquier enunciado en un lenguaje NP dando sólo ocho puntos de una curva elíptica.
- Estas demostraciones son sólidas bajo asumciones criptográficas estándar (más conocimiento del exponente).
- Además, son en conocimiento cero perfecto (haciendo una pequeña modificación al esquema visto).
- Requiere de un setup de confianza.
- Hay variantes que requieren sólamente tres puntos de la curva.