Il paradosso del sistema PKI: se vuoi che gli altri sappiano chi c'è dietro la chiave pubblica, devi pubblicare un numero sufficiente di informazioni identificative, come nome verificato, email, numero di telefono... Tuttavia, la pubblicazione di queste informazioni può seriamente compromettere la privacy personale, portare a spam, truffe telefoniche e persino generare problemi di sicurezza. Pertanto, la pubblicazione delle informazioni identificative nel PKI deve seguire il principio di crittografia prima e decrittografia flessibile dopo. Un sistema di ri-criptazione proxy ben progettato può risolvere bene questo problema.