Status dos mundos de Impagliazzo?

33

Em 1995, Russell Impagliazzo propôs cinco mundos de complexidade:

1- Algoritmica: com todas as conseqüências surpreendentes.P=NP

2- Heurística: completos de são difíceis no pior dos casos ( ), mas são eficientemente solucionáveis ​​no caso médio.NPP≠NP

3- Pessiland: Existem completos de casos médios , mas funções unidirecionais não existem. Isso implica que não podemos gerar instâncias rígidas do de com solução conhecida. NPNP

4- Minicrypt: Existem funções de mão única, mas os sistemas criptográficos de chave pública são impossíveis

5- Criptomania: Existem sistemas criptográficos de chave pública e a comunicação segura é possível.

Qual mundo é favorecido pelos recentes avanços na complexidade computacional? Qual é a melhor evidência para a escolha?

Russell Impagliazzo, uma visão pessoal da complexidade dos casos médios , 1995

Cinco mundos de Impagliazzo, O blog da complexidade computacional

cc.complexity-theory conditional-results average-case-complexity Mohammad Al-Turkistany
fonte
2
Não sou especialista o suficiente para responder, mas achei que você gostaria de saber que, no primeiro Workshop de Barreiras na Complexidade, Impagliazzo pediu um programa de pesquisa muito alinhado com a sua pergunta. Chame "oráculos semelhantes à Terra" oráculos nos quais os mesmos teoremas de complexidade se mantêm no mundo não relativizado "real" em que vivemos. Em seguida, estude as propriedades desses oráculos que são como a Terra real. Portanto, nessa estrutura, sua pergunta se torna: "O que um oráculo precisa satisfazer para se parecer com a Terra?"
Aaron Sterling

Respostas:

26

Há cerca de um ano, organizei um workshop sobre complexidade e criptografia: status dos mundos de Impagliazzo , e os slides e vídeos no site podem ser de interesse.

A resposta curta é que pouco mudou no sentido de que a maioria dos pesquisadores ainda acredita que vivemos na "criptomania" e ainda temos mais ou menos a mesma evidência para isso, e não há muito progresso em colapsar um dos mundos um para o outro.

Talvez a parte mais significativa das novas informações seja o algoritmo de Shor, que mostra que, pelo menos, se você substituir P ​​por BQP, os sistemas de criptografia de chave pública mais usados ​​são inseguros. Mas, devido aos sistemas de criptografia baseados em Lattice, a suposição padrão é que vivemos na criptomania mesmo nesse caso, embora talvez o consenso aqui seja um pouco mais fraco que o caso clássico. Mesmo no caso clássico, parece haver muito mais evidências da existência de funções unidirecionais ("Minicrypt") do que a existência de criptografia de chave pública ("Cryptomania"). Ainda assim, dado o esforço que as pessoas gastaram na tentativa de quebrar vários sistemas de criptografia de chave pública, há evidências significativas para esse último também.

Boaz Barak
fonte
Este link pode funcionar melhor: archive.dimacs.rutgers.edu/Workshops/Cryptography/program.html
Timothy Chow
18

Boa pergunta, mas o cientista não conseguiu nem separar a "Algoritmica" dos casos restantes, muito menos decidir o mundo exato em que vivemos.

Dito isto, existem vários trabalhos de pesquisa sobre o assunto. Veja, por exemplo: Sobre a possibilidade de basear a criptografia na suposição de que P! = NP por Goldreich e Goldwasser e suas referências.

Veja também Baseando funções unidirecionais na dureza NP por Adi Akavia et al.

Além disso, é sabido que a decodificação de alguns sistemas de criptografia é difícil para NP (consulte, por exemplo, o sistema de criptografia McEliece ou criptografia baseada em Lattice ). Não sei por que isso NÃO resolve o problema, pois não estou familiarizado com esses sistemas de criptografia. Veja os comentários de Peter Shor abaixo.

Eu também sugiro que você dê uma olhada rápida na discussão no Stackoverflow . Revisar a literatura que cita o trabalho de Impagliazzo também pode ser instrutivo.

EDIT: Os seguintes resultados podem ser interessantes:

Feigenbaum e Fortnow. Auto-redutibilidade aleatória de conjuntos completos. SIAM Journal on Computing, 22: 994–1005, 1993.

Bogdanov e Trevisan. Em reduções de pior caso a caso médio para problemas de PN. Em Anais do 44º Simpósio Anual da IEEE sobre Fundamentos da Ciência da Computação, páginas 308-317, 2003.

Akavia, Goldreich, Goldwasser e Moshkovitz. Baseando funções unidirecionais na dureza NP

Gutfreund e Ta-Shma. Novas conexões entre derandomização, complexidade de pior caso e complexidade de caso médio. Tech. Rep. TR06-108, Colóquio Eletrônico sobre Complexidade Computacional, 2006.

Bogdanov e Trevisan. Complexidade média de casos. Encontrado. Tendências Theor. Comput. Sci. 2, 1 (outubro de 2006), 1-106. DOI = http://dx.doi.org/10.1561/0400000004

MS Dousti
fonte
5
O sistema de criptografia McEliece não é um sistema de criptografia; é uma família inteira de sistemas de criptografia, dependendo da classe de códigos de correção de erros que você usa nele. Se você usar códigos arbitrários de correção de erros, será difícil quebrar o NP, mas também será difícil decodificar uma mensagem. Se você usar uma classe de códigos de correção de erros que possui um algoritmo de decodificação em tempo polinomial, é realmente hora de decodificar a mensagem, mas não temos mais uma prova de que a quebra do sistema de criptografia é NP difícil. A situação da criptografia baseada em treliça é melhor, mas ainda não é difícil de decifrar o NP.
Peter Shor
@ Peter: Muito obrigado! Você resolveu um quebra-cabeça que me intrigou por muito tempo!
MS Dousti
De fato, parece que, para algumas famílias de códigos de correção de erros, o sistema de criptografia McEliece foi quebrado, embora não para os códigos Goppa, que estavam na proposta original de McEliece.
Peter Shor