To what degree can we define an RSA variant, with a security argument that it is as safe as regular RSA with a given modulus size $m$ (e.g. $m=2048$), in which the public key has a compact representation of $k\ll m$ bits?
We can fix the public exponent to our favorite customary value, e.g. $e=2^{16}+1$ or $e=3$, thus need to store only the public modulus $n$. We need not store the leftmost bit of $n$, which is always set by definition; nor the rightmost bit, which is always set since $n$ is odd. With a little effort, we could save (very) few more bits noticing $n$ has no small divisors, but that will still be $k \sim m$ bits.
We can do better by forcing the $\left\lfloor m/2-\log_2(m)-2\right\rfloor$ high bits of $n$ to some arbitrary constant such as $\left\lfloor\pi \cdot 2^{\left\lfloor m/2-log_2(m)-4\right\rfloor}\right\rfloor$. Observe that we can chose the smallest prime factor $p$ of $n$ just as we would do in regular RSA, then find the maximum integer interval $[q_0,q_1]$ such that any $q$ in that interval cause $n=p\cdot q$ to have the right high bits, then pick a random prime $q$ in that interval (most often there will be at least one, if not we try another $p$). Some of the security argument is that
- generating an RSA key $(p,q')$ using a regular method, with random huge primes in some appropriate range and no other criteria beside the number of bits in $n'=p\cdot q'$, and $p<q$;
- then deciding the high bits of $n$ from those in $n'$;
- then finding $[q_0,q_1]$, generating $q$ as a random prime in that interval, and setting $n=p\cdot q$;
demonstrably gives the same distribution of $(p,q)$ as said regular generation method, hence is as secure; then we remark that the high bits of $n$ are random (with some distribution not too far from uniform), and public, thus fixing it can't much help an attack (I think this can be made rigorous).
This is now $k \sim m/2+\log_2(m)$ bits to express the public key. We can save a few more bits, each one at worse doubles the amount of work to generate the private key (we can repeat the generation process outlined above until we find a key with these bits equal to some public arbitrary constant; or equal to bits from a hash of the other bits if we want a tighter assurance that the scheme is not weakened).
Can we do better, and what's the practical limit?