💻 computer science

Lower Bounds on Black-Box Constructions of Pseudorandom Functions

Este artigo estabelece que nenhuma construção totalmente black-box de uma função pseudorrandom (PRF) a partir de um gerador pseudorrandom (PRG) pode alcançar $o(n/\log n)$ chamadas não adaptativas ao PRG, mesmo para PRFs fracas com saídas de um bit, fornecendo, desta forma, limites inferiores fortes sobre a eficiência de tais construções e deixando a possibilidade de uma construção de invocação única como um grande desafio em aberto.

Autores originais: Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

Publicado 2026-08-17

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

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

O Dilema do Chaveiro Digital

Imagine que você é um mestre chaveiro tentando construir uma porta de cofre inquebrável. No mundo da segurança digital, este "cofre" é uma Função Pseudorrandom (PRF). Pense em uma PRF como uma máquina mágica: você fornece a ela uma chave secreta e uma entrada específica (como um número de quarto), e ela cospe uma sequência de números que parece completamente aleatória para qualquer pessoa que esteja observando. No entanto, se você usar a mesma chave secreta novamente, ela sempre produzirá exatamente a mesma sequência "aleatória". Essa consistência é o que a torna útil para proteger seus e-mails, garantir suas transações bancárias e manter suas senhas seguras.

Para construir esta máquina mágica, os criptógrafos frequentemente começam com algo mais simples chamado Gerador de Números Pseudorrandom (PRG). Um PRG é como uma semente minúscula e eficiente que cresce em uma floresta massiva e de aparência aleatória. Ele pega uma sequência curta e secreta e a estende em uma muito mais longa, que parece aleatória para qualquer programa de computador. A grande questão na criptografia tem sido: Quantas vezes precisamos usar essa máquina de "extensão de semente" para construir nossa "porta de cofre"?

Por décadas, a receita padrão (conhecida como construção GGM) tem sido usar a máquina de extensão de semente repetidamente, em uma estrutura semelhante a uma árvore, aproximadamente $\omega(\log n)$ vezes (onde $n$ é o tamanho da semente). Funciona muito bem, mas parece um pouco desajeitado. Existe um atalho? Poderíamos construir uma porta de cofre perfeita usando a máquina de extensão de semente apenas uma vez? Ou talvez apenas algumas vezes? Este artigo mergulha profundamente nessa questão, agindo como um detetive tentando provar que, não importa o quão inteligente você seja, você simplesmente não consegue construir uma porta de cofre segura com poucas extensões da semente.

A Grande Descoberta do Artigo: O Problema do "Pouco Demais"

Este artigo, escrito por Bar Alon, Itai Dinur e Muthuramakrishnan Venkitasubramaniam, aborda a questão fundamental: Qual é o número absoluto mínimo de vezes que devemos chamar um Gerador de Números Pseudorrandom (PRG) para construir uma Função Pseudorrandom (PRF)?

Os autores provam que, para um tipo específico e muito razoável de construção, a resposta é "muito mais do que você poderia esperar". Especificamente, eles mostm que você não pode construir uma PRF segura usando um método "totalmente de caixa preta" se chamar o PRG um número ínfimo de vezes — especificamente, menos de aproximadamente $n / \log n$ vezes (onde $n$ é o comprimento da entrada do PRG).

Para entender a prova deles, imagine um jogo de "Identifique o Falso".

