Why require that public and private key each have length at least the security parameter?

Question

In Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography (3^rd edition), the key generator of e.g. signature has

The key-generation algorithm $\mathsf{Gen}$ takes as input a security parameter $1^n$ and outputs a pair of keys $(\mathrm{pk},\mathrm{sk})$. These are called the public key and the private key, respectively. We assume that $\mathrm{pk}$ and $\mathrm{sk}$ each has length at least $n$, and that $n$ can be determined from $\mathrm{pk}$ or $\mathrm{sk}$.

I see why the minimum size of $\mathrm{pk}$ and $\mathrm{sk}$ must grow with $n$ (with some minimum rate) in order to meet any sound security definition, but not why that's made a requirement.

Answer 1

You're probably familiar with the convention of giving input $1^n$ to an algorithm as a way to indicate "this algorithm is allowed to run in polynomial time in $n$." Suppose you are writing about an encryption scheme and want to be very precise about this. You would write:

• $\textsf{KeyGen}(1^n) \to (sk,pk)$
• $\textsf{Enc}(1^n, pk, m) \to c$
• $\textsf{Dec}(1^n, sk, c) \to m$

Now suppose you know (or insist) that $|pk| \ge n$ and $|sk| \ge n$, and that $n$ can be efficiently computed by looking at $pk$, $sk$. Then $1^n$ can be omitted as input from $\textsf{Enc}$ and $\textsf{Dec}$ without loss of generality: these algorithms have enough information and running-time budget to efficiently reconstruct the string $1^n$ if needed. In short, this requirement simplifies the notation without sacrificing any rigor.

It would have also worked to insist that $|sk|, |pk|$ are $\Omega(n^c)$, so that any polynomial function of $|sk|$ is also a polynomial function of $n$. Basically, $|sk|, |pk|$ can't be exponentially smaller than $n$. (The fact that $\textsf{KeyGen}$ is a polynomial time algorithm already means that $|sk|,|pk|$ can't be exponentially larger than $n$.)