É sabido que a existência de funções unidirecionais é necessária e suficiente para grande parte da criptografia (assinaturas digitais, geradores pseudo-aleatórios, criptografia de chave privada, etc.). Minha pergunta é: Quais são as consequências teóricas da complexidade da existência de funções unidirecionais? Por exemplo, os OWFs sugerem que , e . Existem outras consequências conhecidas? Em particular, os OWFs implicam que a hierarquia polinomial é infinita?
Espero entender melhor a relação entre o pior caso e a dureza do caso médio. Também estou interessado em resultados que vão para o outro lado (ou seja, resultados teóricos da complexidade que implicariam OWFs).
cc.complexity-theory
reference-request
complexity-classes
cr.crypto-security
one-way-function
Thomas
fonte
fonte
Respostas:
Esta é uma resposta tardia.
Primeiro, para corrigir o que você escreveu: A pseudo-aleatoriedade criptográfica (a obtida de OWFs) não tem extensão suficiente para derandomizar aleatoriamente as classes de complexidade computacional "naturalmente definidas". Em um artigo antigo (início dos anos 80), Andrew Yao mostra uma derandomização subexponencial no tempo para RP etc. usando esses objetos (btw, isso é imediato), mas nenhuma derandomização mais forte é conhecida. Observe que, em termos de poder de enganação, os PRGs criptográficos são mais fortes do que o necessário para deserandomização, mas, ao mesmo tempo, em termos de extensão, são mais fracos que seus análogos teóricos da complexidade típicos (isso segue a ordem da quantificação na definição do PRGs).
Como Sasho Nikolov mencionou, há muitos exemplos no aprendizado do PAC. Dê uma olhada em um artigo muito antigo de Kearns e Valiant sobre a impossibilidade de aprender fórmulas e autômatos (siga no google scholar as referências de lá). Além disso, há consequências na complexidade da prova através da interpolação - veja também os primeiros trabalhos de Jan Krajicek e Pavel Pudlak. No entanto, não tenho certeza se você considera essas implicações teóricas da complexidade (mas eu considero).
- Periklis
fonte
A fatoração de número inteiro é amplamente considerada o melhor candidato para funções de sentido único e está no TFNP. A partir do resumo deste artigo, a hierarquia polinomial entra em colapso se as funções Onto são invertíveis? , fornece um resultado negativo relativizado construindo um oráculo sob o qual as funções TFNP são eficientemente computáveis, mas a hierarquia de tempo polinomial é infinita. No entanto, o resultado não é exatamente o que você está procurando.
fonte