Does a public key cryptography method that enables the public key to be orders of magnitude smaller than the private key exist?

  • $\begingroup$ Yes. $\:$ It's called "pad the private key". $\;\;\;\;$ $\endgroup$ – user991 May 25 '14 at 6:58
  • $\begingroup$ Stretching a secret key often appears in the context of leakage-resilient cryptography. $\endgroup$ – xagawa May 27 '14 at 2:48

Yes. Hash based signature schemes are a prime example. The private/secret key of a Merkle tree is the whole list of leaves, while the public key is the root hash.

In practice the leaves are not usually all stored, but derived from a shorter key. Even then it may be useful to store e.g. $O(h)$ hashes to accelerate signing, where $h$ is the tree height. With CMSS (pdf) $T$ levels of trees are generated and the signer stores the verification keys for the active tree at each level, which is about $T$ times as much data as the public key.


Yes, there are public-key cryptographic systems with a public key orders of magnitude smaller than the private key. One way to illustrate this is modifying a cryptosystem to make its private key larger: as noted by Ricky Demer we can use padding; another example would be an RSA variant where the private exponent $d$ is replaced by $d'=((p-1)\cdot(q-1))^{(10^3)}+d$, making the private key $3$ orders of magnitude larger than the public key.

For all secure cryptosystems with a public key orders of magnitude smaller than the private key, this is because the private key is large, and in some sense larger than it could be: we can turn any such system into one with the same public key format, and a short private key. That's by modifying the key generation procedure to use a CSPRNG to generate the required randomness. Knowledge of the CSPRNG seed allows to reconstruct the same public/private key pair, from which it is easy to extract the original private key. That seed can thus be considered to be the private key of a variant cryptosystem, and can be the size of the public key without significantly reducing the overall security of the cryptosystem. Drawbacks of such compression of the private key are that the computational cost of the generation procedure of the original cryptosystem is now part of the procedure using the private key; and we need to trust the CSPRNG.

As pointed in this other answer, some hash-based signature schemes actually proposed have short public key and large private key (the later being when above compression of the private key is not used, in the interest of speed of signature); however that can be seen as deferring transmission of public key material into the signature. Something similar works for any signature (but not encryption) cryptosystem with a long public key: it is possible to define a variant with the public key replaced by its hash, and including the original public key in signatures; the modified signature verification procedure extracts the public key from the signature, checks it against the hash, and proceeds as before. Drawbacks of such compression of the public key are that the signature is larger, and we need to check a hash and trust its preimage resistance in that circumstance (basic second-preimage resistance of the hash is not enough, as rightly pointed in a comment)

  • 1
    $\begingroup$ Note that second-preimage resistance is not necessarily sufficient for this answer's last paragraph, since the original signature verification key is not necessarily uniformly distributed, and even when it is uniformly distributed, the adversary can see signatures for it. $\:$ In general, an eTCR property would suffice, although the signatures would also need to include the hash's randomness. $\;\;\;\;$ $\endgroup$ – user991 May 26 '14 at 5:39

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.