Função arapuca, eventualmente conhecida também como função armadilha ou função alçapão, são designações possíveis na língua portuguesa para uma função que é fácil de computar em uma direção, mas difícil de computar na direção oposta (achar a inversa) sem uma informação especial, chamada de "arapuca". Funções arapuca são amplamente usadas em criptografia.
Em termos matemático, se f é uma função arapuca, então existe uma informação secreta y, tal que, dado f(x) e y, é fácil computar x. Considere um cadeado e sua chave. É trivial mudar o cadeado de aberto para fechado sem usar a chave, apenas empurrando a trava. Abrir o cadeado de maneira fácil, no entanto, requer o uso da chave. Aqui a chave é a arapuca.
Funções arapuca começaram a ser bastante usadas na criptografia na metade dos anos 70, com a publicação de técnicas de encriptação assimétrica (chave pública) por Diffie, Hellman e Merkle. Na realidade, Diffie e Hellman cunharam o termo (Diffie e Hellman, 1976). Diversas classes de funções foram propostas, e rapidamente percebeu-se que funções arapuca são mais difíceis de se encontrar do que era imaginado. Por exemplo, uma sugestão foi usar esquemas baseados no problema da soma de subconjuntos. Isso mostrou-se, porém, inapropriado.
Em 2004, as melhores candidatas a funções arapuca eram as das famílias de funções do RSA e de Rabin. Ambas são escritas como exponenciações módulo um número composto, e são relacionadas ao problema da fatoração em primos.
Funções relacionadas à dificuldade do problema do logaritmo discreto (tanto módulo um primo como num grupo definido sobre uma curva elíptica) não são conhecidas como funções arapuca, porque não existe uma informação "arapuca" conhecida sobre o grupo que torne eficiente a computação sobre logaritmos discretos. Entretanto, o problema do logaritmo discreto pode ser usado como base para uma arapuca quando os problemas relacionados chamados de problemas computacionais Diffie-Hellman ou variantes decisionais são usados. A versão semanticamente segura do cripto-sistema ElGamal se apóia no problema decisional de Diffie-Hellman. O algoritmo de assinatura digital é baseado no problema computacional de Diffie-Hellman num subgrupo de ordem prima.
Uma arapuca, em criptografia, tem o significado bastante específico citado anteriormente, e não deve ser confundida com porta dos fundos (erro muito frequente). Uma porta dos fundos é um mecanismo deliberadamente embutido num algoritmo criptográfico ou sistema operacional, que permite por exemplo que um ou mais usuários não autorizados passe por cima da segurança do sistema, de alguma maneira.
Ver também
Referencias
- W. Diffie and M. Hellman. New Directions in Cryptography. IEEE Trans. Info. Theory 22(6), pp. 644–654 (1976). PDF version of the paper
