Cryptographically Secure Elliptic Curves

Overview

In order to communicate by using an EC cryptosystem, any two parties have to agree on elliptic curve domain parameters to identify a certain EC group E. The security of elliptic curve-based cryptosystems depends on the choice of the curve parameters, which should be chosen such that the ECDLP is resistant to all known cryptographic attacks we discussed in the previous lesson. Simultaneously, the curve parameters should allow efficient computation since the selection of the parameters influences the performance of the cryptosystem. Hence, the security and performance of ECC can only be assured by using appropriate curve parameters, thus their choice is crucial.

Furthermore, the curve parameters should be generated in a way that’s trusted by the cryptographic community.

There are mainly two kinds of curves in use:

1. Pseudo-random curves whose coefficients $A$ and $B$ were “generated from the output of a seeded cryptographic hash.” These curves are referred to as being “verifiably random,” which means that their parameters were computed verifiably at random by using a special algorithm and thus allow verification that the coefficients $A$ and $B$ were indeed generated through that method if the seed value and the algorithm are known.
2. Special curves whose coefficients and underlying field have been selected to optimize the efficiency of the elliptic curve operations.

These curves can be defined either over the prime field $\mathbb{F}_{p}$ or the binary field $\mathbb{F}_{p^{m}}$ for $m \geq 2$. In the following sections, we give an introduction to the requirement of the domain parameters in order to form robust cryptographic curves (Ethan Heilman et al. (2015)Ethan Heilman, Alison Kendler, Aviv Zohar, and Sharon Goldberg. Eclipse attacks bitcoin’s peer-to-peer network. In Proceedings of the 24th USENIX Conference on Security Symposium, SEC’15, pages 129-44, Berkeley, CA, USA, 2015. USENIX Association.).