2
$\begingroup$

In Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography (3rd 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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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$.)

$\endgroup$
3
  • 2
    $\begingroup$ Ah. So the requirement $|\mathrm{sk}| \ge n$ is to $\mathsf{Sign}$ what the truism $|1^n| \ge n$ is to $\mathsf{Gen}$. That now makes perfect sense! $\endgroup$
    – fgrieu
    May 22, 2021 at 17:35
  • $\begingroup$ I don’t think removing this requirement costs rigor. If a hypothetical algorithm has very short keys, it simply has less time budget for Sign/Verify. If they can still satisfy correctness and could still satisfy security, that would be marvelous. For this reason, I regard that as a hint for the usual situation. $\endgroup$
    – Gee Law
    May 22, 2021 at 17:52
  • $\begingroup$ Removing the requirement can cost rigor. If you hypothetically had an algorithm that could work with keys of length $\log^2 n$ then the algorithm wouldn't have time to read a message of length $n$. You can easily solve this by including $1^n$ but that's a pain. This assumption is easy and doesn't limit anything in practice, and so just simplifies things. $\endgroup$ May 23, 2021 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.