Abstract—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 Cortex-
A9 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.
We provide the code for the protocol.
The code can be found here.(Authentication Protocol Codes).