Certified-Everlasting Quantum NIZK Proofs

1. Problema e Motivação

O artigo aborda a construção de Provas de Conhecimento Zero Não Interativas (NIZK) para a classe de complexidade NP que satisfaçam simultaneamente três propriedades críticas:

1. Correção Estatística (Statistical Soundness): Um provador malicioso, mesmo com poder computacional ilimitado, não consegue convencer o verificador de uma afirmação falsa.
2. Zero-Knowledge Computacional: Um verificador computacionalmente limitado não aprende nada além da validade da afirmação.
3. Zero-Knowledge Eterno Certificado (Certified-Everlasting Zero-Knowledge - CE-ZK): Esta é a contribuição central. O protocolo permite que o verificador "revogue" a prova de forma verificável (emitindo um certificado de exclusão). Se a revogação for certificada com sucesso, o estado do verificador pode ser simulado estatisticamente apenas com a afirmação, garantindo que, mesmo que o verificador se torne computacionalmente ilimitado no futuro, ele não poderá recuperar a prova ou qualquer informação sobre o segredo (witness).

O Desafio: Em cenários clássicos, é geralmente impossível obter Soundness Estatística e Zero-Knowledge Estatística simultaneamente para todas as linguagens em NP. A solução quântica proposta busca contornar essa limitação usando o teorema da não-clonagem e a exclusão certificada de estados quânticos (como estados BB84), onde o verificador deve destruir o estado quântico para provar que não o possui mais.

2. Metodologia e Abordagem

O autor investiga a viabilidade de construir tais protocolos em dois modelos de configuração diferentes: o Modelo de String de Referência Comum (CRS) e o Modelo de EPR Compartilhado.

2.1. Barreira no Modelo CRS

O trabalho identifica uma barreira fundamental para a construção de CE-NIZKs no modelo CRS através de generalizações diretas de protocolos interativos conhecidos (como os baseados em compromissos ou o paradigma de bits ocultos).

• Definição de "Deletion-Resistant": O autor define uma classe de protocolos onde o estado da prova pode ser dividido em duas partes: uma que passa pela verificação de exclusão e outra que passa pela verificação da prova.
• Impossibilidade: É provado que a existência de tais protocolos implicaria a existência de NIZKs que possuem Soundness Estatística e Zero-Knowledge Estatística simultaneamente, o que é considerado impossível para NP completo.
• Conclusão: Protocolos baseados em Fiat-Shamir ou generalizações diretas de provas interativas de exclusão certificada falham neste modelo.

2.2. Solução no Modelo CRS (Superposição e NIZK Duplo)

Para contornar a barreira, o autor propõe uma construção inovadora no modelo CRS que utiliza:

• NIZK Quântico-Seguro: Um NIZK subjacente que possui Soundness Estatística Adaptativa e Zero-Knowledge Quântico-Seguro (seguro contra ataques em superposição).
• Estados BB84 e One-Time Pad (OTP): O provador gera um estado quântico BB84 entrelaçado com a prova. A prova interna ($\pi_{in}$) é criptografada usando um OTP derivado das medições do estado BB84.
• Provas Externas em Superposição: O provador gera provas "externas" em superposição quântica que atestam a validade da prova criptografada.
• Técnica de Dois Slots (Two-Slot Technique): Para garantir a segurança, o protocolo utiliza uma estrutura de prova "OU" (OR). Isso permite ao simulador substituir bits da prova real por bits simulados (ou zeros) bit a bit, sem violar a correção da prova, desde que a exclusão do estado BB84 seja verificada.
• Suposições: A construção baseia-se em Funções de Hash Resistentes a Colisão (OWFs) e na dureza do problema LWE (Learning With Errors) para garantir a existência de NIZKs com as propriedades quânticas necessárias.

2.3. Solução no Modelo EPR Compartilhado (Eficiência Quântica)

O autor observa que a barreira de impossibilidade não se aplica ao modelo onde o provador e o verificador compartilham pares EPR (estados emaranhados) desde o início.

