Liam Peet-Paré
← Writing

Essay · 2015

A Gentle Introduction to Mathematical Cryptography, Part 2: Security

Note that this is the second post in a three-part series on cryptography. The first post giving an introduction is here, and the third post, on NTRU, is here.

What does it mean for a cryptosystem to be secure?

At first glance it may appear that the notion of security for an encryption scheme is clear - if an adversary cannot break the encryption scheme then it is secure. This, however, merely begs the question of what it means to break an encryption scheme. There are several answers one might give to this question, and it immediately becomes clear that a definition of security is not so obvious after all. What, then, does it mean for a cryptosystem to be secure? There are many possible answers to this question, and we will evaluate some of them now. The following discussion is indebted to [6].

  1. If no adversary can find the secret key when given a ciphertext the cryptosystem is secure. Certainly if an adversary can find the secret key the cryptosytem will be completely broken, but what if an adversary can recover the plaintext of every single ciphertext sent, but cannot actually recover the private key? Clearly the cryptosystem would not be secure. As a contrived example, consider some scheme where a message is permuted many times, but eventually returns to the original message before being sent as ciphertext. If the private key inverts this series of permutations to recover the plaintext it may be very difficult for an adversary to recover the private key, but the plaintext and ciphertext are identical, so an eavesdropper would always know the plaintext of any given ciphertext. Clearly this cryptosystem cannot be secure.
  2. If no adversary can recover the plaintext that corresponds to the ciphertext, the cryptosystem is secure. This answer is an improvement over the first answer given, but what if an adversary can recover 90% of a plaintext, or even 99% of a plaintext? If this is the case, then the crytposystem is also clearly not secure.
  3. If no adversary can determine any meaningful information about the plaintext from the ciphertext, the cryptosystem is secure. This answer is yet another improvement, but it is not clear what is meant by "meaningful information." We will need to refine this definition slightly to achieve the precision we are looking for.
  4. If no adversary can compute any function of the plaintext from the ciphertext, a cryptosystem is secure. This makes our previous answer more precise, and provides very strong criteria for security. We will still have to reformulate in a way that allows us to evaluate the security of actual cryptosystems, but this is in fact what is considered to be the "right" definition of security in modern cryptography.

The fourth answer provided above moves us closer to a definition of security, but we still need to formalize it mathematically. Additionally, we need to consider what we assume the power of an adversary is (e.g. computing power), and also the type of attack an adversary will conduct against an encryption scheme.

We will first consider the power of an adversary. We will want to ensure security against any efficient adversary (i.e. any adversary running in polynomial time). We define an efficient adversary as any adversary that is capable of performing efficient computations. We refer to [6] for their definition of an efficient computation.

"We have defined efficient computation as that which can be carried out in $\textit{probabilistic polynomial time}$ (sometimes abbreviated $\texttt{PPT}$). An algorithm $A$ is said to run in polynomial time if there exists a polynomial $p(\cdot)$ such that, for every input $x \in \{0,1\}^*$, the computation of $A(x)$ terminates within at most $p(\|x\|)$ steps (here, $\|x\|$ denotes the length of the string $x$). A probabilistic algorithm is one that has the capability of "tossing coins"; this is a metaphorical way of saying that the algorithm has access to a source of randomness that yields unbiased random bits that are each independently equal to $1$ with probability $\frac{1}{2}$ and 0 with probability $\frac{1}{2}$."

It is important to define the power of an adversary because a cryptosystem's security will depend on the capability of any adversary. For example, security against an adversary running in exponential time is completely different than security against an adversary running in polynomial time. Note that while we choose to consider an efficient adversary, a different level of power could be chosen instead. We will not elaborate further on the power of an adversary, but if the reader desires, a detailed treatment can be found in [6].

Types of attack

