A Cybersecurity Paradigm Shift: Post-Quantum Cryptography
June 27, 2012
PhD Candidates working with Dr. Nicolosi
Cybersecurity has transformed into an everyday reality for all users of Internet-connected devices. Joining wireless networks, shopping or paying bills online, logging into password-protected Web accounts, and toting always-connected mobile devices presents a constant security challenge. Cisco estimates that 1 trillion unique devices will be connected to the Internet by the year 2013, amplifying issues of information security and reliability.
Cisco estimates that 1 trillion unique devices will be connected to the Internet by the year 2013, amplifying issues of information security and reliability.
Researchers at Stevens Institute of Technology are planning for an even bigger challenge to cryptography and cybersecurity. While scientists and engineers worldwide are working intently to make the dream of quantum computing a reality, information security managers are watching the horizon with some apprehension. The overwhelming computational abilities accessible upon the arrival quantum computers would quickly unravel the most advanced public key encryption available today, thus rendering current cryptographic standards obsolete. If quantum computers appeared as a viable technology tomorrow, there would be precious little alternative and acceptable means for securing our online and wireless transactions.
In the meantime, cybersecurity is becoming even more critical to our future. The White House issued its Cyberspace Policy Review in 2009, declaring cybersecurity a matter of national public safety and a priority for the current administration.
“Information technology is an established component of the infrastructure of modern societies, and cryptography is a cornerstone of information security.”
–Dr. Antonio Nicolosi
“Information technology is an established component of the infrastructure of modern societies, and cryptography is a cornerstone of information security,” says Dr. Antonio Nicolosi, professor of Computer Science at Stevens.
Experts predict another twenty years before the advent of quantum computing. However, the magnitude of these concerns is enough for researchers across the world to devote millions to the study of new methods for online encryption and the hiding of messages, known as Post-Quantum Cryptography.
Traditional Vs. Post-Quantum Cryptography
Cryptography is the practice and study of protecting information and computation processes. This fundamental computing discipline is the backbone of the security which converts your message into a secure format that can reach its destination without being read by an eavesdropping party.
Image courtesy NIST
Our most widely implemented use of Traditional Cryptography is a public-key encryption algorithm known as RSA. To use RSA, a user creates and publishes a public key that is the product of two large prime numbers, and keeps the prime factors secret. Anyone can use the public key to encode a message to that user, but only that user has the private key (based on the prime factors) which is necessary for decoding. The security of RSA depends on the difficulty of recovering the prime factors when only the multiplicative product is known.
Current cryptographic encryption methods are analogous to an arms race. Researchers add complexity to the algorithms that encode our messages while hackers attempt to break them. For now, researchers are able to outpace the majority of these malicious attempts. However, quantum computing would compel the use of keys so long that most public key systems in use today would not be practical. This necessitates a complete redesign of the algorithms involved in online encryption, and those efforts are known as Post-Quantum Cryptography.
Because the most complex encryption methods in existence today will be resolved in “real-time” on quantum computers, the challenge for researchers is to develop newly structured mathematical algorithms that maintain security amid quantum computers.
“Each of the major public-key protocols used in e-commerce today depends on a procedure which is easy to do but difficult to undo,” says Dr. Robert Gilman of the Department of Mathematical Sciences at Stevens. In RSA, for instance, it is easy to multiply two large primes, but very difficult to factor a large integer into a product of primes. Researchers have long thought factoring to be a "hard" problem, but they have not proved it. “If it turns out that there is an easy way to factor, or in the case of quantum computing, if technology suddenly gains the power to solve hard problems much more quickly, then RSA will not be secure.”
Public key systems are built from computational problems in algebra and number theory. For the system to be secure its corresponding computational problem should be virtually impossible to solve in the absence of the secret key. However, none of the computational problems in use today have been proven to be “hard” in this sense. (And the computational problems corresponding to most public key systems are known to be not hard for quantum computers.)
Setting up the challenge as an interdisciplinary pursuit, researchers at Stevens have effectively organized their skills by focusing on specific aspects of the greater problem. The methodologies being investigated by individual researchers, such as the use of lattice theory and group theory, function as part of an all-encompassing approach to defining, planning, and executing a strategy for complete cryptographic enhancement.
Mathematics Department Director Alexei Miasnikov founded the Algebraic Cryptography Center (ACC) to investigate new techniques from computational algebra and their applications to practical problems in cryptography and cryptanalysis. Post-quantum cryptography is one of the research themesbeing investigated by Alexei Miasnikov, Alex Myasnikov, Alexander Ushakov, Denis Serbin, Werner Backes, Sven Dietrich, Antonio Nicolosi, Susanne Wetzel, and Dr. Robert Gilman.
The ACC was established to facilitate interdisciplinary research on foundational problems of cryptography and cybersecurity in collaboration with associate members at other institutions throughout the world. The center investigates unique applications of mathematical algorithms that may be used to facilitate security in quantum computing systems – an integral blending of both computer science and mathematics in pursuit of a greater goal.
Dr. Miasnikov looks upon this emerging research with genuine enthusiasm. “Everything in the field of quantum computing and cryptographic mathematics is wide open. There remain fundamental mathematical questions that affect the very nature of current and future cryptographic methods. These not only present challenging and exciting opportunities for researchers such as myself, but offer an exceptional chance for students to participate in this groundbreaking field.”
Dr. Miasnikov’s sentiments were echoed by Professors Wetzel and Gilman who feel the programs at Stevens illustrate the importance of collaboration between Computer Science and Mathematical disciplines to success in this field. According to Dr. Nicolosi, the pursuit of more secure cryptography is a great area for students at all levels who are interested in research. It has provided undergraduate students with an opportunity to help code encryption systems. Meanwhile, graduate students with training in cryptography can try their hand at refining the techniques that researchers are developing, or assessing their robustness by devising new approaches to the cryptoanalysis of the underlying computational problems.
The Search for Hard Problems
The question of what makes a computational problem difficult is a focus of research for Mathematics Department colleagues Alex Myasnikov, Alexander Ushakov, and Robert Gilman. This work can be classified as a pursuit within Complexity Theory.
In the face of a growing need for robust new encryption methods, there is a gap in the system that researchers must overcome. Beyond empirical demonstration, it is difficult to mathematically prove that a security algorithm is “hard.” As researchers go beyond incremental improvements—such as boosting the integer size in an RSA key—and propose innovative departures from traditional cryptography, increasingly there will be a demand for proof of a computational problem’s hardness.
The ideal problem for use in cryptography is difficult to solve for every possible key. However, that is impossible in practice, because at the most basic level, one can store answers for some keys in memory. Therefore, researchers at the Algebraic Cryptography Center have been seeking problems with generic complexity—those that are “hard” to solve for most inputs. They are directing their energies to the cases that occur "most of the time" rather than the "worst possible or average scenarios", because problems that have proven to be difficult for the latter cases have occasionally turned out to be not “hard” overall.
An important point about security measures is that they are never foolproof. Current methods of encryption are based upon mathematical equations with the idea being that the more complex the equation, the longer it takes to decode. While security advancements are continuously advancing, so are the methods of intrusion, and breaches still occur.
“As we move forward, we have to be able to ask, ‘To what extent can we prove a crypto system is secure?’” Dr. Gilman states. “And we need to be able to find an answer.”
As a Professor of Mathematics at Stevens and leading member of the Algebraic Cryptography Center, Dr. Gilman is sparking conversation about how to examine cryptographic effectiveness and therefore plan for the future.
Hard Problems in Group Theory
According to Dr. Antonio Nicolosi of the Department of Computer Science at Stevens, there are many approaches to improving cryptography being investigated within Stevens and at institutions around the world. He says, “Heterogeneity has an inherent strength to it, and diversifying the set of difficult problems used to encrypt our vital information enhances the robustness of the overall structure of cryptography.” It is highly beneficial for the future health of cryptography because, as Dr. Gilman noted, no security measure is foolproof, using various difficult problems means that even if one is broken, the information secured by other methods would not be compromised.
Dr. Nicolosi, with collaborators at CCNY, aims to make unauthorized decryption of a message so difficult that even the power of a quantum computer would not help. They are pursuing a line of research in post-quantum cryptography which looks at identifying “hard” group-theoretic learning problems. This approach is inspired by the recent success of the learning parity with noise (LPN) and learning with errors (LWE) problems as a platform for a wide variety of cryptographic applications.
LPN and LWE can be thought of as a variation of the elementary problem of solving a system of linear equations, Ax=b (where x and b are vectors and A is matrix), which can be solved with standard techniques from linear algebra. The new ingredient in the LPN/LWE problems is the introduction of noise, which perturbs the system in a very slight and unpredictable manner. The issue then becomes akin to approximately solving a noisy linear system Ax + v = b (where v is a mostly-zero vector, with a few "noise" entries). Using known methods, solving this problem is unfeasible when the length of the vector x is in the order of a couple of hundreds (much shorter than a typical key in popular crypto-system like RSA).
Dr. Nicolosi’s group is taking a LWE approach into the realm of homomorphisms, or structure-preserving mappings between groups. This potentially yields “hard” problems where the computational task is the recognition of noisy (preimage, image) samples for a hidden homomorphism, as opposed to random pairs of elements from the relevant domain and co-domain. Their working hypothesis is that the problems obtained in this manner are even harder than the ones resulting from the LPN/LWE approach, and thus shorter keys are sufficient.
Lattice theory has also been proposed as a possible source of post-quantum cryptographic systems. Werner Backes, Antonio Nicolosi, and Susanne Wetzel are investigating various aspects of lattice-based systems. Lattices are geometric objects that can be visualized as the set of intersection points of a regular but not necessarily orthogonal n-dimensional grid. They were first found to be useful in breaking cryptosystems, but since certain lattice problems can also be very difficult to solve, researchers have found them to be promising in the design of secure cryptosystems.
According to Werner Backes, this work “not only provides effective tools for cryptanalysis, but is also believed that it can even bring about new cryptographic primitives that exhibit strong security even in the presence of quantum computers.” Since joining Stevens as a Post Doctoral Researcher in 2005, Dr. Backes has worked with Professor Wetzel in developing state-of-the-art algorithms that have the potential of being used in a multi-core, many-core or distributed environment.
Developments in Post-Quantum Cryptography are indeed required to keep us secure well into the future. If researchers crack the code behind Post-Quantum Cryptography, these solutions could be immediately put into use of our current infrastructure to improve it exponentially. Any advancement discovered in the research phases would have an equally dramatic impact today as well as twenty years into the future.
Interested in learning more and finding out how you can participate? Learn more about the Department of Mathematical Sciences or the Department of Computer Science, or apply at Undergraduate Admissions or Graduate Admissions.