Função de mão única

Em Ciência da Computação, uma função de mão única ou função de sentido único é uma função que é fácil de calcular para qualquer entrada (qualquer valor do seu domínio), mas difícil de inverter dada a imagem de uma entrada aleatória. Aqui "fácil" e "difícil" são entendidos em termos da teoria da complexidade computacional, especificamente a teoria dos problemas de tempo polinomial. Não sendo um-para-um não é considerado suficiente para um função ser chamada de mão única.

A existência de funções de sentido único ainda é uma conjetura em aberto. Na realidade, a existência delas provaria que as classes de complexidade P e NP não seriam iguais, resolvendo assim o principal problema da teoria da Ciência da Computação [1]:ex. 2.2, page 70. A existência da prova que P não é igual a NP não implica, porém, na existência de funções de mão única.[2]

Em alguns contextos, os termos "fácil" e "difícil" são interpretados geralmente relativos a alguma entidade computacional específica; tipicamente "barato o bastante para usuários legítimos" e "muito caro para agentes maliciosos". Funções de mão única, nesse sentido, são ferramentas fundamentais para criptografia, identificação pessoal, autenticação e outras aplicações de segurança de dados. Enquanto a existência de tais funções ainda é uma conjetura em aberto, existem diversas funções candidatas que resistiram décadas de intensa investigação. Algumas dessas são essenciais para a maioria dos sistemas de telecomunicações, comércio eletrônico e internet banking, por todo o mundo.

Definição teórica

Uma função f: {0, 1}* → {0, 1}* é de mão única, se f pode ser computada por um algoritmo de tempo polinomial, mas para todo algoritmo A aleatório de tempo polinomial,

${\displaystyle Pr[f(A(f(x)))=f(x)]<{\frac {1}{p(n)}}}$

para todo p(n) positivo polinomial e n suficientemente grande, assumindo que x é escolhido de uma distribuição uniforme em {0, 1}^n e da aleatoriedade de A.

Note que, por esta definição a função deve ser "difícil de inverter" no caso médio (ao invés do pior caso); enquanto na maior parte da teoria da complexidade o termo "difícil" se refere ao pior caso.

Note também que apenas criar uma função que não seja um-para-um, não faz dela uma função de mão única. Nesse contexto, inverter uma função significa identificar algum elemento da pré-imagem de um valor dado, o qual não requer a existência de uma função inversa. Por exemplo, f(x) = x^2 não é invertível (exemplo: f(2) = f(-2) = 4), mas também não é de mão única, pois dado um valor, é possível computar um dos elementos da pré-imagem em tempo polinomial, tirando sua raiz quadrada.

Conceitos relacionados

Uma função arapuca de mão única ou permutação arapuca é um tipo especial de função de mão única. Esta função é difícil de inverter ao menos que uma informação secreta, chamada de arapuca, é conhecida.

Uma permutação de mão única é uma função de mão única que também é uma permutação - isso é, uma função de mão única que é injetora (injetiva) e sobrejetora (sobrejetiva). Permutações de mão única são primitivas importantes da criptografia, mas não se sabe se a existência de funções de mão única implicam na sua existência.

Uma função hash sem colisão f é uma função de mão única que também é resistente a colisão; isto é, nenhum algoritmo aleatório de tempo polinomial consegue achar uma colisão - valores x e y tal que f(x) = f(y) - com probabilidade não desprezível.[3]

Implicações teóricas de funções de mão única

Se f é uma função de mão única, então a inversão de f seria um problema cuja saída é difícil de computar (por definição), mas fácil de verificar (apenas computando f nela). Assim, a existência de uma função de mão única implicaria que P≠NP. Entretanto, não se sabe se P≠NP implica a existência de funções de mão única.

A existência de uma função de mão única implicaria a existência de muitos outros conceitos, incluindo:

• Geradores pseudoaleatórios
• Famílias de funções pseudoaleatórias
• Esquemas de comprometimento de bits
• Esquemas de encriptação de chave privada seguros contra ataques adaptativos de cifro-texto escolhido
• Códigos de autenticação de mensagens
• Esquemas de assinaturas digitais (seguro contra ataques adaptativos de mensagem escolhida)

