International Association
for Cryptologic Research

Credentials are used to verify a user’s identity and attributes and form the basis of securing user access to the system resources. Users obtain credentials and store them on their (mobile) devices, and present them when needed. Anonymous credentials protect the user’s identity, and ensure unlinkability of multiple showing of the credential. In this paper, we consider a setting where a user is issued multiple credentials in sequence (e.g., for completing courses), and credential subsequences must be presented in order of issuance. We focus on the anonymous credential system where information such as the time of issuing is hidden for anonymity, or settings where there is no global clock and issuing time information is not recorded. We propose a novel order-preserving Proof-of-Credential-Subsequence (PoCS) system called KROM that allows a user that is potentially untrusted, to present a subsequence of their locally stored credentials to a verifier, while the relative chronological order of issuance is preserved. We formalize the security and privacy of KROM and present two constructions: a basic one that is based on Merkle trees and one with batched verification that significantly improves the efficiency of the system. We use KROM to construct an anonymous order-preserving proof-of-location-subsequence system and prove its security. The system enables users to selectively present a subsequence of their visited locations to a verifier or an auditor. The main challenge that is addressed is to ensure that the location information that must be in plaintext, does not breach privacy when used in sequence.