A Practical Protocol for Quantum Oblivious Transfer from One-Way Functions

Resumo Técnico: Um Protocolo Prático para Transferência Oblívia Quântica a partir de Funções de Uma Via

1. Declaração do Problema

A Transferência Oblívia Quântica (QOT) é um primitivo fundamental para a construção de Computação Multi-Partidária (MPC) no cenário quântico. Embora trabalhos anteriores [6, 7] tenham demonstrado que a QOT poderia ser construída a partir de Funções de Uma Via (OWFs) e recursos quânticos, esses protocolos enfrentaram barreiras significativas para a realização experimental. Os principais problemas identificados foram:

• Fragilidade: Os protocolos existentes eram intolerantes a erros experimentais (por exemplo, inversões de bits durante a distribuição de estados).
• Complexidade de Implementação: A dependência de Provas de Conhecimento Zero que não faziam uso de caixa-preta das OWFs tornava a integração com funções de hash pós-quânticas práticas (como SHA) não trivial.
• Ineficiência: A estrutura iterativa dos protocolos anteriores exigia um número impraticável de estados quânticos (por exemplo, $\sim 10^{13}$ estados BB84 por execução), resultando em tempos de transmissão na ordem de meses.

Os autores visam fornecer um protocolo QOT tolerante a ruídos e eficiente, baseado em OWFs no modelo plano, que seja viável para configurações experimentais atuais.

2. Metodologia e Abordagem Técnica

A solução proposta constrói um protocolo QOT seguro por simulação, introduzindo um novo primitivo criptográfico: um esquema de Comprometimento de Bit Equívoco e Extraível Relaxado (ERE).

Inovações Principais:

• Extraibilidade Relaxada: Os autores observam que a extraibilidade total não é estritamente necessária para provar a segurança da QOT. Eles introduzem a "extraibilidade relaxada", onde um simulador pode extrair a mensagem comprometida para uma grande fração dos comprometimentos, enquanto uma fração negligenciável pode permanecer não extraível. Esse relaxamento permite uma estrutura de protocolo mais eficiente.
• Tolerância a Ruídos via Correção de Erros: Diferentemente de trabalhos anteriores que assumiam dispositivos sem ruído, este protocolo incorpora códigos de correção de erros lineares (especificamente códigos baseados em síndrome, como LDPC). O remetente transmite síndromes de valores codificados, permitindo que o destinatário (ou um simulador) corrija erros e extraia sementes corretas mesmo na presença de ruído.
• Destilação Eficiente de Sementes: O protocolo utiliza técnicas de amplificação de privacidade (Lema do Hash Residual) em estados BB84 para destilar sementes aleatórias. Essas sementes servem como chaves para comprometimentos equívocos. A estrutura agrupa essas sementes em famílias para permitir comprometimentos paralelos, evitando a sobrecarga quadrática encontrada em compiladores anteriores.
• Estrutura de Comprometimento: O esquema de Comprometimento ERE combina:
  1. EqComprometimento: Um compilador que transforma um comprometimento estatisticamente vinculante padrão em um equívoco. Os autores modificam o compilador original [7] reduzindo o número de repetições sequenciais de $\lambda$ para uma única instância, trocando a vinculação total por "vinculação relaxada".
  2. Comprometimento ERE: Um protocolo de nível superior que utiliza o esquema EqComprometimento. Envolve o remetente enviando estados BB84, o destinatário comprometendo-se com os resultados da medição e uma fase de desafio onde um subconjunto é aberto para verificação. Os estados restantes são usados para gerar sementes para a criptografia da mensagem final.

Fluxo do Protocolo (Protocolo 1):

