💻 computer science

Weak Zero-Knowledge and One-Way Functions

O artigo demonstra que a existência de protocolos de conhecimento zero fracos (com erros não negligenciáveis) para linguagens difíceis no pior caso implica a existência de funções de mão única, generalizando resultados anteriores para condições de erro mais amplas e menos restritivas.

Autores originais: Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan

Publicado 2026-02-19

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você tem um segredo muito valioso, como a senha do seu cofre. Você quer provar para um amigo que você sabe a senha, mas sem nunca revelar qual é a senha. Na criptografia, chamamos isso de Zero-Knowledge (Conhecimento Zero). É como se você dissesse: "Eu sei a senha, e posso provar isso, mas você não vai aprender nada além do fato de que eu sei."

Por muito tempo, os cientistas acreditaram que, para que esse truque funcionasse perfeitamente, ele precisava ser "infalível". Ou seja, a chance de você errar a prova ou o amigo conseguir enganar o sistema tinha que ser tão pequena que fosse praticamente zero (como ganhar na loteria várias vezes seguidas).

Mas, na vida real, muitos desses truques não são perfeitos. Eles têm uma pequena chance de falha. A pergunta que este novo artigo de pesquisa faz é: "E se esses truques não forem perfeitos? Eles ainda são fortes o suficiente para garantir a segurança do nosso mundo digital?"

A resposta dos autores (Rohit Chatterjee, Yunqi Li e Prashant Nalini Vasudevan) é um grande SIM. E aqui está o que eles descobriram, explicado de forma simples:

1. O Problema: Truques com "Falhas"

Pense em um mágico que faz um truque de carta.

Versão Perfeita: O mágico nunca erra. A plateia nunca vê o truque falhar.
Versão "Fraca" (Weak): O mágico erra uma vez a cada 100 vezes. O público pode, às vezes, ver algo estranho ou o mágico pode ser enganado.

Antes, os cientistas diziam: "Se o mágico erra muito, o truque é inútil para criar segurança." Mas este artigo diz: "Não importa o quanto ele erre, desde que a soma das chances de erro não seja 100% (ou seja, desde que o truque funcione algumas vezes), ele ainda esconde um poder secreto."

2. A Descoberta: O Segredo é a "Função de Um Caminho"

O grande segredo que eles desvendaram é que, se existirem esses truques de "Conhecimento Zero" (mesmo com falhas) para problemas difíceis, isso prova automaticamente que existem Funções de Um Caminho (One-Way Functions).

A Analogia da Pimenta e do Molho:
Imagine que você pode transformar uma pimenta inteira em um molho delicioso e complexo. Isso é fácil (é a função "fácil").
Mas, se alguém te der apenas o molho, é impossível (ou extremamente difícil) descobrir exatamente quais pimentas foram usadas e em que ordem. Isso é a "Função de Um Caminho".

Essas funções são a base de quase toda a segurança moderna (senhas, criptomoedas, bancos). O artigo prova que, se você tiver o "truque de mágica" (Zero-Knowledge), você automaticamente tem a "pimenta que vira molho" (Função de Um Caminho).

3. O Que Eles Melhoraram?

Antes, os cientistas tinham uma regra muito rígida. Eles diziam: "O truque só funciona se a chance de erro for menor que X".

Regra Antiga: Era como dizer: "Só podemos usar o mágico se ele errar menos de 10% das vezes."
Nova Regra (deste artigo): Eles mostraram que podemos usar o mágico mesmo se ele errar 40%, 50% ou mais, desde que a soma dos erros não chegue a 100%.

Eles conseguiram isso criando uma nova maneira de "testar" o mágico. Em vez de apenas olhar se o truque funcionou, eles criaram um sistema onde, se o mágico tentar enganar o teste, ele acaba revelando a senha (o que é impossível, provando que o truque é seguro).

4. Por Que Isso é Importante?

Imagine que você está construindo um castelo de cartas (a segurança da internet).

Antes, você só podia usar cartas que eram perfeitamente retas e rígidas.
Agora, este artigo diz: "Você pode usar cartas um pouco tortas, cartas com manchas, cartas que dobram um pouco, desde que elas ainda se mantenham em pé."

Isso é incrível porque:

