Na teoria da complexidade computacional, uma suposição de dureza computacional (ou hipótese de dificuldade) é a hipótese de que um problema específico não pode ser resolvido de forma eficiente (onde eficiente normalmente significa em "tempo polinomial"). Não se sabe como provar a dureza (incondicional) para essencialmente nenhum problema útil. Em vez disso, os cientistas da computação dependem de reduções para relacionar formalmente a dureza de um problema novo ou complicado a uma suposição de dureza computacional sobre um problema que é melhor compreendido.

As suposições de dureza computacional são de particular importância na criptografia. Um objetivo principal na criptografia é criar primitivas criptográficas com segurança comprovável. Em alguns casos, descobre-se que protocolos criptográficos possuem segurança teórica da informação; o one-time pad é um exemplo comum. No entanto, a segurança de teoria da informação nem sempre pode ser alcançada; nesses casos, os criptógrafos recorrem à segurança computacional. Grosso modo, isso significa que esses sistemas são seguros assumindo que quaisquer adversários sejam computacionalmente limitados, como todos os adversários são na prática.

As suposições de dureza computacional também são úteis para orientar projetistas de algoritmos: é improvável que um algoritmo simples refute uma suposição de dureza computacional bem estudada, como o P ≠ NP.

Comparando suposições de dureza Os cientistas da computação têm diferentes maneiras de avaliar quais suposições de dureza são mais confiáveis.

Força das suposições de dureza Dizemos que a suposição é mais forte que a suposição quando implica (e a recíproca é falsa ou desconhecida). Em outras palavras, mesmo que a suposição fosse falsa, a suposição ainda poderia ser verdadeira, e os protocolos criptográficos baseados na suposição ainda poderiam ser seguros para uso. Assim, ao projetar protocolos criptográficos, espera-se ser capaz de provar a segurança usando as suposições mais fracas possíveis.

Suposições de caso médio vs. pior caso

Uma suposição de caso médio afirma que um problema específico é difícil na maioria das instâncias de alguma distribuição explícita, enquanto uma suposição de pior caso apenas afirma que o problema é difícil em algumas instâncias. Para um determinado problema, a dureza de caso médio implica dureza de pior caso, portanto, uma suposição de dureza de caso médio é mais forte do que uma suposição de dureza de pior caso para o mesmo problema. Além disso, mesmo para problemas incomparáveis, uma suposição como a hipótese do tempo exponencial é frequentemente considerada preferível a uma suposição de caso médio como a conjectura do clique plantado. No entanto, para aplicações criptográficas, saber que um problema tem alguma instância difícil (o problema é difícil no pior caso) é inútil porque não nos fornece uma maneira de gerar instâncias difíceis.J. Katz and Y. Lindell, Introduction to Modern Cryptography (Chapman and Hall/CRC Cryptography and Network Security Series), Chapman and Hall/CRC, 2007. Felizmente, muitas suposições de caso médio usadas em criptografia (incluindo RSA, logaritmo discreto e alguns problemas de reticulado) podem ser baseadas em suposições de pior caso por meio de reduções de pior caso para caso médio.

Falsificabilidade Uma característica desejada de uma suposição de dureza computacional é a falsificabilidade, ou seja, se a suposição fosse falsa, então seria possível provar isso. Em particular, introduziu uma noção formal de falsificabilidade criptográfica. Grosso modo, uma suposição de dureza computacional é dita falsificável se puder ser formulada em termos de um desafio: um protocolo interativo entre um adversário e um verificador eficiente, onde um adversário eficiente pode convencer o verificador a aceitar se e somente se a suposição for falsa.

Suposições comuns de dureza criptográfica

Existem muitas suposições de dureza criptográfica em uso. Esta é uma lista de algumas das mais comuns e alguns protocolos criptográficos que as utilizam.

Fatoração de inteiros

Dado um inteiro composto , e em particular um que seja o produto de dois números primos grandes , o problema da fatoração de inteiros é encontrar e (mais geralmente, encontrar primos tais que ). É um grande problema em aberto encontrar um algoritmo para fatoração de inteiros que rode em tempo polinomial no tamanho da representação (). A segurança de muitos protocolos criptográficos depende da suposição de que a fatoração de inteiros é difícil (ou seja, não pode ser resolvida em tempo polinomial). Criptossistemas cuja segurança é equivalente a esta suposição incluem a assinatura de Rabin e o criptossistema Okamoto-Uchiyama. Muitos outros criptossistemas dependem de suposições mais fortes, como o RSA, problemas de residuocidade e a ocultação de phi.

Problema RSA

Dado um número composto , expoente e um número , o problema RSA é encontrar . Conjetura-se que o problema seja difícil, mas torna-se fácil dada a fatoração de . No criptossistema RSA, é a chave pública, é a cifragem da mensagem , e a fatoração de é a chave secreta usada para a decifragem.

Problemas de residuocidade

Dado um número composto e inteiros , o problema da residuocidade é determinar se existe (alternativamente, encontrar um) tal que

Casos especiais importantes incluem o problema da residuocidade quadrática e o suposição de residuocidade composta decisional. Como no caso do RSA, este problema (e seus casos especiais) são conjeturados como sendo difíceis, mas tornam-se fáceis dada a fatoração de . Alguns criptossistemas que dependem da dureza dos problemas de residuocidade incluem: Criptossistema Goldwasser-Micali (problema da residuocidade quadrática) Gerador Blum Blum Shub (problema da residuocidade quadrática) Criptossistema Paillier (problema da residuocidade composta decisional) Criptossistema Benaloh (problema da residuocidade superior) Criptossistema Naccache-Stern (problema da residuocidade superior)

