Security parameter

In cryptography, a security parameter is a way of measuring of how "hard" it is for an adversary to break a cryptographic scheme. There are two main types of security parameter: computational and statistical, often denoted by and , respectively. Roughly speaking, the computational security parameter is a measure for the input size of the computational problem on which the cryptographic scheme is based, which determines its computational complexity, whereas the statistical security parameter is a measure of the probability with which an adversary can break the scheme (whatever that means for the protocol). Security parameters are usually expressed in unary representation i. e. is expressed as a string of s, , conventionally written as so that the time complexity of the cryptographic algorithm is polynomial in the size of the input.

The security of cryptographic primitives relies on the hardness of some hard problems. One sets the computational security parameter such that computation is considered intractable.

If the security of a scheme depends on the secrecy of a key for a pseudorandom function (PRF), then we may specify that the PRF key should be sampled from the space so that a brute force search requires computational power. In the RSA cryptosystem, the security parameter denotes the length in bits of the modulus n; the positive integer n must therefore be a number in the set {0, , 2 1}.

In encryption schemes, one aspect of security is (at a high level) that anything that can be learnt about a plaintext given a ciphertext can also be learnt from a randomly sampled string (of the same length as ciphertexts) that is independent of the plaintext. Formally, one would need to show that a uniform distribution over a set of strings of fixed length is statistically close to a uniform distribution over the space of all possible ciphertexts. In zero knowledge protocols, we can further subdivide the statistical security parameters into zero knowledge and soundness statistical security parameters. The former parameterises what the transcript leaks about the secret knowledge, and the latter parameterises the chance with which a dishonest prover can convince an honest verifier that he knows a secret even if he doesn't. In universal composability, the security of a protocol relies on the statistical indistinguishability of distributions of a real world and an ideal world execution. Interestingly, for a computationally unbounded environment it is not sufficient for distributions to be statistically indistinguishable since the environment can run the experiment enough times to observe which distribution is being produced (real or ideal); however, any standalone adversary against the protocol will only win with negligible probability in the statistical security parameter since it only engages in the protocol once.