DARPA Takes Step Toward ‘Holy Grail of Encryption’

A look at the latest in the field of cryptography.


An abstract image showing multiple dimensions.

By Edd Gent – Live Science Contributor

The U.S. defense department is searching for what could be considered the “holy grail of data encryption,” which would seal up a loophole that allows hackers to access sensitive information while it’s being processed.

In modern encryption, a well-defined set of calculations, known as an algorithm, scrambles data so that it’s no longer readable. Those allowed access to the data are given a string of numbers called a key, which is the code that lets you unscramble that data again.

If someone wanted to use the encrypted data to do anything useful, they first would have to decrypt it back into so-called “plain text,” which makes it susceptible to snooping again. To help protect that now decrypted information, those working with the plain text typically only do soon trusted computers. But, as is apparent from regular headlines about data breaches at major organizations, it’s becoming difficult to tell which devices are secure.

“Given all of the news about these hacks, these malware attacks, we can’t trust fully all of our hardware or software systems,” Tom Rondeau, a program manager at the Defense Advanced Research Projects Agency (DARPA), told Live Science.

Related: Flying saucers to mind control: 22 declassified military secrets

That’s why DARPA is trying to spur breakthroughs in something called fully homomorphic encryption (FHE). The technique makes it possible to analyze compute data while it’s still in encrypted form. That could allow financial crimes investigators to scour sensitive bank records without exposing customer details, for instance, or let health researchers analyze private health data while preserving patients’ privacy, Rondeau said. The technique could also help the military keep their battlefield data more secure and make it easier to let allies work with classified intelligence data. 

The key to the approach is in its name, which is derived from the Greek words “homos,” meaning “same,” and “morphe,” meaning “shape.” It refers to the fact that certain mathematical operations can map data from one form to another without altering the underlying structure of the data. That means changes made to the data while in one form will be preserved when that data is converted back to the other. This principle can be applied to encryption, because computers represent all data, including text, as numbers.

Here’s a highly simplified example of how this might work: Imagine an encryption scheme that scrambles data by multiplying it by 3, so if you encrypt the number 8 you get 24. If you multiply your encrypted data by 2, you get 48. When you decrypt it again by dividing it by 3, you get 16, which is the same result you’d get if you just multiplied your unencrypted data by 2.

In this example, the encryption method is pretty easy to work out from the result, so it’s not secure. But FHE relies on something far more complicated called lattice cryptography, which encodes data as coordinates on a lattice. Lattices can be thought of as grids of regularly spaced dots, but, unlike the 2D grids we’re used to, the FHE lattices are multidimensional.

Related: The 11 most beautiful mathematical equations

So rather than describing each data point’s position with simple X, Y coordinates, the number of axes can be huge, with each unique piece of data being described by thousands of coordinates. Data points can also be positioned between dots, so each coordinate can have many decimal places to denote their precise location. This makes the encryption essentially impossible to crack, even by quantum computers. That’s a promising feature, Rondeau said, because today’s leading encryption methods are not quantum-proof.

FHE relies on a multi-dimensional lattice.

The big problem is that processing this data is very slow on current computers — roughly a million times slower than processing times for unencrypted data. That’s why DARPA has launched a research program called Data Protection in Virtual Environments (DPRIVE), which Rondeau is managing, to speed things up. The program recently awarded contracts to an encryption start-up Duality Technologies, software company Galois, nonprofit SRI International and a division of Intel, called Intel Federal to design new processors and software to boost speeds to just 10 times slower than normal, which is 100,000 times faster than current processing for fully homomorphic encryption.

FHE is so slow because of the way computations are carried out.To complicate matters more, those data points don’t remain static. Researchers discovered you can carry out mathematical operations such as multiplication or addition by moving data points around inside the lattice. By combining lots of these operations, researchers can carry out all kinds of computations without decrypting the data. When you decode the answer, there’s a chance that someone could spy on it; but that answer still wouldn’t reveal anything about the data used to compute it. 

Related: The 9 most massive numbers in existence

The overall problem with this process is that moving precisely-placed data points around in a high-dimensional space is far more complicated than doing calculations on simple binary data — the typical 1s and 0s of today’s computers.RELATED CONTENT

Photos: Large numbers that define the universe
9 numbers that are cooler Than Pi
8 ways you can see Einstein’s theory of relativity in real life

“It’s this data explosion,” Rondeau told Live Science. “Now, every computation isn’t just manipulating one bit. It’s manipulating all of this information, all these representations of the dimensions.”

There are two main approaches the DARPA-funded companies can use to simplify things, Rondeau said. One tactic is to improve the computer’s ability to deal with high-precision numbers, by changing the way numbers are represented in binary code and altering chips circuits to process them more efficiently. The other is to translate the data into a lower dimensional space where the calculations are simpler, which also requires new hardware and software approaches.

Each of the teams involved in the program is taking a slightly different approach, but Rondeau says he’s confident they will be able to hit the targeted 100,000-fold improvement in processing speeds.

Originally published on Live Science.

Editor’s note: This article was updated to indicate that “homos” and “morphe” are Greek words, not Latin as had been stated previously.

Leave a Reply

Your email address will not be published.
