Meet the Fastest Public-Key Algorithm Few have Even Heard of

Here comes the fastest public-key algorithm that most people have never heard of: It’s called NTRUEncrypt and this month was approved by the financial services standards body, the Accredited Standards Committee X9.

The X9.98 standard specifies how to use NTRU, as it’s called for short, in financial transactions.

DO THE MATH: Software said to match quantum-computing speed

“The NTRU public-key algorithm competes with RSA and elliptic curve” says Ed Adams, CEO of Security Innovation, which owns the rights and patents associated with the NTRU algorithm. It was invented in the mid-1990s. Unlike RSA, NTRU is not widely used, and in fact the NTRU cryptosystem needed changes early on to improve its security by addressing weaknesses and performance. But today NTRU is recognized as faster than the widely used RSA algorithm.

“It is considerably faster; that is something we acknowledge,” says RSA Labs chief scientist Ari Juels.

One study that compared NTRU with both elliptic-curve cryptography and RSA was conducted by researchers at Katholieke Universiteit Leuven In Belgium. “Comparing NTRU to other cryptosystems like RSA and ECC shows that NTRU, at a high security level, is much faster than RSA (around five orders of magnitude) and ECC (around three orders of magnitude),” the researchers said.

Juels argues that the RSA algorithm and cryptosystem, which dates to the 1970s, is a more “mature” public-key crypto technology, having been found to work securely in a time-tested way for many applications.

“NTRU hasn’t received a lot of scrutiny,” Juels says.

Adams fires back that NTRU may be more resistant over time to attack than RSA because NTRU is constructed in what crypto researchers call a “lattice” framework. He claims this type of lattice design makes it more resistant than an algorithm like RSA to so-called quantum-computing attacks. Scientists are continually evaluating the processing power of cutting-edge quantum computers to determine whether it is possible to break public-key cryptosystems through them.

“A quantum bit assumes multiple values simultaneously and can explore a massive key length,” Juels acknowledges. “A quantum computer, if successfully built, would compromise the RSA algorithm and elliptic curve. But it’s unclear if it’s feasible to construct such a machine.”

While such hazy futuristic concerns about public-key systems may worry scientists, it’s clear that NTRU has not gained the kind of widespread use in practical applications that RSA has.

Adams does cite a few examples, saying satellite-services provider EchoSat is using NTRU in IP-based payment processing related to Citgo gas stations. Adams also says he is engaged in discussions with Microsoft, McAfee and Symantec on how they might use NTRU in applications such as auto-updates, though no announcements on that score have been made. NTRU may gain more interest from industry later this year if Security Innovation pursues plans to make NTRU available in an open-source model later this summer.

Read more about wide area network in Network World’s Wide Area Network section.