Mais Flexibilidade: Podemos usar protocolos de segurança mais simples e rápidos que antes eram descartados por não serem "perfeitos".
Segurança Garantida: Mesmo com essas imperfeições, a matemática prova que a segurança fundamental (a Função de Um Caminho) ainda existe.
Futuro: Isso abre portas para criar sistemas de criptografia mais eficientes que funcionam em dispositivos com pouca energia (como celulares ou sensores), onde protocolos perfeitos seriam muito pesados.

Resumo em Uma Frase

Este artigo prova que, mesmo que nossos protocolos de "prova sem revelar segredos" não sejam perfeitos e tenham algumas falhas, eles ainda são fortes o suficiente para garantir que a base de toda a segurança digital (as funções de um caminho) continue existindo e protegendo nossos dados.

É como descobrir que você não precisa de um cofre de aço inquebrável para esconder seu segredo; um cofre de madeira com algumas rachaduras, mas que ainda não abre, é suficiente para garantir que ninguém consiga entrar sem a chave!

1. Problema e Motivação

O artigo investiga as implicações criptográficas da existência de protocolos de Conhecimento Zero (Zero-Knowledge - ZK) fracos para linguagens difíceis no pior caso (worst-case hard languages).

Contexto: Protocolos ZK tradicionais garantem que um verificador malicioso não aprenda nada além da validade da afirmação, com erros de completude ( $\epsilon_c$ ), sombreamento ( $\epsilon_s$ ) e conhecimento zero ( $\epsilon_z$ ) negligíveis.
O Desafio: Muitos protocolos ZK naturais e úteis (como os para 3-Coloração ou Isomorfismo de Grafos) não possuem erros negligíveis nativamente; eles podem ter erros constantes ou polinomiais. Estes são chamados de ZK Fracos.
Questão Central: A existência de tais protocolos fracos para todas as linguagens em NP (assumindo que NP é difícil no pior caso) implica a existência de Funções de Uma Via (OWFs - One-Way Functions)?
Estado da Arte: Trabalhos anteriores (como Chakraborty et al., CRYPTO 2025) mostraram que OWFs existem sob a condição restritiva $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ . O objetivo deste trabalho é eliminar essa restrição e cobrir o espectro completo de parâmetros não triviais.

2. Metodologia e Abordagem Técnica

Os autores utilizam uma abordagem de redução, construindo funções candidatas a OWFs a partir dos simuladores dos protocolos ZK. A lógica central é: se uma função derivada do protocolo for fácil de inverter, então é possível construir um algoritmo eficiente que decide a linguagem NP, contradizendo sua dificuldade no pior caso.

Principais Técnicas:

Redução de NIZK (Não Interativo):
- Eles refinam a construção clássica de Ostrovsky-Wigderson.
- Inovação: Em vez de apenas usar o simulador para gerar a string de referência comum e a prova, eles incluem o resultado da verificação ( $a = V(x; r, \pi)$ ) na saída da função candidata.
- A função candidata é definida como $f_x(\rho) = (r, a)$ , onde $(r, \pi) \leftarrow Sim(x; \rho)$ e $a = V(x; r, \pi)$ .
- Isso permite que o "inversor" seja forçado a encontrar um pré-imagem que corresponda a uma prova válida (aceita pelo verificador), eliminando a necessidade de uma verificação explícita adicional que consumiria uma margem de erro extra de ZK.
- Resultado: A condição para existência de OWFs auxiliares (ai-OWFs) torna-se $\epsilon_c + \epsilon_s + \epsilon_z < 1$ .
Redução para Protocolos Públicos (Public-Coin) de Múltiplas Rodadas:
- Para protocolos interativos onde o verificador envia bits aleatórios públicos, eles generalizam a construção.
- Para um protocolo de $t$ mensagens, a condição derivada inicialmente é $\epsilon_c + \epsilon_s + (t-1)\epsilon_z < 1$ .
- Eles utilizam uma estratégia de simulação eficiente onde o provador "falso" ( $\tilde{P}$ ) usa o inversor para gerar mensagens que maximizam a probabilidade de aceitação.
Protocolos de Rodada Constante (Constant-Round):
- Para protocolos com um número fixo de rodadas $k$ , eles empregam uma construção recursiva.
- Definem uma cadeia de funções $f_1, \dots, f_k$ , onde cada função depende de inversores das funções subsequentes.
- A função $f_{i,x}$ estima a probabilidade de aceitação das rodadas futuras. O inversor é usado para encontrar a melhor resposta para a rodada atual que maximiza essa estimativa.
- Isso permite uma condição mais forte: $\epsilon_c + \epsilon_s + k \cdot \epsilon_z < 1$ .
- Limitação: Devido à natureza da contradição (que exige que todos os inversores $A_1, \dots, A_k$ funcionem simultaneamente), o resultado para este caso específico garante apenas OWFs "infinitamente-ocasionalmente" (io-OWFs), em vez de OWFs padrão.

