Information theoretical lower limit on the size of public and private keys 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 &quot;yes, it's is provably impossible&quot;, 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?
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.