6
$\begingroup$

What does $1^\lambda$ mean when you pass it as a parameter to the functions of a cryptosystem. The cryptosystem in question is this and a picture reference is this.

I have been told it signifies the "security parameter of the cryptosystem" but this is not clear to me. In this picture, you can see that

$\lvert p \rvert = \mu$ bits

$\lvert q \rvert = 2\lambda - \mu$ bits

which means $\lvert \Delta_K \rvert = 2\lambda$ bits

So does all this mean that if I want 128 bits of security, $\lambda$ has to be 128 and $\Delta_K$ 256 bits?

If yes, this would not make sense with their results they mention and also all the work I have done with this system. For a 128-bit security in this system, the size of $\Delta_K$ has to be 1828 bits. This is something I can strongly assure you of.

Any pointers would be greatly appreciated. Lastly reiterating the question,

"What does the notation $1^\lambda$ mean when it is passed to KeyGen(), Encrypt() and Decrypt() ?"

Improve this question
$\endgroup$
3

1 Answer 1

Reset to default
10
$\begingroup$

The notation $1^\lambda$ means a string with $\lambda$ characters all of them equal to 1. For instance, if $\lambda = 3$, then $1^\lambda$ is $111$.

And yes, it typically stands to the security parameter, from which the probability of "breaking" the system is measured (as well as the resources needed to do so and also to execute the cryptosystem's procedures).

The reason to use $1^\lambda$ instead of $\lambda$ is theoretical. The point is that the functions run by the users (KeyGen, Enc, Dec, etc) are supposed to run in polynomial time and the best attacks are usually supposed to take exponential time. But polynomial/exponential time regarding what? Regarding the size (length) of the input. So if you say that the input is simply an integer $\lambda$, what is the input's length? But using $1^\lambda$ as the input, the size is clearly $\lambda$, because the input has $\lambda$ characters (or letters, or bits...).

And about this specific scheme that you've cited, I would say that the authors are probably miss-using the notation. It seems that $\lambda$ measures how many bits the integers used there have. So, the algorithms run in poly$(\lambda)$ as expected. But, as it happens often (e.g. with RSA), for a security level of $\lambda$ bits, the integers used in the scheme must have much more than $\lambda$ bits.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So if I were to use the power notation in its correct sense, then the exponent should really refer to the security level of the system. In this particular case, I should really be using a different symbol like gamma where gamma would refer the level of security at any given point. Am I right? $\endgroup$
    – Papa Delta
    Commented Aug 23, 2018 at 15:39
  • $\begingroup$ @Mojo-Jojo since it is already standard to use $\lambda$ for the security parameter, I think it would be better to replace the $\lambda$ in the paper by another symbol, let's say, $\gamma$ and to explicitly define $\gamma$ and $\mu$ as a function of $\lambda$ writing something like $\mu := \mu(\lambda)$. What those functions would be depends on the security properties of the system. For instance, as you said that $\Delta_K$ with 1828 bits guarantees a security of 128 bits, $\Delta_K$ would have $2\gamma$ bits, then $\gamma$ should be a function such that $\gamma(128) = 1828/ 2 = 914$. $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented Aug 23, 2018 at 17:17

Your Answer

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

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