• Paradigma de Bits Ocultos (Hidden-Bits): O protocolo adapta o paradigma de bits ocultos para o ambiente quântico. O provador e o verificador medem suas metades dos pares EPR em bases escolhidas (definidas por um gerador de bits ocultos) para gerar uma string de bits ocultos compartilhada.
• Exclusão Certificada: O verificador é solicitado a medir as partes não reveladas dos pares EPR na base de Hadamard. Se a exclusão for verificada, a informação sobre os bits ocultos é destruída estatisticamente.
• Eficiência: Diferente do protocolo CRS, este modelo exige apenas medições de qubits únicos (computacional ou Hadamard) e comunicação clássica, tornando-o altamente eficiente em termos de operações quânticas.

3. Principais Contribuições

1. Definições Formais: Estabelece definições rigorosas para CE-NIZKs nos modelos CRS e EPR compartilhado.
2. Teorema de Impossibilidade: Demonstra que generalizações diretas de protocolos interativos de exclusão certificada para o modelo CRS falham, pois levariam a NIZKs com propriedades estatísticas contraditórias.
3. Construção no CRS: Apresenta a primeira construção de CE-NIZK para NP no modelo CRS, baseada em:
   • Uso de NIZKs quântico-seguros (implícitos por LWE).
   • Criptografia One-Time Pad com estados BB84.
   • Técnica de dois slots e provas OR para permitir a simulação.
4. Construção no Modelo EPR: Demonstra que, no modelo de EPR compartilhado, a barreira de impossibilidade desaparece. Constrói um protocolo CE-NIZK baseado em qualquer gerador de bits ocultos com binding estatístico (também baseado em LWE), que é computacionalmente muito mais eficiente (apenas medições de qubit único).
5. Análise de Segurança: Prova que os protocolos satisfazem Soundness Estatística, Zero-Knowledge Computacional e Zero-Knowledge Eterno Certificado (condicionado à exclusão verificada).

4. Resultados

• Existência: O artigo prova que CE-NIZKs para NP existem no modelo CRS sob a suposição de dureza polinomial do problema LWE.
• Eficiência: No modelo EPR compartilhado, o protocolo é altamente eficiente, exigindo apenas medições de qubits únicos e computação clássica, evitando a necessidade de gerar e verificar estados altamente emaranhados complexos durante a execução.
• Segurança: Os protocolos garantem que, se o verificador fornecer um certificado de exclusão válido, qualquer adversário futuro (mesmo com poder computacional ilimitado) não poderá recuperar a prova ou o segredo, pois o estado quântico foi destruído de forma verificável.

5. Significado e Impacto

Este trabalho é significativo por várias razões:

• Ponte entre Teoria e Prática Quântica: Resolve um problema aberto sobre a viabilidade de NIZKs com garantias de segurança eterna em cenários não interativos, algo crucial para aplicações futuras em criptografia pós-quântica e privacidade de dados.
• Novo Paradigma de Segurança: Introduz o conceito de "Zero-Knowledge Eterno Certificado" para provas não interativas, permitindo que a privacidade seja garantida mesmo contra adversários futuros com computadores quânticos ilimitados, desde que o verificador coopere na exclusão.
• Distinção de Modelos: Clarifica as diferenças fundamentais entre o modelo CRS e o modelo EPR compartilhado, mostrando que o emaranhamento pré-compartilhado pode contornar barreiras de impossibilidade que existem no modelo CRS.
• Aplicações Potenciais: Tais protocolos são fundamentais para sistemas de credenciais anônimas, assinaturas de grupo, moedas quânticas e computação verificável, onde a privacidade deve ser mantida indefinidamente, mesmo após a revogação da prova.

Em resumo, o artigo de Nikhil Pappu estabelece a viabilidade teórica de provas de conhecimento zero não interativas com segurança eterna certificada, superando barreiras de impossibilidade através de técnicas quânticas sofisticadas e oferecendo soluções eficientes em modelos de configuração específicos.