New Faculty Shows Where Cryptography Meets the Computer System

Taking a Where’s Waldo? book from his shelf, Assistant Professor Alex Ozdemir posed a simple question: Is it possible to prove Waldo is somewhere on the page without showing anyone where he is?

The answer is yes. Ozdemir demonstrated the technique by taking a piece of paper with a small Waldo-shaped hole cut out and placing it over the page. The demonstration confirms that Waldo is on the page without revealing his location or other details and is a simple example of a concept called a zero-knowledge proof.

In computer science, zero-knowledge proofs allow one person to prove that something is true without revealing the information that makes it true.

These types of problems sit at the center of Ozdemir’s work. As a computer scientist and cryptographer, he studies ways to use mathematics and computer programs to protect information. But his work goes beyond creating new methods for keeping data secret. He is interested in connecting those methods to the computer systems that use them.

“I get excited about what no one else is working on,” he said. “What I’m excited about now is how you relate the security of a computer system to a crypto scheme.”

Two recent papers published at USENIX Security show how Ozdemir is applying this approach to real-world privacy and security problems.

One of these problems is how to handle sensitive information without revealing it.

Imagine two organizations want to combine or analyze information, but neither wants to share its private data with the other. Cryptography can make this possible, but some of these privacy protections can be slow and difficult to use with large amounts of information.

Ozdemir and his collaborators developed a new system called FLOSS (Fast Linear Online Secret-Shared Shuffling) to make one of these tasks much faster.

FLOSS allows two parties to mix a set of private information without either party seeing the original data or learning the final order. This process, known as shuffling, is useful in privacy-preserving applications such as data analysis, anonymous messaging, and private advertising.

In tests, FLOSS shuffled more than one million items in less than half a second, making it more than 800 times faster than previous leading methods.

FLOSS achieves much of this speed by doing some of the hard mathematical work in advance, before the actual data is available. When the data arrives, the system can complete the shuffle quickly, with very little communication between the two computers.

The system is designed to protect against cheating. If one of the parties tries to manipulate the process or access information it shouldn’t, FLOSS can detect the problem and stop the computation.

The researchers also used FLOSS to create a faster way to sort private information. Sorting is a basic computer task but doing it while keeping the information secret can be expensive. Making that process faster could allow privacy-preserving tools to handle much larger amounts of data.

Ozdemir tackled another problem through a project called Orbit: How can computers perform useful work on information that remains encrypted?

Fully homomorphic encryption, or FHE, is a form of encryption that allows computers to perform calculations on protected data without first decrypting it. For example, a hospital could send encrypted medical information to a cloud service for analysis without the service seeing the patients' records.

The challenge is that this type of computing can be extremely slow.

Orbit is a computing tool called a compiler that helps make these encrypted calculations more efficient. A compiler takes computer code and turns it into instructions that a computer can run. Orbit examines an entire computation and identifies more efficient ways to handle some of the most expensive steps in fully homomorphic encryption.

Rather than treating those steps separately, Orbit looks at how they work together and identifies opportunities to reduce the amount of work the computer must do.

In tests, Orbit was between 1.19 and 1.73 times faster than previous leading systems on the workloads studied, including complex tasks such as running artificial intelligence models. The calculations also remained within 0.3% of the accuracy of those performed on unencrypted data.

For Ozdemir, projects like FLOSS and Orbit are part of a broader goal: making advanced cryptography practical enough to use with the computer systems people use every day. 

Now at Georgia Tech’s School of Cybersecurity and Privacy (SCP), Ozdemir is recruiting Ph.D. students from across the computing stack to work with him. He was drawn to Georgia Tech in part for its multidisciplinary approach to security.

“I also just love being around universities,” he said.

At SCP, Ozdemir plans to continue exploring programmable cryptography across the computing stack, integrating cryptography, compilers, and automated reasoning to address security problems from multiple angles.