Sobre a existência de geradores pseudorrandômicos

Sabe-se que geradores pseudorrandômicos existem, assumindo a existência de funções que não podem ser invertidas eficientemente nas distribuições induzidas pela aplicação da função iterativamente um número polinomial de vezes. Essa condição suficiente é também necessária, mas é difícil verificar se funções particulares, assumidas como unidirecionais, também são unidirecionais em suas iterações. Isso levanta a questão fundamental se a mera existência de funções unidirecionais é suficiente para a construção de geradores pseudorrandômicos. O progresso em direção à resolução dessa questão é apresentado. Funções regulares nas quais cada imagem de uma string de k bits tem o mesmo número de pré-imagens de comprimento k são consideradas. Mostra-se que, se uma função regular é unidirecional, então geradores pseudorrandômicos realmente existem. Em particular, assumindo a intransitabilidade da fatoração geral, pode-se provar que os geradores pseudorrandômicos existem. Outra aplicação é a construção de um gerador pseudorrandômico com base na intransitabilidade assumida de decodificação de códigos lineares aleatórios.