The Need for Being Explicit: Failed Attempts to Construct Implicit Certificates from Lattices

Global efforts such as the National Institute of Standards and Technology (NIST)’s post-quantum standardization center on cryptographic primitives like public-key encryption and signature schemes that are secure even in the presence of quantum adversaries. In addition, one must also consider efficient certificate management as new technologies like the Internet of Things and 5G wireless networks rely on them. For example, the IEEE Standard for vehicle-to-vehicle communication depends on implicit certificates. However, the only efficient construction available is over elliptic curves, and hence not quantum-secure.

This paper investigates approaches to construct implicit certificate schemes from lattices, employing the NIST Round 3 signature schemes Dilithium and Falcon. We consider emulation of the existing implicit certificate scheme and proceed to more innovative techniques like combining the two schemes or pairing them with encryption. Unfortunately, we encounter problems with each design, due to recurring causes like conflicting secret key and signature sizes, unique sampler requirements and the rigidity of the parameter sets. By explaining each of these issues, this paper will hopefully spark ideas for more successful constructions.