Information theoretical lower limit on the size of public and private keys

Question

When we consider public key algorithms, those usually require keys that are much longer than their security level. According to the Crypto++ Security Level page, for example, integer factorisation algorithms (RSA et al.) require 3072 bits of modulus for a security level of 128 bits.

After RSA, we started to have more efficient systems (both in terms of speed and size), like the very efficient (to todays standards) Curve25519 elliptic curve. This curve requires around 256 bits of storage for the public key, and around 256 bits of storage for the secret key for the equivalent security level of 128 bits.

While RSA doesn't accept any bitstring as secret key, Curve25519 (give or take three bits) does. EC can be broken in $\mathcal{O}(\sqrt n)$, which sadly halves the security level.

So, while practically all public key algorithms have longer keys than symmetric counterparts, I wonder whether this is explicitely necessery. In short: is it (provably) impossible to devise a public key system wherein the public key and private key only take $k$ bits, with the security level equal to $k$, the information theoretical limit?

Bonus:

(If the answer to the above question is "yes, it's is provably impossible", this question gets redundant)

Notably post-quantum algorithms (thinking about SIDH) are heavy on key sizes (NTRU takes a few kB, SIDH a few kb). I restrict the above question to post-quantum public key algorithms: is there a (formal) reason for the requirement of large key sizes in post-quantum cryptography?

Answer 1

The private key can be reduced to $k$-bit in any asymmetric cryptosystem (encryption or signature) with a resistance to brute force of $O(2^k)$ steps (on a conventional, non-quantum computer). Proof sketch: replace the RNG used for key generation by a PRNG with at least $k$-bit security and seeded with a $k$-bit key. And that bound can't be much improved since there must be at least $O(2^k)$ private keys to avoid a brute force search. Note: that does not apply to already generated private keys.

On a quantum computer, that goes reducing private key to $2k$-bit for $O(2^k)$-something quantum resistance. Argument: a symmetric cryptosystem secure to $O(4^k)$ classical steps is widely believed to require at least $O(2^k)$-something (time or/and qubits) on a quantum computer.

---

The public key must be at least about $k$-bit in any asymmetric cryptosystem (encryption or signature) with a resistance $O(2^k)$ to brute force (on a conventional, non-quantum computer). Argument: we could use the above compressed form of the private key, and there can't be much less public keys than there are private keys, since that would allow finding by enumeration with effort $O(2^k)$ a private key matching a given public key.

But there is doubt that a $k$-bit public key is achievable. All known asymmetric cryptosystems actually have their public key $2k$-bit or more, for security as above. $2k$-bit is achieved by schemes based on the Discrete Logarithm in an Elliptic Curve group, and that's a plausible lower bound for the public key size. I vaguely remember having seen it conjectured at sci.crypt(.fr?), but without a convincing argument; and I fail to dig it up.

Answer 2

The premise of your question is a bit flawed.

No modern cipher achieves or even approaches the information theoretical limit, be it public key or symmetric key.

No practical block cipher is a purely randomly chosen permutation, no practical stream cipher is an OTP. No PKC algorithm supplies us with a perfect one way trapdoor function (to the best of my knowledge no one has proved even a strong polynomial lower bound on the margin of strength of the inverse of an explicit one way function compared to the forward function--James Massey, The difficulty with difficulty, Google for his talk slides).

They all have computational security, based on, say, best known algorithm for factoring (PKC) or best known attacks, such as linear cryptanalysis.

As for requirements beyond your estimated security level, it's for having a security margin against future attacks, if a cipher is to be used for a decade, say.

Also, public keys guard certificate information, while symmetric keys guard, say, communication sessions.