Beyond RSA: A New Path to Post-Quantum Encryption

by

Author: Denis Avetisyan

Researchers detail a novel cryptographic scheme leveraging advanced mathematical structures to secure communications against future quantum computer attacks.

The isogeny-based cryptosystem exhibits distinct power consumption signatures during key generation, encryption, and decryption-revealing algorithmic stages as traceable peaks at $240 \text{MHz}$-and suggesting opportunities for side-channel analysis or hardware optimization.
The isogeny-based cryptosystem exhibits distinct power consumption signatures during key generation, encryption, and decryption-revealing algorithmic stages as traceable peaks at $240 \text{MHz}$-and suggesting opportunities for side-channel analysis or hardware optimization.

This review explores an isogeny-based key encapsulation mechanism utilizing Engel expansions and p-adic arithmetic, optimized for embedded systems like the ESP32.

The demand for compact and efficient post-quantum cryptography clashes with the computational overhead of many promising candidates. This paper introduces ‘Engel p-adic Isogeny-based Cryptography over Laurent Series: Foundations, Security, and an ESP32 Implementation’, a novel isogeny-based key encapsulation mechanism (KEM) that encodes elliptic curve data using Engel expansions over p-adic Laurent series. This approach compresses key sizes to ~1.1-16.9 kbits and enables efficient fixed-precision arithmetic suitable for resource-constrained embedded systems, demonstrated via an ESP32 implementation. Could this framework represent a viable path toward scalable and secure IoT deployments in a post-quantum world?

Decoding the Quantum Threat: A New Cryptographic Imperative

The bedrock of modern digital security, public-key cryptography – encompassing widely used algorithms like RSA and Elliptic Curve Cryptography (ECC) – faces an unprecedented threat from the advent of quantum computing. These algorithms rely on the computational difficulty of certain mathematical problems, such as factoring large numbers or solving the discrete logarithm problem. However, quantum computers, leveraging principles of quantum mechanics, can execute algorithms – notably Shor’s algorithm – that solve these problems with exponentially increased efficiency. This means a sufficiently powerful quantum computer could break the encryption protecting sensitive data transmitted across the internet, compromising financial transactions, government communications, and personal privacy. The looming possibility of “crypto-apocalypse” is driving urgent research into new cryptographic methods capable of withstanding attacks from both classical and quantum adversaries, fundamentally reshaping the landscape of digital security.

The looming potential of quantum computers to break widely used public-key cryptographic systems has spurred intensive research into Post-Quantum Cryptography (PQC). Current encryption methods, such as RSA and Elliptic Curve Cryptography, rely on the computational difficulty of certain mathematical problems – problems quantum computers, leveraging algorithms like Shor’s, are uniquely positioned to solve efficiently. PQC, therefore, focuses on developing and standardizing cryptographic algorithms that are believed to be secure against both classical computers and foreseeable quantum attacks. These algorithms draw upon different mathematical foundations, including lattice-based cryptography, code-based cryptography, multivariate cryptography, and hash-based signatures, aiming to provide a long-term security solution in a post-quantum world and ensure the continued confidentiality and integrity of digital communications and data.

Supersingular elliptic curves represent a significant approach in the development of post-quantum cryptography due to their unique mathematical properties. Unlike traditional elliptic curves used in current cryptographic systems-which are vulnerable to Shor’s algorithm on a quantum computer-supersingular curves offer a different algebraic structure that resists known quantum attacks. This resilience stems from the difficulty in solving the elliptic curve discrete logarithm problem on these curves, even with quantum computation. Several leading PQC candidates, including SIKE and some variants of key encapsulation mechanisms, leverage supersingular isogenies-mappings between these curves-to construct cryptosystems. While not a panacea, the inherent difficulty of problems involving supersingular elliptic curves positions them as a crucial element in securing digital communications against the looming threat of quantum computers, offering a pathway to algorithms that maintain confidentiality and integrity in a post-quantum world. The focus remains on refining these methods to achieve both strong security and practical efficiency for widespread implementation.

An ESP32 node sequentially performs encryption, decryption, and metric collection as part of a single-board cryptographic process.
An ESP32 node sequentially performs encryption, decryption, and metric collection as part of a single-board cryptographic process.

Isogeny-Based Cryptography: A Path Through Complexity

