N
news
Science | DOI:10.1145/3398388 Gregory Mone
The Quantum Threat
Cryptographers are developing algorithms to ensure
security in a world of quantum computing.
T
H E S E C U R I T Y O F modern
communications could soon
expire. The precise day,
month, or year is impossible
to predict because the tech-
nology capable of cracking our codes—
practical, robust quantum comput-
ers—does not exist. Yet experts insist
that the time to prepare is now.
“It’s beyond something you can just
ignore, even though we still don’t know
when it will happen,” says mathematician
Michele Mosca of the Institute for Quan-
tum Computing at the University of Wa-
terloo in Canada. “The chance of it hap-
pening in five, 10, or 20 years is not a risk
you can accept. It’s a systematic threat to
the global economy, and it’s real enough
that you definitely have to plan for it now.”
Today’s most successful crypto-
graphic systems, which we depend
upon to secure online transactions and
communications, rely on one of two
mathematical problems: factoring large
numbers or finding discrete algorithms. for machines that speak in the common While the threat is theoretical, it
If you’re using online encryption, buying digital language of 1s and 0s. Shor’s still has contemporary implications.
something, or even downloading a soft- algorithm is designed to run on a quantum A malicious actor could store a cache
ware update for your PC, the security of computer—one that uses quantum of email encrypted with today’s cryp-
that exchange probably relies on the dif- bits, or qubits. These qubits could exist tographic approaches, and then use
ficulty of these mathematical challenges. in a superposition of an exponential quantum computing to unlock them
For today’s computers, these problems number of states, and a quantum some 10 or 15 years in the future.
IMAGE BY TEX VECTOR
are all but impossible to solve. computer running Shor’s algorithm Government, academia, and in-
In 1994, mathematician Peter Shor could solve both of the difficult dustry are working diligently to pre-
described an algorithm that could un- mathematical problems that under- pare for this post-quantum-comput-
lock these codes, but it was not designed pin most cryptography. ing world. The German government,
12 COM MUNICATIO NS O F TH E ACM | J U LY 2020 | VO L . 63 | NO. 7
news
for example, is funding seven initia-
tives, including efforts to increase
“It’s not a paint job.
ACM
collaboration between academia and
industry. However, most experts cur-
rently are focused on the Post-Quan-
It’s like replacing Member
tum Cryptography Standardization every brick in News
project being run by the U.S. Nation- the foundation
al Institute of Standards and Tech-
nology (NIST). The goal of the proj- of your house. WHERE CYBERSECURITY
AND DATA SCIENCE MEET
ect, which has many hallmarks of a You can’t just ACM Fellow
Bhavani
competition but declines to be de-
fined as such, is to spark the develop- throw on some Thuraisingham
is a Founders
ment, refinement, and testing of quantum-safe Chair Professor
and Executive
cryptographic algorithms that could
maintain security in a world of quan- fairy dust at Director of the
Cyber Security Research and
tum computers. the last minute.” Education Institute at the
University of Texas at Dallas.
Living on the Edge Thuraisingham received
an undergraduate degree in
In one sense, the threat of quantum mathematics and physics from
computers is not entirely new, as the University of Ceylon (now
there is always a risk cryptography Sri Lanka), a master’s degree
in Mathematical Logic and
can be broken. “We live on the edge cryptography community quickly set Foundations of Computer
because none of the cryptographic about testing the approaches. Some Science at the University of
systems we use are proven secure in were broken within a few weeks; others Bristol in the U.K., and a Ph.D.
the sense that there’s no mathemat- survived longer. When a group or indi- in Theory of Computation from
the University of Wales in the
ical proof that these things cannot vidual breaks a technique, the result U.K. “I also earned a higher
be broken,” says Massachusetts In- is announced in an NIST forum. The doctorate (D. Eng) from the
stitute of Technology mathemati- prize? Peer recognition. By 2019, the University of Bristol, England,
cian Vinod Vaikuntanathan. “A field narrowed to 26 candidates, and for my published work in secure
data management,” she adds.
bunch of smart people try to attack that number will be winnowed down Over Thuraisingham’s nearly-
them for 10 to 20 years, and if they again this year or early next. 40-year career, she has worked in
can’t, then we say it’s probably good NIST mathematician Dustin Moody, industry at the non-profit MITRE
Corp., at a federal laboratory,
enough. But we’re always at risk of director of the program, expects and for the U.S. National Science
someone coming up with a clever al- approximately a dozen candidates will Foundation. In 2004, she joined
gorithm for factoring large numbers emerge as finalists. NIST has encour- the faculty of The University of
or, with quantum computers, we’re aged several teams to merge, as their Texas at Dallas as a professor of
computer science and director
at the risk of the underlying com- approaches were similar, and some have of the university’s Cyber Security
puting technology changing so dra- followed these recommendations, while Research Center.
matically that new attacks suddenly others remained independent. One of Thuraisingham’s research
focus is on the intersection of
become possible.” the more popular methods among the cybersecurity and data science.
Since the problems on which most entries hinges on lattices, or grids, and “One area my research has
cryptography relies would be solvable the difficulty of finding a point close to centered on is applying machine
in a post-quantum world, experts have the origin in a lattice defined by a basis learning to detect malevolent
threats, such as malicious code
to find a new, harder mathematical prob- of long vectors. In two dimensions, the and malware,” she says.
lem. Luckily, this effort has been under- lattice problem can be relatively sim- More recently, she has
way for some time. “People have been ple, but “When you go to 1,000 dimen- focused on adversarial machine
trying to build post-quantum-secure sions, this becomes insanely hard,” says learning, an ongoing process of
introducing countermeasures
cryptography for 20 years,” says crypto– Vaikuntanathan. “Nobody has been able against evolving threats.
graphy researcher Vadim Lyubashevsky to put a dent in this problem.” “Malicious threats keep updating
of IBM Research, Zurich. “This was The other advantage of the lattice- and adapting, so cybersecurity
measures have to as well.”
already a mature field.” based approach is that cryptography Thuraisingham is a
researchers have been testing it— passionate advocate for women
Narrowing the Field and attacking it without success—for in computing. She supports,
The aim of the NIST program is to years. “This gives you confidence in motivates, and encourages
women to become involved
transform this theoretical work into the security,” says Moody. “It gives you in cybersecurity, data science,
practical methods and results that can confidence that the hard problem and artificial intelligence
be widely attacked and tested. The ini- we’re going to rely on really is going to by organizing conferences
and workshops and giving
tial call for proposals yielded 82 sub- be a hard problem.” motivational addresses.
missions, of which 69 were accepted. At the same time, Moody stresses, —John Delaney
NIST researchers and members of the there are no favorites, and several other
JU LY 2 0 2 0 | VO L. 6 3 | N O. 7 | C OM M U N IC AT ION S OF T HE ACM 13
news
approaches have their own strengths. hardcoded that your packets are go- they wait for the new NIST standards
Mosca notes that advocates of another ing to be less than 3,000 bits, you’re to be released. While no date has been
popular option—a code-based ap- going to be in trouble,” says Lyuba- set, and no clear winner has emerged,
proach—would argue their scheme has shevsky. Systems that have placed a Moody does offer some sense of the
been around and tested even longer. limit on key size will have to be ad- end-results.
justed, or they will not be able to run Moody and other experts expect sev-
Practical Considerations these new cryptographic standards. eral algorithms to be selected, instead
The program is not merely evaluating Also, the exchange of keys needs to of a single victor. “There’s no perfect
the strength or security of the algo- be fast enough that the operation silver-bullet winner that will have all
rithms; the practical implications of re- does not time out. the properties everyone wants,” Moody
al-world implementation are essential, Regardless of which algorithms says. But the work of the remaining
too. For example, if the schemes are go- emerge from the competition, experts teams, and the efforts of the larger
ing to run on embedded systems such say it will still take years to implement cryptography community to attack
as Internet of Things (IoT) devices, they a post-quantum approach. “If I say it is their algorithms, should bring us clos-
will need to be sufficiently lightweight five years away, and tell a random en- er to a more secure post-quantum fu-
that they will not demand significant terprise they have to fix all their sys- ture. “We’re all working for the same
compute or storage resources. tems, there is no practical way they purpose,” Moody notes. “We want
“In general, post-quantum cryptog- could do it,” says Mosca. “Even a sim- strong cryptography to protect against
raphy schemes will require more re- ple fix takes a long time. It’s not a paint a future with quantum computers.”
sources,” says cryptographic engineer job. It’s like replacing every brick in
Ruben Niederhagen of the Fraunhofer the foundation of your house. You
Further Reading
Institute for Secure Information Tech- can’t just throw on some quantum-
nology (SIT) in Germany. “That’s fine if safe fairy dust at the last minute. You Bernstein, D.J., Buchmann, J., and Dahmen, E.
Post-Quantum Cryptography, Springer, 2009.
you have a large device like a smart- have to really start planning and work-
phone or a server, but if you go down to ing on it now.” Chen, L., Jordan, S., Liu, Y.-K., Moody, D.,
embedded systems, which have limit- This is especially true for large enter- Peralta, R., Perlner, R., and Smith-Tone, D.
Report on Post-Quantum Cryptography,
ed computational resources and limit- prises. Niederhagen and his Fraunhofer NISTIR 8105.
ed storage, this gets very tricky.” colleagues work closely with major
Kaye, P., Laflamme, R., and Mosca, M.
Speed will be an essential quality, companies, studying their products or An Introduction to Quantum Computing,
too. Online transactions need to be product lines to determine which will Oxford University Press, 2007.
fast, so new quantum-safe algorithms need to be post-quantum secure. Auto-
Lyubashevsky, V., and Seiler, G.
should not slow down exchanges ex- mobiles, power plants, trains—each of NTTRU: Truly Fast NTRU Using NTT, IACR
cessively, and Lyubashevsky says these relies on embedded devices, and Transactions on Cryptographic Hardware
some post-quantum techniques may the products they are manufacturing and Embedded Systems, 2019.
actually prove faster. today will likely still be operational in As We Enter a New Quantum Era
Another factor to consider will be 15 years, at which point quantum com- https://www.youtube.com/
the size of the keys that need to be ex- puters could be operational. watch?v=vWP4LF2hz80
changed. The lattice-based encryption
Gregory Mone is a Boston-based science writer and the
approach, for example, might result in No Silver Bullet author, with Bill Nye, of Jack and the Geniuses: At the
keys that are 8,000 bits long, instead Niederhagen says researchers who Bottom of the World.
of the 2,048-bit keys exchanged with focus more on implementation are
the popular RSA technique. “If you in something of a holding pattern as © 2020 ACM 0001-0782/20/7 $15.00
Milestones
ACM Members Elected to National Academy of Sciences
Eight members of ACM were president, Institute for Science Science Center, St. Louis, MO. Harvard University, and Simons
among the 120 members and 26 and Technology Austria. Jennifer Rexford, Gordon Y.S. Professor of Mathematics in
international members recently Yonggang Huang, Walter P. Wu Professor in Engineering, the department of mathematics
elected to the National Academy Murphy Professor of Civil and and chair of the department of and professor of electrical
of Sciences in recognition of Environmental Engineering computer science, at Princeton engineering and computer
their continuing achievements in and Mechanical Engineering in University, Princeton, NJ. science at MIT.
original research. the department of mechanical Jeffrey D. Ullman, Stanford The National Academy of
The honored scientists were: engineering of the McCormick W. Ascherman Professor of Sciences is a private, non-
Vinton G. Cerf, vice president School of Engineering of Computer Science (Emeritus) at profit society established by an
and chief Internet evangelist, Northwestern University, Stanford University, Stanford, CA. Act of Congress and charged
Google Inc., Reston, VA. Evanston, IL. Bonnie Berger, associate with providing independent,
Ronald Fagin, IBM Almaden Elizabeth A. Kellogg, Robert E. member of The Broad Institute objective advice to the nation
Research Center, San Jose, CA. King Distinguished Investigator of the Massachusetts Institute on matters related to science
Thomas Henzinger, university at the Donald Danforth Plant of Technology (MIT) and and technology.
14 COMMUNICATIO NS O F TH E AC M | J U LY 2020 | VO L . 63 | NO. 7
