Cryptographic Video Games

Jul 2024

Massimo Ostuzzi

Cheat Codes are just like Trapdoors

David has just got enrolled in his math master’s degree at the most prestigious university in his country. Despite being brilliant at school, he doesn’t enjoy studying very much. Instead, he loves spending his time playing video games. Every day after class, he rushes home, grabs a snack, and immerses himself in the latest adventures on his console. His favourite game is a racing game, filled with hidden features and challenging hurdles.

One day, while browsing the internet for the latest updates about his game, David stumbled upon a forum discussing some weird game mechanic, called cheat codes. Intrigued, he read through the posts and discovered a code ensuring doubled speed in all game scenarios. Excited, he scribbled the code on a piece of paper and entered it into his game.

To his amazement, it worked! Suddenly, his race car could run unprecedentedly fast, allowing him to get incredible rewards. David’s eyes widened with excitement as he became more and more comfortable with the new pace and explored parts of the game he had never reached before. The cheat code felt like a secret superpower, giving him access to a game experience his friends couldn’t even imagine.

A few days later, during cryptography class, Prof. McCipher was explaining concepts like encryption and decryption, talking about how messages can be hidden and deciphered. Then she mentioned something that immediately caught David’s attention: cryptographic trapdoors.

Prof. McCipher explained:”A cryptographic trapdoor is like a secret shortcut. Imagine you have a special key that lets you unlock a easy path, while everyone else is forced to go through a though one. This key is the trapdoor—it gives you access to something hidden or protected.”

David’s mind raced back to his cheat code video game experience. Once the class was over, he approached Prof. McCipher:”Excuse me, Prof. McCipher, cryptographic trapdoors are just like a cheat code in a video game, aren’t they?”

Prof. McCipher smiled warmly. “That’s a brilliant analogy, David! Just like a cheat code gives you special powers in the game, a cryptographic trapdoor allows someone with the right knowledge to unlock something quickly, while others can’t.” It turns out Prof. McCipher is a video game fun as well.

David was thrilled. He’d discovered a whole new and intriguing way to think about his favourite hobby. The world of video games and cryptography suddenly felt connected in his mind. He started enjoying cryptography, realising that studying this subject and playing video games are two activities not that far apart from each other.  He began to see patterns and connections everywhere, blending his love for gaming with a newfound interest in the secrets of encryption. And as he played his games, he couldn’t help but smile, knowing that the cheat codes he used were just like the magical keys of the cryptographic world.

Isogeny Trapdoor

Studying cryptography one may encounter many trapdoors, useful to create a huge variety of protocols. Usually, trapdoors rely on hardness assumptions, namely computational problems considered hard to solve.

An example of a quantum-resistant hardness assumption is the Supersingular Isogeny Problem (SIP), which, in its natural form, involves discovering an isogeny between two specified supersingular elliptic curves. Both classical and quantum algorithms need an exponential number of steps in the field’s characteristics to achieve a solution.

Endomorphisms, isogenies mapping a curve to itself, play a crucial role in this setting. The collection of all such mappings forms the endomorphism ring. Another significant challenge involving supersingular elliptic curves is the Endomorphism Ring Problem (ERP), which entails identifying the endomorphism ring for a given curve. Like SIP, solving ERP with the best algorithms requires exponential time.

A breakthrough in cryptographic circles reveals that knowing the endomorphism rings of both the source and target elliptic curves enables solving SIP in classical polynomial time. This insight effectively creates a cheat code… hmm… sorry… a trapdoor.

David wants to master the SIP video game. After browsing the internet again, he finds the appropriate cheat code! Armed with knowledge of the endomorphism rings of the two supersingular elliptic curves, David easily cracks the challenge, outpacing all his friends and identify the isogeny in record time.

To conclude, it is worth mentioning that Wesolowski in 2021 proved SIP and ERP are actually equivalent, under just one highly plausible heuristic assumption.