A Configuração: Uma "Redução" (o construtor) tenta criar uma PRF usando um PRG. Eles também têm um "Adversário" (um hacker) tentando descobrir se a PRF é real ou apenas uma função aleatória.
O Truque: Os autores imaginam um cenário onde o construtor é "limitado em consultas" (query-bounded). Isso significa que o construtor pode pedir ajuda ao hacker, mas o número de vezes que ele pode perguntar é limitado e não explode com base em quantas perguntas o hacker faz.
O Contra-ataque: Os autores constroem um "Adversário Real" e um "Adversário Ideal".
- O Adversário Ideal é um computador superpoderoso e lento que pode verificar todas as chaves secretas possíveis para ver se elas se encaixam nos dados. Ele consegue facilmente distinguir se uma função é uma PRF ou aleatória.
- O Adversário Real é o que o construtor realmente usa. Ele não possui superpoderes; ele apenas vê as perguntas limitadas que o construtor fez ao PRG.
A Revelação: Os autores provam que, se o construtor usar poucas chamadas ao PRG, o "Adversário Real" pode imitar perfeitamente o "Adversário Ideal" sem, de fato, quebrar a segurança do PRG. Isso cria um paradoxo: se o construtor pudesse construir uma PRF segura com tão poucas chamadas, ele também seria capaz de quebrar o próprio PRG usando um método que é lento demais para ser prático, o que contradiz a suposição de que o PRG é seguro.

O Resultado Principal:
O artigo prova que para construções não adaptativas (onde o construtor decide todas as perguntas ao PRG antes de ver qualquer resposta), é impossível construir uma PRF com menos de $o(n / \log n)$ chamadas ao PRG. Isso se mantém verdadeiro mesmo se a PRF produzir apenas um bit (0 ou 1) e mesmo se o hacker for restrito a fazer perguntas simples e aleatórias.

O Resultado de "Saída Longa":
Os autores também analisaram PRFs que produzem sequências longas de dados (não apenas um único bit). Eles provaram que, mesmo se o construtor for permitido ser "adaptativo" (fazendo perguntas uma por uma e usando as respostas para decidir a próxima pergunta), ainda existe um limite rígido. Se o PRG estender a entrada em uma pequena quantidade, você precisa de pelo menos aproximadamente $out / \log n$ chamadas. Se o PRG estender a entrada em uma grande quantidade, você precisa de pelo menos $out / r$ chamadas.

O Que Isso Significa para o Sonho da "Chamada Única"

Por muito tempo, os criptógrafos se perguntaram se uma construção de "chamada única" seria possível — construir uma PRF perfeita estendendo a semente apenas uma vez.

Para métodos não adaptativos: Este artigo efetivamente descarta essa possibilidade. Você não pode construir uma PRF segura com um número constante de chamadas (como 1, 2 ou 10) se o tamanho da entrada crescer. A matemática simplesmente não permite.
Para métodos adaptativos: O artigo não descarta uma construção de chamada única para todos os cenários adaptativos. Em vez disso, mostra que, para PRFs com saídas longas, o número de chamadas deve escalar com o tamanho da saída. Você não pode se livrar de um número pequeno e fixo de chamadas para uma porta de cofre massiva se a saída for grande. A questão de saber se uma construção de chamada única adaptativa existe para PRFs com saídas curtas permanece aberta.

A Ressalva do "Limitado em Consultas"

Os autores são muito cuidadosos com suas suposições. Eles focam em uma classe de reduções que chamam de "limitadas em consultas" (query-bounded). Em termos simples, isso significa que a interação do construtor com o hacker é limitada de uma forma que não depende de quantas perguntas o hacker faz. Os autores argumentam que quase toda construção na história da criptografia se encaixa nessa descrição. Eles reconhecem que, se alguém inventar uma maneira estranha e não padronizada de construir uma PRF onde o construtor faz milhões de perguntas ao hacker apenas porque o hacker fez uma pergunta, a prova deles pode não se aplicar. Mas para todos os designs criptográficos práticos e padrão, os limites inferiores que encontraram permanecem firmes.

A Conclusão

Este artigo não apenas sugere um limite; ele fornece uma prova matemática de que o "atalho" para construir PRFs é um beco sem saída. Se você quer uma PRF de caixa preta segura, você não pode pular etapas. Você tem que pagar o custo de chamar o PRG vezes o suficiente para garantir que a "entropia" (a aleatoriedade e imprevisibilidade) seja alta o suficiente para enganar qualquer hacker. A famosa construção GGM, que utiliza cerca de $\omega(\log n)$ chamadas, acaba sendo quase ótima. O sonho de construir uma fortaleza com um único tijolo é matematicamente impossível neste contexto.

