Polynomial time attack reveals keys in elliptic code cryptosystems
A Polynomial-Time Attack on the McEliece Cryptosystem on Elliptic Codes with Arbitrary Divisors
Information Theory
Summary
The McEliece cryptosystem is a way to keep information safe using complex math from geometry, but some versions can be cracked by clever methods. The authors show a new attack that can find secret keys quickly when the system uses elliptic codes, even with any kind of settings. Their method needs some small extra clues but can be made stronger to need no extra clues at all, making the cryptosystem much less secure than previously thought.
What this means in practice
- •For cryptography engineers: Evaluate and avoid using vulnerable elliptic code parameters when designing secure McEliece-based encryption systems to prevent efficient key recovery.
- •For cybersecurity auditors: Identify cryptographic implementations at risk from structural attacks exploiting elliptic codes with arbitrary divisors and flag them for remediation.
Authors
Artyom Kuninets, Ekaterina Malygina, Evgeniy Melnichuk
Abstract
The McEliece cryptosystem based on algebraic geometry codes has been proposed as a way to reduce the key size of code-based cryptography, but several structural attacks have demonstrated the vulnerability of particular families of algebraic geometry codes. Despite this, until recently, there remained schemes and parameter sets that were not vulnerable to any known attack. We propose a new structural attack with ``hints'' that applies to elliptic codes with arbitrary effective divisors. In particular, we prove that, given the elliptic curve, the public generator matrix, and three points from the evaluation divisor, the entire divisor can be recovered in polynomial time, independently of the number of errors used in the cryptosystem. The attack requires $\mathcal{O}(k^2n^2+|\mathcal{E}(\mathbb{F}_q)|+n)$ operations in $\mathbb{F}_q$ and succeeds with overwhelming probability, after which the second divisor is recovered in $\mathcal{O}\!\left(k^2n^2 + (|\mathcal{E}(\mathbb{F}_q)|-n)n^2\right)$ operations. We further propose an optimized version of the attack that requires no additional information at all. Exploiting the action of the automorphisms of the curve, the three known points are replaced by the enumeration of a single pair of field elements, which yields an equivalent key on the given public curve in $\mathcal{O}\!\left(k^2n^2 + q^2 + (|\mathcal{E}(\mathbb{F}_q)|-n)n^2\right)$ operations on average.