Supersingular Isogeny Diffie-Hellman (SIDH) is a post-quantum key exchange protocol founded on the mathematical hardness of computing isogenies between supersingular elliptic curves defined over finite fields. In SIDH, two parties each select a private key, which is an integer $d$. They then compute a corresponding public key, which is a supersingular elliptic curve $E$ and a point $Q$ of prime order $l$ on $E$, obtained by applying an isogeny of degree $l$ to a common starting curve. The key exchange derives a shared secret by computing isogenies using the received public keys. The security of SIDH relies on the presumed difficulty of the Isogeny Path Problem – finding a path of isogenies between two given supersingular elliptic curves.

Isogeny-based cryptography, specifically schemes like SIDH, presents a favorable trade-off between security and performance for devices with limited resources. Traditional public-key cryptosystems, such as those based on RSA or ECC, require key sizes of at least 2048 bits to achieve security comparable to AES-128. In contrast, SIDH can achieve similar security levels with key sizes ranging from 480 to 768 bits. This reduction in key size translates directly to lower bandwidth requirements for key exchange and reduced storage needs on constrained devices, like those used in IoT applications or embedded systems. Furthermore, the computational cost of SIDH key exchange, while involving more complex operations than ECC, remains competitive and can be efficiently implemented in software, offering a viable alternative where hardware acceleration is unavailable or impractical.

The security of the Supersingular Isogeny Diffie-Hellman (SIDH) protocol depends on the computational complexity of finding an isogeny – a non-singular homomorphism between elliptic curves – given only the starting and ending curves. Navigating the space of supersingular elliptic curves to compute these isogenies is facilitated by algorithms like Engel expansion. This method represents an isogeny as a sequence of operations corresponding to adding or subtracting torsion points on intermediate curves. Specifically, Engel expansion allows computation of a large isogeny degree, $l$, by iteratively applying a 2-torsion point addition or subtraction $l$ times, enabling efficient calculation of isogenies of high degree without explicitly computing all intermediate curves. This process is crucial for key exchange as it allows parties to generate a shared secret through the exchange of intermediate curve data derived from isogeny computations.

P-adic Arithmetic: Engineering Precision in a Quantum Age

PPAdic Arithmetic utilizes fixed-precision limbs – essentially, representing numbers as a sum of powers of a chosen prime $p$ multiplied by coefficients within a finite field – to facilitate arithmetic operations. This approach contrasts with standard floating-point or arbitrary-precision methods by bounding the size of intermediate values. The fixed-precision nature allows for the creation of highly structured kernels optimized for specific hardware architectures, notably SIMD instructions and GPUs. By decomposing computations into operations on these fixed-size limbs, PPAdic Arithmetic enables efficient implementations with predictable performance characteristics and reduced memory access overhead, contributing to overall computational speedups in applications such as isogeny-based cryptography.

Isogeny computations, central to certain cryptographic protocols, benefit substantially from representing parameters as Laurent series within the framework of p-adic arithmetic. This approach allows for the efficient computation of functions involving these parameters by truncating the series to a fixed precision, effectively working with finite approximations. The use of p-adic arithmetic enables the replacement of floating-point operations with fixed-precision arithmetic on polynomial rings, which are better suited for hardware acceleration and parallelization. Benchmarks demonstrate that this technique provides significant speedups-ranging from 2x to 10x-compared to traditional methods reliant on floating-point representation and manipulation of elliptic curve parameters, particularly for computations involving isogeny classes of large characteristic.

PPAdic Arithmetic is designed to facilitate ConstantTimeExecution, a critical property for cryptographic security. This means that all arithmetic operations, regardless of the input data, take a predictable and consistent amount of time to complete. This predictability is essential to mitigate side-channel attacks, particularly timing attacks, which exploit variations in execution time to infer sensitive information such as private keys. Verification of ConstantTimeExecution within PPAdic Arithmetic has been achieved through deterministic power traces, demonstrating that power consumption during computations is independent of the processed data and therefore resistant to analysis via power-based side channels.

Relative execution time improvements demonstrate the efficiency of frequency scaling for both encryption and decryption processes.
Relative execution time improvements demonstrate the efficiency of frequency scaling for both encryption and decryption processes.

SIKE: A Practical Key Encapsulation Mechanism for the Quantum Future

