Resumo Técnico: MPC no Cabeça Quântico (Zero-Knowledge de Superposição-Seguro)

Declaração do Problema

O artigo aborda a construção de protocolos de Conhecimento Zero (ZK - Zero-Knowledge) que permanecem seguros mesmo quando um verificador malicioso pode emitir desafios e receber respostas em superposição quântica. Esta "segurança de superposição" é um fortalecimento crítico da segurança clássica, motivado por cenários onde adversários quânticos podem interagir com dispositivos criptográficos clássicos ou onde primitivas clássicas estão inseridas em protocolos quânticos maiores.

Embora Damgård et al. [19] tenham sido pioneiros nesta noção para NP, sua construção dependia de compromissos de modo duplo perfeitamente ocultos e incondicionalmente vinculativos, uma primitiva não conhecida de existir sob suposições criptográficas padrão. Além disso, suas técnicas não se estenderam naturalmente para QMA (Merlin-Arthur Quântico), o análogo quântico de NP, devido à dificuldade fundamental de verificar computações quânticas sem revelar a testemunha quântica.

Alternativas existentes, como provas de Conhecimento Zero Não Interativo (NIZK), são ou desconhecidas para QMA sob suposições padrão ou dependem de modelos heurísticos (ex: oráculos quânticos aleatórios ou ofuscação). Adicionalmente, as NIZKs são geralmente mais pesadas do que os protocolos $\Sigma$ de três rodadas preferidos pela eficiência.

Metodologia

Os autores propõem uma generalização do paradigma MPC-in-the-Head [30] para o cenário quântico, denominada "MPC no Cabeça Quântico" (MPC in the Quantum Head). A metodologia central envolve duas construções distintas, mas relacionadas:

1. ZK de Superposição-Seguro para NP

Os autores revisitam o protocolo de Damgård et al. [19], mas substituem a exigência de compromissos perfeitamente ocultos por compromissos de modo duplo (estatisticamente ocultos, computacionalmente vinculativos em um modo; perfeitamente vinculativos, computacionalmente ocultos no outro).

• Técnica: A estratégia de prova utiliza um argumento de híbrido. No mundo real, os compromissos são para as visões (views) do MPC. Em um híbrido, os compromissos são alternados para o modo estatisticamente oculto. Crucialmente, os autores introduzem um híbrido onde o provador se compromete com 0 (em vez de visões honestas), mas ainda pode abri-los para as visções honestas usando a propriedade de vinculação computacional (que é quebrada por um simulador ilimitado).
• Argumento de Segurança: Uma vez que os compromissos são para 0, as visões abertas (um subconjunto de partes/shares) e os compromissos não abertos formam um esquema de compartilhamento secreto perfeitamente seguro. Os autores utilizam um lema de [19] afirmando que o compartilhamento secreto perfeito permanece seguro contra ataques de superposição se menos de $2t$ partes forem consultadas (onde $t$ é o limiar de privacidade). Isso permite que a prova de segurança proceda sem exigir compromissos perfeitamente ocultos.

2. MPC no Cabeça Quântico para QMA

Estender isso para QMA requer lidar com testemunhas quânticas e circuitos de verificação quânticos.

• O Obstáculo: No MPC-in-the-Head clássico, o provador revela "visões" (transcritos) de partes. Na Computação Quântica Multipartidária (MPQC), as partes trocam mensagens quânticas, o que significa que não há um transcrito clássico para revelar; uma parte possui apenas um estado quântico final.
• A Solução: Os autores modelam o protocolo global de MPQC como um circuito quântico (substituindo a passagem de mensagens por portas SWAP). Eles aplicam a redução de Circuito-para-Hamiltoniano de Kitaev [34] a este circuito.
  • A "testemunha" torna-se o estado de história (history state) do Hamiltoniano, que possui baixa energia se, e somente se, o MPQC aceitar.
  • O provador se compromete com este estado de história (qubit por qubit) usando um One-Time Pad Quântico (QOTP) e se compromete com as chaves do QOTP usando compromissos de modo duplo.
  • O verificador desafia o provador a abrir qubits específicos correspondentes a termos locais do Hamiltoniano.
