Elliptic curves are widely used in cryptographic algorithms for key exchange and blockchain applications. In addition, there is growing interest in moving to more efficient options, such as hyperelliptic curves. The jury is still out when it comes to deciding if hyperelliptic curves make the computations faster.
Now a collaborative team of researchers from across Technology Innovation Institute (TII) in the UAE, the National Polytechnic Institute of Mexico, and Institut Polytechnique de Paris have discovered how a new mathematical technique could both break and build these hyperelliptic curves more efficiently.
Jesús-Javier Chi-Domínguez Senior Cryptographer, said, “We discovered how a family of algorithms is less secure than people had assumed earlier.”
Modern cryptographic libraries use elliptic curves to encrypt public keys and signatures that can be decrypted using a shared key. There are two broad classes of elliptic curves built on binary and prime numbers. The binary fields tend to be faster because they are better aligned with the logic built into computers. The prime fields must first be translated into binary numbers and are not as computationally efficient.
Other researchers have discovered various ways of translating the elliptic curves generated by these tools into another form called a hyperelliptic curve. While more complex in a sense, it makes it easier to find relationships between the points. This technique was called GHS Weil descent, in honor of the researchers that found it. These approaches worked best on some but not all binary elliptic curves. As a result, some researchers have tended to avoid binary elliptic curve techniques in many applications.
Discovering hidden simplicity
An endomorphism is a broad scientific term to describe various approaches used in translating a mathematical group, module, ring, or vector into another form. Endomorphism techniques are often leveraged to carry out faster scalar point multiplication on elliptic curves.
Elliptic curve cryptography security is derived from the fact that the fastest search algorithm on the set of private keys, has exponential complexity. The Weil decent technique reduces that in some cases, whereby a particular curve may be converted into a form that only grows with sub-exponential complexity.
The researchers discovered that a specific type of endomorphism, called GLS endomorphism, could speed up GHS Weil calculations. In addition, it could also apply to a broader range of binary elliptic curves compared to previous techniques. The new techniques will make it easier for researchers to detect these less secure implementations more quickly.
Chi-Domínguez said, “GLS was previously used for constructing faster cryptography. We showed how it could be used to carry out faster attacks.”
Seeding the future of endomorphism research
Chi-Domínguez said this work was designed as a proof of concept to demonstrate how the new algorithm worked in practice. The main result is that it shines a light on some unforeseen weaknesses cryptographers need to consider in designing safer cryptography.
The team wrote a program capable of breaking binary field elliptic curves with 2155 elements in a week that was 8-times faster than the previous state-of-the-art attacks. It was coded in Magma, a programming language designed to simplify mathematical research. An optimized version of their algorithm coded in the C programming language might be 80-times faster than the state-of-the-art algorithms.
Thus far, they have only focused on binary elliptic curves. Next, Chi-Domínguez is hoping to explore how similar techniques may be applied to prime field elliptic curves. Down the road, he expects these same techniques will also help researchers discover ways that related endomorphism functions could be used to speed up cryptographic calculations in a safe manner.
One exciting possibility might be to discover and map out a family of endomorphisms. The current research focused on one endomorphism technique based on Weil descent. Combining a much larger family of endomorphisms could substantially accelerate the attacks on (hyper)elliptic curves. He also believes that these techniques could eventually expand the range of techniques available for implementing quantum-resistant primitives.
About Technology Innovation Institute (TII)
Technology Innovation Institute (TII) is the dedicated ‘applied research’ pillar of Advanced Technology Research Council (ATRC). TII is a pioneering global research and development centre that focuses on applied research and new-age technology capabilities. The Institute has seven initial dedicated research centres in quantum, autonomous robotics, cryptography, advanced materials, digital security, directed energy and secure systems. By working with exceptional talent, universities, research institutions and industry partners from all over the world, the Institute connects an intellectual community and contributes to building an R&D ecosystem reinforcing Abu Dhabi and the UAE’s status as a global hub for innovation.
For more information, visit www.tii.ae
