Join Log in
Score:2
HelloWorld123 avatar Crypto

Statistical security parameter -> information theoretically secure

ua flag
HelloWorld123

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?

272
2 + 0
Score:6
Daniel avatar Crypto
ru flag
Daniel

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.

0 + 2
HelloWorld123 avatar
ua flag
HelloWorld123
Thank you, that answer was extremely helpful! I would assume then that the following protocol is information-theoretically secure because it states in Appendix A that "the following quantity is negligible (in λ)", right? http://web.eecs.umich.edu/~mosharaf/Readings/SecureML.pdf
0
Reply
Daniel avatar
ru flag
Daniel
@HelloWorld123 Yes, SecureML is computationally secure because it makes use of Oblivious Transfer
0
Reply
Score:3
avatar Crypto
us flag
Mikero

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.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.