Se você executar uma função unidirecional com entrada diferente, ainda é uma função unidirecional?

7

Suponha que seja uma função unidirecional. E quanto a , onde e \ lvert x_1 \ rvert = \ lvert x_2 \ rvert ?f(x)h(x)=f(x1)f(x2)x=x1||x2|x1|=|x2|

  • é disjunção exclusiva (xor)
  • ||é concatenação
  • |u|é o comprimento de u
Kate Green
fonte
por que é uma pergunta se f(x1)f(x2) é unidirecional assumindo que f é unidirecional uma duplicata da pergunta se f(x)x é unidirecional quando f é unidirecional?
Sasho Nikolov 11/03/2013
@ShohoNikolov Concordo com você: as hipóteses são bem diferentes. Nesses casos, vote para reabrir.
Gilles 'SO- stop be evil'
Como você define h(x) quando |x|é estranho?
Gilles 'SO- stop be evil'
É um one-way permutação em ou é possível que o comprimento do e diferem? f(x){0,1}|x|f(x1)f(x2)
frafl
@rafrafl provavelmente não importa.
Ran G.

Respostas:

9

A função pode não ser mais unidirecional.h

Construímos um contra-exemplo - uma maneira específica cuja não é mais uma mão única - da seguinte maneira. Suponha que é uma função unidirecional que preserva o tamanho e define na entrada da seguinte maneira, (assumindo e .) É fácil ver que também é unidirecional - para invertê-lo, você precisa inverter na primeira metade ou inverter na segunda metade.fhgfw=bx1x2

f(bx1x2)={g(x1)x2b=0x1g(x2)b=1
b{0,1}|x1|=|x2|fgg

Agora vamos mostrar como inverter . Suponha que você receba , nós o escrevemos como com . Então uma possível pré-imagem de é hh(u,v)=Zh(u,v)=z1z2|z1|=|z2|=nZ

u=00ng(0n)z2
v=1g(0n)z10n

porque e portanto, seu XOR fornece exatamente conforme necessário.f(u)=g(0n)g(0n)z2f(v)=g(0n)z1g(0n)z1z2

Tocou.
fonte
Você poderia adicionar mais detalhes sobre a inversão de ? Dado algum , você concatena um ou aleatório e depois calcula e / ou . Mas o resultado pode produzir e . Você deve garantir que isso não aconteça em muitos casos. Dado que você precisa de dois exemplos positivos para construir um negativo, isso deve ser possível, mas não é tão óbvio (para mim) quanto você afirma. gxx1x2f1(xx2)f1(x1x)g1(x1)g1(x2)
frafl
@frafl você está perguntando por que é uma maneira? Suponha que você tenha que o inverte e use-o para inverter consultando em . fAg(x)Ag(x)g(x)
Ran G.
@RanG: Como é óbvio . Obrigado! f1(xx)
frafl