Funções unidirecionais que preservam o comprimento

Infelizmente, minha formação em complexidade computacional ainda é fraca, mas estou trabalhando nisso.

Pelo que entendi, a questão da existência de funções de mão única é muito importante no campo.

Suponha que existam funções unidirecionais, como pode ser demonstrado que existem funções unidirecionais que preservam o comprimento?

Se o wlog permitir que seja uma função forte de mão única, agora construiremos um comprimento preservando a função de mão única .$g$$f$

Como é PPT computável por suposição, existe um polinômio st para todos Definir$g$$p$$|f(x)| \le p(|x|)$$x$

$$g'(x) = g(x)||10^{p(|x|) - |g(x)|}$$ essa função sempre tem . e é trivialmente fortemente uma maneira.$|g'(x)| = p(|x|)$

Agora temos que forçar.$|x| = |f(x)|$

Isso podemos fazer pegando bits como entrada e pegando apenasem conta, ou seja,$p(|x|)$$|x|$

$f(x||y) = g'(x)$ para .$|y| = p(|x|) - |x| + 1$

O sentido único forte de segue o sentido único forte de .$f$$g'$

Se não tivesse sido uma maneira forte, poderíamos consultar um adversário PPT de para obter volte e tente para cada se e, eventualmente, encontre uma pré-imagem de sob em tempo polinomial com probabilidade não desprezível. Conradição.$f$$f$$z = f(y)$$x = x_1 || \ldots || x_n$$m \in [n]$$g'(x_1||\ldots||x_m) = z$$z$$g'$

Veja a prova original aqui .