Provocado por uma pergunta que Greg Kuperberg me perguntou, estou me perguntando se existem documentos que definam e estudem classes de complexidade de idiomas que admitem vários tipos de provas de conhecimento . Classes como SZK e NISZK são extremamente naturais do ponto de vista da complexidade, mesmo se nos esquecemos completamente de zero conhecimento e apenas os definimos em termos de seus problemas completos de promessa. Por outro lado, ao pesquisar no Google 'provas de conhecimento', fiquei surpreso por não encontrar trabalhos ou notas de aula discutindo esse adorável conceito em termos de classes de complexidade.
Para dar alguns exemplos: o que se pode dizer sobre a subclasse de SZK∩MA∩coMA que consiste em todas as línguas L que admitem provas estatísticas de zero conhecimento para x∈L ou x∉L, que também são provas de conhecimento de uma testemunha que prova x ∈L ou x∉L? Certamente essa classe contém itens como log discreto, mas não podemos provar que ela contém isomorfismo de gráfico sem colocar GI no coMA. A classe abrange todo o SZK∩MA∩coMA? Pode-se também perguntar: se existem funções de mão única, então toda linguagem L∈MA∩coMA admite uma prova computacional de zero conhecimento, que também é uma prova de conhecimento de uma testemunha que prova x∈L ou x∉L? (Minhas desculpas se uma ou as duas tiverem respostas triviais - estou apenas tentando ilustrar o tipo de coisa que alguém poderia pergunte, uma vez que se decidiu analisar o PoK em termos teóricos da complexidade.)
fonte
Respostas:
Esta não é uma resposta real; Estou apenas compartilhando alguns resultados (que não se encaixam em um comentário).
Alguns problemas em aberto (talvez resolvidos, mas não que eu saiba) relacionados aos aspectos teóricos da complexidade dos PoKs:
Várias medidas de eficiência para ZK PoKs de uma relação específica com certa complexidade (por exemplo, uma relação em AM):
A complexidade das relações que admitem o ZK PoK com certas limitações, por exemplo, complexidades redondas limitadas (Itoh e Sakurai consideram o ZK PoK de rodada constante). Outro exemplo é quando o provador está no tempo polinomial: ele não pode usar a redução para 3 cores, pois não pode resolver relações NP-completas. Todos os problemas de NP-completo têm uma redução de Cook da pesquisa para a decisão. No entanto, pelo resultado de Bellare-Goldwasser citado acima, essas reduções não existem necessariamente para todas as línguas / relações NP.
Antes de concluir, permita-me mencionar que, na verdade, existem várias definições para PoKs, algumas das quais são citadas abaixo:
1) Tentativas iniciais: Feige, Fiat e Shamir ( J. Cryptology, 1988 ), Tompa e Woll ( FOCS 1987 ) e Feige e Shamir ( STOC 1990 ).
2) Padrão de fato: Bellare e Goldreich ( CRYPTO '92 ). Este artigo examina as tentativas iniciais de definir PoKs, observa suas deficiências e sugere uma nova definição que pode ser considerada como "a" definição de PoK. Essa definição tem uma natureza de caixa preta (o extrator de conhecimento tem acesso à caixa preta ao provador de trapaça).
3) PoKs conservadores: definidos por Halevi e Micali ( ePrint Archive: Report 1998/015 ), essa definição aumenta a definição anterior para garantir a viabilidade do comprovador. Também fornece uma definição para o conhecimento de um único provador, o que é bom ao responder à pergunta "o que significa dizer que P sabe alguma coisa?"
4) Argumentos do Conhecimento com Non Black-Box Extração: Como mencionado acima, a definição padrão de PoKs é caixa preta, o que torna impossível ter repostos e provas de conhecimento zero (ou argumentos) de conhecimento para idiomas não-triviais. Barak et al. ( FOCS 2001 ) fornecem uma definição que não é de caixa preta, que se baseia (mas difere) da definição de Feige e Shamir (STOC 1990) citada acima.
fonte