La equivalencia de dos definiciones de integridad y solidez en sistemas de prueba interactivos

11

La integridad y solidez en los sistemas de prueba interactivos se definen informalmente como:

  • Integridad: si una afirmación es verdadera, el probador honesto puede convencer al verificador honesto de este hecho whp .

  • Solidez: si una declaración es falsa, el probador de trampa no puede convencer al verificador honesto (de la validez de la declaración falsa) whp

El término "whp" se interpreta como "con una probabilidad mayor que (digamos) 2/3" o "con una probabilidad mayor que el recíproco de cualquier polinomio". Parece irrelevante para la siguiente discusión qué interpretación de "whp" elegir.

La parte difícil es cómo se calcula la probabilidad: en algunas fuentes, la probabilidad se toma sobre las monedas aleatorias tanto del probador como del verificador. En otras fuentes, la probabilidad solo se calcula sobre las monedas aleatorias del verificador. Esto último generalmente se justifica como: "sean cuales sean las monedas aleatorias del probador, el verificador toma la decisión correcta".

Para mí, ambas definiciones de probabilidad parecen equivalentes; Sin embargo, no puedo probar esto. Estoy en lo cierto? ¿Puedes demostrar que son equivalentes?

cc.complexity-theory interactive-proofs Increíble
fuente
2
También debe considerar si se refiere a monedas "públicas" o monedas "privadas". En la configuración de monedas públicas, tanto el verificador como el verificador conocen los resultados de las elecciones aleatorias, y para las monedas privadas, el verificador no conoce las elecciones aleatorias del verificador. En este último caso, solo te importa lo que hace el verificador sin mirar al probador porque el probador simplemente no sabe los lanzamientos de monedas al azar.
Marcos Villagra
@Marcos: Eche un vistazo a la definición original de pruebas interactivas, que es una moneda "privada" en la naturaleza. La última oración de la primera columna en la página 293, que está subrayada, establece que "las probabilidades se toman solo sobre los lanzamientos de monedas de B". (Aquí, B es el verificador.) Por otro lado, la versión de diario del documento mencionado anteriormente permite que las probabilidades se tomen sobre los lanzamientos de monedas de ambas partes. Esta podría ser la fuente de confusión, ¿verdad?
MS Dousti
@Sadeq: Ya veo, no sabía sobre esa diferencia entre el diario y las versiones de la conferencia. Aún así, para las monedas privadas, no veo el punto de tener en cuenta los lanzamientos de monedas de prueba, porque podría decidir no decirle al verificador al respecto. El verificador es el encargado de decidir la aceptación o el rechazo, y es posible que no sepa qué está haciendo el probador.
Marcos Villagra
1
@Marcos: Tienes razón, pero el mismo razonamiento se aplica a las pruebas de monedas públicas; dado que en esos sistemas los lanzamientos de monedas de prueba son privados (solo las monedas del verificador son públicas). En general, uno puede considerar un probador determinista: dado que el probador es todopoderoso, no necesita aleatoriedad y puede elegir la respuesta óptima de manera determinista. Sin embargo, este tipo de razonamiento no funciona si consideramos los sistemas de conocimiento cero, en los que la estrategia del probador debería ser probabilística (de lo contrario, su conocimiento se filtraría).
MS Dousti
2
(Cont.) Si el comprobador es aleatorio, entonces creo que la formulación adecuada es calcular la probabilidad sobre ambos lanzamientos de monedas del comprobador y el verificador: mientras que como dijo Marcos, el verificador está a cargo de la decisión final, su decisión es hecho (entre otros) basado en los mensajes que provienen del probador. Dado el hecho de que el probador es aleatorio, su lanzamiento de monedas ciertamente afecta los mensajes que envía. Por lo tanto, los lanzamientos de monedas del probador afectan la probabilidad de aceptación. Estoy en lo cierto?
MS Dousti

Respuestas:

6

El probador es "todopoderoso y posee recursos computacionales ilimitados", por lo que no necesita bits aleatorios. Por lo tanto, la única aleatoriedad es la aleatoriedad del verificador.

Si el probador usa bits aleatorios, debe reemplazarlos con la cadena de bits aleatoria que es más probable que haga que el verificador acepte (esto es cierto tanto para el probador honesto como para cualquier deshonesto). Además, el probador puede determinar esta cadena de bits óptima porque el probador es "todopoderoso".

Tyson Williams
fuente
1
Como dije en un comentario anterior, esto solo es cierto cuando considera solo las pruebas interactivas. Sin embargo, las cosas son muy diferentes si tiene en cuenta otras propiedades, como el "conocimiento cero", que está naturalmente conectado a las pruebas interactivas.
MS Dousti
1
Continúa: Específicamente, Oren demostró lo siguiente: "... bajo la definición de entrada auxiliar de conocimiento cero, la aleatoriedad del probador es esencial para la no trivialidad de los sistemas de prueba de conocimiento cero. En otras palabras, cualquier lenguaje que tiene un sistema de prueba de conocimiento cero de entrada auxiliar en el que el probador es determinista para BPP ". (Consulte la sección 4.5 de Oren para obtener más información). Por lo tanto, no siempre puede suponer que P es determinista.
MS Dousti