We now have to consider the $\textit{type}$ of attack an adversary can mount. By this we do not mean the strategy that an adversary will use, as we do not want to make any assumptions about attack strategies. Making assumptions regarding the strategy that an adversary will employ is dangerous because it is always possible that an adversary could discover a novel way of attacking a cryptosystem that the cryptosystem's creators did not foresee. If we assumed that only certain strategies would be employed in attacking a cryptosystem, we could never show that an encryption scheme was safe against an unaccounted for strategy. Instead, when we refer to the type of attack an adversary can mount we mean what kind of information does an adversary have access to in order to mount their attack. In other words, we are specifying an attack scenario or model, rather than an attack strategy. We now list the main types of attack scenarios, referring to [6] for our discussion:

  • $\texttt{Ciphertext-only attack:}$ This is the most basic of the attack scenarios. In a ciphertext-only attack an adversary just observes a ciphertext and attempts to determine the plaintext that was encrypted.
  • $\texttt{Known-plaintext attack:}$ In this scenario an adversary knows one or more pairs of plaintexts/ciphertexts all encrypted using the same key. The adversary then attempts to determine the plaintext corresponding to some other ciphertext for which it does not know the corresponding plaintext.
  • $\texttt{Chosen-plaintext attack:}$ Here, an adversary has the ability to obtain the encryption of any plaintext that it chooses. The goal of the adversary is to determine the plaintext that corresponds to some other ciphertext. Note that in a public-key encryption scheme an adversary always has the ability to mount a chosen-plaintext attack, as it has access to the public encryption key.
  • $\texttt{Chosen-ciphertext attack:}$ This is the strongest attack scenario. In a chosen-ciphertext-attack, an adversary has access to a decryption oracle by which it can obtain the decryption of any ciphertext of its choice. Here, an adversary attempts to determine the plaintext corresponding to some other ciphertext for which it cannot obtain the decryption.

It is important to note that these types of attack increase in their severity, and therefore form a hierarchy of security. Encryption schemes that are secure against chosen-ciphertext attacks will be secure against all other types of attacks, but the converse is not true. For example, an encryption scheme could be secure against a chosen-plaintext attack (and hence secure against the first two attack models as well), but be trivially broken by a chosen-ciphertext attack. While desirable, it is not always necessary to attain the highest degree of security. It may be appropriate to consider different attack models in different situations. For example, as mentioned above, a public-key encryption scheme ought to strive for at least security against chosen-plaintext attacks as an adversary does in fact have the ability to to obtain encryptions of plaintexts of its choice. A secret key scheme on the other hand, may not necessarily need to achieve chosen-plaintext security.

Our preceding discussion finally enables us to state a general definition of security for a cryptographic scheme.

Definition (secure cryptosystem) A cryptographic scheme for a given task is secure if no efficient adversary can compute any function of the plaintext given a ciphertext, under a certain attack model.

This definition of security is a good start, but it is still too general to really make it all that useful. We will still have to elaborate further in order to come up with a truly testable notion of security.

CPA and CCA security

As we mentioned in our discussion of the types of attack that an adversary can mount, a public key encryption scheme should be secure against at least chosen-plaintext attacks, as an adversary will certainly have the ability to encrypt messages using the public key. Because of this, security against chosen-plaintext attacks is in some sense the minimum required security for a public-key encryption scheme. Security against chosen-plaintext attacks is known as $\textit{semantic security under CPA}$ or simply as $\textit{CPA security}$, while security against chosen-ciphertext attacks is known as $\textit{CCA security}$. In this section we will explain how one can test a cryptosystem to determine whether or not it is CPA secure or CCA secure.

We will begin with a discussion of semantic security or CPA security. Semantic security more or less refers to the definition of an encryption scheme's security that we presented earlier. As we saw, however, this definition provided no straightforward way to prove the security of cryptosystems used in practice. The notion of semantic security was first proposed in 1982 by Goldwasser and Micali [3], but the pair later showed that this notion of security is equivalent to another definition of security known as $\textit{ciphertext indistinguishability under chosen-plaintext attack}$ or IND-CPA. This latter notion of security finally provides us with a testable definition of security, as we will explain now.

