Paper 2022/1280

Group Time-based One-time Passwords and its Application to Efficient Privacy-Preserving Proof of Location

Abstract

Time-based One-Time Password (TOTP) provides a strong second factor for user authentication. In TOTP, a prover authenticates to a verifier by using the current time and a secret key to generate an authentication token (or password) which is valid for a short time period. Our goal is to extend TOTP to the group setting, and to provide both authentication and privacy. To this end, we introduce a new authentication scheme, called Group TOTP (GTOTP), that allows the prover to prove that it is a member of an authenticated group without revealing its identity. We propose a novel construction that transforms any asymmetric TOTP scheme into a GTOTP scheme. Our approach combines Merkle tree and Bloom filter to reduce the verifier's states to constant sizes. As a promising application of GTOTP, we show that GTOTP can be used to construct an efficient privacy-preserving Proof of Location (PoL) scheme. We utilize a commitment protocol, a privacy-preserving location proximity scheme, and our GTOTP scheme to build the PoL scheme, in which GTOTP is used not only for user authentication but also as a tool to glue up other building blocks. In the PoL scheme, with the help of some witnesses, a user can prove its location to a verifier, while ensuring the identity and location privacy of both the prover and witnesses. Our PoL scheme outperforms the alternatives based on group digital signatures. We evaluate our schemes on Raspberry Pi hardware, and demonstrate that they achieve practical performance. In particular, the password generation and verification time are in the order of microseconds and milliseconds, respectively, while the computation time of proof generation is less than $1$ second.