A robust and composable device-independent protocol for oblivious transfer using (fully) untrusted quantum devices in the bounded storage model

Este artigo apresenta um protocolo de transferência oblívia independente de dispositivos, robusto e composável no modelo de armazenamento limitado, que opera com dispositivos quânticos não confiáveis e sem memória de longo prazo, superando limitações anteriores ao garantir segurança contra ataques quânticos conjuntos e tolerar imperfeições de fabricação.

O essencial

Imagine que você e um amigo (vamos chamá-lo de "Bob") querem realizar um truque de mágica muito secreto chamado Transferência Obliviosa (Oblivious Transfer).

A regra é simples:

• Você tem dois segredos (dois bits de informação, digamos, "0" e "1").
• Bob quer escolher apenas um desses segredos para saber.
• O problema? Você não pode saber qual ele escolheu, e ele não pode descobrir o segredo que ele não escolheu.

No mundo real, isso é como se dois bancos rivais quisessem trocar informações financeiras sem que um espione o outro. Mas aqui está o grande desafio: quem fornece a "máquina" que faz a mágica pode ser um trapaceiro.

O Cenário: Máquinas Desconfiadas e o "Tempo de Decaimento"

Normalmente, para confiar em um protocolo de segurança, você precisa confiar que a máquina foi feita perfeitamente. Mas e se a máquina vier de um fornecedor mal-intencionado que a construiu com defeitos de propósito? Ou e se ela tiver "memória" para guardar segredos por anos?

Os autores deste paper propõem uma solução genial baseada em duas ideias principais:

1. Dispositivos Independentes (DI): Você não precisa confiar na máquina. Você apenas dá entradas (botões) e recebe saídas (luzes). Se a máquina se comportar como a física quântica diz que deve (usando um jogo chamado "Quadrado Mágico"), você sabe que está seguro, mesmo que a máquina tenha sido feita pelo vilão.
2. O "Delay" (O Atraso Mágico): Esta é a parte mais criativa. O protocolo assume que, após um certo tempo curto (digamos, 1 segundo), qualquer informação quântica que a máquina ou o vilão tentaram guardar desaparece (decoerência). É como se o vilão tivesse uma caixa de areia mágica: ele pode guardar areia (informação) por um segundo, mas depois disso, o vento (o tempo) sopra e a areia se espalha, tornando impossível recuperar o que estava lá.

A Analogia do "Jogo do Quadrado Mágico"

Para provar que a máquina não está trapaceando, vocês jogam um jogo chamado Quadrado Mágico.

• Imagine que a máquina é um tabuleiro de xadrez onde as peças se comportam de forma estranha e correlacionada.
• Se a máquina for "perfeita" (ou quase perfeita), ela ganha o jogo quase 100% das vezes.
• Se a máquina for trapaceira, ela perde mais vezes.

O protocolo faz o seguinte:

1. Teste: Vocês jogam o Quadrado Mágico várias vezes com uma parte das máquinas para ver se elas estão funcionando corretamente.
2. O "Delay": Depois dos testes, o tempo passa (o "DELAY"). Qualquer segredo quântico que o vilão tentou guardar para usar depois, desaparece.
3. A Escolha: Agora, com a confiança de que a máquina funcionou bem e que o vilão "esqueceu" o que tinha, vocês realizam a transferência dos segredos.

A Grande Inovação: "Não é só uma máquina, é um exército!"

Antes, os cientistas assumiam que todas as máquinas eram idênticas e independentes (como se você comprasse 100 moedas iguais de um banco). Mas no mundo real, um vilão poderia fazer 100 máquinas que "conversam" entre si de formas secretas para trapacear.

Este paper resolve um problema de anos: como garantir segurança mesmo se as máquinas forem todas diferentes, conectadas e feitas pelo vilão?

Eles usam uma técnica chamada Repetição Paralela.

• Pense nisso como jogar 1000 vezes o jogo do Quadrado Mágico ao mesmo tempo.
• Se o vilão tentar trapacear em uma rodada, ele precisa trapacear em todas as rodadas simultaneamente para não ser pego.
• A matemática mostra que, se o vilão tentar trapacear em muitas rodadas ao mesmo tempo, a probabilidade de sucesso cai para quase zero. É como tentar adivinhar 1000 senhas ao mesmo tempo: impossível.

Por que isso é importante?