The IND-CPA experiment is designed to determine whether or not an adversary can distinguish between ciphertexts given some plaintexts. In the experiment, an adversary is given the public key $\texttt{pk}$ and oracle access (this means that the adversary can ask for the encryption of plaintexts and will receive ciphertexts back) to the encryption algorithm $\texttt{Enc}_{pk}$. The adversary then chooses two plaintexts $m_0$ and $m_1$, and one of the two plaintexts is randomly chosen, encrypted, and the ciphertext is sent back to the adversary. If the adversary can determine which plaintext was encrypted, they win the experiment. At first glance this may sound rather odd, so we will summarize the IND-CPA experiment below.

Let $\Pi=(\texttt{keyGen}, \texttt{Enc}_{pk}$, $\texttt{Dec}_{sk})$ be a public key cryptosystem and $\mathcal{A}$ be an efficient adversary. The CPA indistinguishability experiment is as follows:

The CPA indsitinguishability experiment $\texttt{PubK}^{\texttt{cpa}}_{\mathcal{A}, \Pi}(\lambda)$:

  1. $\texttt{keyGen}(1^\lambda)$ is run by the challenger to obtain keys $\texttt{(pk, sk)}$.
  2. Adversary $\mathcal{A}$ is given $\texttt{pk}$ as well as oracle access to $\texttt{Enc}_{pk}(\cdot)$. The adversary outputs a pair of messages $m_0, m_1 \in \mathcal{P}$ such that $m_0 \neq m_1$.
  3. A random bit $b \in \{0,1\}$ is chosen, and the ciphertext $c \leftarrow \texttt{Enc}_{pk}(m_b)$ is computed and given to $\mathcal{A}$. The ciphertext $c$ is called the $\texttt{challenge ciphertext}$. At this point $\mathcal{A}$ still has access to $\texttt{Enc}_{pk}(\cdot)$.
  4. $\mathcal{A}$ outputs a bit $b' \in \{0,1\}$ which is given to the challenger. Note that $\mathcal{A}$ can compute any function that it likes on $c$.
  5. The output of the experiment is defined to be $1$ if $b'=b$, and $0$ otherwise.

Definition (IND-CPA Security) A public-key encryption scheme $\Pi=(\texttt{keyGen}, \texttt{Enc}_{pk}$, $\texttt{Dec}_{sk})$ has indistinguishable encryptions under chosen-plaintext attacks (or is CPA secure), if for all probabilistic, polynomial time adversaries $\mathcal{A}$, there exists a negligible function $\texttt{negl}$ such that: $$Pr[\texttt{PubK}^{\texttt{cpa}}_{\mathcal{A}, \Pi}(\lambda)=1] \le \frac{1}{2} + \texttt{negl}(\lambda).$$

The CPA indistinguishability experiment given above is just a more exact formulation of the preceding discussion, but Definition 3.2 may not be so obvious at first glance. This definition however, finally provides us with a testable notion of security. It says that a public-key cryptosystem $\Pi=(\texttt{keyGen}, \texttt{Enc}_{pk}$, $\texttt{Dec}_{sk})$ is CPA secure if an adversary's probability of success under the CPA indistinguishability experiment is less than or equal to $\frac{1}{2}$ plus some negligible function of the security parameter $\lambda$. A negligible function, $\texttt{negl}$, refers to a function with the property that $\texttt{negl}(\lambda) < \frac{1}{poly(\lambda)}$ for all positive $poly(\lambda)$, where $poly(\lambda)$ is a polynomial in $\lambda$.

In other words, a cryptosystem is CPA secure if any adversary cannot win the CPA indistinguishability experiment with probability significantly more than one-half -- which would be the probability of success if the adversary were to randomly choose the bit $b'$. CPA security is considered essential for any public-key cryptosystem, but surprisingly, the original formulation of the most famous public-key cryptosystem, RSA, is not CPA secure. This is because what is now known as textbook RSA is a deterministic rather than probabilistic cryptosystem. We will not go into detail here, but it is a nice, and in fact simple, exercise for the reader to verify that textbook RSA is not CPA secure.

We now have a working definition to determine whether or not an encryption scheme is secure against chosen-plaintext attacks, but this tells us nothing about whether or not an encryption scheme is secure against chosen-ciphertext attacks. Allowing an adversary to have access to a decryption oracle could potentially enable it to break encryption schemes that are CPA secure, so we will need a new test for CCA security. It may seem unrealistic to allow an adversary access to a decryption oracle (i.e. allow $\mathcal{A}$ to ask for decryptions of ciphertexts of its choice), but there are many scenarios where this is a genuine risk. The reader can refer to [6] for examples of hypothetical scenarios where CCA security would be desired.

