El secreto perfecto requiere que ninguna información sobre el mensaje pueda ser obtenida en base al cyphertext, incluso con poder computacional infinito. Esto es innecesario en el mundo real, donde podemos considerar a un criptosistema seguro si se filtra un poco de información para atacantes con un limite computacional, por ejemplo usando 200 años de esfuerzo computacional en la supercomputadora más rápida. Pero limitando los escenarios y las garantías llegamos a un nuevo nivel de seguridad, donde garantizamos seguridad solo contra adversarios “limitados” (asumimos un limite en los recursos del atacante, especialmente en el tiempo) y aceptamos una pequeña probabilidad de éxito para el atacante, por lo que dejamos de lado la infalibilidad.
Asymptotic Approach
Hablamos de algoritmos eficientes cuando corre en tiempo polinómico. Es decir, un algoritmo corre en tiempo polinómico si existe un polinomio tal que, para todo , el calculo de termina en menos de pasos.
Una función negligible es una que es asintóticamente más chica que cualquier función polinómica inversa.