Asymmetric algorithm for one time signing of small cleartext

Question

I want to generate a key pair such that the private key can be used once to sign a small message (1024 bytes) at some indeterminate point in the future and the public key can be used to verify that signature, what can I do to get better security than a regular asymmetric algorithm (e.g. RSA)?

The use case is allowing a user to "revoke" data by bundling the public key with the data. The user can then publish a revocation message (which can also contain some arbitrary but short message) with the private key.

And, do these requirements make any of the post-quantum algorithms especially suitable?

Answer 1

One algorithm that is especially suited to one-use key pars is lamport signatures. Like many (all?) other signature functions, lamport signatures first hash the message to get it down to a size that is more reasonable to sign.

For this use case, if you are willing to have $n^{2}$-bit signatures and $2n^{2}$-bit keys (public and private), you can sign a $n$-bit (or less) message with only a one-way function, by skipping the hash message step and just signing the message directly.

This is nice, because the security of all hash functions and many other algorithms relies on one-way functions. Using such a simple algorithm also removes most attack vectors (the remaining one is the one-way function, which is still an attack vector with most (all?) complex signature schemes).

There are various ways to reduce the sizes required.

Answer 2

Your use case is specific enough that you may be able to avoid full signatures and use a one-way function directly.

When publishing the data you can use as a public key the hash of a random value $H(r)$, so that the full message is $(H(r), m, H(H(r) || m))$. Revealing $r$ is then seen as the revocation of that data, since that is the only message required. The only way to revoke is to know $r$. Conversely, $r$ will only revoke that particular message (if chosen as random 256-bit value).

When publishing the data there must be some way to ensure authenticity and integrity of the data and the revocation hash. It is the same if you attached a public key: without authenticity an active attacker could have replaced the key/hash with one for which they know the private half. For example, receiving the data and hash together through a pre-established, authenticated, encrypted channel would suffice.

The advantage of using just a hash function is that you get the post-quantum security of hash functions without the key and signature size of Lamport signatures. You only need a 256-bit hash of a 256-bit value for 128-bit post quantum preimage resistance.

Answer 3

What do you mean by better security? RSA was proved to be as difficult as prime factorisation and is thus one of the best understood public key cryptosystems. Also, since its widely used their implementations have withstood years of attacks. Since you are going for a one-time usage of the keys, speed is not of importance (or is it?). If you can handle the key size requirements of RSA, I don't see you can do better.

Edit: @Ricky-Demer has a very good approach of taking a hash function $f$ together with some private data $s$ and publish the value $p:=f(s)$ for everyone to see. If you ever need to send your revoke message, you can bundle this message $m$ together with $s$: $(m,s)$. Everyone will now be able to use $f$ to compare $f(s)$ to $p$ and check that the one sending the message was indeed the (only) one who was in posession of $s$. Of course, after you have done this, everyone else in the world is able to forge revocation messages $(m',s$).