1. Robustez: O protocolo funciona mesmo se as máquinas tiverem pequenos defeitos de fábrica (como um botão que aperta meio torto).
2. Segurança Composta: O protocolo é como um "bloco de Lego" seguro. Você pode usá-lo para construir sistemas maiores, como contratos digitais ou votações seguras, sem perder a segurança.
3. Realidade Atual (NISQ): Ele foi desenhado para funcionar com a tecnologia quântica de hoje (que é barulhenta e imperfeita), não exigindo computadores quânticos do futuro.

Resumo em uma frase

Os autores criaram um protocolo de segurança onde duas pessoas podem trocar segredos usando máquinas quânticas que podem ser defeituosas ou maliciosas, garantindo que, se o vilão tentar guardar segredos por muito tempo, o "vento do tempo" (decoerência) apagará a memória dele, e a matemática de jogos repetidos garantirá que ele não consiga trapacear sem ser pego.

É como se você e seu amigo fizessem um acordo: "Vamos jogar um jogo de azar. Se você tentar guardar a resposta para depois, o relógio vai zerar sua memória. E se você tentar trapacear em 1000 jogos ao mesmo tempo, a matemática vai garantir que você perca tudo."

Resumo técnico

Resumo Técnico: Protocolo de Transferência Oblívia (OT) Independente de Dispositivos no Modelo de Armazenamento Limitado

1. O Problema

A criptografia quântica tradicional frequentemente assume que os dispositivos quânticos utilizados (fontes de estados, medidores) são confiáveis e seguem especificações ideais. No entanto, em cenários do mundo real (como bancos trocando informações sensíveis), as partes podem não ter laboratórios próprios e depender de dispositivos de terceiros. Isso introduz riscos se o fornecedor for malicioso ou se houver erros de fabricação.

O problema central abordado é o desenvolvimento de um protocolo de Transferência Oblívia (OT) que seja:

• Independente de Dispositivos (DI): As partes (Alice e Bob) são clássicas e não precisam confiar na física interna dos dispositivos quânticos; eles apenas fornecem entradas e recebem saídas.
• Seguro contra Ataques Gerais (Não-IID): O adversário pode controlar completamente a fabricação dos dispositivos, permitindo correlações arbitrárias entre eles (não assumindo que são independentes e identicamente distribuídos - IID).
• Robusto: Deve funcionar mesmo com pequenos erros de fabricação nos dispositivos.
• Componível: O protocolo deve poder ser usado como um bloco de construção para protocolos maiores (como computação multipartidária segura) sem comprometer a segurança.
• Viável na Era NISQ: Deve ser implementável com dispositivos quânticos atuais (escala intermediária ruidosa), que não possuem memória quântica de longo prazo.

A OT é um primitivo fundamental, pois permite calcular qualquer funcionalidade multipartidária segura. No entanto, a OT é impossível com segurança incondicional sem restrições computacionais ou de memória.

2. Metodologia e Assunções

O protocolo opera sob o Modelo de Armazenamento Quântico Limitado (BQSM) com as seguintes premissas:

• Sem Memória de Longo Prazo: Tanto as partes honestas quanto o adversário possuem dispositivos que não podem armazenar estados quânticos indefinidamente. Após um intervalo de tempo fixo e constante no mundo real, chamado DELAY, qualquer estado quântico armazenado sofre decoerência completa (torna-se clássico).
• Dispositivos Não-Sinalizantes: Não há comunicação entre as partes de um dispositivo compartilhado após a entrada ser fornecida, mas antes da saída.
• Ataques Não-IID: O adversário pode preparar um estado global emaranhado e medições conjuntas para todos os dispositivos antes do protocolo começar.
• Recursos: Alice e Bob são entidades clássicas que interagem com dispositivos de "Quadrado Mágico" (Magic Square - MS).

Estrutura do Protocolo:
O protocolo utiliza $n = \text{polylog}(\lambda)$ dispositivos de Quadrado Mágico, onde $\lambda$ é o parâmetro de segurança.

1. Fase de Teste: Alice seleciona aleatoriamente um subconjunto de dispositivos para testar a propriedade do Quadrado Mágico. Ela gera entradas para ambos e envia as entradas de Bob. Bob executa os dispositivos e envia as saídas de volta. Alice verifica se a propriedade do MS foi satisfeita.
2. Fase de Protocolo (DELAY): Após o DELAY, os estados quânticos decoerem. Alice gera entradas aleatórias para os dispositivos restantes (não testados). Bob insere sua escolha $D$ em todos os seus dispositivos.
3. Extração e Ocultação: Alice usa bits extraídos das saídas de seus dispositivos (que devem ter alta entropia condicional dada a informação de Bob) para ocultar suas mensagens $S_0$ e $S_1$ usando um extrator forte (seeded extractor).
4. Correção de Erros: Para lidar com dispositivos não ideais (robustez), Alice envia síndromes de um código de correção de erros. Bob usa a garantia de vitória no jogo do Quadrado Mágico (do teste) e a síndrome para decodificar e recuperar a mensagem correta $S_D$.