The definition of CCA security is analogous to that of CPA security, except it has the additional feature that the adversary now has access to a decryption oracle. We explain the CCA indistinguishability test and define CCA security now.

The CCA indsitinguishability experiment $\texttt{PubK}^{\texttt{cca}}_{\mathcal{A}, \Pi}(\lambda)$:

  1. $\texttt{keyGen}(1^\lambda)$ is run by the challenger to obtain keys $\texttt{(pk, sk)}$.
  2. Adversary $\mathcal{A}$ is given $\texttt{pk}$, oracle access to $\texttt{Enc}_{pk}(\cdot)$, and access to a decryption oracle $\texttt{Dec}_{sk}(\cdot)$. The adversary outputs a pair of messages $m_0, m_1 \in \mathcal{P}$ such that $m_0 \neq m_1$.
  3. A random bit $b \in \{0,1\}$ is chosen, and the ciphertext $c \leftarrow \texttt{Enc}_{pk}(m_b)$ is computed and given to $\mathcal{A}$. The ciphertext $c$ is called the \texttt{challenge ciphertext}.
  4. $\mathcal{A}$ still has access to $\texttt{Enc}_{pk}(\cdot)$ and the decryption oracle $\texttt{Dec}_{sk}(\cdot)$, with the restriction that $\mathcal{A}$ cannot request the decryption of $c$ itself. Finally, $\mathcal{A}$ outputs a bit $b' \in \{0,1\}$ which is given to the challenger. Note that $\mathcal{A}$ can compute any function that it likes on $c$.
  5. The output of the experiment is defined to be $1$ if $b'=b$, and $0$ otherwise.

Definition (IND-CCA Security) A public-key encryption scheme $\Pi=(\texttt{keyGen}, \texttt{Enc}_{pk}$, $\texttt{Dec}_{sk})$ has indistinguishable encryptions under chosen-ciphertext attacks (or is CCA secure), if for all probabilistic, polynomial time adversaries $\mathcal{A}$, there exists a negligible function $\texttt{negl}$ such that: $$Pr[\texttt{PubK}^{\texttt{cca}}_{\mathcal{A}, \Pi}(\lambda)=1] \le \frac{1}{2} + \texttt{negl}(\lambda).$$

There are actually two versions of the CCA indistinguishability experiment. The first is known as CCA1 or a lunchtime attack while the second is known as CCA2 or an adaptive chosen-ciphertext attack. In a CCA1 attack, the adversary only has access to the decryption oracle $\texttt{Dec}_{sk}(\cdot)$ before it receives the challenge ciphertext, while a CCA2 attack allows the adversary to have access to the decryption oracle after receiving the challenge ciphertext. The CCA indistinguishability experiment we have provided is actually meant for CCA2 attacks, as the adversary $\mathcal{A}$ continues to have access to the decryption oracle even after receiving the challenge ciphertext $c$. Note that it is possible for an encryption scheme to be CCA1 secure, but not CCA2 secure. CCA2 security is a very high security requirement, and creators of encryption schemes will ideally strive to achieve this level of security, although it is very difficult to design an efficient encryption scheme that actually attains security against chosen-ciphertext attacks.

The preceding discussion on CPA and CCA security draws on the excellent expository treatment by [6], and the reader should refer to this work if more detail is desired.

The Role of Assumptions

We now have working definitions that allow us to test a cryptosystem's security under different types of attacks, but we are still missing a key ingredient for furnishing a proof of cryptographic security. The security of most encryption schemes, and in particular public-key schemes, relies on some kind of operation that would allow an adversary to break the scheme being difficult to perform. For example, as we have seen with RSA, it is easy to multiply to large prime numbers together but computationally very difficult to factor a large integer. The difficulty, however, is that integer factorization (in the worst case) is believed to be a very hard problem, but it has not been proven that no classical polynomial time algorithm exists for integer factorization. This is not to say that there are not good reasons for believing that integer factorization is a very hard problem, but the reality is that it is still assumed to be hard, rather than proven to be hard. An interesting side note here is that the security of RSA does not actually rely on the assumed hardness of integer factorization, but instead on the related RSA Problem, which has not been shown to be equivalent to integer factorization [2].

