La difficulté calculatoire supposée de ce problème implique la sécurité sémantique du chiffrement RSA avec un remplissage adéquat (comme OAEP par exemple), puisque le chiffrement RSA tel qu`il est usuellement décrit est déterministe et ne peut donc pas être sémantiquement sûr.