Modern Cryptography: Applied Mathematics for Encryption and Informanion Security (2016)
PART IV. Applications
Chapter 19. The Future of Cryptography
In this chapter we will cover the following:
Cryptography and the cloud
Homomorphic cryptography
Quantum cryptography
In the preceding 18 chapters, you have learned about the development of cryptography from ancient times (Scytale, Caesar, Atbash, and so on) through modern times (AES, Serpent, RSA, ECC, and so on). But what does the future hold for cryptography? It is always difficult to predict the future trends in any scientific or technological discipline. However, several emerging issues today can offer a glimpse at what is likely to be occurring in the next few decades. In this chapter we will explore these issues.
Cryptography and the Cloud
It is impossible today to avoid discussions of the cloud. Although most people misunderstand what the cloud is, that does not impede conversations about it. Clearly, a great deal of data is being stored in the cloud, and that means that data must be secured. In some cases, the traditional encryption methods that you have read about in previous chapters are adequate for security, but in other cases they may not be. Here we will explore cryptographic solutions that are uniquely suited for the cloud.
What Is the Cloud?
Before we can meaningfully explore cryptographic solutions in the cloud, you need to have a firm understanding of what “the cloud” is. To begin with, there really is no such thing as “the cloud”; there are, in fact, many clouds. A brief discussion of the evolution of data storage that has culminated in cloud storage might help explain this.
When most of us think of data storage, a simple server comes immediately to mind. And for many years, this was the primary storage modality (and still is for very small organizations). However, this modality eventually became impractical for larger data storage needs: the first problem was the need for more storage capacity than a single server could provide, and second was the need to maintain data access, even if a server was offline. So two different, but quite similar and overlapping, approaches were developed.
The first approach was the storage area network (SAN), which connects multiple servers and network storage devices via high-speed connections such as fiber-optics. In a SAN, there is redundancy—so, for example, three servers might store data, but each server has a duplicate server on the SAN. In this way, should a server go down, data access is not interrupted. The SAN is presented to the primary network as a single, monolithic storage device—but, in fact, it is an entirely separate network of servers, as shown in Figure 19-1.
FIGURE 19-1 The SAN
A SAN provides a very resilient, high capacity storage solution. The failure of one or more servers does not render the data inaccessible; in fact, such a failure would not even be noticed by the end users.
Closely related to the SAN is the cluster, a grouping of servers that includes redundant copies of other servers that can be accessed either locally or over the Internet.
Both the SAN and the cluster solutions provide a high degree of resiliency, along with easily expandable storage capacity. A weakness with both solutions, however, can be seen if a problem occurs at the location where the SAN or cluster is stored—something as simple as interrupted connectivity to that location or as disastrous as a fire, earthquake, hurricane, or other natural disaster can render the network inoperable.
This brings us to cloud storage, which spreads the concepts of clustering and SAN over a diverse geographic area. If, for example, one cluster (or SAN) exists in Paris and a duplicate cluster (or SAN) is located in London, and both appear as a single storage area to end users, this is a cloud. You can see this in Figure 19-2.
FIGURE 19-2 Basic cloud
The cloud concept is actually rather simple. By having data replicated across diverse geographical areas, the only disaster that would wipe out all the data would be of such an enormous magnitude as to make accessing data an irrelevant issue. Essentially, as long as modern civilization is intact, the data will be accessible in the cloud.
In addition to there being numerous clouds, there are different types of clouds. There are actually three types of clouds: public, private, and community.
Public clouds are defined by the National Institute of Standards and Technology (NIST) as clouds that offer their infrastructure or services to either the general public or a large industry group.
Private clouds are used specifically by a single organization without offering the services to an outside party. Hybrid clouds combine the elements of a private and public cloud, but these are essentially private clouds that have some limited public access.
Community clouds are a midway point between private and public. These are systems wherein several organizations share a cloud for specific community needs. For example, several computer companies might join to create a cloud devoted to common security issues.
Regardless of the type of cloud, the structure is the same: geographically dispersed, replicated data. And the issues of securing that data are the same.
Cryptography Options for the Cloud
You might think that cryptography in the cloud is no different from encrypting any file or hard drive, but that would be a mistake. Certainly you can use traditional algorithms such as Blowfish or AES to encrypt files or folders that are stored in the cloud. The issue arises when cloud customers want to have data that is encrypted in such a way that the cloud vendor cannot access it.
One of the options for cryptography in the cloud is homomorphic cryptography, which we will explore later in this chapter. For now, just keep in mind that homomorphic encryption is important to cloud computing because it allows the cloud vendor to perform some limited mathematical operations on the cipher text without first decrypting it or even having the key.
Proof of storage (PoS) is another option for the cloud. Proof of storage is a mechanism whereby the user can get proof that the vendor has not tampered with the data. There are a number of ways of doing this, many of which involve the use of hashing algorithms (see Chapter 9). However, proof of storage has evolved beyond simply maintaining a hash of your data to become an interactive protocol that allows a client to verify that the server possesses the original data without retrieving it.
Other related concepts include provable data possession (PDP) or proof of retrievability (POR). With both terms, the idea is the same: The data owner does not have a copy of all the data in the cloud; however, the owner wants to make sure their data is still available in the cloud. One simple solution is to sign data digitally and to check the signature when needed.
According to the Microsoft Research web site,
Using a proof of storage (also known as a proof of data possession or a proof of retrievability) a client can verify whether the cloud operator has tampered with its data. In particular, this can be done without the client storing a local copy of the data and without it having to retrieve any of the data. In fact, the work for the client is negligible no matter how large the data is.1
Of course, there is a simpler option. Each customer keeps its own cryptographic keys in its own network and is responsible for key management. The problem with this approach, however, is that it leads to a wide range of different levels of security within the same cloud, because customers may be adept or not so adept at key management. Invariably, some end user may lose his or her key and expect the cloud vendor to be able to recover it. But if each customer is responsible for its own key management, there is nothing the vendor can do. Also, the vendor is unable to perform any operations with the encrypted data (see the next section, “Homomorphic Cryptography”).
Homomorphic Cryptography
Homomorphic encryption is a fascinating branch of cryptography that enables someone to carry out computations on cipher text without first decrypting the message. In other words, you can perform math on the encrypted data without actually decrypting the data. It must be stressed, however, that the entity performing the operation on the encrypted data has no idea what the actual data is. The entity cannot see the plain text, since it doesn’t have access to the encryption key. This is particularly interesting in cloud environments because it allows the cloud vendor to perform some operations on the encrypted data without having access to the encryption key.
In Wired magazine, Andy Greenberg described homomorphic encryption, as well as its uses, as follows:
A homomorphic encryption scheme is a crypto system that allows computations to be performed on data without decrypting it. A homomorphically encrypted search engine, for instance, could take in encrypted search terms and compare them with an encrypted index of the web. Or a homomorphically encrypted financial database stored in the cloud would allow users to ask how much money an employee earned in the second quarter of 2013. But it would accept an encrypted employee name and output an encrypted answer, avoiding the privacy problems that usually plague online services that deal with such sensitive data.2
Craig Gentry described the first plausible homomorphic encryption process, which supported both addition and multiplication on cipher text, without first decrypting the cipher text. Several algorithms are either partially homomorphic (that is, they allow one operation to be done homomorphically) or fully homomorphic (they allow addition and multiplication).
Note
Craig Gentry is an American computer scientist who won a MacArthur Fellowship in 2014. He also invented the first plausible construction for a fully homomorphic encryption scheme. The MacArthur Fellowship, often referred to as the “Genius Grant,” is awarded each year to several individuals who show exceptionally creative work. The prize is currently $625,000 awarded over five years in quarterly installments. An anonymous group nominates potential MacArthur Fellows; there are no applications.
Although homomorphic encryption has uses beyond the cloud, it has been specifically lauded as a solution to cloud issues. In a 2011 MIT Technology Review article, author Erica Neone specifically described Gentry’s innovations as follows: “Craig Gentry is creating an encryption system that could solve the problem keeping many organizations from using cloud computing to analyze and mine data: it’s too much of a security risk to give a public cloud provider such as Amazon or Google access to unencrypted data.”3
Note
When the first papers on homomorphic encryption were published, it was an impractical, theoretical technology. However, in the past several years it has moved from the theoretical to the practical and applied. For example, as early as 2011, researchers at Microsoft developed a practical, applicable homomorphic approach.4 In 2011, Gentry and Shai Halevi published a methodology for implementing Gentry’s original homomorphic process.5
RSA
RSA in textbook format (that is, not modified) can be used homomorphically. Here’s an example. Assume that the public key is modulus m and exponent e. You encrypt any message by xe mod m. You can certainly perform some mathematical operations on the encrypted data by simply encrypting that data and applying the operation to the two encrypted texts. For example, let’s use E to represent the encryption operation of RSA: E(x1) * e(x2) = x1ex2e mod m, which is, in turn, equal to E(x1 * x2). Basically multiplying two cipher texts together is the same as multiplying two plain texts and then encrypting them. Not all ciphers lend themselves to this sort of operation, but RSA does. ElGamal can also be used in a homomorphic manner.
Goldwasser–Micali
Goldwasser–Micali is an asymmetric cipher developed by Shafi Goldwasser and Silvio Micali in 1982. It was the first probabilistic public key algorithm that is provably secure. This algorithm has not gained wide use because the cipher texts are far larger than the initial plain text—as much as several hundred times larger. However, this algorithm supports homomorphic properties.
Note
Shafi Goldwasser is an Israeli computer scientist born in New York City. She has held professorships at MIT and the Weizmann Institute of Science in Israel. Silvio Micali is a professor of computer science at MIT and has done extensive research in cryptography.
The Benaloh cipher is an extension of the Goldwasser–Micali cipher that was created by Josh Benaloh in 1994. It allows for longer segments of plain text to be encrypted at a single time. Since it is an extension of Goldwasser–Micali, Benoloh also has homomorphic properties.
Note
Josh Benaloh has a Ph.D. in computer science from Yale University and works for Microsoft.
Paillier
Perhaps the most widely known homomorphic system is the Paillier system. This probabilistic asymmetric algorithm was invented by Pascal Paillier in 1999. The math is a bit more complex than some of the other algorithms we have studied in this book.
Note
Pascal Paillier is a French mathematician who has published extensively on cryptography and has a number of patents in cryptography.
The entire algorithm is presented here, but if you do not fully understand it, it is enough that you have a good understanding of the general concepts:
1. The algorithm begins much like RSA, in that you select two large prime numbers p and q. The values p and q should have the property that the greatest common denominator (pq, (p–1)(q–1)) = 1.
2. Next you compute p * q. Usually this is denoted as n = pq.
3. You also need to compute the least common multiple of p–1 and q–1. This is often denoted as λ (lambda) so that:
λ = lcm(p–1,q–1)
Note this is also referred to as the Carmichael function. (Robert Carmichael was an American mathematician known for his research in what are now called the Carmichael numbers, a subset of Fermat pseudoprime numbers.)
4. Select a random integer g that is where g 
.
Note that a number is said to be an n-th residue modulo n2 if there exists any number g such that z = gn mod n2.
5. Ensure that n divides the order of g by checking the existence of the following modular multiplicative inverse. That equation is given here:
μ = (L(gλ mod n2))–1 mod n
The L in the above equation is itself an equation, shown here:
L(u) = (u –1)/n
The public key, used for encryption, is (n, g); the private key, used for decryption, is (λ, μ).
After the key is generated, you can encrypt with the following steps:
1. Let m be the plain-text message.
2. Select random r where r 
.
3. The cipher text c is computed with the following formula: c = gm · rn mod n2.
Decryption is accomplished via this formula:
1. Let c be the cipher text you wish to decrypt.
2. Compute the plain-text message as m = L (cλ mod n2) · μmodn.
Encryption in Paillier is additively homomorphic. That means you can add data without first decrypting the cipher text.
Note
As I stated at the beginning of our discussion of the Paillier crypto system, the mathematics for this particular algorithm is a bit more complex than the math used in other algorithms we have studied in this text. If you have trouble with the math shown here, don’t be overly concerned. It is not critical that you have a detailed understanding of this algorithm.
If you have a programming background, it might be helpful for you to see the Paillier system in code. The University of Maryland offers the following code as open source, free to use.6 This is a complete code example that would allow a programmer to implement a homomorphic system.
You may also find the following sources useful:
The Google Homomorphic Code Project: http://code.google.com/p/thep/.
IBM Homomorphic research: http://researcher.watson.ibm.com/researcher/view_group.php?id=1548.
Quantum Cryptography
Quantum cryptography is clearly the next innovation in cryptography, but what exactly does it mean? There are several ways to apply quantum mechanics to cryptography. Two of the most obvious are quantum key distribution and using quantum computing to break cryptographic implementations. Before we can examine these issues, however, let’s briefly review the essentials of quantum mechanics.
What Is Quantum Mechanics?
Quantum mechanics deals with the physics that occurs at the subatomic level. At this level, things behave very differently from their behavior in our ordinary world. The term quantum comes from the fact that at the subatomic level things change by discrete amounts, rather than across a continuum. A classic example often encountered in university freshman and sophomore chemistry is the orbit of electrons around the nucleus of an atom. Electrons appear at discrete energy states and do not appear at intermediate states. In other words, they are in specific quantum states.
Note
Obviously a single section in one chapter of a book cannot provide thorough coverage of such a complex topic. But you need to have only a broad outline of quantum mechanics to understand quantum cryptography.
Another fascinating, and counter-intuitive, aspect of quantum mechanics is the wave-particle duality. In fact, this was one of the issues that led to the discovery of quantum mechanics. At the end of the 19th century and the beginning of the 20th, there was a debate in physics as to whether or not light behaved as a particle or a wave. It turns out that it behaves in both ways, depending on circumstances, and it turns out that all particles are both a wave and a particle.
Two aspects of quantum mechanics are particularly relevant to quantum cryptography. The first is quantum entanglement, a process that occurs when two particles (or two groups of particles) are generated together or interact so that they become entangled. Even if you separate the particles (or groups of particles), any changes to one will immediately be correlated on the other. So, for example, if one particle is given a clockwise spin, the other will have a counterclockwise spin. The distance between the particles doesn’t matter, and there is no known transformation of information—the two entangled particles just somehow “know” each other’s state and correlate their states to match. If this seems remarkable to you, even hard to believe, you are in good company. Albert Einstein referred to this as “spooky action at a distance,” and it is one reason he died believing quantum mechanics was flawed.
The other aspect of quantum mechanics that is of use in cryptography is the Heisenberg uncertainty principle, which states that the more precisely the position of some particle is determined, the less precisely its momentum can be known—and vice versa. In essence, attempting to measure a particle changes properties of that particle. We will examine some cryptographic implications for this principle later in this chapter.
Quantum Key Distribution
The most practical use of quantum cryptography, and the one most likely to be implemented in the foreseeable future, is quantum key distribution. The issue of key distribution is at the heart of many algorithms such as Diffie-Hellman and Menezes–Qu–Vanstone, or MQV (recall both algorithms were discussed in Chapter 10). How do two parties exchange a key in such a way that a third party cannot intercept it? If the key is encoded as quantum bits, then the Heisenberg uncertainty principle provides security for key transmission. Any attempt to read the key will in fact alter the key.7
It is also possible to use quantum entanglement for key exchange. If a set of particles is entangled and then separated, the party on one end can encode bits as properties (such as spin) on the particles. By changing the property on the sender’s side, the bits of the key are instantly transmitted to the receiving side. Because there is no known communication medium, it is impossible for someone to intercept the key transmission.
Breaking Quantum Code
Quantum computing is still in a nascent stage, a very long way from practical implementation. But the possibilities could radically change cryptography. Current digital computers maintain data in states of bits, a 1 or 0. A quantum computer maintains data in qubits. These qubits can use a 1, a 0, or a superposition of these states. This allows quantum computers to store much more data and to process data much faster.
What this means in practical terms is that a quantum computer would have immensely more computational power than any digital computer. Consider the asymmetric algorithms you’ve studied in this book. They were all based on some problem being infeasible to solve, such as factoring a composite number into its prime factors (as seen in RSA), or solving a discrete logarithm problem (as in elliptic curve cryptography). If quantum computers become a practical reality, these problems will no longer be impractical to solve. In fact, they will be solvable in a reasonably short period of time, thus undermining the basis for all asymmetric algorithms.
Symmetric cryptography will not be safe from the onslaught of quantum computing either. Consider that keys such as the AES 256-bit key are essentially immune from brute-force attacks using current methods; a quantum computer could try far more keys in a shorter period of time, making brute-force attacks far more practical.
Currently there are no working quantum computers, so these issues are only hypothetical at this point. But given the attention and resources committed to quantum computing, it seems likely that we will eventually face these problems. Right now, the only solution is to use much larger keys, but this is only a stopgap solution, not a permanent one. Quantum computing will require an entirely new approach to cryptography—one that has not yet been developed.
Conclusions
Cryptography is evolving, and new issues are on the horizon. Currently one of the more immediate issues in cryptography is that of homomorphic encryption, which allows an entity to perform operations on encrypted data without first decrypting the data, and indeed without even having the capability to decrypt the data. Homomorphic encryption has applications in electronic voting, e-commerce, and cloud computing. Cloud computing itself poses cryptographic challenges, and homomorphic cryptography is one of the primary solutions to those challenges.
Quantum mechanics has not only revolutionized physics, but it could revolutionize computing and cryptography as well. Quantum key exchanges is perhaps the most immediate issue in cryptography and could solve secure key exchange issues. Code-breaking could also be enhanced dramatically by quantum computing.
Test Your Knowledge
1. __________ is a mechanism whereby the user can get proof that the vendor has not tampered with the data.
2. Briefly describe homomorphic encryption.
3. Who invented the first plausible construction for a fully homomorphic encryption scheme?
4. ____________ was the first probabilistic public key algorithm that is provably secure.
5. What is the most widely known homomorphic system?
6. What is (currently) the most practical application of quantum mechanics to cryptography?
7. What property of quantum mechanics makes it impossible to tamper with a key being transmitted with quantum bits?
Answers
1. Proof of storage
2. Homomorphic encryption allows an entity to carry out computations on cipher text, without first decrypting the message.
3. Craig Gentry
4. Goldwasser–Micali
5. Paillier system
6. Quantum key distribution
7. The Heisenberg uncertainty principle
Endnotes
1. “Cloud Security & Cryptography,” http://research.microsoft.com/en-us/projects/cryptocloud/.
2. A. Greenberg, “Hacker Lexicon: What is Homomorphic Encryption?” Wired, 2014, www.wired.com/2014/11/hacker-lexicon-homomorphic-encryption/.
3. E. Naone, “Homomorphic Encryption: Making Cloud Computing More Secure,” MIT Technology Review, 2011, www2.technologyreview.com/article/423683/homomorphic-encryption/.
4. K. Lauter, M. Naehrig, and V. Vaikuntanathan, “Can Homomorphic Encryption be Practical?” Microsoft Research, 2011, www.msr-waypoint.com/pubs/148825/ccs2011_submission_412.pdf.
5. C. Gentry and S. Halevi, “Implementing Gentry’s Fully-Homomorphic Encryption Scheme,” in Advances in Cryptology – EUROCRYPT 2011 Lecture Notes in Computer Science, vol. 6632, 2011, 129–148, http://link.springer.com/chapter/10.1007%2F978-3-642-20465-4_9#page-2.
6. You can download the Paillier code from www.csee.umbc.edu/~kunliu1/research/Paillier.html.
7. S. Selvan, R. Rajan, and S. Tamilenthi, “An overview of new trends in cryptography,” Recent Research in Science and Technology 2012, 4(6), 38–42.