RSA is not unique in its reliance on an unproven assumption, and in fact, most cryptographic constructions rely on questions in computational complexity theory that are as yet unproven [6]. As a result, the security of encryption schemes often hinges on an assumption. At first blush, the central role of assumptions may make it appear that any hope of rigorous proofs of security within cryptography must be abandoned, but this is not the case. There is often good reason to believe that assumptions regarding computational complexity are true, even if we cannot prove them; so although we may not be able to provide unconditional proofs of security for many encryption schemes, a rigorous proof that can demonstrate that an encryption scheme is secure if a certain assumption is true can still be a very satisfying proof.

Because our proofs of an encryption scheme's security will often rely on an assumption, it becomes very important to precisely and clearly state this assumption. If we are to have confidence in a security proof, we will need to know exactly what is being assumed. Proofs of security in cryptography therefore often use what can be called a reductionist approach [6]. The reductionist approach attempts to reduce the problem given by some assumption to the problem of breaking the cryptosystem. Again, we can consider RSA as an example. RSA attempts to reduce the known hard problem of integer factorization to the problem of breaking RSA. Hence, in an ideal scenario we could prove that breaking RSA is equivalent to integer factorization (or the RSA Problem) which would give us confidence in RSA's security, as we have good reason to believe that integer factorization is a very hard problem. This is the methodology that is used in general for modern cryptography: attempt to reduce a known and well studied hard mathematical problem to the problem of breaking a cryptosystem.

The Random Oracle Model

We have worked hard so far to determine how one can prove the security of a given cryptosystem, but we have not considered the question of whether or not practical encryption schemes can actually be proven secure using this methodology. The answer to this query is both yes and no. The definitions we have presented so far have been enormously successful in putting cryptography on a solid footing and ensuring that we can rigorously address the question of what it means for an encryption scheme to be secure. Thanks to this work, many provably secure cryptosystems now exist. There has, however, been quite a bit of difficulty developing provably secure efficient encryption schemes. In practice, efficiency is almost as important as security for cryptosystems, as there is a desire and expectation that transactions be carried out quickly and efficiently, regardless of whether or not the transaction needs to be encrypted. As a result, many people would prefer to have compromised security rather than use a secure, but inefficient scheme [6]. For example, textbook RSA is not even CPA secure, and no provably secure encryption scheme based on RSA with efficiency that is comparable to textbook RSA is currently known.

Thus far we have emphasized the importance of having provable security, but if major cryptosystems that are used in practice are not provably secure, what is the point of these rigorous notions of security? Furthermore, if we cannot prove the security of most of our efficient cryptosystems, how do we decide which encryption scheme is better to use? Attempts to address these questions have given rise to what is known as the random oracle model. The random oracle model can be seen as a compromise between a fully rigorous proof of security and no proof whatsoever. The idea of the random oracle model is to introduce an idealized model in which we can furnish a proof of security for an encryption scheme. Even if this idealized model does not hold true in reality, the hope is that if an encryption scheme is secure in the random oracle model it will still be secure in practice, and at least does not have any fundamental security flaws [6]. The random oracle model may seem slightly strange for those who have not encountered similar ideas in the past. Before we can explain the random oracle model, however, we will need to introduce the notion of hash functions.

