La prueba de Goldreich et al. De que tres colorabilidad tiene cero pruebas de conocimiento utiliza un poco de compromiso para una coloración completa del gráfico en cada ronda [1]. Si un gráfico tiene vértices y bordes e , un hash seguro tiene b bits, y buscamos la probabilidad de error p , el costo total de comunicación es
sobre rondas. Usando un árbol Merkle revelado gradualmente, la comunicación total se puede reducir a O ( b e log n log ( 1 / p ) ) a costa de aumentar el número de rondas a O ( log n ) .
¿Es posible hacerlo mejor que esto, ya sea en términos de comunicación total o número de rondas?
Editar : Gracias a Ricky Demer por señalar el factor faltante de .
fuente
Actualización : Esta respuesta está obsoleta por mi otra respuesta, con límites completamente polilogarítmicos de referencias apropiadas.
Pensándolo bien, no hay necesidad de revelar el árbol Merkle gradualmente, por lo que la versión de comunicación inferior no necesita rondas adicionales. Los pasos de comunicación son
En la primera ronda, el probador envía solo el valor raíz, que no proporciona información, ya que está en hash con el nonce de la raíz. En la tercera ronda, no se transmite información sobre ningún nodo no expandido en el árbol binario, ya que dicho nodo se ha generado con un nonce en ese nodo. Aquí estoy asumiendo que el probador y el verificador están acotados computacionalmente y no pueden romper el hash.
Editar : Gracias a Ricky Demer por señalar el factor faltante de ee
fuente
Hay un aumento reciente en la actividad en argumentos sucintos no interactivos de conocimiento cero. Se sabe cómo, por ejemplo, construir un argumento NIZK para Circuit-SAT donde la longitud del argumento es un número constante muy pequeño de elementos de grupo (ver Groth 2010, Lipmaa 2012, Gennaro, Gentry, etc., Eurocrypt 2013, etc.). Basado en una reducción de NP, puede construir claramente un argumento para la colorabilidad 3 con la misma comunicación.
Por supuesto, este es un modelo diferente en comparación con su pregunta original; por ejemplo, en esos argumentos, la longitud de CRS es lineal en el tamaño del circuito y, en cierto sentido, puede considerarse como parte de la comunicación (aunque puede reutilizarse en muchos argumentos diferentes).
fuente
(Esto no cabe en un comentario).
Creo que ahora veo cómo demostrar que la salazón no necesariamente proporcionaH0
H0 H1 H0
H1 H0
|| H2
x z ((3⋅b)+6) y
m m=x||111...[b of them]...111||y||z ,
H2(m)=x||111...[b of them]...111||H1(m)||z
x r m x r m
H2(m)=x||111...[b of them]...111||H1(m)||x
m
H2(m)=
[b+3 bits whose values don't matter]||H1(m)||[3 bits whose values don't matter] .
un conocimiento honesto de verificador honesto.
Se tiene
.
fuente