Methods and systems for verification of indicia that do not require key management systems, and in which revocation of key pairs is easily performed without adding costs to the verification process are provided. Indicia are generated and authenticated utilizing an identity-based encryption (IBE) scheme. A key generating authority generates a private key for a PSD, distributes the private key securely to the PSD, and provides public information for use by a verification service when verifying cryptographic digital signatures generated with the private key. The corresponding public key is a string consisting of PSD information that is provided as part of the indicium. The verification service can verify the signature of each indicium by obtaining the public key string from the indicium, and utilizing the key generating authority's public information.