Computational security

Relevant readings: Katz and Lindell 3.1–3.4

Defining the impossible

Back in Lecture 2, we introduced the notion of perfect secrecy. Perfect secrecy is what we also call information-theoretic security, where absolutely no information about the plaintext is leaked even if the attacker has unlimited computational power. But for practical purposes, perfect secrecy is a bit “too strong” because it would consider insecure an encryption scheme for which a successful attack would take trillions of years. The average person would not be able to witness such an attack in their lifetime for them to consider the scheme as insecure.

Rather, we would still consider an encryption scheme secure even if there is a tiny probability that it leaked information to an attacker with bounded computational power (i.e., within a “reasonable” amount of time, memory, budget, etc.). This approach of taking into account the computational limitations of the attacker and allowing a tiny probability that security is broken is called computational security.

The concrete approach

Computational security introduces two necessary relaxations:

1. Security is only guaranteed against efficient adversaries that run for some feasible amount of time.

2. Adversaries can potentially succeed (i.e., security can potentially fail) with some very small probability.

It is useful to quantify a limit on each of them as follows:

• Let \(t\) denote the upper bound on the amount of time¹ that an attacker will consume,

• Let \(\varepsilon\) denote the upper bound on the probability of success of an attack.

This concrete approach is important in practice, but it may turn out to be difficult to prove (let alone provide) such precise statements. Claiming, for example, that no attacker running for \(5\) years can break a given scheme with probability better than \(\varepsilon\) begs many questions, one of which is: does it take into consideration any future advances in technology? Keep in mind that hardware improves over time — remember Moore’s Law?

Understanding security levels

Another way at looking at the effort required for an attacker is through the amount of energy required to do so. A paper by (Lenstra, Kleinjung, and Thomé 2013) attempts to offer an intutive interpretation of “\(n\)-bit security” by comparing the energy required to break an \(n\)-bit encryption scheme with the energy required to boil an equivalent amount of water, as detailed in Table [tbl:security_levels]. For example, the energy required in breaking a \(65\)-bit encryption scheme would be enough to bring an Olympic-size swimming pool to a boil, thus a \(65\)-bit key offers “pool security.”

(Rosulek 2021) shows another interpretation of different levels of security in terms of monetary value, specifically, how much it would cost on Amazon EC2 for an attacker to carry out a brute force attack for various key lengths.

The asymptotic approach

In the same way that we prefer to use asymptotic notation to describe the running time of algorithms rather than actually counting the number of operations, it is more convenient to use an asymptotic approach to security. Here, we use an integer \(n\) called the security parameter, which is similar to the notion of an algorithm’s input size. Instead of having fixed values for the running time of the adversary and its success probability, we define them as functions of the security parameter, so:

1. “efficient adversaries” refer to randomized algorithms running in polynomial time, meaning it runs in \(O(p(n))\) time, where \(p(n)\) is some polynomial in \(n\), and

2. “small probabilities of success” are success probabilities smaller than any inverse polynomial in \(n\), thus we call these probabilities negligible.

An asymptotic definition of security will look something like this:

Efficient algorithms

We have seen in Lecture 5 that an algorithm is efficient if it runs in polynomial time, and that polynomial-time algorithms are closed under composition which makes them particularly nice to work with.

By default, we allow all algorithms to be randomized. We consider randomized algorithms by default for two reasons:

1. Randomness is essential to cryptography, since we need it to choose random keys, etc., so honest parties must be probabilistic. Given this, it is natural to allow adversaries to be probabilistic as well.

2. Randomization is practical and gives attackers additional power.

Negligible functions

A negligible function is one that is asymptotically smaller than any inverse polynomial function.

It’s nice working with negligible success probabilities since negligible functions follow these closure properties:

1. If \(\mu_1\) and \(\mu_2\) are negligible functions, then so is \(\mu_3 (n) = \mu_1 (n) + \mu_2 (n)\).

2. If \(\mu\) is negligible and \(p\) is any polynomial, then so is \(\mu_4 (n) = p(n) \cdot \mu (n)\).

   Conversely, if \(f\) is not negligible, then neither is \(g(x) = f(x)/p(x)\) for any polynomial \(p\).

Computationally secure encryption

EAV-security

We present the most basic notion of computational security in the context of private-key encryption: security against a ciphertext-only attack where the adversary observes only a single ciphertext.

If you recall from Lecture 1, a security definition consists of a threat model (a specification of the power of the adversary) and a security goal (a definition of what is considered a “break” of the scheme). Here we assume that our threat model consists of an eavesdropping adversary (running in polynomial time) who can observe the encryption of a single message. Again, we don’t assume about the strategy that the adversary will use.

