As “Funções unidirecionais” têm aplicativos fora da criptografia?

16

Uma função f:{0 0,1 1}{0 0,1 1} é unidirecional se f puder ser calculada por um algoritmo de tempo polinomial, mas para cada algoritmo de tempo polinomial aleatório UMA ,

Pr[f(UMA(f(x)))=f(x)]<1 1/p(n)

para cada polinio e suficientemente grande , assumindo que x é escolhido de forma uniforme a partir de \ {0, 1 \} ^ n . A probabilidade é tomado sobre a escolha de x e a aleatoriedade da A .p(n)nx{0 0,1 1}nxUMA

Então ... as "Funções unidirecionais" têm aplicativos fora da criptografia? Se sim, o que são?

Tarek Radwan
fonte
11
Corrigi as fórmulas para o formato LaTeX, mas parece haver uma falha no MathJax, pois ele visualiza as equações corretamente, mas mostra o erro `Misplaced \`. Eu acho que vai ser corrigido em breve ...
MS Dousti
11
Para mim, isso parece mais um bug no SE. Por alguma razão, parece não reconhecer um duplo \ como uma sequência de escape que deve gerar um único \, que seria processado pelo MathJax.
Jukka Suomela
2
No post, é Pr[f(UMA(f(x),1 1n)=x]<1 1/p(n) , mas precisa de um colchete de fechamento adicional ")".
precisa
2
@Sadeq e Jukka: Isso pode estar relacionado a um bug corrigido recentemente no SE: meta.math.stackexchange.com/questions/1115/…
Tsuyoshi Ito
@Tsuyoshi: Obrigado pelo comentário informativo!
MS Dousti 13/11/2010

Respostas:

23

As funções de mão única aparecem crucialmente no resultado das provas naturais de Razborov-Rudich. Eu não consideraria os limites inferiores do circuito como parte da "criptografia", então talvez isso se encaixe nos seus critérios.

mikero
fonte
11

Funções unidirecionais também apareceram em algumas discussões em torno da conjectura de isomorfismo de Berman-Hartman . Joseph e Young conjeturaram que, se existissem funções unidirecionais, a conjectura do isomorfismo falha (unidirecional contra adversários determinísticos, não probabilísticos, mas espero que seja próximo o suficiente para os propósitos desta pergunta). John Rogers deu um mundo relativizado em que a conjectura de Joseph-Young falhou (ou seja, onde existem funções de mão única, mas a conjectura de isomorfismo se mantém). Mas, tanto quanto eu sei, a conjectura de JY ainda é uma das principais evidências técnicas que levam as pessoas a pensar que a conjectura de isomorfismo é falsa (se é que pensam isso).

A essência da idéia de Joseph e Young é que, se é uma função unidirecional, então é completo, mas "não" deve ser isomórfico para SAT.ff(SUMAT)NP

Joshua Grochow
fonte
8

Sim, uma tabela de hash ou um mapa de hash requer uma função unidirecional. Também a detecção duplicada (veja isto e isto ) pode ser feita com muita eficiência usando funções unidirecionais. Ambos os casos exigem funções "boas" (com poucas chances de colisão) de mão única, enquanto a força criptográfica geralmente não é necessária .

dente afiado
fonte
Sim, funções hash são amplamente usadas para tabelas hash.
Gamlor
2
sua resposta não está correta. O que é necessário para a detecção duplicada é a resistência à colisão, que não é o mesmo que ser unidirecional. Veja a definição na pergunta original para uma definição cuidadosa de mão única. Às vezes, as pessoas usam livremente a frase "hash unidirecional" como sinônimo de função de hash criptográfica, mas isso é altamente enganador, pois em muitos aplicativos não é a propriedade "unidirecional" que é importante, mas sim a resistência à colisão ( como na detecção duplicada) ou comportamento como um oráculo aleatório (como no hash).
DW
6

Existem muitos resultados de "dureza criptográfica" (apenas Google esta frase) para problemas de aprendizado. Estes são resultados de dureza assumindo que existem funções de sentido único.

Dana Moshkovitz
fonte
4
Você pode me dar uma definição precisa de "dureza criptográfica"?
Tarek Radwan
11
Os resultados da dureza padrão assumem que P não é igual a NP; se for esse o caso, o problema leva um tempo super-polinomial. Os resultados da "dureza criptográfica" assumem algo mais forte: que existem funções de sentido único. Essa suposição implica (e é mais forte que) a dureza média de alguns problemas.
Dana Moshkovitz
5

Funções unidirecionais têm uma aplicação na Complexidade Kolmogorov:

xy

Kq(x,y)=Kq(x)+Kq(y|x)+O(registron)q

Se existirem funções unidirecionais, a simetria limitada por tempo polinomial da conjectura da informação é falsa.

L. Longpre e S. Mocas. Simetria de informações e funções de mão única. Information processing Letters, 46 (2): 95 {100, 1993

L. Longpre e O. Watanabe. Sobre simetria da informação e invertibilidade do tempo polinomial. Informação e computação, 121 (1): 14 {22, 1995

Mohammad Al-Turkistany
fonte