La criptografía sin certificado es una variante de la criptografía basada en identificación destinada a evitar el problema del depósito de claves . Normalmente, las claves las genera una autoridad de certificación o un centro de generación de claves (KGC), al que se le otorga pleno poder y en el que se confía implícitamente. Para evitar un colapso total del sistema en el caso de que un KGC se vea comprometido, el proceso de generación de claves se divide entre el KGC y el usuario. El KGC genera primero un par de claves, donde la clave privada es ahora la clave privada parcial del sistema. El resto de la clave es un valor aleatorio generado por el usuario y nunca se revela a nadie, ni siquiera al KGC. Todas las operaciones criptográficas del usuario se realizan utilizando una clave privada completa que incluye tanto la clave parcial del KGC como el valor secreto aleatorio del usuario.
Una desventaja de esto es que la información de identidad ya no forma la clave pública completa. Es decir, la clave pública del usuario no se puede descubrir únicamente a partir de la cadena de identidad del usuario y la clave pública del KGC. Por lo tanto, la clave pública del usuario debe ser publicada u obtenida de otro modo por otros usuarios. Una ventaja del sistema es que es posible verificar que cualquier clave pública obtenida pertenece a la cadena de identidad indicada. (En otras palabras, el método de distribución de la clave pública del usuario no tiene que ser seguro). La cadena de identidad y la clave pública del KGC se pueden utilizar para verificar que la clave pública obtenida pertenece a la cadena de identidad. (Se puede verificar que la clave pública obtenida se generó a partir de la cadena de identidad, la clave privada del KGC y algún valor desconocido). Tenga en cuenta que se pueden generar múltiples pares de claves pública/privada para cualquier cadena de identidad, pero los atacantes no tendrían acceso a la clave privada del KGC en el proceso de creación.
Para cifrar un mensaje enviado a otro usuario, se necesitan tres datos: 1) la clave pública del destinatario y 2) la cadena de identidad, y también 3) la información pública del KGC (clave pública). La cadena de identidad y la clave pública del KGC se utilizan para verificar que la clave pública del destinatario pertenece al destinatario (se generó a partir de la cadena de identidad y la clave pública del KGC). Para descifrar, un usuario solo necesita usar su clave privada.
Para garantizar una seguridad estricta, un sistema sin certificados debe demostrar su seguridad frente a dos tipos de adversarios. Adversario de tipo 1: se refiere a cualquier tercero que pueda falsificar las claves públicas del usuario, lo que corresponde a la obtención del valor secreto aleatorio del usuario. Adversario de tipo 2: se refiere a un KGC comprometido o malicioso, que tiene acceso a las claves públicas y privadas parciales de todos los usuarios.