Suposições de Dificuldade Computacional

As suposições de dificuldade computacional são conjecturas não provadas, mas bem estudadas — como a dificuldade de fatoração, logaritmos discretos e problemas de rede (lattice) — nas quais a segurança dos esquemas criptográficos se baseia em última instância.

Definition

Uma suposição de dificuldade computacional é uma conjectura de que um problema computacional específico não pode ser resolvido eficientemente (em tempo polinomial) por qualquer adversário realista, servindo como a base sobre a qual a segurança provável é construída.

Scope

Este tópico abrange as suposições nas quais a criptografia se baseia: a existência de funções de mão única, problemas de teoria dos números (fatoração, RSA, logaritmo discreto) e os problemas de rede (lattice) e código usados na criptografia pós-quântica. Ele aborda a hierarquia entre as suposições, a distinção entre dificuldade no pior caso e no caso médio, e como as suposições são verificadas. Exclui o mecanismo de redução que conecta as suposições aos esquemas e as próprias definições de segurança, tratados em tópicos relacionados.

Core questions

• Por que a segurança criptográfica deve se basear em suposições de dificuldade não provadas?
• Quais são as principais suposições (funções de mão única, fatoração, logaritmo discreto, redes (lattices))?
• Como as suposições se relacionam em termos de força?
• Qual é a diferença entre dificuldade no pior caso e no caso médio?
• Como os problemas difíceis candidatos são verificados e o que acontece quando um deles é quebrado?

Key concepts

• função de mão única
• função de armadilha (trapdoor function)
• suposição de fatoração de inteiros
• suposição de logaritmo discreto
• suposições RSA e Diffie-Hellman
• aprendizado com erros (LWE)
• dificuldade no pior caso vs. no caso médio
• P versus NP
• hierarquia de suposições

Key theories

Funções de mão única como uma suposição mínima

A existência de funções de mão única — fáceis de calcular, difíceis de inverter — é necessária e suficiente para grande parte da criptografia simétrica e é a suposição mais básica; quase toda a criptografia pressupõe pelo menos isso.

Suposições de teoria dos números e de rede (lattice)

A criptografia de chave pública baseia-se em problemas estruturados — fatoração de inteiros, o problema RSA e logaritmos discretos (classicamente), e problemas de aprendizado com erros e de vetor mais curto em redes (lattices) (pós-quântica) — cada um apoiado por décadas de escrutínio criptoanalítico.

Mechanisms

A criptografia necessita de problemas que sejam difíceis em média (em instâncias aleatórias), não apenas no pior caso, uma vez que as chaves são escolhidas aleatoriamente. As suposições são organizadas em uma hierarquia aproximada: uma quebra de uma suposição mais fraca (por exemplo, fatoração) frequentemente quebra esquemas construídos sobre ela, enquanto reduções relacionam as suposições umas às outras. As suposições de rede (lattice) são notáveis por reduções do pior caso para o caso médio, conferindo maior confiança. A confiança em qualquer suposição provém de um esforço criptoanalítico sustentado e malsucedido, em vez de prova.

Clinical relevance

As suposições de dificuldade determinam o que é e o que não é seguro para ser implementado. A descoberta de que computadores quânticos quebrariam a fatoração e os logaritmos discretos (via algoritmo de Shor) invalidou as suposições por trás da criptografia RSA e de curva elíptica contra adversários quânticos, impulsionando diretamente a mudança para padrões pós-quânticos baseados em rede (lattice). Escolher esquemas construídos sobre suposições bem estudadas e acompanhar seu status é essencial para a segurança a longo prazo.

Evidence & guidelines

Os órgãos de padronização favorecem suposições com longos históricos criptoanalíticos; o processo pós-quântico do NIST avaliou explicitamente a maturidade e a confiança das suposições subjacentes de rede (lattice), código e hash. A melhor prática evita suposições exóticas ou recém-propostas para sistemas de alta segurança e prefere problemas conservadores e bem verificados, com tamanhos de chave definidos contra os melhores ataques conhecidos.

History

A dependência da dificuldade surgiu com a criptografia de chave pública em 1976, quando Diffie e Hellman vincularam a segurança ao logaritmo discreto, e o RSA à fatoração. A década de 1980 formalizou as funções de mão única e a distinção entre pior caso/caso médio. As reduções do pior caso para o caso médio de Ajtai (1996) e o problema de aprendizado com erros (LWE) de Regev (2005) estabeleceram as suposições de rede (lattice), que ganharam proeminência como fundamentos resistentes a ataques quânticos e sustentam os novos padrões pós-quânticos.

Key figures

• Whitfield Diffie
• Martin Hellman
• Oded Goldreich
• Oded Regev
• Andrew Yao

Seminal works

• diffie1976
• goldreich2001
• katz2020

Frequently asked questions

Por que não podemos simplesmente provar que esses problemas são difíceis?

Provar que um problema requer tempo superpolinomial resolveria questões abertas profundas na teoria da complexidade (notavelmente P versus NP), que permanecem sem solução. Assim, a criptografia depende de suposições cuja plausibilidade advém de décadas de tentativas malsucedidas de resolvê-los eficientemente.

O que acontece se uma suposição de dificuldade for quebrada?

Todo esquema cuja segurança se reduz a essa suposição torna-se potencialmente inseguro e deve ser substituído. É por isso que a ameaça quântica à fatoração e aos logaritmos discretos impulsionou uma migração global para esquemas baseados em suposições diferentes e resistentes a ataques quânticos.