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?

  • $\begingroup$ You should probably represent $1^k$ with the binary representation of $k$. $\:$ $\endgroup$ – user991 Apr 30 '13 at 0:50
  • 3
    $\begingroup$ Related: What does the expression $1^n$ mean as a function argument? $\endgroup$ – Ilmari Karonen Apr 30 '13 at 4:10
  • $\begingroup$ I've edited the question to be more general, so that it'll be helpful to others as well. (As it turns out, this question is not specific to the McEliece cryptosystem.) $\endgroup$ – D.W. May 1 '13 at 20:08

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.

  • 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

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.

  • $\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.