1
$\begingroup$

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.)

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, simply check that hashing the private key together with the timestamp produces the same hash as on the document.

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.

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?

(Forgive me if this is a silly question. I'm very much a layman.)

$\endgroup$
  • 1
    $\begingroup$ There was an area that PUF was popular maybe still, researches looked into paper PUF and signing the document with square code. They proposed to scan the surface of the paper - that is actually 3d in close up - and the print on the paper. Then apply the usual hash then sign. $\endgroup$ – kelalaka Mar 19 at 21:19
  • 3
    $\begingroup$ I'd point out that the great seal does indeed call for a central authority. There must be an agency who states "this is what the great seal looks like" to prevent people from making up things that are almost correct and stamping documents with them. $\endgroup$ – Cort Ammon Mar 19 at 23:11
  • 1
    $\begingroup$ For specifically US (Federal) laws, regulations (CFR), and bills published electronically by the Government Publishing Office (formerly Printing, GPO) see govinfo.gov/about/authentication (Remember Internet started in US and although .com .org .edu .net are now worldwide, .gov .mil remain US-only.) $\endgroup$ – dave_thompson_085 Mar 20 at 13:59
  • 1
    $\begingroup$ @JoshEller Look athow the question says the private keys work though. $\endgroup$ – user253751 Mar 20 at 14:47
  • 2
    $\begingroup$ I'd like to point out that you are severely overstating the purpose of the seal. The exact design of the seal (and others like it) is publicly known and the seal is trivial to reproduce. The only purpose it serves on any kind of document is for tradition (and because it's required by law) and as a pretty picture to make people feel good. Basically it lends a document a certain gravitas, but serves no security purpose. So the answer to the question in the title is "Yes, we can digitally represent pretty pictures." $\endgroup$ – Maeher Mar 20 at 16:16
4
$\begingroup$

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...

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It looks like you might have a parenthesis out of place. Should it be '...(where "sign" means generate a signature that verifies) with the signature validation algorithm and the public key.'? $\endgroup$ – David Z Mar 20 at 7:07
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Well, nobody knows that the US's "great seal" is actually from the US, either. $\endgroup$ – user253751 Mar 20 at 14:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.