1. Transmissão Quântica: Alice envia $2\lambda_{OT}$ estados BB84 para Bob.
2. Comprometimento: Bob mede e compromete-se com suas escolhas de base e resultados usando o esquema de Comprometimento ERE.
3. Desafio: Alice desafia um subconjunto aleatório $T$ dos comprometimentos. Bob abre esses para verificar a consistência com os estados enviados por Alice (contabilizando o erro experimental $\alpha$).
4. Geração de Chaves: Alice envia a informação de base para o conjunto não desafiado $\bar{T}$. Bob particiona $\bar{T}$ em conjuntos $I_0$ e $I_1$ com base em bases correspondentes.
5. Criptografia: Alice envia síndromes de correção de erros e criptografa suas mensagens $m_0, m_1$ usando sementes derivadas dos estados não desafiados e um Gerador Pseudoaleatório (PRG).
6. Descriptografia: Bob corrige seus erros usando as síndromes e descriptografa a mensagem correspondente ao seu bit de escolha $b$.

3. Contribuições Principais

• Novo Primitivo: A definição e construção de um esquema de Comprometimento de Bit Equívoco e Extraível Relaxado (ERE) baseado em OWFs.
• QOT Tolerante a Ruídos: Um protocolo QOT que lida explicitamente com erros experimentais (inversões de bits e eventos de múltiplos fótons) por meio de correção de erros baseada em síndrome, uma característica ausente em construções teóricas anteriores.
• Melhoria de Eficiência: Ao otimizar a estrutura de comprometimento e utilizar correção de erros, o protocolo reduz o número necessário de estados BB84 de $\sim 10^{13}$ (em [7]) para $\sim 10^7$.
• Destilação Multi-OT: O protocolo permite a destilação de múltiplas chaves OT ($n_{OT}$) a partir de uma única execução do protocolo, o que é crucial para uma implementação eficiente de MPC.
• Estrutura Analítica: O artigo fornece expressões analíticas para avaliar os recursos quânticos necessários contra parâmetros de segurança alvo (distância de traço $\Delta$), contabilizando taxas de erro físicas ($\alpha$) e vazamento ($\vartheta$).

4. Resultados e Desempenho

Os autores fornecem uma métrica de desempenho (Tabela 1) comparando seu protocolo com [7] e [21] para uma distância de traço alvo $\Delta \le 10^{-15}$:

• Redução de Recursos: O número necessário de estados BB84 ($N_{BB84}$) é reduzido para aproximadamente $1,43 \times 10^6$ (ideal) a $3,33 \times 10^7$ (cenário realista com ruído), comparado a $2,27 \times 10^{13}$ para o protocolo em [7].
• Eficiência Temporal: Essa redução traduz-se em um tempo de aquisição ($T_{acq}$) de segundos (por exemplo, 1,43s a 43,6s assumindo uma taxa de 1 MHz), enquanto o trabalho anterior [7] exigiria aproximadamente 8,6 meses.
• Segurança: O protocolo é provado ser seguro por simulação contra partes maliciosas no modelo plano, dependendo apenas da existência de funções de uma via pós-quânticas.

5. Significado e Alegações

O artigo afirma que este trabalho preenche a lacuna entre a criptografia quântica teórica e a implementação prática. Ao remover a exigência de dispositivos sem ruído e reduzir drasticamente a sobrecarga de recursos quânticos, os autores afirmam que seu protocolo torna a realização experimental da QOT (e, por extensão, da MPC quântica) viável com a tecnologia atual.

Os autores enfatizam que sua construção alcança custos de BB84 comparáveis aos protocolos baseados no Modelo de Oráculo Aleatório (ROM) [21], mas opera sob suposições computacionais estritamente mais fracas (modelo plano com OWFs em vez de ROM). Eles afirmam explicitamente que seu objetivo é uma "implementação prática", e não reivindicam igualar a eficiência clássica de comprometimentos baseados em ROM, mas sim fornecer um caminho viável para OT segura contra ataques quânticos no mundo real. O trabalho também destaca que a propriedade de extraibilidade relaxada é suficiente para a segurança, uma percepção técnica que permite os ganhos de eficiência sem comprometer as garantias de segurança baseadas em simulação exigidas para a MPC.