As for our security goal, we just recall that the idea behind the definition is that the adversary should be unable to learn any partial information about the plaintext from the ciphertext. This is formalized as semantic security. But semantic security is complicated to work with, so we’ll just settle with a simpler but equivalent definition called indistinguishability.

Indistinguishability

The definition of indistinguishability has an associated game called the IND-EAV game, defined for a scheme \(\Pi = (\textsf{Gen}, \textsf{Enc}, \textsf{Dec})\), a security parameter \(n\), and a PPT adversary \(\mathcal{A}\), that works like this:

1. The adversary \(\mathcal{A}\) is given input \(\texttt{1}^n\) and outputs a pair of messages \(m_{\texttt{0}}\) and \(m_{\texttt{1}}\) with \(\Len{m_{\texttt{0}}} = \Len{m_{\texttt{1}}}\).

2. A key \(k\) is generated by running \(\Gen{\texttt{1}^n}\) and a uniform bit \(b \in \Set{\texttt{0}, \texttt{1}}\) is chosen. The ciphertext \(c \mathrel{\hspace{1pt}\leftarrow\hspace{1pt}}\Enc{k}{m_b}\) is computed and given to \(\mathcal{A}\). We refer to \(c\) as the challenge ciphertext.

3. \(\mathcal{A}\) outputs a bit \(b^\prime\).

4. \(\mathcal{A}\) wins if \(b^\prime = b\).

The definition of indistinguishability states that an encryption scheme is secure if no PPT adversary \(\mathcal{A}\) wins the IND-EAV game by guessing which message was encrypted with probability significantly better than random guessing, which is correct with probability \(1/2\):

Chosen-plaintext attacks

A chosen-plaintext attack assumes that the adversary can get a hold of one or more plaintext-ciphertext pairs generated for plaintexts of their choice.

Suppose Alice and Bob share a key \(k\), and Eve can influence them to encrypt messages \(m_1, m_2\) using \(k\) and send the resulting ciphertexts over a channel that Eve can observe. Later, Eve observes a ciphertext corresponding to some unknown message \(m\) encrypted with the same key \(k\); additionally we assume that Eve knows that there are two possibilities for \(m\): either \(m_1\) or \(m_2\). Security against chosen-plaintext attacks means that even in this case Eve cannot tell which of those two messages was encrypted with probability significantly better than random guessing.

CPA-security

In a chosen-plaintext attack, the adversary \(\mathcal{A}\) has access to an encryption oracle \(\Enc{k}{\cdot}\), a “black box” or an “API” that encrypts messages of \(\mathcal{A}\)’s choice using a key \(k\) that is unknown to \(\mathcal{A}\). When \(\mathcal{A}\) queries the oracle by providing it with a message \(m\) as input, the oracle returns a ciphertext \(c \mathrel{\hspace{1pt}\leftarrow\hspace{1pt}}\Enc{k}{m}\) in response.

Now we consider the IND-CPA game defined for a scheme \(\Pi = (\textsf{Gen}, \textsf{Enc}, \textsf{Dec})\), a security parameter \(n\), and a PPT adversary \(\mathcal{A}\):

1. A key \(k\) is generated by running \(\Gen{\texttt{1}^n}\).

2. The adversary \(\mathcal{A}\) is given input \(\texttt{1}^n\) and oracle access to \(\Enc{k}{\cdot}\), and outputs a pair of message \(m_{\texttt{0}}\) and \(m_{\texttt{1}}\) of the same length.

3. A uniform bit \(b \in \Set{\texttt{0}, \texttt{1}}\) is chosen, and then a ciphertext \(c \mathrel{\hspace{1pt}\leftarrow\hspace{1pt}}\Enc{k}{m_b}\) is computed and given to \(\mathcal{A}\).

4. \(\mathcal{A}\) continues to have oracle access to \(\Enc{k}{\cdot}\) and outputs a bit \(b^\prime\).

5. \(\mathcal{A}\) wins if \(b^\prime = b\).

Nowadays, CPA-security is the bare minimum notion of security an encryption scheme should satisfy.

References

• Lenstra, Arjen K., Thorsten Kleinjung, and Emmanuel Thomé. 2013. "Universal Security: From Bits and Mips to Pools, Lakes --- and Beyond." Cryptology ePrint Archive, Report 2013/635.

• Rosulek, Mike. 2021. The Joy of Cryptography. https://joyofcryptography.com/.