💻 computer science

Non-Trivial Zero-Knowledge Implies One-Way Functions

Assumindo que $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$ , este trabalho demonstra que a existência de argumentos de conhecimento zero não triviais (onde a soma dos erros de completude, sombreamento e zero-conhecimento é estritamente menor que 1) para $\mathsf{NP}$ implica a existência de funções de mão única, fechando assim uma lacuna aberta na literatura sobre regimes de alto erro tanto para provas não interativas quanto interativas.

Autores originais: Suvradip Chakraborty, James Hulett, Dakshita Khurana, Kabir Tomer

Publicado 2026-02-20

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Suvradip Chakraborty, James Hulett, Dakshita Khurana, Kabir Tomer

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 (uma "prova" de que você sabe algo) e quer convencer um amigo de que você realmente sabe, sem nunca revelar qual é o segredo. Na criptografia, isso se chama Prova de Conhecimento Zero (Zero-Knowledge Proof). É como se você provasse que tem a chave da casa sem mostrar a chave e sem abrir a porta.

Por décadas, os cientistas acreditaram que para criar esses sistemas de prova "perfeitos" (onde a chance de erro é quase zero), você precisava de um ingrediente mágico e difícil de encontrar: Funções de Mão Única (One-Way Functions). Pense nelas como uma "trituração de papel": é fácil triturar um papel, mas impossível colar os pedaços de volta para ler o texto original. Acreditava-se que sem essa "trituração" matemática, não era possível ter provas de conhecimento zero seguras.

Mas e se a prova não for perfeita? E se houver um pouco de "ruído" ou erro? O que acontece se a prova for apenas "razoável" e não "perfeita"?

Este novo artigo responde a uma pergunta fundamental: Se existirem provas de conhecimento zero que não sejam perfeitamente seguras (mas que não sejam totalmente inúteis), isso ainda nos obriga a ter "Funções de Mão Única"?

A resposta dos autores é um SIM estrondoso.

Aqui está a explicação simplificada, usando analogias do dia a dia:

1. O Problema do "Erro Grande"

Antes, os cientistas diziam: "Se a prova tiver um erro muito grande (digamos, 50% de chance de falhar ou de vazar segredos), ela é inútil e não nos diz nada sobre a segurança do mundo."
Eles achavam que só provas com erros minúsculos (quase zero) poderiam gerar "Funções de Mão Única".

O artigo diz: "Esperem! Mesmo que a prova seja 'suja', com erros grandes, mas desde que não seja totalmente absurda (ou seja, a soma dos erros não chegue a 100%), ela ainda é poderosa o suficiente para criar essas funções de mão única."

2. A Analogia do Detetive e do "CRS" (O Cartão de Identidade)

Para entender como eles provaram isso, imagine um jogo de detetive:

O Cenário: Existe um sistema onde você recebe um "Cartão de Identidade" (chamado CRS) e tenta provar algo.
O Truque Antigo: Os métodos antigos tentavam "reverter" o processo. Eles diziam: "Se não existirem Funções de Mão Única, podemos simular qualquer prova perfeitamente." Se conseguíssemos simular perfeitamente, o detetive não conseguiria distinguir a prova real da falsa.
O Problema: Quando os erros são grandes, essa simulação falha. O detetive consegue ver que algo está errado, mas não consegue usar isso para quebrar o sistema. Era como tentar adivinhar a senha de alguém olhando para uma foto borrada; os métodos antigos diziam "se a foto estiver muito borrada, não dá para fazer nada".

3. A Solução Criativa: "Repetição e Estatística"

A grande inovação deste trabalho é uma técnica que chamaremos de "O Método do Amigo Exagerado".

Em vez de tentar adivinhar a prova perfeita de uma só vez, o novo método diz:

"Vamos repetir o processo de prova muitas, muitas vezes com o mesmo cartão de identidade!"

A Ideia: Imagine que você tem um amigo que é um pouco desajeitado (o simulador). Às vezes ele acerta a prova, às vezes erra.
A Estratégia: Em vez de confiar em uma única tentativa, o algoritmo pede ao amigo para tentar mil vezes.
- Se a prova for falsa (o criminoso tentando enganar), ele falhará quase todas as vezes, não importa quantas vezes tente.
- Se a prova for verdadeira (alguém que realmente sabe o segredo), mesmo que o amigo seja desajeitado, estatisticamente, em algum momento das mil tentativas, ele vai conseguir gerar uma prova que funciona.

