What is the difference between security parameter and $b$-bit security?

Question

In a previous question, I read

... for $b$-bit security meaning $O(2^b)$ work for an attacker to break the system...

While in Katz's Introduction to modern Cryptography, I read:

The key-generation algorithm $\text{Gen}$ takes as input $1^n$ (i.e., the security parameter written in unary) and outputs a key $k$".

What is the difference between security parameter and $b$-bit security?

Edit: Can I have an example for the McEliece cryptosystem?

Answer 1

They both have to do with complexity in terms of a bitlength but there the similarity ends.

The $b-$ bit security uses the brute force number of guesses $2^b$ which would be required in the worst case to determine a $b-$ bit key (since there are exactly as many possible keys).

The other notation regarding security parameter is a notational construct that ensures that a certain input has the "right size", in terms of use in asymptotic analysis of security proofs.

Wikipedia:

In cryptography, the security parameter is a variable that measures the input size of the computational problem. Both the resource requirements of the cryptographic algorithm or protocol as well as the adversary's probability of breaking security are expressed in terms of the security parameter.

The security parameter is usually expressed in unary representation (for example, a security parameter of $n$ is expressed as a string of $n$ 1s

Note: this is your $1^n$

so that the time complexity of the cryptographic algorithm is polynomial in the size of the input.

Answer 2

What is the difference between security parameter $1^n$ and $b$-bit security?

There's not one, but two:

1. A security parameter $1^n$ does not precisely specify how the attacker work grows with $n$. Depending on author and context, that can be: unspecified; faster than any polynomial in $n$ (common in asymmetric cryptography); exponential in $n$ (common in theoretical symmetric cryptography); or roughly¹ as $2^n$ (common in applied symmetric cryptography).
   By contrast, "$b$-bit security" specifies that the work for attack grows roughly¹ as $2^b$, as it can in symmetric cryptography for attacks aiming at recovery of a $b$-bit key for an ideal cipher. The distinction is paramount in RSA, where $n$ most often is the bit size of the modulus, and $n=2048$ is believed to yield $b\approx112$.

2. When we consider algorithms running in time at most polynomial to the size of their input, as is customary in theoretical work: passing $1^n$ (meaning a bitstring consisting of $n$ bits at one) as input implies that the run time is polynomial in $n$, when passing $n$ would allow the run time to be a polynomial in $\log(n)$. Usually the former is desired in cryptography.
   Whereas "$b$-bit security" says nothing about the run time.

---

¹ For some definition of roughly. Many, including me, often state that the expected attacker work is $O(2^b)$,. That's improper because that upper-bounds said work. We should at least write $\Omega(2^b)$ or $\Theta(2^b)$; see this. I corrected that (minor and common) issue in my answer to the "previous question" mentioned.