POKEx: Performance analysis of POKE-key exchange and SIDH-variants

Imagine the internet is a giant, bustling city where everyone sends secret letters to each other. To keep these letters safe from thieves, we use "locks" called encryption. For decades, the best locks were made using math problems that are easy to do one way but incredibly hard to undo, like mixing paint colors together. However, scientists are worried that in the future, super-powerful computers (called quantum computers) will be able to undo these locks instantly, leaving our secrets wide open. To stop this, researchers are building new locks based on a strange and beautiful branch of math called "isogenies." Think of isogenies as a special kind of bridge that connects different shapes (mathematical curves). The secret to the lock is the specific path you take across the bridge. For a long time, the most popular bridge design was called SIDH. It was famous because the locks were tiny and fast, making it a top contender to protect our future digital world.

But then, in 2023, a pair of researchers discovered a clever trick to break the SIDH bridge. They found that the bridge designers had accidentally left a map of the path visible to anyone looking, allowing them to figure out the secret route in seconds. This was a huge blow, as it meant the most promising "quantum-proof" lock was actually broken. Since then, scientists have been frantically trying to build new bridges that hide the map better. Some tried to cover the map with a blanket (masking), while others tried to build the bridge out of different materials. The big question remained: Can we build a bridge that is both unbreakable and fast enough to use in the real world?

This paper, titled "POKEx," steps into that chaotic construction site to test a new, shiny bridge design called POKÉ. The authors, Hyeonhak Kim and Suhri Kim, decided to turn the POKÉ encryption method into a full key-exchange system (which they call POKEx) and race it against the other top contenders trying to fix the broken SIDH bridge. They didn't just guess; they built working versions of these systems and timed them on a powerful computer. Their main finding is that POKEx is currently the fastest and most efficient of all the isogeny-based bridges. In their tests, it was about 21 times faster than the next best alternative (terSIDH) and nearly 65 times faster than another popular design (CSIDH). While it's still slower than some other types of quantum-safe locks, its speed and tiny size make it a very promising candidate for the future, offering a way to keep our digital secrets safe without slowing down the internet.

The Story of the Broken Bridge and the New Solution

To understand why this paper matters, we first need to look at the "bridge" problem. In the world of cryptography, a "key exchange" is like two people agreeing on a secret password without ever saying it out loud. For a long time, the SIDH system was the star player. It used supersingular elliptic curves—think of these as complex, wiggly shapes in a mathematical universe. The magic of SIDH was that it used "torsion points," which are like specific landmarks on these curves, to build the bridge. The system was so efficient that it had small keys (the digital equivalent of a tiny, lightweight lock) and was very fast.

However, the SIDH bridge had a fatal flaw. To build the bridge, the system had to publish some information about the landmarks (torsion points) it used. In 2023, Castryck and Decru found a way to use these published landmarks, combined with a clever mathematical trick called "Kani's glue-and-split," to reconstruct the secret path. It was like leaving a trail of breadcrumbs that led straight to the treasure. Once this attack was discovered, SIDH was considered broken and removed from the list of candidates for the future of internet security.

The Race to Fix the Bridge

After SIDH fell, the cryptography community didn't give up. They started building new bridges to replace it. Some tried to hide the landmarks by covering them with random noise (a method called M-SIDH). Others tried to change the shape of the bridge entirely by using "artificial orientation" (terSIDH). There was also CSIDH, a different type of bridge that wasn't affected by the same attack but had its own speed issues.

The problem was that these new bridges were either too slow or too big. Covering the landmarks with noise required much larger numbers to stay secure, which made the locks heavy and slow to use. Changing the shape of the bridge (terSIDH) helped, but it still had variations in speed that could be dangerous. The community needed a solution that was both secure and fast.

Enter POKEx: The Speed Demon

This is where the paper's new hero, POKEx, enters the scene. POKEx is based on a scheme called POKÉ, which was proposed recently by Basso and Maino. The authors of this paper took POKÉ and turned it into a full key-exchange system, complete with all the necessary steps to generate keys and exchange secrets safely.

The secret sauce of POKEx is how it handles the "landmarks." Instead of just using one-dimensional paths like the old SIDH, POKEx uses a "two-dimensional representation." Imagine trying to cross a river. SIDH was like walking on a single plank. If someone saw where you stepped, they could figure out your path. POKEx, however, is like walking on a grid of planks where you can move in two directions at once. This makes the path much harder to guess. Furthermore, POKEx uses a special type of math field (a prime number of the form $2^a3^b5^c-1$) that allows for very fast calculations, unlike the other new bridges that had to use much larger, slower numbers.

The Big Showdown: What the Numbers Say

The authors didn't just talk about POKEx; they put it to the test. They built software to run POKEx alongside the other top contenders: M-SIDH, terSIDH, and CSIDH. They set them all to the same security level (NIST security level 1, which is the standard for protecting top-secret government data) and timed how long it took to exchange a key.

The results were striking.

• M-SIDH was the slowest of the bunch, taking nearly 190 seconds to do what POKEx did in a fraction of a second. The authors noted that this makes M-SIDH impractical for real-world use.
• terSIDH was much faster than M-SIDH but still took about 6.5 seconds.
• CSIDH took about 20 seconds.
• POKEx, however, finished the job in just 306.95 milliseconds (about 0.3 seconds).

To put this in perspective, POKEx was 21.21 times faster than terSIDH and 64.97 times faster than CSIDH. This makes POKEx the current champion of isogeny-based key exchange.

Is It Perfect?

The paper is careful not to call this a "perfect" solution. While POKEx is the fastest among the isogeny bridges, it is still much slower than other types of quantum-safe locks, like ML-KEM (which took only 0.10 milliseconds in the test). However, the authors point out a crucial trade-off. ML-KEM is fast, but its "locks" (public keys and ciphertexts) are huge, taking up a lot of space on the internet. POKEx, on the other hand, has very small keys (only 324 bytes for the public key), which means it uses less bandwidth. In a world where internet speed and data limits matter, this small size is a massive advantage.

The Bottom Line

This paper shows that while the old SIDH bridge is broken, the road to a new, safe bridge is open. POKEx is currently the most promising candidate in the isogeny family, offering a rare combination of high speed and small size. It proves that we can build quantum-resistant locks that don't slow down our digital lives. While it still needs more work to catch up to the speed of other quantum-safe methods, its efficiency suggests it could become a vital tool for keeping our future internet secure, especially in situations where saving data space is just as important as saving time.