Return to Answer

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 represent it: you omit it completely from the actual implementation.

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 some 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 working in the context where performance is measured in asymptotic complexity (somewhat unreasonable in practice, but we can let that one go). 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.

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.

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 represent it: you omit it completely from the actual implementation.

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. 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 working in the context where performance is measured in asymptotic complexity (somewhat unreasonable in practice, but we can let that one go). 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.

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 represent it: you omit it completely from the actual implementation.

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 some 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 working in the context where performance is measured in asymptotic complexity (somewhat unreasonable in practice, but we can let that one go). 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.

The $1^k$ is a formalism that's only there to make the theoreticians happy. You can safely ignore it.

Why is it there? For totally stupid reasons. They want to the security of the scheme 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. They 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. They're working in the context where performance is measured in asymptotic complexity (somewhat unreasonable in practice, but we can let that one go). 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 a polynomial-time algorithm 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 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 the 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. 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.

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 represent it: you omit it completely from the actual implementation.

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. 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 working in the context where performance is measured in asymptotic complexity (somewhat unreasonable in practice, but we can let that one go). 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.