3. Contribuições Principais

O artigo estabelece três teoremas principais que expandem significativamente o conhecimento sobre a relação entre ZK fraco e OWFs:

NIZK Generalizado:
- Se todas as linguagens em NP possuem provas NIZK (ou argumentos) com erros satisfazendo $\epsilon_c + \epsilon_s + \epsilon_z < 1$ (assumindo $NP \not\subseteq ioP/poly$ ), então OWFs existem.
- Isso cobre todos os valores não triviais possíveis, superando a barreira anterior de $\sqrt{\epsilon_s}$ .
- Consequência: Se $\epsilon_c$ for negligível, é possível amplificar o protocolo para ter todos os erros negligíveis.
Protocolos Públicos de $t$ Mensagens:
- Se todas as linguagens em NP possuem protocolos ZK públicos de $t$ mensagens com $\epsilon_c + \epsilon_s + (t-1)\epsilon_z < 1$ , então OWFs existem.
Protocolos Públicos de $k$ Rodadas (Constantes):
- Se todas as linguagens em NP possuem protocolos ZK públicos de $k$ rodadas (onde $k$ é uma constante) com $\epsilon_c + \epsilon_s + k \cdot \epsilon_z < 1$ , então io-OWFs existem.
- Nota: A condição é estritamente melhor ( $k$ em vez de $2k-1$ ) em comparação com abordagens anteriores, mas o resultado de segurança é mais fraco (infinitamente-ocasional).

4. Resultados e Implicações

Unificação de Parâmetros: O trabalho demonstra que a fronteira para a existência de OWFs a partir de ZK fraco é simplesmente a soma dos erros ser estritamente menor que 1. Não há necessidade de raízes quadradas ou fatores de amplificação complexos para a existência básica de OWFs.
Amplificação: Os resultados permitem a amplificação de protocolos NIZK com completude quase perfeita para protocolos com erros totalmente negligíveis, desde que se assuma apenas a dificuldade no pior caso de NP.
Distinção entre OWF Padrão e io-OWF: O artigo esclarece que, para protocolos de rodada constante, a técnica atual (não-black-box) só consegue garantir segurança "infinitamente-ocasional". Isso destaca uma lacuna técnica: como obter OWFs padrão para protocolos de rodada constante com erros fracos.

5. Significado e Impacto

Este trabalho é fundamental para a teoria da complexidade criptográfica porque:

Completa o Mapa de Implicações: Antes deste trabalho, havia uma "zona de incerteza" para protocolos ZK fracos com erros de sombreamento ( $\epsilon_s$ ) significativos. O artigo fecha essa lacuna, mostrando que a existência de tais protocolos para NP duro implica necessariamente em OWFs.
Robustez de OWFs: Reforça a crença de que OWFs são o primitivo criptográfico mais básico, pois são implicados até mesmo por protocolos de segurança "imperfeitos" (com erros constantes), desde que a linguagem subjacente seja difícil.
Direção para Futuras Pesquisas: O artigo levanta questões abertas importantes, como:
- É possível obter OWFs padrão (e não apenas io-OWFs) para protocolos de rodada constante com essa condição de erro melhorada?
- A análise pode ser estendida para protocolos de "private-coin" (moedas privadas)?
- Quais outras primitivas criptográficas mais fortes podem ser derivadas de ZK fraco?

Em resumo, o artigo demonstra que a barreira para a existência de OWFs a partir de ZK é muito mais baixa do que se pensava anteriormente, abrangendo praticamente qualquer protocolo ZK não trivial, o que solidifica a conexão entre a dificuldade computacional de linguagens NP e a segurança criptográfica fundamental.