As “Funções unidirecionais” têm aplicativos fora da criptografia?

Uma função $f \colon \{0, 1\}^* \to \{0, 1\}^*$ é unidirecional se $f$ puder ser calculada por um algoritmo de tempo polinomial, mas para cada algoritmo de tempo polinomial aleatório $A$ ,

$\Pr[f(A(f(x))) = f(x)] < 1/p(n)$

para cada polinio e suficientemente grande , assumindo que x é escolhido de forma uniforme a partir de \ {0, 1 \} ^ n . A probabilidade é tomado sobre a escolha de x e a aleatoriedade da A .$p(n)$$n$$x$$\{ 0, 1 \}^n$$x$$A$

Então ... as "Funções unidirecionais" têm aplicativos fora da criptografia? Se sim, o que são?

As funções de mão única aparecem crucialmente no resultado das provas naturais de Razborov-Rudich. Eu não consideraria os limites inferiores do circuito como parte da "criptografia", então talvez isso se encaixe nos seus critérios.

Funções unidirecionais também apareceram em algumas discussões em torno da conjectura de isomorfismo de Berman-Hartman . Joseph e Young conjeturaram que, se existissem funções unidirecionais, a conjectura do isomorfismo falha (unidirecional contra adversários determinísticos, não probabilísticos, mas espero que seja próximo o suficiente para os propósitos desta pergunta). John Rogers deu um mundo relativizado em que a conjectura de Joseph-Young falhou (ou seja, onde existem funções de mão única, mas a conjectura de isomorfismo se mantém). Mas, tanto quanto eu sei, a conjectura de JY ainda é uma das principais evidências técnicas que levam as pessoas a pensar que a conjectura de isomorfismo é falsa (se é que pensam isso).

A essência da idéia de Joseph e Young é que, se é uma função unidirecional, então é completo, mas "não" deve ser isomórfico para SAT.$f$$f(SAT)$$NP$

Sim, uma tabela de hash ou um mapa de hash requer uma função unidirecional. Também a detecção duplicada (veja isto e isto ) pode ser feita com muita eficiência usando funções unidirecionais. Ambos os casos exigem funções "boas" (com poucas chances de colisão) de mão única, enquanto a força criptográfica geralmente não é necessária .

Existem muitos resultados de "dureza criptográfica" (apenas Google esta frase) para problemas de aprendizado. Estes são resultados de dureza assumindo que existem funções de sentido único.

Funções unidirecionais têm uma aplicação na Complexidade Kolmogorov:

$x$$y$

$K^q(x, y) = K^q(x) + K^q(y|x) + O(\log n)$$q$

Se existirem funções unidirecionais, a simetria limitada por tempo polinomial da conjectura da informação é falsa.

L. Longpre e S. Mocas. Simetria de informações e funções de mão única. Information processing Letters, 46 (2): 95 {100, 1993

L. Longpre e O. Watanabe. Sobre simetria da informação e invertibilidade do tempo polinomial. Informação e computação, 121 (1): 14 {22, 1995