Resumo Técnico: Limites Inferiores em Construções de Caixa-Preta de Funções Pseudorandomas

Declaração do Problema

O artigo aborda uma questão fundamental e aberta na criptografia: Qual é o número mínimo de invocações de um gerador de números pseudorandomos (PRG) necessário para construir uma função pseudorandoma (PRF) via uma construção de caixa-preta total?

O trabalho seminal de Goldreich, Goldwasser e Micali (GGM) estabeleceu que uma PRF pode ser construída a partir de um PRG usando uma abordagem baseada em árvores. Quando combinado com a técnica de extensão de domínio de Levin, essa construção requer $\omega(\log n)$ chamadas ao PRG, onde $n$ é o comprimento de entrada do PRG. Embora o trabalho recente de Beimel, Malkin e Mazor tenha provado a otimalidade de GGM para uma classe específica de "construções de árvore", o caso geral permanece não resolvido. Especificamente, não se sabe se uma PRF pode ser construída com menos de $\omega(\log n)$ chamadas, ou mesmo com uma única chamada, utilizando técnicas gerais de caixa-preta.

Este trabalho investiga essa questão dentro do framework de construções de caixa-preta total, onde tanto a construção quanto a redução de segurança são de caixa-preta. Os autores focam especificamente em uma classe de reduções denominada reduções limitadas por consultas (query-bounded), onde o número de interações que a redução faz com o adversário é limitado por um polinômio independente da complexidade de consulta do adversário (desde que o adversário seja suficientemente bem-sucedido).

Metodologia

Os autores empregam o paradigma de meta-redução para estabelecer seus limites inferiores. Esta técnica envolve a construção de um adversário "real" ineficiente que pode simular um adversário "ideal" (que quebra a PRF) sem acesso direto ao subjacente PRG, thereby quebrando a segurança do PRG usando menos consultas do que o permitido.

Componentes Técnicos Chave:

Reduções Limitadas por Consultas: Os autores definem uma redução como limitada por consultas se o número de vezes que ela consulta o adversário distinguidor é limitado por um polinômio $d(n)$ , independentemente de quantas consultas o adversário faz ao seu oracle. Esta classe captura a maioria das reduções conhecidas na literatura, incluindo as construções de GGM e Goldreich-Levin.
Adversários Ideal vs. Real:
- Adversário Ideal ( $A_{ideal}$ ): Um adversário ineficiente que possui acesso exponencial ao oracle do PRG. Ele tenta quebrar a PRF encontrando uma chave consistente com uma grande fração de pares entrada-saída.
- Adversário Real ( $A_{real}$ ): Um adversário ineficiente que não possui acesso ao PRG. Em vez disso, ele recebe os pares consulta-resposta gerados pela interação da redução com o PRG. Ele tenta simular o $A_{ideal}$ estimando a probabilidade de uma chave ser consistente com as saídas observadas.
Funções de Pontuação e Independência:
- O desafio central é que as saídas da PRF em diferentes entradas podem ser dependentes se compartilharem sementes (seeds) do PRG.
- Os autores introduzem um procedimento para identificar "sementes frequentes" (sementes usadas por muitas entradas) e substituir suas saídas por valores fixos. Isso reduz o número de chamadas ativas ao PRG.
- Para as entradas restantes, eles utilizam uma afirmação combinatória (Claim 3/6) para mostrar que ou um grande conjunto de entradas usa sementes do PRG mutuamente disjuntas (permitindo argumentos de independência via desigualdade de Hoeffding) ou o número de tais chaves é desprezível.
- Para lidar com a distância estatística entre os adversários ideal e real, os autores utilizam um limiar randomizado (amostrado uniformemente de $[0.8, 1]$ ) em vez de um limiar fixo. Isso suaviza a fronteira de decisão, garantindo que a distribuição de saída do adversário real seja estatisticamente próxima da do adversário ideal, desde que o número de entradas $m$ seja suficientemente grande em relação ao número de consultas da redução $d$ .
Argumentos de Entropia para Saídas Longas: Para o segundo resultado (Teorema 2), os autores utilizam um argumento baseado em entropia. Eles constroem um PRG específico que aplica aleatoriedade apenas a um pequeno prefixo da semente. Isso limita a entropia da saída da PRF para ser significativamente menor do que a de uma função verdadeiramente aleatória, permitindo que um distinguidor quebre a construção se o número de chamadas for muito baixo.

