Funções unidirecionais que preservam o comprimento

7

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?

com
fonte

Respostas:

7

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 .gf

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

g(x)=g(x)||10p(|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 .fg

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.ffz=f(y)x=x1||||xnm[n]g(x1||||xm)=zzg

Veja a prova original aqui .

Eu.
fonte
Por favor, esboce a prova aqui.
Raphael
2
ESTÁ BEM. O esboço está lá agora.
Me.
Essa prova parece um pouco confusa. O que é ? Introduz sem defini-lo. ff
DW