Security parameter

From CRYPTUTOR

The security parameter of a cryptographic scheme is a "knob" we can use to tune its security level to make breaking the scheme infeasible. All of the complexities of the scheme depend on security parameter. Almost always, the dependence is as follows:

• The computational & communication complexities (i.e, length of keys & messages) of the scheme have a polynomial dependence on the security parameter.
• In security definitions that involve an adversary, we insist that an adversary which runs in polynomial time in the security parameter only be able to "break" the scheme (however this is defined) with negligible probability in the security parameter.

As an example, in an encryption scheme, the security parameter controls the length of the keys, and ciphertexts. If we increase these sizes by just a little, then encrypting and decrypting takes slightly more time, but it becomes much harder for an adversary to break the scheme's security.

Often, when defining cryptographic schemes, the security parameter is implicit. We often reason about a scheme without explicitly considering all values of the security parameter. However, we always consider the scheme's asymptotic behavior as the security parameter grows (i.e, polynomial or negligible in the security parameter).