A proof complexity perspective on effectively zero-knowledge proofs

Resumo Técnico: Uma Perspectiva da Complexidade de Provas sobre Provas de Conhecimento Zero Eficazes

Enunciado do Problema
O artigo aborda o conceito de provas de "conhecimento zero eficaz" (ZK - effectively zero-knowledge), uma variante introduzida por Ilango [4] que se baseia em ideias da lógica matemática. A formulação original de Ilango evitava noções lógicas padrão (como teorias, provabilidade e consistência) em favor de simulações algorítmicas. O artigo identifica uma limitação específica na definição de Ilango: a propriedade de que uma prova é "indistinguível da verdade" está incorporada diretamente na definição do provador, em vez de ser derivada como uma consequência. Além disso, a construção de provas de ZK eficazes baseia-se em conjecturas tanto da criptografia quanto da complexidade de provas, especificamente em relação à existência de tautologias proposicionais difíceis para sistemas de prova específicos. O artigo busca reformular este conceito utilizando a linguagem da lógica e da complexidade de provas para fornecer provas de existência mais simples e para esclarecer a relação entre a definição do provador e a propriedade de "indistinguibilidade".

Metodologia
O autor utiliza o arcabouço da complexidade de provas e da aritmética limitada, utilizando especificamente teorias capazes de raciocinar sobre computações e provas (tais como $S^1_2$ e $S_2$). A metodologia envolve:

1. Reformulação Lógica: Substituição de simulações algorítmicas por teorias formais $T$ e suas extensões $T^*$. O provador é definido em relação a uma teoria $T$, e a propriedade ZK é caracterizada pela não existência de provas curtas dentro de $T$ para a não existência de um simulador.
2. Teoria dos Modelos da Aritmética: As provas utilizam modelos não-padrão de aritmética e o "princípio do transbordamento" (overspill principle). Especificamente, o artigo baseia-se em um teorema de K.-Pudlák [13] que vincula a não existência de provas proposicionais curtas em um sistema de prova $P(T)$ à existência de extensões de modelos de aritmética limitada onde certas fórmulas são satisfatíveis.
3. Geradores de Complexidade de Prova: Na seção final, o artigo explora a transformação de provas de ZK eficazes em provas de conhecimento zero "genuínas". Isso é alcançado substituindo a sequência de tautologias difíceis $\Psi$ por geradores de complexidade de prova. A construção assume a existência de "demi-bits" (um tipo de gerador difícil definido por Rudich [16]) e permite que o provador e o verificador compartilhem uma string aleatória comum.

Contribuições Principais e Resultados

• Reformulação do Provador: O artigo define um provador $Prover[A, B, \Psi]$ em relação a uma teoria $T$. A propriedade ZK é definida não pela existência imediata de um simulador, mas pela condição de que, para qualquer tamanho polinomial $d$, a teoria $T$ não pode provar (com provas de tamanho superpolinomial) que nenhum simulador de tamanho $n^d$ existe.
• Derivação de "Indistinguibilidade da Verdade": Um resultado primário (Teorema 2.4) demonstra que a propriedade de ser "indistinguível da verdade" é uma consequência da definição de ZK em relação a uma teoria, em vez de um pré-requisito. Se uma afirmação $S(n)$ é provável em $T$ como consequência da existência de um simulador, e o provador é ZK em relação a $T$, então $S(n)$ deve ser verdadeira para todos os $n$, exceto para um número finito de casos. Isso contrasta com a definição de Ilango, onde isso era parte dos requisitos axiomáticos do provador.
• Prova de Existência (Teorema 2.2): O artigo prova que, se $A, B$ formam um esquema de Indistinguibilidade de Testemunha Não-Interativa (NIWI - Non-Interactive Witness Indistinguishable) e a sequência de tautologias $\Psi$ é difícil para o sistema de prova $P(T^*)$, então o provador construído é ZK em relação a $T$. A prova utiliza modelos não-padrão para mostrar que a existência de um simulador é consistente com a teoria, thereby impedindo provas curtas de sua não existência.
• Transformação para ZK Genuína (Seção 3): O artigo mostra que o conceito de ZK eficaz pode ser convertido em provas de conhecimento zero padrão (onde um simulador realmente existe) sob suposições específicas. Ao utilizar geradores de complexidade de prova derivados de "demi-bits" e permitir que as partes compartilhem uma string aleatória comum, a dificuldade das fórmulas subjacentes pode ser garantida uniformemente. Isso contorna a necessidade de o provador e o verificador confiarem em uma sequência específica de tautologias sem verificação.

Significância e Alegações
O artigo afirma oferecer uma "prova simples" da existência e das propriedades fundamentais das provas de conhecimento zero eficazes ao alavancar a estrutura lógica da complexidade de provas. Sua significância reside em:

1. Clareza Conceitual: Esclarece os fundamentos lógicos das provas de ZK eficazes, mostrando que a propriedade de "indistinguibilidade da verdade" é uma consequência derivável da definição do provador em relação a uma teoria.
2. Ponte entre Lógica e Criptografia: Conecta explicitamente a noção criptográfica de indistinguibilidade de testemunha com a noção lógica de extensões de modelos e a não existência de provas curtas.
3. Caminho para o ZK Padrão: Traça um caminho teórico para transformar essas provas condicionais, baseadas em lógica, em provas de conhecimento zero padrão, dependendo da existência de geradores de complexidade de prova difíceis (especificamente demi-bits) e do uso de uma string aleatória comum.

O autor permanece modesto quanto à construção das próprias sequências difíceis, observando que, embora existam conjecturas (por exemplo, sobre a existência de geradores difíceis para todos os sistemas de prova), uma prova de que uma construção específica funciona permanece um problema aberto em complexidade de provas. O artigo serve como um refinamento teórico e uma ponte entre a formulação lógica de ZK e as definições criptográficas padrão.