Russell Impagliazzo, a professor of computer science at the University of California, San Diego, said the LLL algorithm has also led to what is known as 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 to, in turn, calculate your credit score without ever learning anything about you.
The algorithms, he said, were already “almost fast enough” to be practical.
One of Dr. Wigderson’s key advances involves what are known as zero-knowledge proofs. It is often important to show that you possess something — for cryptocurrency, that you actually have the money — without divulging any information about what you know.
“You should really think of two parties that don’t trust each other,” Dr. Wigderson said.
A fanciful example is that someone has a “Where’s Waldo?” puzzle where the small character Waldo (outside of North America, Waldo is usually known as Wally) is hidden within a complex drawing and this person has not found Waldo. You, on the other hand, have found Waldo and are willing to sell the solution. How could you convince the other person you actually have found Waldo without giving away the answer for free?
What you could do is ask the other person to turn around as you place a large piece of cardboard over the image with a small window cut that allows Waldo to be seen without revealing his exact location.
What Dr. Wigderson, working with other mathematicians, showed was that any mathematical proof could be cast as a zero-knowledge 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. Following 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 selecting, arranging and counting objects. That area became important for many problems in computer science like the design of computer networks.
