I'm educating myself about cryptography. I know this is a long one, but please, bear with me. :) Now I have a scenario in my mind and I'd like to ask if what I've thought is sound (enough), what more to take into account and possible pointers.

Describing the scenario

  1. Let's assume there are producers, P, that produce 64-bit integers or UUIDs and signs them with a key, K, let's call these signed integers or UUIDs as tokens.
  2. Then P pairs each token with its ID, let's call the result as code where code = (token, ID).
  3. P stores the integers or UUIDs to a third party server S, along with its ID.
  4. P then releases these codes to Internet.
  5. S has the mission to answer true or false when somebody from the Internet sends a code to ask if it is a genuine one. A genuine token is one that has been issued by a producer that has stored its UUID or integer to server S.
  6. Number of released codes is significantly larger than the number of P.


  1. It should not be possible for P to claim it has not generated a given token if it in fact has and it is stored in S.
  2. It should not be possible for a malicious party, M, to generate tokens and fool S claim they originate from P if M has not acquired the key P used to sign the tokens it has released.
  3. It should not be possible for M to alter the contents of a released token.

I see this assumes S should not lie about the result of its testing and I don't see there is a way around it other than trusting S short of contacting P during validation. If it is assumed S is trustworthy in its answers, it seem feasible to assume S shouldn't be able to produce tokens either and claim they originate from P.

I think in general this calls for digital signatures where P stores the public key into S so that it can first choose a correct stored public key by key_id = code(_, ID) and then use it like so is_valid = check_validity(key_id, code(token, _) where check_validity recovers the integer or UUID and checks if it finds it from the data store.


  1. Can the ID be dropped from the code and still have an efficient way to differentiate the originator P from the token only? Even if there were a lot of Ps? Say from thousands to some millions (or whatever makes sense as a plausible upper boundary)?

2015-10-29: To answer to my own question: No. Reading from how digital signature verification process works I gather this is the reason there are certificiate authorities. However, there are differences. Here the public key isn't the public key of P that S could use to verify the signature, but a substitute ID (which S uses to retrieve the actual public key from its private cache). Maybe this adds "a line of defence", so to speak, even if not security in cryptographical sense. P and S could use the public (or private) certificate of P here, but is not necessary.

Would use certificate bring any benefits here other than perhaps using "standard infrastructure"?

  1. Reading the Wikipedia links, it seem to be the long integer or UUID needs to be hashed before signing. Would format-preserving encryption be enough (I read about the Thorp Shuffle) or should something else be used? I'm afraid I don't have concrete use case in mind beyond that having a long integer or UUID is still fairly efficient to store and to point to even in large quantities.
  2. Is there a way to limit the time of validity of signatures within the signatures themselves so that one wouldn't need to store the time along with a token and restoring it from a data store during a check?
  3. Is it possible to "chain" signatures together with something like a Merkle tree? I'm thinking a scenario where P has multiple signatures (some out-of-date) and correspondingly released tokens and then S could (efficiently) check whether a token was valid when it was signed (assuming a valid signature).

2015-10-30: To partially answer to my own question (with an answer by Tom Leek): What are the real-time applications of long term digital signature with timestamp answers rather well with references to the time part of the question.

It starts to feel I should destructure this into multiple little questions and/or move to Information Security, though I find it more interesting to entertain cryptographical security of a system like is as a whole too.

It would look like encrypting the UUID or long integers makes sense when reading Using the same RSA keypair to sign and encrypt and Why should one not use the same asymmetric key for encryption as they do for signing?. What algorithms one could use here for signing and then for hashing? Which would be "quantum proof"?

Indeed, I've been exploring ways to securely store the hashing and decryption keys to S too and threshold cryptosystems seem to be the way to go, but I think they warrant some new questions!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.