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

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

$\oplus$ é disjunção exclusiva (xor)
$||$ é concatenação
$|u|$ é o comprimento de $u$

cryptography one-way-functions Kate Green
fonte

por que é uma pergunta se

f (x_{1}) \oplus f (x_{2})

$f(x_1) \oplus f(x_2)$ é unidirecional assumindo que

f

$f$ é unidirecional uma duplicata da pergunta se

f (x) \oplus x

$f(x) \oplus x$ é unidirecional quando

f

$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)

$h(x)$ quando

| x |

$|x|$ é estranho?

Gilles 'SO- stop be evil'

É um one-way permutação em ou é possível que o comprimento do e diferem?

f (x)

$f(x)$

{0, 1}^{| x |}

$\{0,1\}^{|x|}$

f (x_{1})

$f(x_1)$

f (x_{2})

$f(x_2)$

frafl

@rafrafl provavelmente não importa.

Ran G.

Respostas:

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. $f$ $h$ $g$ $f$ $w=bx_1x_2$

f (b x_{1} x_{2}) = {\begin{cases} g (x_{1}) x_{2} & b = 0 \\ x_{1} g (x_{2}) & b = 1 \end{cases}

$f(bx_1x_2) = \begin{cases} g(x_1)\,x_2 & b=0 \\ x_1\, g(x_2) & b=1 \end{cases}$

b \in {0, 1}

$b\in\{0,1\}$

| x_{1} | = | x_{2} |

$|x_1|=|x_2|$

f

$f$

g

$g$

g

$g$

Agora vamos mostrar como inverter . Suponha que você receba , nós o escrevemos como com . Então uma possível pré-imagem de é $h$ $h(u,v)=Z$ $h(u,v)= z_1z_2$ $|z_1|=|z_2|=n$ $Z$

u = 0 0^{n} ⟨ g (0^{n}) \oplus z_{2} ⟩

$u=0 \,0^n \,\langle g(0^n)\oplus z_2\rangle$

v = 1 ⟨ g (0^{n}) \oplus z_{1} ⟩ 0^{n}

$v=1 \, \langle g(0^n)\oplus z_1\rangle \, 0^n$

porque e portanto, seu XOR fornece exatamente conforme necessário. $f(u) = g(0^n)\, \langle g(0^n)\oplus z_2\rangle$ $f(v) = \langle g(0^n)\oplus z_1\rangle \, g(0^n)$ $z_1\,z_2$

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.

g

$g$

x

$x$

x_{1}

$x_1$

x_{2}

$x_2$

f^{- 1} (x x_{2})

$f^{-1}(xx_2)$

f^{- 1} (x_{1} x)

$f^{-1}(x_1x)$

g^{- 1} (x_{1})

$g^{-1}(x_1)$

g^{- 1} (x_{2})

$g^{-1}(x_2)$

frafl

@frafl você está perguntando por que é uma maneira? Suponha que você tenha que o inverte e use-o para inverter consultando em .

f

$f$

A

$A$

g (x)

$g(x)$

A

$A$

g (x) g (x)

$g(x)g(x)$

Ran G.

@RanG: Como é óbvio . Obrigado!

f^{- 1} (x x)

$f^{-1}(xx)$

frafl