3PAA: A Private PUF Protocol for Anonymous Authentication

Anonymous authentication (AA) schemes are used by an application provider to grant services to its n users for pre-defined k times after they have authenticated themselves anonymously. These privacy-preserving cryptographic schemes are essentially based on the secret key that is embedded in a trusted platform module (TPM). In this work, we propose a private physically unclonable function (PUF) based scheme that overcomes the shortcomings of prior attempts to incorporate PUF for AA schemes. Traditional PUF based authentication protocols have their limitations as they only work based on challenge-response pairs (CRPs) exposed to the verifier, thus violating the principle of anonymity. Here, we ensure that even if the PUF instance is private to the user, it can be used for authentication to the application provider. Besides, no raw CRPs need to be stored in a secure database, thus making it more difficult for an adversary to launch model-building attacks on the deployed PUFs. We reduce the execution time from O(n) to O(1) and storage overhead from O(nk) to O(n) compared to state-of-the-art AA protocols and also dispense the necessity of maintaining a revocation list for the compromised keys. In addition, we provide security proofs of the protocol under Elliptic Curve Diffie-Hellman assumption and decisional uniqueness assumption of a PUF. A prototype of the protocol has been implemented on a Z-Turn board integrated with dual-core ARM CortexA9 processor and Artix-7 FPGA. The resource footprint and performance characterization results show that the proposed scheme is suitable for implementation on resource-constrained platforms.