Supersingular Isogeny Key Encapsulation (SIKE) represents a practical advancement in post-quantum cryptography, functioning as a concrete Key Encapsulation Mechanism (KEM) designed to establish secure communication channels. Building upon the mathematical foundations of Supersingular Isogeny Diffie-Hellman (SIDH), SIKE translates theoretical cryptographic principles into a usable protocol. This process involves generating a shared secret between communicating parties through the computation of isogenies – special mappings between elliptic curves. The security of SIKE hinges on the difficulty of finding isogenies between carefully chosen supersingular elliptic curves, providing a potential defense against quantum computers that threaten currently widely-used public-key cryptosystems like RSA and ECC. By establishing a secure key exchange, SIKE enables the encryption and decryption of sensitive data, offering a path toward long-term confidentiality in a post-quantum world.

Supersingular Isogeny Key Encapsulation (SIKE) achieves practical performance through innovative mathematical techniques. Specifically, the implementation utilizes $p$-adic arithmetic, which allows for efficient computation with large numbers by representing them in a different number system, and Engel expansion, a method for constructing rational numbers with desirable properties for cryptographic operations. These approaches circumvent the computational bottlenecks often associated with elliptic curve cryptography, leading to a Key Encapsulation Mechanism (KEM) that offers a compelling balance between security and speed. By optimizing these core calculations, SIKE positions itself as a viable post-quantum cryptographic solution capable of competing with existing standards in terms of practical deployment and resource utilization.

A functional implementation of the SIKE post-quantum cryptographic scheme was successfully demonstrated on an ESP32 microcontroller, revealing key characteristics of its performance profile. Power trace analysis of the key generation process exhibited a distinctly ‘narrow, tall’ peak, indicative of rapid computation and a peak power draw of approximately 350mW. This suggests that the cryptographic operations themselves are highly efficient; measured latency was found to be predominantly influenced by network communication overhead, rather than the computational demands of the SIKE algorithm itself. These findings highlight the feasibility of deploying post-quantum cryptography on resource-constrained embedded devices, paving the way for secure communication in the emerging landscape of quantum-resistant security.

Power analysis reveals distinct consumption patterns for key generation, encryption, decryption, and complete cryptographic processing at 8080MHz.
Power analysis reveals distinct consumption patterns for key generation, encryption, decryption, and complete cryptographic processing at 8080MHz.

The pursuit of cryptographic resilience, as demonstrated by this exploration of Engel p-adic isogeny-based cryptography, echoes a fundamental tenet of mathematical inquiry: the necessity of rigorous testing. This work doesn’t simply apply existing frameworks, but actively deconstructs and rebuilds them for efficiency within the constraints of embedded systems. As Paul Erdős famously stated, “A mathematician who doesn’t enjoy thinking about unsolved problems is like a shoemaker who doesn’t enjoy making shoes.” The presented scheme, by challenging conventional implementations and leveraging pp-adic arithmetic, exemplifies this spirit. The core idea – optimizing key encapsulation for resource-constrained devices – isn’t about finding the easiest path, but about systematically dismantling assumptions to reveal and address hidden vulnerabilities, much like a relentless search for elegant solutions to unsolved problems.

What Lies Beyond?

The pursuit of post-quantum cryptography often feels like rearranging deck chairs on the Titanic, a frantic effort to secure communications while the fundamental assumptions of decades crumble. This work, leveraging the curious interplay of isogenies, Engel expansions, and the almost-forgotten world of p-adic numbers, at least attempts a novel rearrangement. The elegance of mapping a computationally hard problem onto the structure of these mathematical objects is undeniable, but true security isn’t found in obscurity, it’s found in withstanding scrutiny. The current implementation, while demonstrating feasibility on embedded systems, merely invites a more focused assault.

The real challenge isn’t simply achieving acceptable key encapsulation speeds on an ESP32, it’s understanding the subtle vulnerabilities inherent in reducing these complex computations to finite fields. Side-channel resistance is a moving target, and the optimization strategies employed here likely introduce new avenues for attack. Future work must move beyond mere implementation and delve into a rigorous analysis of the scheme’s algebraic structure – a dissection, if you will – to expose any hidden weaknesses.

One wonders if the fascination with number theory as a source of cryptographic primitives isn’t a form of intellectual comfort. It’s aesthetically pleasing, certainly, but the universe doesn’t care about aesthetics. Perhaps the most fruitful avenue for exploration lies not in refining existing schemes, but in abandoning the assumption that security must be built upon mathematical difficulty. What if the true solution is not to hide the key, but to render it irrelevant?

Original article: https://arxiv.org/pdf/2511.20533.pdf

Contact the author: https://www.linkedin.com/in/avetisyan/

See also:

2025-11-26 15:59