Statistical security parameter -> information theoretically secure

Question

If a cryptographic protocol has a computational security parameter and a statistical security parameter, does this mean it is only computationally secure instead of information-theoretically secure?

I am wondering because this answer says that statistical indistinguishability is when the adversary is computationally unbounded: https://crypto.stackexchange.com/a/11790 . That would imply that the presence of a statistical security parameter means that a protocol is information-theoretically secure. Is that true?

Thank you!

And apart from that how do I find out whether a protocol is information-theoretically secure if it is not explicitly stated?

Answer 1

A protocol (and in general, a cryptographic construction) satisfies information-theoretic security if no adversary can break the system, no matter how powerful the adversary is. The term "information-theoretic" is rooted in the idea that the leakage from the interaction can be studied from the perspective of information theory, and it can be concluded using these tools, which typically involve a simple of mix of statistics and probability theory, that the interaction with the system really leaks almost nothing. Now, perfect and statistical security are two forms of information-theoretic security: in the former, there is zero leakage, but in the latter there is a negligible leakage than can be made smaller and smaller by appropriately choosing a statistical security parameter.

Now, a protocol, or again, in general, a cryptographic construction, can satisfy computational security, meaning that it is only secure as long as the adversary has bounded computational resources. This is typically the case when tools like encryption (usually with some kind of homomorphism) are used, which have an associated computational problem that the adversary should not be able to solve in order to guarantee security of the system. The way security of these tools is formalized is by means of a computational security parameter, which, as it grows, it makes the underlying computational problem harder to solve, hence providing much more confidence (but also, typically, making parameters worse).

Although researchers can be a bit lax with language, the most typical situation is that you will find the type of security explicitly stated, e.g. ...protocol X instantiates functionality Y with perfect security/statistical security/computational security... However, sometimes this is assumed to be known from context, or the focus in terms of clarity lies in other aspects of the construction, so the authors will not state this quite explicitly. As a rule of thumb, if there is any construction that assumes a bounded adversary, which typically include encryption, signatures, commitments, among others, then security is for sure computational. It should also be mentioned that it is quite customary that the computational security parameter is not explicitly stated.

Furthermore, and this is directly related to your initial question, it is important to take into account that a protocol can be computationally secure but also have a statistical security parameter. This can happen, for example, if the protocol makes use of cryptographic tools such as encryption and so on, but in some parts it relies on, for instance, a statistical check that the adversary can cheat on with negligible probability. Since it is still true that the protocol is broken if an adversary has unbounded resources then your conclusion is right: the type of security would be only computational.

Answer 2

In interactive protocols (like MPC) you will often see a combination of computational and statistical security parameters used together.

• Computational security parameter: tunes the hardness of some attack that depends on the adversary's running time. For example, a protocol uses a pseudorandom function, and breaking that pseudorandom function will break the protocol. The key size of the pseudorandom function is governed by the protocol's computational security parameter. When you look closely at the adversary's formal advantage, and you see a term of the form $T/2^\kappa$ or $q^2/2^\kappa$ where $T$ or $q$ is related to the adversary's computational effort, then $\kappa$ is a computational security parameter.

• Statistical security parameter: tunes the hardness of some attack where the adversary's running time is irrelevant. Usually this is because there is some event that happens only once in the protocol, and the adversary has only one chance to succeed at the attack. For example, one party generates a commitment to a string, and the adversary breaks the protocol only if it can exactly guess the contents of that string before it is revealed. The length of the string needs to be governed by the protocol's statistical security parameter. When you examine the adversary's advantage and see a term of the form $c/2^\lambda$ for a constant $c$ (independent of the adversary's computational effort), then $\lambda$ is a statistical security parameter.

A concrete example containing both kinds of security parameters is cut-and-choose protocols for garbled circuits (I very roughly sketch the protocol of Lindell here).

• Alice is supposed to generate $\lambda$ independent garblings of a circuit. A garbled circuit can either be generated correctly or incorrectly. Given the "seed" which produced the garbled circuit, it is easy to check whether the circuit was generated correctly or not.
• Bob tosses a fair coin for each of the $\lambda$ circuits. If the coin is heads, he challenges Alice to prove that the circuit was generated correctly (by revealing its "seed"). If the coin is tails, the circuit is used later on for usual garbled circuit stuff.

Because of some clever mechanisms in the rest of the protocol, Alice can succeed in cheating only by making all "checked" circuits correct and all "unchecked" circuits incorrect. In other words, she can succeed only if she exactly predicts all $\lambda$ of Bob's coin tosses before they happen (with probability $1/2^\lambda$). Hence $\lambda$ is a statistical security parameter of the protocol.

To answer your question: just because a protocol contains a statistical security parameter, it doesn't mean the entire protocol is information-theoretically secure. If it contains a computational security parameter at all, then the entire protocol achieves computational security, if can be proven so.

Implications of differentiating computational vs statistical security parameters: In this example and others, the statistical security parameter can be much smaller (leading to a concretely more efficient protocol). In practice it is typical to set the statistical security parameter to be 40, which bounds all "bad one-shot events" to probability $1/2^{40}$. In the cut-and-choose example, this means Alice sends only 40 garbled circuits instead of, say, 128. Meanwhile, the protocol still uses PRFs and other things, which need computational security parameter 128.