Ein Kryptosystem ist beweisbar sicher, wenn beim Design ein schwieriges Problem im Sinne der Komplexitätstheorie zugrunde gelegt wurde und ein Sicherheitsbeweis vorliegt, der besagt, dass ein Erfolg eines Angreifers gleichwertig ist mit der Lösung des schwierigen Problems – das ist jedoch ein Widerspruch.
Beispiele für nicht-effizient berechenbare Probleme mit Relevanz für die Kryptologie:

• Faktorisierung ganzer Zahlen (integer factorization problem)
• RSA Problem (RSA problem)
• Quadratische Reste-Problem (quadratic residuosity problem)
• Quadratwurzeln modulo n Problem (square root modulo n problem)
• Diskreter Logarithmus Problem (discrete logarithm problem)
• Diffie-Hellman-Problem (Diffie-Hellman problem)
• Teilmengen-Summen-Problem (subset sum problem)