Argumentos para a existência de funções unidirecionais

Li em vários artigos que se acredita amplamente na existência de funções de mão única . Alguém pode esclarecer por que esse é o caso? Que argumentos temos para apoiar a existência de funções unidirecionais?

Aqui está um argumento de que funções unidirecionais devem ser difíceis de inverter. Suponha que exista uma classe de problemas 3-SAT com soluções plantadas difíceis de resolver. Considere o seguinte mapa:

onde $x$ é qualquer cadeia de bits, $r$ é uma cadeia de bits (você pode usá-los para propagar um gerador de números aleatórios ou pode pedir quantos bits aleatórios precisar) $s$ é um problema $k$ -SAT com $x$ como uma solução plantada, em que o gerador de números aleatórios determina exatamente qual problema $k$ -SAT você escolhe. Para inverter esta função unidirecional, é necessário resolver um problema $k$ -SAT com uma solução plantada.

Este argumento mostra que a inversão de uma função unidirecional é tão difícil quanto resolver problemas de SAT com soluções plantadas. E como o k -SAT é um problema completo do NP, se você puder descobrir como construir instâncias rígidas com soluções plantadas para qualquer problema do NP, poderá plantar soluções nas fórmulas do k -SAT.$k$$k$$k$

Não foi provado que seja possível encontrar uma classe de problemas completos de NP com soluções plantadas que são tão difíceis quanto problemas arbitrários de NP completos (e mesmo que isso seja verdade, será incrivelmente difícil de provar) , mas as pessoas definitivamente sabem como plantar soluções nos problemas -SAT de maneiras que ninguém sabe como resolver no momento.$k$

ADICIONADO: Agora percebo que essa conexão já foi dada (em mais detalhes) em Abadi, Allender, Broder, Feigenbaum e Hemachandra ; eles apontam que funções unidirecionais podem fornecer instâncias rígidas resolvidas do SAT e vice-versa.

Colocando-o em uma linguagem mais informal, a inexistência de funções de mão única mostra que quebra-cabeças realmente difíceis não podem existir. Se existe um tipo de quebra-cabeça em que alguém pode criar um quebra-cabeça e sua solução algoritmicamente, também existe um algoritmo de tempo polinomial para encontrar uma solução para o quebra-cabeça. Isso parece muito contra-intuitivo para mim. Obviamente, uma lacuna polinomial poderia existir; pode ser que, se criar o quebra-cabeça tenha etapas, resolvê-lo possa levar O ( n 3 ) etapas. No entanto, minha intuição diz que deve haver uma lacuna superpolinomial. $n$$O(n^3)$

Darei uma resposta curta: a existência de problemas aparentemente difíceis, como FACTORING ou DISCRETE LOG, fez os teóricos acreditarem que a OWF existe. Em particular, eles tentaram por décadas (desde a década de 1970) encontrar algoritmos eficientes (tempo polinomial probabilístico) para esses problemas, mas nenhuma tentativa foi bem-sucedida. Esse raciocínio é muito semelhante ao motivo pelo qual a maioria dos pesquisadores acredita que P ≠ NP.

O argumento de Sasho se apóia no eterno problema de P = NP, para o qual atualmente não existe consenso.

No entanto, se seguirmos a análise de criptografia de C. Shannon do bloco único, desclassificada em 1947, ou seja: não há outro algoritmo de criptografia matematicamente seguro além do bloco único. Seu argumento é baseado na ideia de que, se tivermos uma sequência verdadeiramente aleatória dos números e para alguma sequência criptografar, s 1 , s 2 , s 3 , … , s n , criptografamos da seguinte forma:$r_1,r_2,r_3,\ldots,r_n$$s_1,s_2,s_3,\ldots,s_n$

$f(r_i,s_i) = r_i \oplus s_i = c_i$

Se a sequência for verdadeiramente aleatória, tentaremos calcular e o resultado seria, então, que todas as sequências são equiprováveis.$f^{-1}(r_i,s_i)$

Poderíamos imitar o resultado de Shannon para funções de mão única.

A função é o mapa e a função inversa é o mapa f : Z / N Z → Z / N Z × Z / N Z .$f:\mathbb{Z}/n\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}\rightarrow\mathbb{Z}/n\mathbb{Z}$$f:\mathbb{Z}/n\mathbb{Z}\rightarrow\mathbb{Z}/n\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}$

O problema é que não sabemos se existem números verdadeiramente aleatórios, pois a pergunta é equivalente ao comentário de Einstein sobre "Deus não joga dados".

No entanto, para todos os fins, um gerador de números aleatórios baseado em um processo físico é considerado aleatório o suficiente pelos especialistas.

Dito isto, no momento em que estamos tentando reverter $(c_i,r_i)$ , ou seja, os números aleatórios não são mais segredo, a reversão é trivial.

Além disso, essa função unidirecional não possui as boas propriedades da maioria das funções de hash criptograficamente seguras, como resistência à colisão. Além disso, temos a situação que . Isso significa que um mesmo valor s k é dividido em hash para dois valores diferentes. E f ( r i , s i ) = f ( r j , s j ) é comum.$f(r_i,s_k)\neq f(r_j,s_k)$$s_k$$f(r_i,s_i) = f(r_j,s_j)$

Seria tão fácil quanto sugerir, por exemplo, a função Seno?

Como para uma determinada entrada e saída, a entrada pode ser aumentada ou diminuída em 360 graus (ou 2 pi, se você estiver em radianos), é muitos para um, para que você nunca possa ter certeza de qual entrada teve?

Diga-me se eu entendi mal a pergunta.