A device and a network can authenticate using a subscription concealed identifier (SUCI). The device can store (i) a plaintext subscription permanent identifier (SUPI) for the device, (ii) a network static public key, and (iii) a key encapsulation mechanism (KEM) for encryption using the network static public key. The network can store (i) a device database with the SUPI, (ii) a network static private key, and (iii) the KEM for decryption using the network static private key. The device can (i) combine a random number with the SUPI as input into the KEM to generate a ciphertext as the SUCI, and (ii) transmit the ciphertext/SUCI to the network. The network can (i) decrypt the ciphertext using the KEM to read the SUPI, (iii) select a key K from the device database using the SUPI, and (iv) conduct an Authentication and Key Agreement (AKA) with the selected key K.