The basic idea of a hash function is that it is a function that can take arbitrary length strings as input and compress these into shorter strings of a fixed length. Hash functions were originally used in data structures to reduce the lookup time for retrieving an element in the data structure [6]. Cryptographic hash functions have several properties that are required in order to make them useful. One of these properties is known as collision resistance. A collision for a function $H$ is a pair of distinct inputs $x, x'$ where $x \neq x'$ such that $H(x)=H(x')$, i.e., two inputs have the same image. A function is considered collision resistant if it is infeasible for any PPT algorithm to find a collision in $H$ [6]. Other useful properties for hash functions are second preimage resistance and preimage resistance, but we will not go into details here. Hash functions should also be quick to compute.

The idealized situation considered in the random oracle model assumes the existence of a public, randomly chosen function $H$. This function $H$ can be evaluated only by querying an oracle. In other words, if one has an input $x$ the oracle will return $H(x)$ when queried, but no one knows how this random function $H$ actually produces this output. The function $H$ is chosen uniformly at random, which is impossible to do in polynomial time. It is perhaps easiest to think of the random oracle as a black box that parties can query and will receive a response, but have no idea what the inner workings of this black box. As we cannot actually have this random oracle in practice, we instantiate the random function $H$ with a cryptographic has function. The proof technique for the random oracle model then comes down to proving security in a model where we assume the existence of this random oracle $H$ and then instantiating $H$ with a cryptographic hash function $\hat{H}$. That is, every time that a party would query the oracle for the value $H(x)$, the party instead computes $\hat{H}(x)$ on its own. The cryptographic has function $\hat{H}$ is in some sense providing a best approximation of the random oracle $H$ as possible. We will not provide further technical details here, as it will not be essential to the final blog post in our series, but the interested reader can find more information on the random oracle model in [6].

It is worth noting that while the random oracle model does not allow one to conclusively prove the security of a cryptosystem, "there have been no real-world attacks on any "natural" schemes proven secure in the random oracle model" [6]. It is also true, however, that it is possible to develop contrived examples of encryption schemes which are provably secure in the random oracle model, but are insecure no matter how the random oracle is instantiated. In these contrived schemes, not only are some instantiations of the random oracle by a cryptographic hash function insecure, but rather all instantiations are insecure. Due to the lack of theoretical justification for the security of encryption schemes proved in this manner, the random oracle remains a controversial topic among cryptographers [6].

Part 3 of the series: NTRU
References

  1. Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen. Post Quantum Cryptography. 2009: Springer-Verlag, Berlin.
  2. Dan Boneh and Ramarathnam Venkatesan. (1998). Breaking RSA may not be equivalent to factoring. Advances in Cryptology - EUROCRYPT '98. Lecture Notes in Computer Science, Volume 1403, 59-71. Springer, Berlin.
  3. Shafi Goldwasser and Silvio Micali. (1982). Probabilistic Encryption & How to Play Mental Poker Keeping Secret all Partial Information. STOC '82 Proceedings of the fourteenth annual ACM symposium on Theory of computing (pp. 365-377). ACM, New York.
  4. Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. (1998). NTRU: A ring based public key cryptosystem. Lecture Notes in Computer Science, Volume 1423, 267-288. Springer, Berlin.
  5. Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. An Introduction to Mathematical Cryptography. 2008: Springer, N.Y.
  6. Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography. 2007: CRC Press, N.Y.
  7. Vadim Lyubashevsky, Chris Peikert, and Oded Regev. (2010). On Ideal Lattices and Learning with Errors over Rings. In H. Gilbert (ed.), Advances in Cryptology - EUROCRYPT 2010 (pp. 1-23). Springer, Berlin.
  8. Phong Q. Nguyen and David Pointcheval. (2002). Analysis and Improvements of NTRU Encyption Paddings. In M. Yung (ed.), Advances in Cryptology - Proceedings of CRYPTO 2002 (pp. 210-225). Springer-Verlag, Berlin.
  9. Chis Peikert. A Decade of Lattice Cryptography 2016: Now Publishers.
  10. Damien Stehle and Ron Steinfeld. (2011). Making NTRU as Secure as Worst-Case Problems over Ideal Lattices. In K.G. Patterson (ed.), Advances in Cryptology - EUROCRYPT 2011 (pp. 27-47). Springer, Berlin.
  11. Ron Steinfeld et al. (2012). NTRUCCA: How to Strengthen NTRUEncrypt to Chosen-Ciphertext Security in the Standard Model. Lecture Notes in Computer Science, Volume 7293, 353-371. Springer, Berlin.
  12. Douglas Stinson. Cryptography Theory and Practice. 2002: CRC Press, Boca Raton.