PAKA: Pseudonymous Authenticated Key Agreement without bilinear cryptography

Anonymity and pseudonymity are important concepts in the domain of the Internet of Things. The existing privacy-preserving key agreement schemes are only concerned with maintaining the privacy of the communicated data that appears on the channel established between two honest entities. However, privacy should also include anonymity or pseudonymity of the device identity. This means there should not exist any correlation handle to associate different communications done by the device. This paper proposes a privacy-preserving key agreement method called the Pseudoonymous Authenticated Key Agreement Protocol (PAKA), which also provides device unlinkability across different domains. This protocol is based on an Elliptic-Curve Diffie-Hellman using standard cryptographic primitives and curves, i.e., no pairing-based cryptography or other computationally intensive cryptography is necessary. For the security analysis, we provide a mathematical proof and an automatic cryptographic protocol verification utilizing Proverif. Last, we show the integration with the Trusted Platform Module and a Proof-of-Concept implementation.