Avi Wigderson and Laszlo Lovasz Nobel for mathematics use in cryptography

2 Win Abel Prize for Math-Computer Science Collaboration

László Lovász and Avi Wigderson will share the annual award, which is modeled after the Nobel Prize in mathematics.

This year's Abel Prize, known as the field's Nobel, will be shared by two mathematicians for developments in understanding the foundations of what can and cannot be solved with computers.

The winners' work — László Lovász, 73, of Budapest's Eötvös Loránd University and Avi Wigderson, 64, of Princeton's Institute for Advanced Study — entails proving theorems and developing methods in pure mathematics, but the research has found applications in computer science, particularly in cryptography.

Dr. Lovász and Dr. Wigderson were honored by the Norwegian Academy of Science and Letters on Wednesday for their “foundational contributions to theoretical computer science and discrete mathematics, and their leading role in forming them into fundamental fields of modern mathematics.”

Dr. Lovász and Dr. Wigderson will share the 7.5 million Norwegian kroner ($880,000) prize money.

The two mathematicians have “really opened up the landscape and shown the fruitful connections between computer science and mathematics,” according to Hans Z. Munthe-Kaas, chairman of the Abel Prize committee and a mathematician at the University of Bergen in Norway.

Dr. Munthe-Kaas explained, "This award is on the applied side, for computer science." “However, it is complex mathematics.”

There is no Nobel Prize in mathematics, and the Fields Medals, issued in small batches every four years to the most experienced mathematicians aged 40 or younger, were the most coveted awards in math for decades.

The Abel, named after Norwegian mathematician Niels Henrik Abel, is structured similarly to the Nobel Prizes. It has been granted annually since 2003 to recognize significant advances in mathematics. Andrew J. Wiles, who proved Fermat's last theorem and now teaches at Oxford; John F. Nash Jr., whose life was depicted in the film "A Beautiful Mind"; and Karen Uhlenbeck, an emeritus professor at the University of Texas at Austin and the first woman to receive an Abel.

Dr. Lovász said he was "interested in this borderline between computer science and mathematics" since many in the early pioneers of computer science, such as Alan Turing and John von Neumann, were mathematicians.

Avi Wigderson and Laszlo Lovasz Nobel
Avi Wigderson of the Institute for Advanced Study in Princeton, N.J., and László Lovász of Eötvös Loránd University in Budapest, winners of the Abel Prize.

The LLL algorithm (the three Ls standing for the surnames of the three mathematicians who developed it: Dr. Lovász and two brothers: Arjen and Hendrik Lenstra) is one of the most influential results in his body of work.

A simple geometric object is used in the algorithm: a lattice. The squares on a sheet of graph paper are an example of a simple two-dimensional lattice. Two line segments — one short vertical line, the side of one of the squares, and one horizontal line of the same length — will build the pattern. Any point on the lattice can be reached by combining these two line segments.

Finding the generators that are the equivalent of the two line segments for a two-dimensional square lattice in higher dimensions, with more complex lattices, is a difficult problem to solve. However, the LLL algorithm demonstrates how to find an easy but accurate approximation.

Other researchers were able to reveal the flaws in certain cryptographic schemes using Dr. Lovász and his colleagues' algorithm, showing how they could be streamlined and then easily cracked.

The algorithm may also point to new encryption techniques that will be needed if, as anticipated, technology enters a quantum computing age.

Encryption today is based on the products of large prime numbers. (A prime number is a positive integer that can only be divided by one and itself.) Thus, the numbers 3, 5, and 7 are prime, but not 9, which is divisible by three.) Quantum-based computers, on the other hand, could factor large numbers easily, ensuring that encryption is safe.

This will necessitate a complete abandonment of prime number-based encryption schemes. The only other choice is to use lattice-based schemes based on the LLL algorithm; no one has yet formulated a strategy to crack them, even with quantum computers.

The LLL algorithm, according to Russell Impagliazzo, a computer science professor at the University of California, San Diego, has also contributed to homomorphic encryption, which enables calculations to be performed on encrypted data without ever decrypting it.

According to Dr. Impagliazzo, homomorphic encryption could allow you to send encrypted financial data to a credit bureau, which would then measure your credit score without learning anything about you.

He said that the algorithms were already “almost fast enough” to be useful.

Zero-knowledge proofs are one of Dr. Wigderson's most significant contributions. It is often possible to demonstrate that you have something — in the case of cryptocurrencies, that you actually have the money — without sharing any details about what you know.

Dr. Wigderson advised, "You should just think about two parties that don't trust each other."

Someone has a "Where's Waldo?" puzzle with the small character Waldo (usually referred to as Wally outside of North America) concealed inside a complex drawing, and this individual has not found Waldo. You, on the other hand, have tracked down Waldo and are prepared to sell the solution. How do you persuade the other person that you have indeed located Waldo without giving away the solution for free?

You could have the other person turn around while you cover the picture with a big piece of cardboard with a small window cut in it, allowing Waldo to be seen without exposing his exact location.

Working with other mathematicians, Dr. Wigderson demonstrated that any mathematical proof could be cast as a zero-knowledge proof. “It astounds me,” he said.

In 1948, Dr. Lovász was born in Budapest. He received gold medals in the International Mathematical Olympiads in 1964, 1965, and 1966 as a teenager. Dr. Lovász concentrated on the field of combinatorics, which studies trends in choosing, arranging, and counting items, in the footsteps of Paul Erdös, perhaps the most prominent Hungarian mathematician of the twentieth century. That field became essential for many computer science problems, such as computer network design.

Dr. Wigderson was born in the Israeli city of Haifa in 1956. In 1983, he earned his doctorate in mathematics from Princeton University. He returned to Israel in 1986 to join the faculty of Jerusalem's Hebrew University. In 1999, he entered the Institute for Advanced Study.

Unlike Nobel Prize winners, who are contacted by phone right before the public announcement, Abel winners are notified days in advance. Some of their coworkers are informed even sooner, and the method of telling the Abel recipient resembles throwing a surprise birthday party.

Some of Dr. Lovász's coworkers set up a Zoom videoconference call for him, reminding him that the Hungarian Academy of Sciences decided to write an article regarding his research on their website.

However, on the Zoom call, he saw far more people than he had expected. Dr. Lovász admitted, "Of course, I was overwhelmed." “When should I tell my wife?” was my first thought.

Dr. Lovász was given permission to immediately inform her, who was in the next room.

There was less deceit for Dr. Wigderson. On Monday morning, he was told to expect a phone call from the Norwegian Academy by Robbert Dijkgraaf, the director of the Institute for Advanced Study, and he believed he had received an Abel.

“I wasn't sure,” Dr. Wigderson admitted, “but at the very least I could guess.”

Tags