Ao repetir o processo, o "ruído" (os erros grandes) é filtrado. O algoritmo consegue separar o "sinal" (quem realmente sabe) do "ruído" (quem está tentando adivinhar), mesmo que o erro inicial fosse enorme.

4. O Resultado Final: O Mundo é Mais Seguro do que Pensávamos

A conclusão do artigo é fascinante:

Não importa o quão "imperfeita" seja a prova: Desde que ela não seja um sistema de "jogo de azar" onde tudo é aleatório (onde a soma dos erros é 100%), ela contém uma "semente" de segurança.
A Semente vira Árvore: Essa "semente" imperfeita é suficiente para cultivar Funções de Mão Única.
Consequência: Se você consegue construir qualquer sistema de prova de conhecimento zero que funcione "mais ou menos bem" (não trivial), você automaticamente tem a base para toda a criptografia moderna (senhas, assinaturas digitais, blockchains).

Resumo em uma frase

Este artigo prova que mesmo provas de conhecimento zero "meia-boca" e com erros grandes são fortes o suficiente para garantir a existência de segredos matemáticos irreversíveis, derrubando a barreira que separava o mundo das provas imperfeitas do mundo da criptografia segura.

É como descobrir que, mesmo que você tenha um mapa antigo e rasgado (com erros), ele ainda contém informações suficientes para encontrar o tesouro, desde que você saiba como dobrar e olhar para ele repetidas vezes.

1. O Problema e o Contexto

A existência de Funções de Uma Via (OWFs - One-Way Functions) é a pedra angular da criptografia moderna. Uma questão fundamental na teoria da complexidade e criptografia, iniciada por Ostrovsky e Wigderson, é: quais são as suposições mínimas necessárias para construir sistemas de Prova de Conhecimento Zero (ZK)?

Trabalhos anteriores estabeleceram que, se $NP$ for difícil na média, a existência de ZK para $NP$ implica a existência de OWFs. Mais recentemente, Hirahara e Nanashima (2024) mostraram que mesmo a dureza no pior caso de $NP$ (especificamente $NP \not\subseteq ioP/poly$ ) é suficiente para derivar OWFs a partir de protocolos ZK, desde que os erros do protocolo sejam negligenciáveis.

A Lacuna: O que acontece se permitirmos protocolos ZK com erros não-negligenciáveis (ou seja, erros grandes, mas ainda "não triviais")?

Protocolos ZK triviais existem sem nenhuma suposição criptográfica se a soma dos erros de completude ( $\epsilon_c$ ), sombreamento ( $\epsilon_s$ ) e conhecimento zero ( $\epsilon_{zk}$ ) for $\ge 1$ .
A questão aberta era: Protocolos ZK não-triviais (onde $\epsilon_c + \epsilon_s + \epsilon_{zk} < 1$ ) implicam a existência de OWFs?
Técnicas anteriores falhavam nessa região de "alto erro" porque dependiam criticamente de erros pequenos para suas reduções.

2. Metodologia e Técnicas Principais

Os autores desenvolvem uma caracterização completa da complexidade no pior caso de protocolos ZK não-triviais. A metodologia envolve superar barreiras analíticas de trabalhos anteriores através de novas abordagens:

A. Repetição para NIZK (Não-Interativo)

Para o caso de NIZK (Non-Interactive Zero-Knowledge), os autores identificam que as técnicas anteriores (como as de [OW93] e [CHK25]) falham porque o simulador pode gerar provas "boas" e "ruins" de forma inconsistente dependendo do CRS (Common Reference String).

Solução: Eles propõem um algoritmo de decisão que repete o processo de amostragem de provas simuladas múltiplas vezes para o mesmo CRS.
Lógica: Se um CRS é "ruim" (o simulador raramente gera uma prova aceita), a repetição exponencialmente reduz a chance de o algoritmo aceitar uma prova falsa. Se o CRS é "bom", a repetição garante que pelo menos uma prova aceita seja encontrada.
Isso permite que o algoritmo distinga entre instâncias em $L$ e fora de $L$ sempre que $\epsilon_s + \epsilon_{zk} < 1$ , eliminando a necessidade de erros negligenciáveis.

B. Provedor Malicioso Eficiente ( $\tilde{P}$ ) para ZK Interativo

Para o caso Interativo (ZK com múltiplas rodadas), a generalização é mais complexa.

