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?

  • $\begingroup$ How is the validity of the public key checked? Would a Diffie Hellman scheme be more appropriate? $\endgroup$ – QuadrExAtt Aug 29 '14 at 22:34
  • 2
    $\begingroup$ Why can't they just bundle f(x) with the data for some one-way function f? $\;$ $\endgroup$ – user991 Aug 30 '14 at 0:35

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.


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.

  • $\begingroup$ The user publishes $(pk,m,H(pk||m))$ (as the message), on an insecure connection. The attacker also shouldn't be able to change to revocation message, but it's fine if they change the message and the public key: it's a different message! $\endgroup$ – fread2281 Sep 1 '14 at 14:21
  • $\begingroup$ @fread2281, that's equivalent to publishing just $(pk,m)$. The hash doesn't add anything, since an attacker who modifies $pk$ or $m$ can just as easily recalculate the hash as well. $\endgroup$ – otus Sep 1 '14 at 14:36
  • $\begingroup$ messages are identified by their hash $\endgroup$ – fread2281 Sep 1 '14 at 14:50
  • $\begingroup$ @fread2281, I don't follow. If Alice sends $(pk, m, H(pk||m))$ to Bob, what's to stop Eve from modifying it to $(pk', m, H(pk'||m))$ in flight and later revoking it? $\endgroup$ – otus Sep 1 '14 at 14:51
  • $\begingroup$ Bob will know it's not the message he requested because it doesn't match the hash he requested $\endgroup$ – fread2281 Sep 1 '14 at 14:55

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

  • $\begingroup$ How was RSA "proved to be as difficult as prime factorisation"? $\;$ $\endgroup$ – user991 Aug 30 '14 at 0:18
  • $\begingroup$ Divesh Aggarwal and Ueli Maurer showed in 2008 [ eprint.iacr.org/2008/260 ], that in general, whoever can break RSA can also factor the modulus $n = p \cdot q$ in polynomial time and vice versa. These two problems are therefore equivallent. You are right, when you say this is not exactly prime factorisation. $\endgroup$ – QuadrExAtt Aug 30 '14 at 0:26
  • 1
    $\begingroup$ One thing he might mean by better security is hopefully being secure against quantum algorithms. $\hspace{.43 in}$ $\endgroup$ – user991 Aug 30 '14 at 0:31
  • 1
    $\begingroup$ I'd like to avoid that forgery. I am interested in security against quantum attacks, but I'll accept this for now. $\endgroup$ – fread2281 Aug 30 '14 at 0:48
  • 3
    $\begingroup$ @QuadrExAtt The Aggarwal-Mauer result applies only to generic algorithms that break RSA. That's a very restrictive model for how the algorithm must work -- in particular, it must consult an oracle to perform ring operations. The result does not imply that breaking RSA is equivalent to factoring the modulus; indeed, this remains a major open problem. $\endgroup$ – Chris Peikert Aug 30 '14 at 10:54

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.