Elliptic Curve PKC and Key Sizes
Fast Crypto using Hyperelliptic Curves — Part One
Brief Introduction
Public key cryptography protocols (PKC protocols) based on the group of points over an elliptic curve have been utilized for many applications in recent years. Several popular secure channel and authentication services like PGP, TLS and SSH use algorithms based on elliptic curves today. Blackberry (Research in Motion, at the time) was the first large scale adopter of elliptic curve cryptography (ECC), and helped bring ECC into mainstream back in the 2000’s. More recently, cryptographic currencies — a type of currency based on blockchain technology, universally implement the elliptic curve digital signature algorithm (ECDSA) to authenticate transactions between users in the network.
What do these applications have in common? All benefit heavily from the smaller key sizes provided by elliptic curve based PKC protocols. For example, every transaction that is stored on a cryptocurrency’s blockchain requires a digital signature to authenticate the transaction — the public key used in the digital signature is stored along side the transaction.
Trap Door Functions for PKCs
The size of keys used in PKC protocols directly correspond to the security against brute force attacks — simply guessing through all possibilities.
Ideally a PKC protocol is designed in a way such that no algorithm (or less formally no “attack”) can do better than brute force. Such a feat has only been achieved for symmetric cryptographic protocols like AES, but is impossible for any PKC protocol.
Why? The security properties of a PKC protocol are based on a trap door function defined over a finite group. Similar to lobster traps, one-way mirrors and actual trap doors, the idea is that the function is easy to compute one way, but extremely hard to reverse. This translates to: it is easy to encrypt, but hard to figure out the secret for decryption.
Most PKC protocols used today implement trap door functions based on two different but related hard problems: factoring and the discrete log problem (DLP). In the following, we focus our attention on two instances of the discrete log problem, the integer DLP and elliptic curve DLP — to better compare between traditional and elliptic curve based PKCs. Note that factoring is strongly related to the integer DLP, meaning that breaking one implies breaking the other, and vice versa.
The following table summarizes some similarities and differences between the Integer and Elliptic Curve DLPs. The composition operation in a finite group is a fundamental operation of the group applied in sequence to perform an encryption. Notice that in both cases of the DLP, the values used when computing encryption are bound by a large maximum number p. The key size of a PKC protocol based on either instance of DLP directly correlates to the size of this maximum value p.
How Attacks on DLP Affect the Key Size
There exists a completely general algorithm (or attack) called “Pollard’s Rho Algorithm” for solving the DLP that works in any finite group setting. On average, Pollard’s Ro Algorithm only requires a square root of the computational steps that a brute force attack would require in order to solve the DLP. Pollard’s Rho Algorithm effectively forces key sizes to be doubled in length, in order to achieve the same desired security.
The “Generalized Number Field Sieve Algorithm”, or GNFS Algorithm, can solve trapdoor functions used in PKC protocols even faster, but is not general. The GNFS algorithm can only be used to solve the DLP (and factoring) in finite groups for which group elements have a well defined size. For example, in integer groups, the element 5 is bigger than 3, 10001 is bigger than 53 and 7 is smaller than 23. All traditional (non elliptic curve) PKC protocols use finite groups that fall into this category. The GNFS algorithm requires exponentially less computational steps than Pollard’s Rho Algorithm to solve the Integer DLP or factoring, ballooning key sizes greatly.
Luckily, there is no well defined way to compare the size of points on elliptic curves and therefore the GNFS attack does not apply. The table below shows the inherent benefit in key sizes when using elliptic curve based protocols.
For example, in order to maintain similar effective security, compare a digital signature scheme using RSA (based on Factoring Modulus) against ECDSA (based on Elliptic Curve). The keys are several times larger and the disparity in key size grows exponentially with the effective (symmetric) security.
The main takeaway is: public key cryptographic protocols based on elliptic curves are more robust and require vastly smaller keys to obtain similar security levels as in traditional PKC protocols.
Can we do better?
As far as key sizes go, elliptic curve based PKC protocols seem to be the best choice, but can they be improved upon? In terms of key length, the short answer is no. Pollard’s Rho attack is general and applies to any setting PKCs are based on.
On the other hand, at equivalent security levels, encryption and decryption efficiency has been improved upon for PKC protocols based on generalizations of elliptic curves called Genus 2 Hyperelliptic curves.
In part two of this series, we introduce hyperelliptic curves and discuss the merits of using genus 2 hyperelliptic curves for PKC protocols. Links to the other parts of this series will be posted below.
