If I want it to be considered reasonable valid proof that I did, indeed, have the data leading to the hash when the notary signed it, and I want stuff I sign today to be acceptable 10 years from now, would you consider HMAC-MD5 viable? How about HMAC-SHA1? I guess plain MD5 and SHA1 are out of the question according to this article.
Speed is not a concern here, so I would be happy with HMAC-SHA3 or anything else... Also, I keep reading that multiple signatures (MD5 + SHA1) are only as strong as the strongest one, but that does not make any sense to me - If you have two differently seeded (initial internal state) MD5 hashes, it should already be much harder to exploit (perhaps not double the number of bits, but surely a large load factor)?
C_{4P}(SHA-2-512, SHA-3-512) should remain solid for a long long time. Your point of failure is, now, the signature scheme. To last for decades, do not use RSA or DSA. Use elliptic curve DSA or similar (EdDSA comes to mind).
As I understand it, ECC is also significantly faster.
(And in a related issue - does anyone know why smart card deployment in the US is so far behind Europe? Why is it that I need to get a PGPcard from germany and can't find anything comparable in the US?)
RSA and DSA are based on the integer factorization and finite field discrete logarithm problems, respectively. The number field sieve has a complexity (very roughly) proportional to 2^(b^(1/3)), for b-bit keys. This means that keys have to be proportional to 2^(b^3) to achieve b-bit security. For a concrete example, 256-bit security requires ~16384 RSA/DSA keys (this is using a less rough approximation of the NFS complexity).
On the other hand, well-chosen elliptic curve groups have (or appear to) much less structure than the above. In generic groups, the best we can do to solve the discrete logarithm are generic attacks, like Rho or BSGS. Those run in time proportional to 2^(b/2). Therefore, we only need keys of size 2^(2b) to achieve b-bit security (512-bit keys for 256-bit security). Bit for bit, elliptic curves are much more efficient to deliver the same level of security. This results in other advantages, like tolerable speed.
Thanks!
You hash your data, and send the hash to them. They embed the hash in a long hash-chain, and publish the current head of the hash chain in Financial Times every month. Once the hash chain head has been published, it is impossible to forge the signed content without destroying all copies of the newspaper in existence.
It seems that the service is free for basic use, only availability SLAs and customer support is paid.