Debido a una pregunta que me hizo Greg Kuperberg, me pregunto si hay documentos que definan y estudien clases complejas de idiomas que admitan varios tipos de pruebas de conocimiento . Las clases como SZK y NISZK son extremadamente natural desde un punto de vista la complejidad, incluso si nos olvidamos por completo sobre el conocimiento cero y sólo les define en términos de sus problemas completas promesa. Por el contrario, al buscar en Google 'pruebas de conocimiento', me sorprendió no encontrar ningún documento o nota de conferencia que discutiera este encantador concepto en términos de clases de complejidad.
Para dar algunos ejemplos: ¿qué se puede decir sobre la subclase de SZK∩MA∩coMA que consta de todos los lenguajes L que admiten pruebas estadísticas de conocimiento cero para x∈L o x∉L, que también son pruebas de conocimiento de un testigo que prueba x ∈L o x∉L? Ciertamente, esta clase contiene cosas como el registro discreto, pero no pudimos probar que contiene isomorfismo gráfico sin poner GI en coMA. ¿La clase abarca todo SZK∩MA∩coMA? También se podría preguntar: si existen funciones unidireccionales, ¿todos los idiomas L∈MA∩coMA admiten una prueba computacional de conocimiento cero, que también es una prueba del conocimiento de un testigo que prueba x∈L o x∉L? (Mis disculpas si uno o ambos tienen respuestas triviales, solo estoy tratando de ilustrar el tipo de cosas que uno podría pregunte, una vez que uno decidió mirar PoK en términos teóricos de complejidad).
fuente
Respuestas:
Esta no es una respuesta real; Solo estoy compartiendo algunos resultados (que no caben en un comentario).
Algunos problemas abiertos (quizás resueltos, pero no que yo sepa) con respecto a los aspectos teóricos de la complejidad de los PoK:
Diversas medidas de eficiencia para ZK PoK de una relación específica con cierta complejidad (por ejemplo, una relación en AM):
Complejidad de las relaciones que admiten ZK PoK con ciertas limitaciones, digamos complejidades redondas limitadas (Itoh y Sakurai solo consideran ZK PoK de ronda constante). Otro ejemplo es cuando el probador es tiempo polinómico: no puede usar la reducción a 3-colorabilidad, ya que no puede resolver relaciones NP-completas. Todos los problemas de NP completo tienen una reducción de Cook desde la búsqueda hasta la decisión. Sin embargo, según el resultado de Bellare-Goldwasser citado anteriormente, tales reducciones no necesariamente existen para todos los idiomas / relaciones NP.
Antes de concluir, permítanme mencionar que en realidad hay varias definiciones para PoK, algunas de las cuales se citan a continuación:
1) Intentos iniciales: Feige, Fiat y Shamir ( J. Cryptology, 1988 ), Tompa y Woll ( FOCS 1987 ), y Feige y Shamir ( STOC 1990 ).
2) Estándar de facto: Bellare y Goldreich ( CRYPTO '92 ). Este documento examina los primeros intentos de definir PoK, observa sus deficiencias y sugiere una nueva definición que puede considerarse como "la" definición de PoK. Esta definición tiene una naturaleza de caja negra (el extractor de conocimiento tiene acceso de caja negra al probador de trampas).
3) PoK conservadores: definidos por Halevi y Micali ( archivo ePrint: Informe 1998/015 ), esta definición aumenta la definición anterior para garantizar la viabilidad de los probadores. También da una definición para el conocimiento de un solo probador, lo cual es bueno al responder la pregunta "¿qué significa decir que P sabe algo?"
4) Argumentos de conocimiento con No-Negro caja de trabajo: Como se mencionó anteriormente, la definición estándar de POKS es cuadro negro, lo que hace que sea imposible tener reajustables pruebas de conocimiento cero (o argumentos) del conocimiento de idiomas no triviales. Barak y col. ( FOCS 2001 ) proporcionan una definición que no es de caja negra, que se basa (pero difiere de) la definición de Feige y Shamir (STOC 1990) citada anteriormente.
fuente