• Verificação: O verificador mede os qubits abertos para verificar os termos do Hamiltoniano local. Se a energia for baixa, o estado de história corresponde a uma execução válida.
• Conhecimento Zero: A propriedade de ZK baseia-se no fato de que abrir um subconjunto de qubits correspondentes a um termo do Hamiltoniano local não revela mais informações do que controlar um subconjunto de partes no MPQC subjacente. Os autores utilizam um protocolo MPQC perfeitamente $2t$-privado [17, 39] para garantir que o estado de história da computação sobre uma testemunha compartilhada secretamente permaneça indistinguível de um estado de história sobre uma entrada fictícia (dummy), mesmo sob consultas de superposição.

Principais Contribuições

1. Generalização do MPC-in-the-Head: O artigo apresenta a primeira instanciação do paradigma MPC-in-the-Head para funcionalidades quânticas (MPQC), criando efetivamente um "MPC Quântico no Cabeça".
2. ZK de Superposição-Seguro para NP: Os autores constroem um protocolo $\Sigma$ de três rodadas para NP seguro contra ataques de superposição baseado em qualquer compromisso de modo duplo pós-quântico (ex: de LWE). Isso melhora [19] ao remover a necessidade de compromissos perfeitamente ocultos não padronizados.
3. ZK de Superposição-Seguro para QMA: O artigo constrói o primeiro protocolo $\Sigma$ de três rodadas para QMA seguro contra ataques de superposição, baseado na suposição de Aprendizado com Erros (LWE). Isso preenche uma lacção onde não existem NIZKs para QMA sob suposições padrão.
4. Novas Técnicas de Prova:
   • Um novo argumento de híbrido para NP que alterna compromissos para 0 para aproveitar as propriedades de compartilhamento secreto perfeito contra ataques de superposição.
   • Uma técnica para QMA que combina a redução de Circuito-para-Hamiltoniano com MPQC e QOTP, utilizando a indistinguibilidade de pares EPR e one-time pads para simular o protocolo na presença de consultas de superposição.

Resultados

O artigo estabelece os seguintes teoremas (informais):

• Teorema 1.1: Assumindo a segurança pós-quântica de LWE, existem protocolos $\Sigma$ de três rodadas para QMA no modelo de Cadeia de Referência Comum (CRS) satisfazendo conhecimento zero contra verificadores maliciosos realizando consultas de superposição.
• Teorema 1.2: Assumindo a existência de quaisquer compromissos de modo duplo pós-quânticos, existem protocolos $\Sigma$ de três rodadas para NP no modelo CRS satisfazendo conhecimento zero contra verificadores maliciosos realizando consultas de superposição.

Os protocolos alcançam solidez estatística (statistical soundness) e conhecimento zero computacional (mesmo contra adversários quânticos de tempo polinomial com acesso a superposição).

Significância e Alegações

Os autores posicionam este trabalho como uma extensão natural e necessária da criptografia de conhecimento zero para o regime quântico.

• Importância Teórica: Resolve o problema aberto de construir ZK de superposição-seguro para QMA sob suposições padrão, uma tarefa anteriormente considerada difícil devido à falta de NIZKs ou esquemas de compromisso adequados.
• Relevância Prática: A estrutura de três rodadas torna estes protocolos significativamente mais leves que as NIZKs, oferecendo um caminho prático para assinaturas pós-quânticas e compiladores de computação multipartidária segura (ex: compiladores estilo GMW) que devem permanecer seguros contra adversários quânticos capazes de ataques de superposição.
• Avanço Conceitual: O framework "MPC no Cabeça Quântico" é apresentado como uma técnica generalizável que pode ser aplicada a outras protocolos de commit-and-open ou cut-and-choose que exigem verificação parcial de computações quânticas.

O artigo observa explicitamente que, embora existam NIZKs para QMA em modelos de oráculo ou com verificadores designados, o foco deles em protocolos de três rodadas com suposições padrão e configuração pública (CRS) fornece uma solução mais direta e eficiente para o modelo de ameaça específico de ataques de superposição.