Candidatos a função de mão única

Seguem diversos candidatos a função de mão única (de Abril de 2009). Claramente, não é conhecido se estas funções são verdadeiramente de mão única; mas até agora, diversas pesquisas falharam em produzir um algoritmo eficiente que inverta uma delas.

Multiplicação e fatorização

A função f pega como entrada dois números primos p e q em notação binária e retorna seu produto. Esta função pode ser computada em tempo O(n^2), onde n é o tamanho total (número de dígitos) das entradas. Inverter esta função requer achar os fatores de um dado inteiro N. Os melhores algoritmos de fatorização conhecidos para esse problema roda em tempo ${\displaystyle 2^{O({(\log N)^{1/3}(\log \log N})^{2/3})}}$, que é apenas pseudo-polinomial em ${\displaystyle \log N}$, o número de bits necessários para representar N.

Esta função pode ser generalizada deixando p e q flutuar sobre um conjunto apropriado de semiprimos. Note que f não é de mão única para um arbitrário p,q>1, pois o produto terá 2 como fator com probabilidade de 3/4.

Quadrado modular e raízes quadradas

A função f pega dois inteiros positivos x e N, onde N é o produto de dois primos p e q, que retorna como saída o resto de x^2 dividido por N. Inverter esta função requer computar raízes quadradas módulo N; que é: dado y e N, ache um x que x^2 mod N = y. Pode ser mostrado que solucionar esse problema é computacionalmente equivalente a fatorizar N (no sentido de redução de tempo polinomial). O cripto-sistema Rabin é baseado na hipótese de que a função Rabin é de mão única.

Exponencial discreta e logaritmo

A função f pega um número primo p e um inteiro x entre 0 e p-1, e retorna o resto de x^2 dividido por p. Esta função exponencial discreta pode ser facilmente computada em tempo O(n^3), onde n é o número de bits em p. Inverter essa função requer computar o logaritmo discreto módulo p. Dado um primo p e um inteiro y entre 0 e p-1, ache um x tal que 2^x = y. Não existe nenhum algoritmo publicado que resolve esse problema em tempo polinomial (Abril de 2009). O esquema de encriptação de ElGamal é baseado nessa função.

Funções hash criptograficamente seguras

Existem várias funções hash criptográficas que são rápidas de computar como o SHA 256. Algumas das versões mais simples sucumbiram a análises sofisticadas, mas as versões mais robustas continuam oferecendo soluções rápidas e práticas para computação de mão única. A maior parte do apoio teórico para essas funções são técnicas para impedir ataques que tiveram sucesso previamente.

Outros candidatos

Outros candidatos para função de mão única têm sido baseados na dificuldade de decodificar códigos lineares aleatórios, o problema da soma de subconjuntos (criptossistema da mochila de Naccache-Stern), dentre outros.

Função de mão única universal

Existe uma determinada função que foi demonstrada que é de mão única se e somente se funções de mão única existirem.[4] Como esta função foi a primeira função de mão única combinatorial completa a ser demonstrada, ela é conhecida como a "função de mão única universal". O problema de determinar a existência de funções de mão única é assim reduzido ao problema de provar que esta função específica é de mão única.

Referências

1. Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools, (draft available from author's site). Cambridge University Press. ISBN 0-521-79172-3.
2. Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography". Summer course on cryptography, MIT, 1996–2001
3. Russell, A. Necessary and Sufficient Conditions for Collision-Free Hashing. Journal of Cryptology vol. 8, no. 2., pp. 87–99. 1992.
4. Leonid Levin (2003). «The Tale of One-Way Functions». ACM. arXiv:cs.CR/0012023 

Leitura adicional

• Jonathan Katz and Yehuda Lindell (2007). Introduction to Modern Cryptography. CRC Press. ISBN 1-584-88551-3.
• Michael Sipser (1997). Introduction to the Theory of Computation. [S.l.]: PWS Publishing. ISBN 0-534-94728-X  Section 10.6.3: One-way functions, pp. 374–376.
• Christos Papadimitriou (1993). Computational Complexity 1st ed. [S.l.]: Addison Wesley. ISBN 0-201-53082-1  Section 12.1: One-way functions, pp. 279–298.