Is there a digital equivalent to the Great Seal of the United States?

Question

Since antiquity (and, for ceremonial purposes, up to the present day), physical documents have had seals affixed. In principle, these seals enable anyone, if he knows what he's looking for, to judge the authenticity of a document without consulting the authority that issued it. (In practice, there are ways of producing convincing forgeries, but leave that to one side for a moment.)

Is it possible, by affixing a string of characters, or suchlike, to a PDF, to achieve the same thing digitally?

I can think of a way of doing something similar:

1. Come up with a private key and a hashing function.
2. Hash the private key together with the timestamp for when the document was issued.
3. Affix the above hash, together with the timestamp, to the document.
4. When someone wants to authenticate a document, check that hashing the private key together with the timestamp produces the same hash as on the document.

However, the major difference between the above method and a physical Great Seal (e.g., The Great Seal of the United States) is the need to consult someone who has the private key. This check would have to come from a central authority since making the private key public would allow free reign to any forger.

Is there a way, then, of doing something like the above, but without the need for a central authority? If no, is it logically impossible, or is it an open problem?

Answer 1

Is there a way, then, of doing something like the above, but without the need for a central authority?

Why, yes, we do have a way to solve that problem - we refer to it as a 'digital signature'

Here's how it works:

1. Select a signature algorithm, and come up with a public/private key pair for a signature algorithm

2. With the private key, generate a signature of the document (possibly with the time stamp and anything else you find relevant). Affix the above hash, together with the timestamp, to the document.

3. When someone wants to authenticate a document, simply get the public key, and check that the signature validation algorithm, together with the document and the timestamp, states that the signature verifies.

The fundamental property of a signature algorithm is that, while it is easy to sign any document you want with the private key, you cannot sign any document (where "sign" means generate a signature that verifies with the signature validation algorithm and the public key).

Common signature algorithms in use today are RSA, ECDSA and EdDSA

Of course, one step I didn't go into is "how, in step 3, does someone get the public key" and "how do they know that the public key they get is actually the signer's, and not some attackers"? These are valid questions, with good answers; but I think I'll leave the exploration of that for another question...

Answer 2

Since antiquity (and, for ceremonial purposes, up to the present day) physical document have had seals affixed to them. In principle, these seals allow anyone, if he knows what he's looking for, to judge the authenticity of a document without consulting the authority that issued it. (In practice, there are obviously ways of producing convincing forgeries, but leave that to one side for a moment.)

Well, let's not leave that out, because that's exactly where the problem lies: trusting the stamp or, for digital files, signature.

The major difference between the above method and a physical Great Seal, however, is the need to consult someone who has the private key. This would have to be some form of central authority, since making the private key public would allow free reign to any forger.

Sharing a private key is a misunderstanding in itself. You cannot share a private key. You might however share a secret key between a specific set of entities that you trust. This would however degenerate into a secret sharing scheme for a symmetric key to be used with e.g. HMAC. This is not a good idea; you'd want asymmetric cryptography with public and private keys.

---

How do you detect that a US seal is real? Hopefully it is not just the materials used and the fact that it looks shiny. No, you've either seen it before or you've seen it described.

You can do something similar with digital signing using X.509 certificates. Instead of setting up a PKI you simply share a fingerprint of a public certificate which you then publish. That way you can take the fingerprint of a certificate that was used to sign a document. If the fingerprint validates then the document is valid. You could also use a fingerprint over the public key directly, but a certificate is more like a seal to me.

A fingerprint may still be 20-32 bytes in size, or 40 to 64 hexadecimal characters (or any other encoding of the same amount of bytes). If that's too much you can choose 4 locations randomly and then remember just those locations and the values - and keep them secret. An adversary would have to know the exact locations to create a forgery. The chances that 4 bytes are correct by chance is 1 in $2^{32}$, i.e. 1 in ~4 billion.

I don't see any reason to include a time stamp service in this scenario; certainly the US seals don't carry a time stamp after all. If you do it would be for other reasons.

Answer 3

I'm unaware of any proof of impossibility (although it wouldn't surprise me if one existed), but the fundamental issue here is there's no fundamental way that "physical identity" and "digital identity" are bound together. In short, given any algorithm $\mathcal{A}$ which generates some "seal" (or some private information used to generate seals in the future), someone else could just run that algorithm and claim to be me. How could you know who's telling the truth?

The typical way this is bypassed is by appealing to some central authority (certificate authorities for example) who do such binding themselves. If you want to explicitly exclude this, it's unclear what options are left. There has been somewhat of a trend of nation states doing such binding (in the US, your social security number is often used as proof of your "identity", although this is a cryptographically horrible solution), so if you don't count such efforts as a "central authority" one may be able to do something based on them.