Think about the humble envelope. For centuries this paper enclosure has shielded important information from prying eyes that might otherwise steal a glance at an unprotected note. Also, by placing information in an envelope, the sender effectively commits to and freezes this information until it gets to the recipient, assuming it is not tampered with or altered on its journey.
This system of secrecy served us well for centuries in an analogue world, but what about the digital environment in which we now communicate, shop and bank? Enter modern cryptography, which is the subject of this year’s Royal Irish Academy Hamilton Lecture by Israeli mathematician and computer scientist Prof Avi Wigderson. He will deliver his talk Cryptography: Secrets and Lies, Knowledge and Trust later this month at Trinity College Dublin.
Cryptography is nothing new, of course — for centuries people have encoded information to scramble its contents, which can then be deciphered or unscrambled by a recipient who knows the key or rules to breaking that code. But cryptography developed a new dimension towards the end of the 20th century thanks to the marriage of computing power and complexity theory, and Wigderson has helped to shape its power.
Hard to solve, easy to verify
Cutting off family members: ‘It had never occurred to me that you could grieve somebody who was still alive’
The bird-shaped obsession that drives James Crombie, one of Ireland’s best sports photographers
The Dublin riots, one year on: ‘I know what happened doesn’t represent Irish people’
The week in US politics: Gaetz fiasco shows Trump he won’t get everything his way
“Imagine a tough Sudoku puzzle or a tough mathematical problem,” he says. “Most people may not be able to solve these, but if they saw the correct answer they could check and verify that it was correct.” Such problems are of extreme importance in complexity theory.
Modern cryptography often makes use of such “hard problems”; difficult to solve but relatively easy to verify once solved, explains Wigderson, who is Herbert H Maass professor of mathematics at the School of Mathematics the Institute for Advanced Study, Princeton, New Jersey.
“About 40 years ago, people started understanding that introducing computational complexity, namely the fact that some problems are easy and some are hard for us and for computers, could be used as a basis for cryptography,” he says.
Cloaking information in such hard-to-solve problems is akin to the sender sealing the envelope in the analogue world. “Here one uses specific hard problems with extra structure — such as factoring integers into primes — which enable encoding any number by another which, like an envelope, obscures the original to anyone else, but commits the encoder to that value,” he says.
In a similar way tough mathematical problems can shield information as it travels digitally, and the solutions can be rapidly verified when the information lands.
“That complexity-based approach provides a system for secrecy without the need for physical means, and it allows us to do many more things than just send secret messages around,” says Wigderson. “You can use it to protect a vast array of transactions you might want to carry out in a digital world, and it led eventually to the revolution of online shopping and internet security.”
Hamiltonian paths
Much like cryptography, the notion of “hard-to-solve” problems is not new. Irish mathematician William Rowan Hamilton, after whom the Hamilton Lecture is named, made contributions to the field in the 19th century, particularly with his exploration of Hamiltonian Paths, Wigderson says.
“Think of a map with several cities on it,” he says. “Can you trace an unbroken route through those cities and visit each city only once? If there are 1,000 cities on this map, then it becomes a very hard problem to solve — you seem to need to try all possible routes — an astronomical number.
But if a solution, namely a route, is provided, then you can look at the map and quickly check that no city has been visited twice in the unbroken route. This was the kind of hard-to-solve but easy-to-verify problem that Hamilton explored. Today we know it to be a prototypical example of problems of this type — it is as hard as any of them.”
The mystery of A to B
One of the “great mysteries” of the field of complexity is what goes on between point A and point B, where some seemingly hard problems are solved. This, he says, has ramifications for questions far beyond cryptography, including climate, neuroscience, artificial intelligence and medicine.
“How do you explain why a particular drug works to cure a disease, or how actions in the atmosphere affect weather and climate, or how a thought is generated in the brain, or how a neural network can beat a world champion at chess,” he asks. “It may be easy to verify that these things happen, but how do they happen?”
Nor can we explain exactly how scientific luminaries such as Newton, Hamilton, Pasteur and Einstein came up with their insights and theories, he adds. “They were extremely successful in explaining things that people hundreds and thousands of years before them couldn’t explain that way,” Wigderson points out. “They came up with something that it seems was much easier to verify than to find.”
Complexity and curiosity
He distinguishes between the questions of finding an algorithm that works, and the question of how it works. “I think many people would be extremely happy if some ‘black box’ would solve all their problems, making them happy and healthy and living for 100 years, even if they didn’t quite understand how this algorithm came up with it,” he says. “I think that would be big progress.”
But Wigderson, who in 2021 shared the prestigious Abel Prize with László Lovász “for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics”, also wants to understand the “how” of the complexity that underpins outcomes. And his drive is simple: he is curious. “I think it is the most natural thing in the world to want to understand how everything happens.”
That curiosity continues to drive Wigderson: “I am totally fascinated by computation and what it can and cannot do. And by computation, I do not necessarily mean computers; every physical and natural process that happens — ocean waves or the weather or the evolution of growth of embryo in the uterus, or the leaves on a plant or the formation of seashells or viruses causing disease — all these processes are computations, in that they evolve in a sequence of simple, local steps like a computer programme.”
Taking a computational approach to the natural world can yield important insights, Wigderson believes. “We saw in the 1950s how Alan Turing, a mathematician famous for deciphering code, proposed a simple model that shows how patterns such as spots and stripes on animals’ skin can evolve. Working with computation and complexity you can get profound insights into the natural world and many of the issues that are facing us today, and I find that fascinating.”
Hamilton Lecture 2022
Prof Avi Wigderson of the Institute for Advanced Study, Princeton University will deliver the 2022 RIA Hamilton Lecture on Cryptography: Secrets and Lies, Knowledge and Trust on Monday, October 17th, 2022 at 6pm-7.30pm. Tickets are free
