Abel Prize: Avi Wigderson, László Lovász Win for Work That Bridged Math and Computer Science
Russell Impagliazzo, a professor of computer science at the University of California at San Diego, said the LLL algorithm also resulted in something called homomorphic encryption, which allows calculations to be performed on encrypted data without ever decrypting it.
Dr. Impagliazzo said homomorphic encryption could allow you to provide encrypted financial information to a credit bureau, and the credit bureau, in turn, could calculate your credit score without ever knowing about you.
The algorithms are already “almost fast enough” to be practical.
One of the most important advances made by Dr. Wigderson is what is known as the no-knowledge evidence. It is often important to show that you own something – for cryptocurrency, that you actually have the money – without revealing any information about what you know.
“You really should think of two parties who don’t trust each other,” said Dr. Wigderson.
A fanciful example is someone saying “Where’s Waldo?” Puzzle in which the small character Waldo (outside of North America, Waldo is usually known as Wally) is hidden in a complex drawing and this person has not found Waldo. You have found Waldo and you are ready to sell the solution. How could you convince the other person you actually found about Waldo without giving the answer for free?
You can ask the other person to turn around while you lay a large piece of cardboard with a small window cut over the picture so Waldo can be seen without revealing his exact location.
What Dr. Wigderson, in collaboration with other mathematicians, showed was that any mathematical proof can be cast as a knowledge-free proof. “It’s amazing to me,” he said.
Dr. Lovász was born in Budapest in 1948. As a teenager, he won gold medals at the International Mathematical Olympiads in 1964, 1965, and 1966. On the path of Paul Erdös, perhaps the most famous Hungarian mathematician of the 20th century, Dr. Lovász focused on the field of combinatorics, which studies patterns in the selection, arrangement and counting of objects. This area became important to many problems in computer science, such as the design of computer networks.