Contribuições Principais e Resultados

1. Limite Inferior para Chamadas Não-Adaptativas (Teorema 1)

O artigo prova que nenhuma construção de caixa-preta total de uma PRF a partir de um PRG existe usando chamadas não-adaptativas e reduções limitadas por consultas se o número de chamadas $c$ satisfizer:
$c = o\left(\frac{n}{\log n}\right) \quad \text{e} \quad c = o\left(\frac{in}{\log in}\right)$
onde $n$ é o comprimento de entrada do PRG e $in$ é o comprimento de entrada da PRF.

Escopo: Este resultado é válido mesmo para PRFs fracas (onde o adversário é restrito a consultas i.i.d. uniformes) e para PRFs com saída de um bit.
Implicação: Isso descarta a possibilidade de construir uma PRF com um número constante de chamadas não-adaptativas (ex: uma única chamada) para PRFs com comprimentos de entrada $in = \omega(\log n)$ , resolvendo um caso específico do problema em aberto para reduções limitadas por consultas.

2. Limite Inferior para Saídas Longas (Teorema 2)

O artigo estabelece um limite inferior para PRFs com saídas longas ($out$) que se mantém mesmo para construções adaptativas e não exige que a redução seja limitada por consultas.

Resultado: Não existe uma construção de caixa-preta total de uma PRF com comprimento de saída $out$ a partir de um PRG com stretch $r$ usando menos de $\frac{out}{\max(r, \omega(\log n))}$ chamadas.
Comparação com GGM: A construção GGM (com o truque de Levin) usa $\omega(\log n)$ chamadas a um PRG de stretch $n$ para produzir uma saída de $n$ bits. Ao compor isso com um PRG de stretch de 1 bit (exigindo $O(n/\log n)$ chamadas), o total de chamadas a um PRG de stretch de 1 bit é $\omega(n)$ . O Teorema 2 implica um limite inferior de $\Omega(n / \omega(\log n))$ , mostrando que GGM é ótima até um fator de $\omega(\log n)$ .

Significância e Alegações

O artigo afirma fazer um progresso significativo na questão da otimalidade das construções de PRF a partir de PRGs.

Otimidade de GGM: Enquanto resultados anteriores eram limitados a "construções de árvore", este trabalho fornece limites inferiores para construções de caixa-preta gerais sob suposições específicas, mas naturais (reduções limitadas por consultas).
Resolução do Caso de Chamada Única: Os autores afirmam explicitamente que seu resultado resolve a questão de se uma PRF pode ser construída com uma única chamada ao PRG para a classe de reduções limitadas por consultas. Eles demonstram que tal construção é impossível para PRFs com comprimentos de entrada $in = \omega(\log n)$ .
Robustez: Os resultados de impossibilidade mantêm-se mesmo para PRFs fracas e, no caso de saídas longas, para construções adaptativas.
Limitações: Os autores reconhecem modestamente que seu principal resultado (Teorema 1) depende da suposição de "limitação por consultas". Eles observam que permanece uma questão em aberto se esses limites inferiores podem ser estendidos a todas as reduções de caixa-preta, já que sua prova depende do fato de a contagem de interação da redução ser independente da complexidade de consulta do adversário.

Em resumo, o artigo demonstra que a construção GGM é quase ótima em termos do número de invocações de PRG necessárias, particularmente para construções não-adaptativas e aquelas com saídas longas, ao utilizar técnicas de meta-redução e análise cuidadosa de entropia.