18
$\begingroup$

In my lecture, the lecturer said:

Let $K$ be the key generation algorithm. Given a security parameter represented in unary, $1^k$, $K(1^k)$ will output a keypair $(pk; sk)$, known as the public key and the private (or secret) key, respectively.

My question is: When I want to implement the cryptosystem, how should I represent this $1^k$? When I implement the key generation procedure, do I literally require callers to pass me a string of $k$ one-bits that the procedure will never use? And, if so, why is it there in the first place?

$\endgroup$
5
34
$\begingroup$

The $1^k$ is a formalism that's only there to make the theoreticians happy. You can safely ignore it. When you actually implement the cryptosystem, you don't try to pass the string $1^k$; instead, you pass $k$, the security parameter (a representation of how much cryptographic strength is desired from the key generation algorithm).

I wish I could leave it at that, because this is nothing deep: it's just something stupid and not important in any fundamental, conceptual sense. However at this point you're probably going to be saying "huh?", so I suppose I have to explain.

Why is it there? For totally stupid reasons. Its only purpose is to help remind theoreticians that key generation should be efficient: its running time should be polynomial in the security parameter.

In more detail, we want the security of our cryptosystems to be parametrizable (totally reasonable so far): for instance, if you want 80-bit security, you should be able to pick the parameter $k=80$ and get corresponding security. Theoreticians also want to impose the requirement that all of the cryptographic operations are pretty efficient (still pretty reasonable): increasing the security parameter doesn't slow down the crypto too much. Some theoreticians work in the context where performance is measured in asymptotic complexity (somewhat unreasonable in practice, but we can let that one go as it is still useful and understandable). So, they formalize the requirement that crypto operations be efficient by requiring that the asymptotic running time of all crypto operations (key generation, encryption, decryption) be polynomial in the the security parameter.

Are you following so far? So far, nothing is totally unreasonable -- but get ready, here comes the silly part. Our standard notion in complexity theory of what it means for an algorithm to be efficient is that the algorithm's running time is a polynomial in the length of the input to the algorithm. The theoreticians want their formalization to fit within this standard complexity-theoretic framework. Therefore, they formalize the requirement that crypto operations run in polynomial time by passing a special dummy padding string as input to the operations whose length is given by the security parameter. Why pass the dummy string? Well, those operations are going to completely ignore the dummy string, so passing this extra useless string seems completely pointless. It is pointless from a practical perspective, but from a theoretician's perspective, it lets them require that the cryptographic operations have a running time that is asymptotically polynomial in the length of their inputs -- and it will follow automatically that their running time is asymptotically polynomial in the security parameter (because they artificially ensured that the length of the inputs is the same as the security parameter). This makes the theoreticians happy.

Like I said, it's stupid and pointless and exists only to make the theoreticians happy. When it comes time to implement the cryptosystem, ignore it.

P.S. Perhaps I should reveal at this point that I have a bit of a theoretician in me, and sometimes it makes me happy too -- but I still realize how silly it will look to someone who cares more about using crypto than about proving theorems in complexity theory.

$\endgroup$
4
  • 1
    $\begingroup$ You do get to this later in your answer, but "you omit it completely from the actual implementation" $\hspace{.6 in}$ should be "you use $k$ instead of $1^k$ in the actual implementation". $\:$ $\endgroup$ – user991 May 1 '13 at 20:24
  • 1
    $\begingroup$ Great point, @RickyDemer! Thanks. I've edited it, and I think I fixed it, but let me know if I missed any spots. $\endgroup$ – D.W. May 1 '13 at 20:30
  • $\begingroup$ While it is correct that $k$ usually represents the amount of desired cryptographic strength is desired from the key generation algorithm, it seems it might represent any parameter that might cause some other aspect of the scheme to grow exponentially. Confer e.g. crypto.stackexchange.com/a/7853/1564 $\endgroup$ – Henrick Hellström May 1 '13 at 23:18
  • $\begingroup$ While the answer is already really good, you could add a number example to make it more clear: If you want to scale the algorithm runtime with a factor $n$, then adding $n$ itself adds $\log n$ bits, e.g. $n= 80$ in binary takes $7$ bits. So anything polynomial on the length of the input would use $7$ and not $80$. $\endgroup$ – tylo Jan 30 '17 at 11:52
10
$\begingroup$

I am confused about “Gen takes as input $1^n$ and outputs a key”. Does it mean that the input of Gen is $1111\ldots111$ with length of $n$?

Yes, it means that the input of Gen is a series of $n$ ones (e.g., $1^4 = 1111$). This is the security parameter given to Gen that determines the length of the key. In reference to the other answer, it does not refer to the random bits since they are not input. In a randomized algorithm, the random coins are not input but are internally generated. The number of random coins may also not be $n$ but any polynomial in $n$. In some cases, we like to be explicit about the randomness used as input, but it is then explicitly stated (and we would write something like $\mathsf{Gen}(1^n;r)$ to denote the input $1^n$ and random coins $r$.

You didn't ask why $1^n$ is needed as input. The answer is first so that Gen knows how long to generate the key. However for that it could have received $n$ in binary for input. The reason that it is given $n$ in unary form is so that it can run in time that is polynomial in its input. If $n$ is the security parameter, then everything runs in time polynomial in $n$. If Gen is given $n$ in binary form, then its input is only of length $\log n$ and so if it runs in time $O(n)$ its running time will actually be exponential in its input length. I hope this helps.

$\endgroup$
2
  • 5
    $\begingroup$ So it's basically a hack for being able to claim "it's polynomial complexity" for the theoretical proofs. In practice you would likely either have $n$ hardcoded in the program (i.e. the security parameter is not actually variable), or pass it in binary. $\endgroup$ – Paŭlo Ebermann May 13 at 21:53
  • 1
    $\begingroup$ Thanks a lot! I am a beginner in this field and I have encountered with quite a lot problems when I am reading the book ‘Introduction to modern cryptography ’. Your answer is absolutely professional and I wish that I can understand all of it. $\endgroup$ – 涂新宇 May 14 at 10:53
3
$\begingroup$

The explanation of why the security parameter $k$ is given in the unary form of $1^k$ as mentioned at the second footnote at page 366 of Foundations of Cryptography Volume 2 is to

allow a smooth transition to fully non-uniform formulations...Specifically $1^n$ indicates that the $n^{th}$ circuit is to be used.

$\endgroup$
3
  • $\begingroup$ Why can't we select the $n^{\text {th}}$ circuit with the usual binary form of $n$? $\endgroup$ – Paŭlo Ebermann Sep 28 '14 at 19:21
  • $\begingroup$ For non-uniform adversaries, the size of the program is polynomial in the input length, so to make it polynomial in $n$ you need to use the unary representation, because the length of the binary form of $n$ is only log $n$ bits. $\endgroup$ – pg1989 Jun 23 '16 at 17:25
  • 1
    $\begingroup$ D.W. is right, though - it's a silly formalism that isn't super important. $\endgroup$ – pg1989 Jun 23 '16 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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