Anonymous Authentication and Key Agreement, Revisited

Yanqi Zhao; Xiangyu Liu; Min Xie; Xiaoyi Yang; Jianting Ning; Baodong Qin; Haibin Zhang; Yong Yu

Paper 2025/1986

Anonymous Authentication and Key Agreement, Revisited

Yanqi Zhao, Xi’an University of Posts and Telecommunications

Xiangyu Liu

, Helmholtz Center for Information Security

Min Xie, Harbin Institute of Technology, Shenzhen

Xiaoyi Yang, Xi’an University of Posts and Telecommunications

Jianting Ning, Wuhan University

Baodong Qin, Xi’an University of Posts and Telecommunications

Haibin Zhang, Yangtze Delta Region Institute of Tsinghua University

Yong Yu, Shaanxi Normal University

Abstract

In NDSS 2024, Yu~et al. proposed AAKA, an Anonymous Authentication and Key Agreement scheme designed to protect users' privacy from mobile tracking by Mobile Network Operators (MNOs). AAKA aims to provide both anti-tracking privacy and traceability (lawful de-anonymization), allowing subscribers to access the network via anonymous proofs while enabling a Law Enforcement Agency (LEA) to trace the real identity if misbehaviors are detected. However, we identify that the AAKA scheme in NDSS 2024 is insecure since the subscriber's identity is exposed within the protocol, thereby failing to achieve the claimed privacy and traceability. Building on the repair of AAKA, we propose AAKA+, Anonymous Authentication and Key Agreement with Verifier-Local Revocation, a new mobile authentication scheme, to ensure privacy against mobile tracking. In addition to the privacy and traceability introduced in NDSS 2024, AAKA+ additionally allows the MNO to immediately assert whether the associated subscriber has been traced and revoked upon receiving an anonymous proof. We formally define the syntax and the security model of AAKA+ and propose two concrete schemes, AAKA+BB and AAKA+PS, based on the Boneh-Boyen signature and the Pointcheval-Sanders signature schemes, respectively. Both AAKA+BB and AAKA+PS are pairing-free on the user equipment side and compatible with existing cellular infrastructure. Experimental results show that our schemes are practical, with anonymous proof generation taking approximately 18 milliseconds for a constrained device.

Note: fix some typos

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. ACSAC 2025
Keywords: Anonymous Credential Anti-Tracking Privacy Verifier-Local Revocation Authentication Protocols
Contact author(s): zhaoyanqi2019 @ 163 com
xiangyu1994liu @ gmail com
minxie @ stu hit edu cn
History: 2025-11-10: revised; 2025-10-23: received; See all versions
Short URL: https://ia.cr/2025/1986
License: CC0

BibTeX

@misc{cryptoeprint:2025/1986,
      author = {Yanqi Zhao and Xiangyu Liu and Min Xie and Xiaoyi Yang and Jianting Ning and Baodong Qin and Haibin Zhang and Yong Yu},
      title = {Anonymous Authentication and Key Agreement, Revisited},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1986},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1986}
}