Desafio: Em protocolos interativos, o provedor não pode verificar instantaneamente se uma mensagem levará à aceitação, pois isso depende de aleatoriedade futura do verificador.
Solução: Os autores definem um Provedor Malicioso Eficiente ( $\tilde{P}$ ).
1. $\tilde{P}$ usa Universal Extrapolation (UE) (que existe se OWFs não existirem) para amostrar "muitas" possíveis mensagens futuras do simulador.
2. $\tilde{P}$ estima a probabilidade de aceitação de cada mensagem simulando o protocolo internamente (possível porque o verificador é de moeda pública).
3. $\tilde{P}$ escolhe a mensagem que maximiza a probabilidade de aceitação entre as amostradas.
Análise: Eles provam que, mesmo com essa estimativa aproximada, $\tilde{P}$ performa quase tão bem quanto o provedor honesto, desde que o número de rodadas seja constante. A análise utiliza limites de Chernoff para garantir que a estimativa de probabilidade seja precisa o suficiente.

C. Tratamento de Moeda Privada

Para protocolos de moeda privada, os autores mostram que, a menos que existam OWFs com entrada auxiliar, qualquer protocolo de moeda privada de rodadas constantes pode ser convertido em um protocolo de moeda pública. Isso estende o resultado para o caso geral, implicando a existência de OWFs com entrada auxiliar.

3. Principais Contribuições e Resultados

O trabalho estabelece os seguintes teoremas principais (de forma informal):

Teorema 1 (NIZK): Se $NP \not\subseteq ioP/poly$ e existem argumentos NIZK não-triviais para $NP$, então Funções de Uma Via (OWFs) existem.
- Melhoria: Supera o limite anterior de [CHK25] que exigia $\epsilon_{zk} + \sqrt{\epsilon_s} < 1$ . O novo resultado funciona para qualquer $\epsilon_c + \epsilon_s + \epsilon_{zk} < 1$ .
Teorema 2 (ZK Interativo): Se $NP \not\subseteq ioP/poly$ e existem argumentos ZK não-triviais de rodadas constantes e moeda pública para $NP$, então OWFs com entrada auxiliar existem.
Teorema 3 (Generalização): Se $NP \not\subseteq ioP/poly$ e existem argumentos ZK não-triviais (mesmo de moeda privada) para $NP$, então OWFs com entrada auxiliar existem.
Aplicação: Amplificação Unconditional:
- Um dos resultados mais impactantes é a capacidade de amplificar protocolos ZK de alto erro para protocolos ZK padrão (com erro negligenciável) sem suposições criptográficas adicionais (além da dureza de $NP$).
- Corolário 1: Sob a suposição de que $NP \not\subseteq ioP/poly$ , qualquer prova NIZK não-trivial pode ser transformada em uma prova NIZK padrão.
- Corolário 2: Sob a mesma suposição, qualquer argumento ZK interativo não-trivial de rodadas constantes implica a existência de argumentos ZK de 4 rodadas com erro negligenciável.

4. Significado e Impacto

Caracterização Completa: O trabalho fecha uma lacuna fundamental na teoria da complexidade criptográfica, mostrando que a existência de qualquer protocolo ZK "não-trivial" (mesmo com erros grandes) para problemas difíceis é tão poderosa quanto a existência de OWFs. Não há um "meio-termo" criptográfico fraco entre ZK trivial e ZK seguro.
Redução de Suposições: Antes deste trabalho, a amplificação de NIZKs de alto erro exigia suposições fortes (como criptografia de chave pública). Este trabalho mostra que, se $NP$ for difícil no pior caso, a existência de OWFs é uma consequência direta da existência de ZK não-trivial, permitindo a amplificação quase incondicionalmente.
Limites de Protocolos: O resultado sugere que tentar construir protocolos ZK com erros grandes (para facilitar a implementação) não é uma rota segura para evitar a necessidade de OWFs; se o protocolo for não-trivial, as OWFs já estão implícitas.
Técnicas Novas: A introdução de provedores maliciosos eficientes baseados em amostragem e estimativa de probabilidade para lidar com ZK de alto erro em cenários interativos abre novas portas para a análise de protocolos criptográficos com parâmetros de segurança relaxados.

Em resumo, o artigo demonstra que a barreira entre "ZK trivial" e "ZK criptograficamente útil" é exatamente a existência de Funções de Uma Via, e que mesmo protocolos com erros significativos já carregam o peso criptográfico necessário para construir a base da criptografia moderna.