3. Contribuições Chave e Inovações Técnicas

A. Teorema de Repetição Paralela para Estratégias Híbridas
A principal contribuição técnica é a prova de um Teorema de Repetição Paralela para uma classe específica de jogos emaranhados com estratégias híbridas (quântico-clássicas).

• O Desafio: Em jogos de segurança padrão, as entradas são independentes. No OT, as entradas de Alice e Bob podem ser correlacionadas (não-IID). Além disso, o modelo BQSM impõe uma restrição temporal (DELAY) que transforma o estado quântico em clássico.
• A Solução: Os autores definem uma estratégia restrita onde o DELAY é modelado como uma porta CNOT obrigatória entre o estado quântico e um registro de ambiente, seguida pela perda de acesso ao registro quântico. Eles combinam ideias de repetição paralela de jogos clássicos, quânticos e jogos "ancorados" (anchored games) para provar que a probabilidade de um adversário vencer o jogo repetido $n$ vezes decai exponencialmente com $n$, mesmo com entradas não independentes.

B. Segurança Composável (Simulador Baseado)
O artigo estabelece um framework para segurança composável em protocolos quânticos de duas partes.

• Eles definem segurança baseada em simuladores "aumentada" (augmented-security), que garante que o estado real do protocolo é indistinguível do estado ideal, mesmo quando o protocolo é executado como sub-rotina em um protocolo externo que possui registros de estado residual.
• Isso resolve uma questão em aberto na literatura: a falta de protocolos DI de OT que sejam simultaneamente seguros contra ataques não-IID e composáveis.

C. Robustez e Eficiência

• Robustez: O protocolo mantém a correção mesmo que os dispositivos usados estejam a uma distância constante (pequena) do dispositivo ideal. Isso é crucial para a implementação prática na era NISQ.
• Eficiência: As partes honestas operam em tempo $\text{polylog}(\lambda)$ e usam $\text{polylog}(\lambda)$ dispositivos, tornando-o altamente eficiente em comparação com protocolos que exigem recursos lineares.

4. Resultados Principais

1. Existência de Protocolo OT DI: Foi demonstrada a existência de um protocolo de OT entre Alice e Bob que é:
   • Independente de dispositivos (DI).
   • Seguro contra um adversário com poder computacional ilimitado e controle total sobre dispositivos não-IID.
   • Seguro no modelo de armazenamento limitado (BQSM).
   • Robusto a erros de fabricação.
   • Composável (segurança baseada em simulador).
2. Implementabilidade NISQ: O protocolo requer apenas o armazenamento de pares EPR por um curto período (antes do DELAY), o que é viável com a tecnologia quântica atual, sem necessidade de memória quântica de longo prazo.
3. Erro Negligível: O protocolo possui erros de correção e segurança negligíveis em relação ao parâmetro de segurança $\lambda$.

5. Significado e Impacto

Este trabalho representa um avanço significativo na criptografia quântica de duas partes desconfiadas:

• Resolução de Questão Aberta: Resolve o problema aberto de como construir protocolos DI de OT que sejam seguros contra ataques gerais (não-IID) e composáveis, algo que trabalhos anteriores (como [KW16] ou [KST22]) não conseguiam fazer simultaneamente.
• Viabilidade Prática: Ao focar no modelo de armazenamento limitado e na robustez, o trabalho conecta a teoria da segurança quântica com a realidade dos dispositivos NISQ, onde a memória quântica de longo prazo é inexistente, mas a decoerência pode ser explorada como uma ferramenta de segurança.
• Fundação para MPC: Como a OT é um bloco de construção universal para Computação Multipartidária Segura (MPC), este protocolo permite a construção de esquemas de MPC totalmente independentes de dispositivos e composáveis no modelo de armazenamento limitado, algo anteriormente inatingível.

Em suma, o artigo fornece a primeira solução prática e teoricamente sólida para a OT independente de dispositivos em um cenário de adversário poderoso e dispositivos não confiáveis, utilizando a decoerência natural como recurso de segurança.