Suposição de ocultação de phi

Para um número composto , não se sabe como calcular eficientemente sua função totiente de Euler . A suposição de ocultação de phi postula que é difícil calcular e, além disso, até mesmo calcular quaisquer fatores primos de é difícil. Esta suposição é usada no protocolo PIR de Cachin–Micali–Stadler.

Problema do logaritmo discreto (DLP)

Dados elementos e de um grupo , o problema do logaritmo discreto pede um inteiro tal que . Não se sabe se o problema do logaritmo discreto é comparável à fatoração de inteiros, mas suas complexidades computacionais estão intimamente relacionadas.

A maioria dos protocolos criptográficos relacionados ao problema do logaritmo discreto na verdade depende da suposição mais forte de Diffie-Hellman: dados os elementos do grupo , onde é um gerador e são inteiros aleatórios, é difícil encontrar . Exemplos de protocolos que usam essa suposição incluem a troca de chaves Diffie-Hellman original, bem como a criptografia ElGamal (que depende da variante ainda mais forte Diffie-Hellman Decisional (DDH)).

Mapas multilineares Um mapa multilinear é uma função (onde são grupos) tal que para quaisquer e , .

Para aplicações criptográficas, gostaria-se de construir grupos e um mapa tal que o mapa e as operações de grupo em possam ser computados eficientemente, mas o problema do logaritmo discreto em ainda seja difícil. Algumas aplicações requerem suposições mais fortes, por exemplo, análogos multilineares das suposições de Diffie-Hellman.

Para o caso especial de , mapas bilineares com segurança acreditável foram construídos usando o pareamento de Weil e o pareamento de Tate. Para , muitas construções foram propostas nos últimos anos, mas muitas delas também foram quebradas, e atualmente não há consenso sobre um candidato seguro.

Alguns criptossistemas que dependem de suposições de dureza multilinear incluem: Esquema de Boneh-Franklin (Diffie-Hellman bilinear) Boneh–Lynn–Shacham (Diffie-Hellman bilinear) Candidato de Garg-Gentry-Halevi-Raykova-Sahai-Waters para ofuscação de indistinguibilidade e criptografia funcional (quebra-cabeças multilineares)

Problemas de reticulado

O problema computacional mais fundamental em reticulados (lattices) é o problema do vetor mais curto (SVP): dado um reticulado , encontrar o vetor não nulo mais curto . A maioria dos criptossistemas requer suposições mais fortes sobre variantes do SVP, como o problema dos vetores independentes mais curtos (SIVP), GapSVP, ou Unique-SVP.

A suposição de dureza de reticulado mais útil em criptografia é para o problema de aprendizagem com erros (LWE): Amostras dadas para , onde para alguma função linear , é fácil aprender usando álgebra linear. No problema LWE, a entrada para o algoritmo tem erros, ou seja, para cada par com alguma pequena probabilidade. Acredita-se que os erros tornem o problema intratável (para parâmetros apropriados); em particular, existem reduções conhecidas de pior caso para caso médio a partir de variantes do SVP.

Para computadores quânticos, os problemas de fatoração e logaritmo discreto são fáceis, mas conjetura-se que os problemas de reticulado sejam difíceis. Isso torna alguns criptossistemas baseados em reticulado candidatos para a criptografia pós-quântica.

Alguns criptossistemas que dependem da dureza de problemas de reticulado incluem: NTRU (tanto NTRUEncrypt quanto NTRUSign) A maioria dos candidatos para criptografia totalmente homomórfica

Suposições de dureza não criptográficas Além de suas aplicações criptográficas, as suposições de dureza são usadas na teoria da complexidade computacional para fornecer evidências para afirmações matemáticas que são difíceis de provar incondicionalmente. Nessas aplicações, prova-se que a suposição de dureza implica alguma afirmação teórica de complexidade desejada, em vez de provar que a própria afirmação é verdadeira. A suposição mais conhecida deste tipo é a suposição de que P ≠ NP,. mas outras incluem a hipótese do tempo exponencial,. a conjectura do clique plantado e a conjectura dos jogos únicos..

Problemas C-difíceis Muitos problemas computacionais de pior caso são conhecidos por serem difíceis ou mesmo completos para alguma classe de complexidade , em particular NP-difícil (mas frequentemente também PSPACE-difícil, PPAD-difícil, etc.). Isso significa que eles são pelo menos tão difíceis quanto qualquer problema na classe . Se um problema é -difícil (em relação a reduções de tempo polinomial), então ele não pode ser resolvido por um algoritmo de tempo polinomial a menos que a suposição de dureza computacional seja falsa.

Hipótese do tempo exponencial (ETH) e variantes

A hipótese do tempo exponencial (ETH) é um fortalecimento da suposição de dureza , que conjetura que não apenas o problema de satisfatibilidade booleana (SAT) não possui um algoritmo de tempo polinomial, mas também requer tempo exponencial (). Uma suposição ainda mais forte, conhecida como a hipótese do tempo exponencial forte (SETH) conjetura que o -SAT requer tempo , onde . ETH, SETH e suposições de dureza computacional relacionadas permitem deduzir resultados de complexidade refinados, por exemplo, resultados que distinguem tempo polinomial e tempo quase-polinomial, ou mesmo versus . Tais suposições também são úteis na complexidade parametrizada.

Suposições de dureza de caso médio

Assume-se que alguns problemas computacionais sejam difíceis em média sobre uma distribuição particular de instâncias.