I want to generate a key pair such that the private key can be used once to sign

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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.