Multiple point compression on elliptic curves

Abstract

Point compression is an essential technique to save bandwidth and memory when deploying elliptic curve based security solutions in wireless communication systems. In this contribution, we provide new linear algebra (LA) based compression algorithms for multiple points on elliptic curves, that are compression algorithms which only make use of LA (with a constant number of field multiplications and at most one inversion, with no quadratic or higher degree polynomial root finding). In particular, we extend the results of Khabbazian et al. (IEEE Trans Comput 56(3):305–313, 2007) to four (resp. five) points on elliptic curves by generically storing five (resp. six) field elements and provide an asymptotic generalization to any number n of points on a curve $y^2=f(x)$ by generically storing $n+1$ values.

1 Introduction

The rapid progress in wireless communication systems, personal communication systems, and smartcard technologies is impacting people’s life at a staggering rate and in significant ways. New security challenges have to be solved in order to protect those communication systems from malicious attacks. Elliptic curve cryptosystems (ECC) provide efficient and robust solutions to many of the existing security issues in wireless communication systems [9, 10, 32]. When implementing ECC based cryptographic protocols on smart devices such as RFID tags, smart cards, and wireless sensor nodes, it is often necessary to transmit or store points on elliptic curves. Since those smart devices usually have constrained resources in terms of computational capabilities, memory, and bandwidth, it is desirable to represent a point in a compact form.

Point compression is a technique that allows points on an elliptic curve to be represented with fewer bits of data, thereby reducing both the storage space on smart devices as well as the amount of data that needs to be transmitted to and from those devices [5]. A single point compression usually involves solving a quadratic equation over a finite field, which might be computationally expensive for low-cost smart devices. To overcome the aforementioned issue, Khabbazian et al. [20] proposed a double and a triple point compression schemes, respectively, which allow a compact representation of two or three points on an elliptic curve without the computational cost associated with ordinary single point compression. Moreover, the authors pointed out that the point compression can be used to reduce the required bandwidth in the case of the random point multiplication. We notice that double point compression technique can also be directly applied to some pairing-free identity-based signature schemes (see [8, 17] for example) to reduce the required bandwidth during wireless transmission. Additional applications of various point compression techniques include the following.

Message authentication in vehicular ad hoc networks (VANETs)

• In VANETs, vehicles are equipped with Dedicated Short Range Communication (DSRC) capabilities to enable vehicles’ On-Board Units (OBUs) communicate wirelessly with other vehicles’ OBU or Road Side Units (RSUs) [26]. Safety provision is one of the core goals of VANET deployment. To this end, an OBU periodically broadcasts traffic-related messages to surrounding vehicles in an authenticated manner. Elliptic curve cryptography and digital certificates have been employed to ensure the authenticity of broadcast safety messages [19]. To save the communication bandwidth in VANETs, public keys in digital certificates are stored and transmitted in compressed form. For verifying digital signatures, an OBU needs first to decompress the received public keys, followed by the verification of multiple digital signatures. Multiple point compression can be directly applied in this case to accelerate the point decompression for multiple public keys, which provides an efficient method to achieving a good trade-off between decompression performance and storage requirement.

Multi-user broadcast authentication in wireless sensor networks (WSNs)

• Multi-user broadcast is an efficient and common communication paradigm in WSNs, where multiple users disseminate messages (i.e., queries or commands) into networks for retrieving the information of their interest [25, 34]. Due to the constrained resources of wireless sensor nodes, elliptic curve cryptography and digital certificates are usually used to ensure the authenticity of the broadcast messages in WSNs [15]. Again, public keys of network users are stored in digital certificates in compressed form to save the energy consumption of sensor nodes. When receiving broadcast messages from multiple users, sensor nodes will verify both digital certificates and signatures. Application of multiple point compression technique enables sensor nodes to balance the performance for signature verifications and the memory footprint on wireless sensor nodes.

Countermeasures against attacks

• Nowadays ECDSA [3], ECDH [4] and other elliptic-curve based cryptographic algorithms are often implemented on secure devices such as smartcards. Such devices must be protected against side channel attacks and perturbation attacks.

• A well-known countermeasure against many side channel attacks is to use randomized projective coordinates. If a smartcard stores only x-coordinates of several points and the sum of their y-coordinates it is possible to randomize or to re-randomize the coordinates in an efficient manner with less field multiplications. The whole set of points will get a common randomly chosen z-coordinate.

• A classical countermeasure against perturbation attacks is the integrity check, such as a parity check or a CRC check. In the case when elliptic-curve points are compressed they can be stored in a smaller buffer and thus the checksum or the CRC value can be computed more efficiently [29].

Other potential applications

• The ciphertext of the ElGamal Elliptic Curve Cryptosystem [21] is a pair of points of an elliptic curve. Point compression may result in shorter ciphertexts, which is crucial for many applications.

• The internal state of some ECC-based pseudorandom generators includes two points of an elliptic curve. If the pseudorandom generator is rarely invoked it makes sense to store its state in a compressed form and decompress it when needed. In particular, the two-point compression method can be effective. An example of such a pseudorandom generator is Dual_EC_DRBG [27]. This pseudorandom generator has recently been deprecated by NIST due to certain security flaws [28]. The point compression techniques are likely to be applicable to the successors of Dual_EC_DRBG as well.

Considering potential applications of multiple point compression technique, we present new linear algebra (LA) based compression algorithms for multiple points on elliptic curves in this paper. Let us emphasize from the start that the goal of these new compression algorithms is not to reduce storage requirements by achieving a higher compression rate, but rather to trade current compression techniques with one which is asymptotically (in storing many points) almost as good and additionally achieves a superior decompression speed.

To this end, a four- and five-point compression scheme is proposed which further generalizes the Khabbazian et al. [20]. Our new compression algorithms only make use of basic linear algebra (multiplications, addition, subtractions and at most one division) and do not need to solve any quadratic or higher degree equations over finite fields. In particular, the number of equivalent basic field multiplications (without considering the division/inversion) is constant and does not increase with the field size. Let us note that the running time for one division is equivalent to finding one square root. However, the strength of our method is that k inversions can be combined into a single inversion and $3k-3$ multiplications  [11, Algorithm 10.3.4 p. 489 a.k.a. Montgomery’s trick], whereas several square root extractions cannot be combined into one modulo a constant number of multiplications.

The remainder of this paper is organized as follows. Section 2 briefly reviews the previous work for double and triple point compression schemes in [20], followed by the new four and five point LA based compression algorithm in Sect. 3. In Sect. 4, we generalize this method to an arbitrary number of points. Finally, Sect. 5 concludes this work.

2 Compression algorithms and previous work

For simplicity in this work we will restrict ourselves to curves over odd characteristic fields $\mathbb {F}$. Given a plane equation $y^2=f(x)$, where f is a polynomial in $\mathbb {F}[x]$ without multiple roots, we usually store a point $P_1=(x_1,y_1)$ by its coordinates (so called trivial, or no compression), otherwise by $x_1$ plus one extra bit and recovering $y_1$ by solving a quadratic equation in $\mathbb {F}$, using the bit to discriminate between the two solutions. The latter method requires less memory, but more resources to decompress the point in order to find all its coordinates. In particular solving a quadratic equation in $\mathbb {F}$ requires the equivalent of a field inversion, costing a number of field multiplications which increases linearly in the field bit size. For instance, solving $y^2 \equiv a \pmod p$ for $p\equiv 3 \pmod 4$ will entail computing $a^{(p+1)/4} \mod p$.

We are interested in this work to study compression-decompression algorithms which make use of a constant number of field operations (multiplications, additions and inversions, with inversions grouped into a single one), independently of the field size. These methods will typically make use of linear algebra only, therefore we are going to call them LA methods. We can distinguish between the following two flavours of compression-decompression algorithms:

• (1) LA compression, non-LA decompression (e.g. the classical method of storing $x_1$ and 1 bit, recover $y_1$ by solving a quadratic equation),

• (2) LA compression, LA decompression (fully LA).

Additionally, one could conceive of a non-LA compression, LA decompression algorithm, although we could not find any in the literature. Nevertheless, our new compression method below (see Sect. 2.2) for two points is a first step towards this paradigm of a slow compression and very fast decompression method.

In [20] a fully LA method is presented to compress $P_1, \dots ,P_n$ points when $n=2,3$. The object of the present article is to extend their work to all values of n less than the characteristic of the field and to present an efficient implementation of this when $n=4,5$.

We review the results of [20] here, in the case of fields of characteristic at least 5. Minor modifications can adapt this method to characteristic 2 and 3. Note that the exact performance improvement of multiple point compression technique over the traditional approach highly depends on the efficiency of solving a quadratic equation over finite fields (see Sect. 3.4 for more details).

2.1 Two-point compression

Given an elliptic curve $y^2=x^3+ax+b=f(x)$ and points $P_1=(x_1,y_1)$ and $P_2=(x_2,y_2)$, we can represent them in general by $(x_1,x_2, \alpha =y_1+y_2)$. Then

$$\begin{aligned} y_1 = \frac{\alpha }{2} + \frac{x_1-x_2}{8\alpha } \left( 3(x_1+x_2)^2+ (x_1-x_2)^2 +4a \right) \end{aligned}$$

and

$$\begin{aligned} y_2 = \alpha - y_1. \end{aligned}$$

This is easily seen by remarking that

$$\begin{aligned} y_1-y_2 = \frac{y_1^2-y_2^2}{y_1+y_2} = \frac{f(x_1)-f(x_2)}{\alpha } \end{aligned}$$

and knowledge of $\alpha =y_1+y_2$ will readily yield $y_1, y_2$ by linear algebra. This algorithm works, as long as $\alpha \ne 0$. This condition can be checked a priori before decompression by computing $y_i^2= f(x_i)$ and checking that $y_1^2\ne y_2^2$ (a stronger condition). Otherwise, if $y_1^2=y_2^2$, the compression algorithm stores $(x_1, x_2, y_1, b)$ where b is an extra bit to distinguish between the generic case and the exceptional case when $y_2=-y_1$. Two-point compression can thus be achieved by storing 3 field elements and up to one extra bit.¹

When $\alpha \ne 0$, the computational complexity of the decompression is $2M + 2S + I$.

2.2 Alternative two-point compression

We introduce new two-point compression algorithm which requires an inverse operation in compression part while decompression phase needs only multiplication and square operations.

In this case, points $P_1 = (x_1,y_1)$ and $P_2=(x_2,y_2)$ are represented by $\Big (A = \frac{x_{1}-x_{2}}{y_{1}-y_{2}}, B = y_{1}-y_{2}, x_{2}\Big )$. Decompression algorithm works as follows:

Since $x_{1}-x_{2} = AB$ we obtain $x_{1} = AB+x_2$.

Then, having two elliptic curve equations

$$\begin{aligned} y_{1}^{2}= & {} x_{1}^{3}+ax_{1}+b\\ y_{2}^{2}= & {} x_{2}^{3}+ax_{2}+b \end{aligned}$$

the following two expressions are derived:

$$\begin{aligned} y_{1}^{2}-y_{2}^{2}= & {} x_{1}^{3}-x_{2}^{3}+a(x_{1}-x_{2})\\ y_{1}+y_{2}= & {} \frac{x_{1}-x_{2}}{y_{1}-y_{2}}\big ((x_{1}-x_{2})^{2}+3x_{1}x_{2}+a\big ) = A\big ((x_{1}-x_{2})^{2}+3x_{1}x_{2}+a\big ) \end{aligned}$$

Since $y_1-y_2=B$, $y_1$ and $y_2$ are easily obtained by Linear Algebra:

$$\begin{aligned} y_{1}= & {} \frac{A\big ((x_{1}-x_{2})^{2}+3x_{1}x_{2}+a\big )+B}{2}\\ y_{2}= & {} y_1-B \end{aligned}$$

The overall computational cost of the algorithm is 3M+1S if multiplication by constant elements is disregarded. This algorithm does require an inverse operation in compression phase. However, decompression part needs only multiplication and square operations, which considerably reduces its computational complexity compared to previously described two-point decompression method.

The algorithm works when $y_1^2 \ne y_2^2$. In case $y_1^2 = y_2^2$, follow the compression algorithm described in the Sect. 2.1.

2.3 Three-point compression

In this case, the generic compression algorithm represents $P_i=(x_i,y_i)$ by $(x_1,x_2,x_3, \alpha =y_1+y_2+y_3)$. Decompression works as follows. Let

$$\begin{aligned} \beta = \alpha ^2 + y_3^2-y_1^2-y_2^2 = 2 (y_3+y_1)(y_3+y_2). \end{aligned}$$

Then

$$\begin{aligned} y_3 = \frac{\beta ^2 + 4\alpha ^2y_3^2- 4 y_1^2y_2^2}{4\alpha \beta } \end{aligned}$$

and since $y_1+y_2 = \alpha -y_3$ we recover $y_1, y_2$ by the previous two-point compression algorithm. We are in the generic case provided $\alpha \ne 0$ and $y_i^2\ne y_j^2$ for $1\le i<j\le 3$, in which case by the above $\beta \ne 0$. We look at the exceptional cases:

• (1) $y_i^2\ne y_j^2$ for $1\le i<j\le 3$ and $\alpha =0$. In this case, the compression part will store $(x_1, x_2, x_3, y_1+y_2)$. We can recover $y_1, y_2$ by the generic case of two-point compression and then $y_3=-y_1-y_2$.

• (2) Two squares are equal but not three. Without loss of generality, $y_1^2=y_2^2\ne y_3^2$. In this case, represent the three points as $(x_1,x_2,x_3, y_2+y_3,q_1)$, where $q_1\in \{0,1\}$. Decompression works out $y_2,y_3$ using generic two-point compression, and bit $q_1$ is used to tell if $y_1=y_2$ or $-y_2$.

• (3) $y_1^2=y_2^2=y_3^2$. In this case, store $(x_1,x_2,x_3,y_1,q_1,q_2)$, with $b_i\in \{0,1\}$. The bits are used to pinpoint the sign of $y_2$ and $y_3$ compared to $y_1$.

Three-point compression can thus be achieved by storing 4 field elements and up to 2 extra bits. As shown in [20], in the computational complexity in the generic case is $12M + 6S + I$.

We next present our generalization of this method to four points.

3 Four- and five-point compression

3.1 General idea

Let n be the number of points to be compressed and let $y_1, y_2, \ldots , y_n$ be the y-coordinates of these points. Denote

$$\begin{aligned} a_1= & {} y_1+y_2+\cdots +y_n, \\ a_2= & {} \sum _{1 \le i< j \le n} y_i y_j, \\&\ldots \\ a_n= & {} y_1y_2\ldots y_{n-1}y_n \end{aligned}$$

the elementary symmetric polynomials in the $y_i$’s. We want to express $y_i$ in terms of the $a_j$’s and the even powers of $y_i$, since we know the value $y_i^2=f(x_i)$.

Theorem 1

For even values of n the y-coordinates $y_1, \ldots , y_n$ can be generically expressed as follows:

$$\begin{aligned} y_i = \frac{a_n+y_i^2 a_{n-2}+ \cdots +y_i^{n-2} a_2+y_i^n}{a_{n-1}+y_i^2 a_{n-3}+ \cdots +y_i^{n-2}a_1},\quad i = 1, \ldots ,n. \end{aligned}$$

(1)

For odd values of n,

$$\begin{aligned} y_i = \frac{a_n+y_i^2 a_{n-2}+ \cdots +y_i^{n-1}a_1}{a_{n-1}+y_i^2 a_{n-3}+ \cdots +y_i^{n-3}a_2+y_i^{n-1}}, i = 1,\ldots ,n. \end{aligned}$$

(2)

Proof

We have

$$\begin{aligned} (x+y_1)\cdots (x+y_n) = x^n+a_1x^{n-1} + \cdots + a_{n-1} x + a_n . \end{aligned}$$

Letting $x=-y_i$, we get

$$\begin{aligned} 0=\,&a_n- y_i a_{n-1} + y_i^2 a_{n-2} - y_i^3 a_{n-3} +\cdots \\ =\,&a_n + y_i^2 a_{n-2} + \cdots -y_i (a_{n-1} + y_i^2 a_{n-3} + \cdots ) \end{aligned}$$

which is what we want. $\square$

We will not consider the exceptional situations when the denominators are equal to 0 (see Sect. 4 for a discussion of this).

3.2 Four-point compression

As a next step, we introduce a four-point compression algorithm based on Theorem 1. The compression algorithm represents the four points $P_i, i = 1, 2, 3, 4,$ by $(x_1, x_2, x_3, x_4, a_1 = y_1 + y_2 + y_3 + y_4)$. The decompression algorithm first retrieves $a_2, a_3, a_4$ and then uses the following equation to compute $y_i$’s:

$$\begin{aligned} y_i = \frac{a_4+y_i^2a_2+y_i^4}{a_3+y_i^2a_1},\quad \text {for} \quad i = 1,2,3,4. \end{aligned}$$

(3)

Our initial goal is to express the elementary symmetric polynomials $a_2, a_3$ and $a_4$ in terms of $a_1$ and $y_i^2$’s. Note that

$$\begin{aligned} a_2 = \frac{a_1^2-b_1}{2}, \end{aligned}$$

(4)

$$\begin{aligned} a_1a_3-a_4 = \frac{a_2^2-b_2}{2}, \end{aligned}$$

(5)

$$\begin{aligned} a_2a_4 = \frac{a_3^2-b_3}{2}, \end{aligned}$$

(6)

where

$$\begin{aligned} b_1= & {} y_1^2+y_2^2+y_3^2+y_4^2, \\ b_2= & {} y_1^2y_2^2+y_1^2y_3^2+y_1^2y_4^2+y_2^2y_3^2+y_2^2y_4^2+y_3^2y_4^2,\\ b_3= & {} y_1^2y_2^2y_3^2+y_1^2y_2^2y_4^2+y_1^2y_3^2y_4^2+y_2^2y_3^2y_4^2.\\ \end{aligned}$$

From (4) $a_2$ is easily computable. Denote the right-hand side of Eq. (5) as A. A is computable since $a_2$ is known. Hence, from (5) we get the following linear relationship between $a_3$ and $a_4$:

$$\begin{aligned} a_3 = \frac{A+a_4}{a_1}. \end{aligned}$$

(7)

Substituting $a_3$ in Eq. (6) by the above expression gives the following quadratic equation in $a_4$:

$$\begin{aligned} 2a_1^2a_2a_4 = A^2+2Aa_4+a_4^2-a_1^2b_3. \end{aligned}$$

$a_4^2$ is efficiently computable since it is equal to $y_1^2y_2^2y_3^2y_4^2$. Therefore

$$\begin{aligned} a_4 = \frac{A^2+a_4^2-a_1^2b_3}{2\big (a_1^2a_2-A\big )}. \end{aligned}$$

(8)

Formula (7) implies that

$$\begin{aligned} a_3 = \frac{2a_1^2a_2A-A^2+a_4^2-a_1^2b_3}{2a_1\big (a_1^2a_2-A\big )}. \end{aligned}$$

(9)

Substituting $a_3$ and $a_4$ from (8) and (9) into (3) gives

$$\begin{aligned} y_i = \frac{a_1\Big (A^2+a_4^2-a_1^2b_3+2\big (a_1^2a_2-A\big )\big (y_i^2a_2+y_i^4\big )\Big )}{2a_1^2a_2A-A^2+a_4^2-a_1^2b_3+2a_1^2y_i^2\big (a_1^2a_2-A\big )}. \end{aligned}$$

(10)

The computational complexity of the decompression algorithm described above is 55M + 11S + 1I, where M, S, and I denote the complexity of the final field multiplication, squaring and inversion, respectively. The complexity can be reduced significantly when only one y-coordinate has to be retrieved. For more details, the reader is referred to Appendix 2. The calculation of the computational complexity is based on the principles described in [23].

3.3 Five-point compression

Theorem 1 can also be used as a basis for a five-point compression algorithm. The compression algorithm represents the five points $P_i, i = 1, 2, 3, 4, 5,$ by $(x_1, x_2, x_3, x_4, x_5, a_1 = y_1 + y_2 + y_3 + y_4 + y_5)$. The decompression algorithm exploits Eq. (2) for $n = 5$:

$$\begin{aligned} a_2= & {} (a_1^2 - b_1)/2, \end{aligned}$$

(11)

$$\begin{aligned} a_3 a_1 - a_4= & {} (a_2^2 - b_2)/2,\end{aligned}$$

(12)

$$\begin{aligned} a_4 a_2 - a_5 a_1= & {} (a_3^2 - b_3)/2,\end{aligned}$$

(13)

$$\begin{aligned} a_5 a_3= & {} (a_4^2 - b_4)/2. \end{aligned}$$

(14)

Equation (11) immediately yields $a_2$ since $a_1$ and $b_i$, $i = 1, 2, 3, 4,$ are known. It follows from (12) that $a_3$ can be expressed as a linear function of $a_4$:

$$\begin{aligned} a_3 = (A + a_4)/a_1. \end{aligned}$$

(15)

Here Formula (15) substituted into (13) gives

$$\begin{aligned} a_4 a_2 - a_5 a_1 = \left( \frac{A^2 + 2 A a_4 + a_4^2}{a_1^2} - b_3 \right) \Bigg /2, \end{aligned}$$

which can be used to express $a_4^2$ as follows:

$$\begin{aligned} a_4^2 = a_1^2 (2 a_4 a_2 - 2 a_5 a_1 + b_3) - A^2 - 2 A a_4. \end{aligned}$$

(16)

As a next step, we use this expression as well as (15) to rewrite (14) as follows:

$$\begin{aligned} a_5 \cdot \left( \frac{A + a_4}{a_1} \right) = \big [ a_1^2 \big (2 a_4 a_2 - 2 a_5 a_1 + b_3\big ) - A^2 - 2 A a_4 - b_4 \big ] \big /2, \end{aligned}$$

which implies

$$\begin{aligned} a_4 = \frac{a_5 \big (2 a_1^4 + 2 A\big ) + a_1 \big (A^2 + b_4 - b_3 a_1^2\big )}{a_1 \big (2a_1^2 a_2 - 2A\big ) - 2 a_5}. \end{aligned}$$

(17)

As before, let $C = a_1 \big (2 a_1^2 a_2 - 2A\big )$. Let $F = 2 a_1^4 + 2 A$ and $G = a_1 \big (A^2 + b_4 - b_3 a_1^2\big )$. Then

$$\begin{aligned} a_4 = \frac{F a_5 + G}{C - 2 a_5}. \end{aligned}$$

Now formula $a_4^2 = 2 a_5 a_3 + b_4$, which follows directly from (14), can be written as follows:

$$\begin{aligned} \left( \frac{F a_5 + G}{C - 2 a_5} \right) ^2 = 2 a_5 \cdot \left( \frac{A + a_4}{a_1} \right) + b_4 \end{aligned}$$

or

$$\begin{aligned} \left( \frac{F a_5 + G}{C - 2 a_5} \right) ^2 = 2 a_5 \cdot \left( \frac{A + (F a_5 + G)/(C - 2 a_5)}{a_1} \right) + b_4. \end{aligned}$$

Note that $a_5^2$ can be efficiently computed, $a_5^2 = y_1^2 y_2^2 y_3^2 y_4^2 y_5^2$. Thus we get

$$\begin{aligned} a_5 = \frac{-F^2 a_5^2 a_1 - G^2 a_1 - 8 ACa_5^2 + 2FC a_5^2 - 4 G a_5 ^2 + C^2 b_4 a_1 + 4 b_4 a_1 a_5^2}{2 G F a_1 - 2 A C^2 - 8 A a_5^2 - 2 G C + 4 F a_5^2 + 4 C b_4 a_1}. \end{aligned}$$

Let J be the numerator and let H be the denominator of the formula so $a_5 = J/H$. Then

$$\begin{aligned} a_4 = \frac{FJ + GH}{CH - 2J}. \end{aligned}$$

Denote $K = CH - 2J$, $L = FJ + GH$. Then

$$\begin{aligned} a_4 = L/K. \end{aligned}$$

and

$$\begin{aligned} a_3 = \frac{AK + L}{a_1 K}. \end{aligned}$$

Since $n = 5$

$$\begin{aligned} y_i = \frac{a_5 + y_i^2 a_3 + y_i^4 a_1}{a_4 + y_i^2 a_2 + y_i^4}, \end{aligned}$$

where $i = 1, 2, 3, 4, 5$. Using the expressions above for $a_3, a_4, a_5$ we get

$$\begin{aligned} y_i = \frac{J K a_1 + H y_i^2 \big (AK + L + K a_1^2 y_i^2\big )}{Ha_1 \big (L + K y_i^2 (a_2 + y_i^2)\big )}. \end{aligned}$$

(18)

Let $M_i$ be the numerator of $y_i$: $M_i = J K a_1 + H y_i^2 (AK + L + K a_1^2 y_i^2)$. Then $y_i$ can be converted to the common denominator

$$\begin{aligned} N = Ha_1 \Big (L + K y_1^2 \big (a_2 + y_1^2\big )\Big ) \cdot \Big (L + K y_2^2 \big (a_2 + y_2^2\big )\Big ) \cdots \Big (L + K y_5^2 \big (a_2 + y_5^2\big )\Big ) \end{aligned}$$

as follows:

$$\begin{aligned} y_1= & {} \frac{M_1 \Big (L + K y_2^2 \big (a_2 + y_2^2\big )\Big ) \cdots \Big (L + K y_5^2 \big (a_2 + y_5^2\big )\Big )}{N},\nonumber \\&\ldots \nonumber \\ y_5= & {} \frac{M_5 \Big (L + K y_1^2 \big (a_2 + y_1^2\big )\Big ) \cdots \Big (L + K y_4^2 \big (a_2 + y_4^2\big )\Big )}{N}. \end{aligned}$$

(19)

The latter formula can be used for the efficient computation of $y_1, y_2, y_3, y_4, y_5$.

The overall computational complexity of the decompression is $120 M + 12 S + I$ in the case when the goal is to retrieve the y-coordinates of all five points. As before, the complexity can be reduced if the goal of the algorithm is to retrieve the y-coordinate of only one point. Please refer to Appendix 3 for details.

3.4 Discussion on the occupied memory and computational complexity

The two-point and three-point compression algorithms proposed by [20] as well as the four-point and five-point compression algorithms presented in this paper reduce the computational cost of the decompression compared to the ordinary single point compression, in which only the x-coordinates are stored and the y-coordinates are extracted through square root operations. On the other hand, the multiple point compression algorithms require roughly $\frac{100}{n} \%$ more storage space than the ordinary point compression, where n denotes the number of points to compress.

3.4.1 Square-and-multiply exponentiation, $p\equiv 3 \pmod 4$

We will make a concrete comparison for the case of 256-bit curves. Observe that solving $x^2 \equiv a \pmod p$ for $p\equiv 3 \pmod 4$ translates into computing $a^{(p+1)/4} \mod p$. At the same time, $x^{-1} \pmod p$ can be computed as $x^{p-2} \pmod p$. Thus we may assume that the square root operation and the inversion operation require roughly the same number of operations on average, that is $R \approx I \approx 127M + 254S$. The complexity of the inversion operation can be reduced by applying the extended Euclidean algorithm instead of the exponentiation. For the sake of simplicity we do not consider this enhancement in the two tables below; in Sect. 3.4.5 alternative values of R and I are discussed.

The following table provides a comparison between the ordinary-point and multiple-point compression algorithms.

n	Occupied memory		Computational complexity
	Ordinary	Multiple	Ordinary	Multiple
2	2	3	$2 R = 254M + 508S$	$129M+256S$
3	3	4	$3 R = 381M + 762S$	$139M+260S$
4	4	5	$4 R = 508M + 1016S$	$182M+265S$
5	5	6	$5 R = 635M + 1270S$	$247M+266S$

Here the unit of memory is one field element; columns “ordinary” and “multiple” correspond to the ordinary-point and multiple-point compression algorithms, respectively. In this table we neglect the extra storage bits needed in exceptional situations (the reader is referred to Sect. 4 for more details).

The table above can be used to illustrate the differences in the memory usage and in the computational complexity between the ordinary-point and multiple-point compression algorithms. We assume that $S = 0.8 M$, which is one of the possibilities considered in the database [23]. Then the table can be rewritten as follows.

n	Occupied memory			Computational complexity
	Ordinary	Multiple	Percentage	Ordinary	Multiple	Percentage
2	2	3	+50	660M	334M	−49
3	3	4	+33	991M	347M	−65
4	4	5	+25	1321M	394M	−70
5	5	6	+20	1651M	460M	−72

The new two-point compression algorithm described in Sect. 2.2 requires one inversion operation in its compression phase. However, the computational complexity of decompression part is $3M + 1S$ which requires 99.4 % less time than decompression phase of ordinary point compression method.

Please note that the multi-exponentiation technique [33] cannot be used to speed up the ordinary point compression algorithm. The end result of the multi-exponentiation is a product of several exponentiations while the ordinary point compression needs the result of each exponentiation separately.

3.4.2 Case $p \equiv 2^s + 1\ \ ({\mathrm{mod}}\ {2^{s+1})}$

So far we have considered only one example of the characteristic p, namely $p\equiv 3 \pmod 4$. To get a broader view on the computational complexity of multiple point compression let us consider one more example.

Let $p \equiv 2^s + 1 \pmod {2^{s+1}}$ for a small positive integer s. In this case square roots can be computed using the algorithm proposed by Koo et al. [22]. The algorithm is useful for small values of s such as $s = 2, 3, 4$ since the number of branches increases exponentially as s grows. In order to compute x such that $x^2 = a$ for a given square $a \in \mathbb {F}_p$ the algorithm requires one of the following exponentiations $a^{\frac{p-5}{8}}$, $a^{\frac{p-9}{16}}$ or $a^{\frac{p-17}{32}}$ depending on whether $s = 2, 3$ or 4. This means that the square root calculation is about as expensive for $p \equiv 2^s + 1 \pmod {2^{s+1}}$ and for $p \equiv 3 \pmod 4$ for any fixed bit length. Thus the comparison tables given in the previous section are applicable for $p \equiv 2^s + 1 \pmod {2^{s+1}}$ as well.

3.4.3 Quadratic extension fields

In [1], the authors proposed two efficient algorithms for computing square roots over even field extensions of the form $\mathbb {F}_{q^2}$, with $q = p^n$, p an odd prime and $n \ge 1$. The proposed two algorithms address the case when $q \equiv 1 \pmod 4$ and $q \equiv 3 \pmod 4$, respectively, and have an associate computational cost roughly equivalent to one exponentiation in $\mathbb {F}_{q^2}$. In the case when $q \equiv 3 \pmod 4$, the authors showed that the complex method of [14] is the most efficient algorithm for square root computation. For instance, when $p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1$ and $q = p$, the square root computation using the complex method requires $1I_p + 1149M_p + 6Mc_p$, where $I_p, M_p$ and $Mc_p$ denote the inversion, multiplication and multiplication by constant over the underlying $\mathbb {F}_p$. Hence, decompressing two points costs $2I_p + 2298M_p + 12Mc_p$. Using the two-point decompression technique in Sect. 2.1, one only needs $I_p + 14M_p + 7Mc_p$, given that $M_{p^2} = 3M_p + Mc_p, S_{p^2} = 2M_p + 2Mc_p$ and $I_{p^2} = I_p + 4M_p + Mc_p$. Using the same complexity estimation as in Sect. 3.4.1, one can find that the two-point compression technique requires $87.5\,\%$ less time when compared to the traditional approach. A similar analysis is also applicable to the case when $q \equiv 1 \pmod 4$ and we omit the details here.

3.4.4 Small characteristic fields

Elliptic curves over binary fields have the shape $y^2+xy=f(x)$ or $y^2+ay=f(x)$ for some cubic polynomial f and constant a. In this case, the trivial compression method stores x and one bit. To decompress we have to solve a quadratic Artin–Schreier equation $y^2+by=c$ instead of taking a square root.

For elliptic curves defined over $\mathbb {F}_{2^m}$ (m is odd), solving a quadratic equation is highly efficient when compared to other finite fields. As shown experimentally in [18], the time complexity is approximately 2/3 the time of a field multiplication. Even in this extreme case, it is not difficult to demonstrate that the two-point decompression technique (which requires $I + 3M + S$ [20]) is roughly $50\,\%$ faster than the traditional method (which requires $2\cdot \big (I + \frac{5}{3}M + S\big )$) for decompressing two points on elliptic curves defined over binary fields, provided that $I \ge 10M$ and $S = 0.1M$ [6].

For elliptic curves defined over $\mathbb {F}_{3^m}$ (m is odd), the best algorithm for square root extraction takes $O(m^2\log m)$ steps [7]. If $m = 2k + 1$ for some k, it is easily verified that the square root computation requires $\left( \lfloor \log _2 k \rfloor + \omega (k) + 1\right) \cdot M$ in this case, where $\omega (k)$ is the Hamming weight of the binary representation of k. In the case of $m = 239$, extracting a square root over $\mathbb {F}_{3^{239}}$ requires 13M. While the traditional method requires 26M (i.e., two square root computations) for decompressing two points, the proposed two-point decompression technique only requires $1I + 2M + S$, which results in about $50\,\%$ performance improvement. Here we assume that $I = 10M, S = M$ and a Type-II normal basis is used, as illustrated in [2]. If $I = 30 M$ the computational complexity of the two-point decompression is roughly the same as that of the traditional method.

3.4.5 Application to resource-constrained environments

When applying multiple point compression technique to resource-constrained environments such as wireless sensor networks, the performance improvement over ordinary point decompression method is further amplified due to the low-power processor architecture design. For instance, when implementing the 192-bit NIST curve on an 8-bit AVR microcontroller, the multiplication, squaring and inversion operations take 4, 042, 2, 658 and 280, 829 clock cycles, respectively [24], which gives us $I \approx 70M$, $S \approx 0.65M$ and $R = 127M + 189S \approx 250M$. Similar to the above estimations, we can obtain that the two-, three-, four- and five-point decompression algorithms requires 85.3, 88.5, 86.8 and $84.2\,\%$ less time than the traditional approach, respectively, which further demonstrates the great advantages of using multiple point compression technique on embedded devices.

4 A unified treatment of n-point compression

Considering the $\mathbb {F}$-rational generic points $P_i=(x_i, y_i), (i=1,\dots , n)$, lying on the curve $y^2=f(x)$, we now describe a fully LA method to compress-decompress these points using only $n+1$ field values. When referring to a “constant number of operations” we mean that this number does not depend on the field size, but only on n and the polynomial f. Our method shows that asymptotically, one can achieve a very fast compression–decompression algorithm by storing only one extra value, compared to the trivial algorithm which stores only the $x_i$’s. However, in practice, ad hoc methods such as those presented in the previous sections will be more efficient. Also, there are exceptional cases which in applications would not arise but can be dealt theoretically by storing a fixed number of extra bits, as in [20], hence our focus on an algorithm for generic points.² Additionally, with cryptographic applications in mind, we assume that $n<{\text {char}} \mathbb F$ to avoid dividing by zero.

To compress n generic points, simply store the values

$$\begin{aligned} \big (x_1, \dots , x_n, a_1= y_1+ \cdots + y_n\big ). \end{aligned}$$

(20)

To decompress, let $a_1, \dots , a_n$ as in Sect. 3 be the elementary symmetric polynomials in the $y_i$’s. Then, by Newton’s identities,

$$\begin{aligned} \nonumber {y_1^{2}+\cdots + y_n^{2}}&= {a_1^2} -2a_2,\\ {y_1^{4}+ \cdots + y_n^{4}}&= {a_1^4} - 4 a_1^2a_2 + 2{a_2^2} + 4a_1a_3- 4a_4, \\ \nonumber {y_1^{6}+ \cdots + y_n^{6}}&= {a_1^{6}} - 6 a_1^{4} a_2 + 9a_1^{2} a_2^{2} + 6a_1^{3} a_3 - 2{a_2^{3}} - 12 a_1 a_2 a_3\\ \nonumber&\quad \,- 6a_1^{2} a_4 + 3{a_3^{2}} + 6 a_2 a_4 + 6 a_1a_5 - 6a_6, \end{aligned}$$

(21)

and so on for $p_{2k}=y_1^{2k}+\cdots + y_n^{2k}$ for $k=1,\dots ,n$. The left-hand sides are computable in a constant number of operations. The right-hand sides are polynomials $f_{2k}(a_1,\dots ,a_n)$, so the previous system (21) can be rewritten as $p_{2k} = f_{2k}(a_1,\dots ,a_n)$ for $k=1,\dots ,n$. One can solve it in $a_1,\dots ,a_n$ by considering the ideal ${\mathcal {I}}$ of $\mathbb {F}(p_2,\dots ,p_{2n})[a_1,\dots ,a_n]$ generated by the $p_{2k} - f_{2k}(a_1,\dots ,a_n)$ for $k=1,\dots ,n$ and computing its reduced Gröbner basis with respect to the lexicographic ordering of the variables with $a_1<a_2<\cdots <a_n$. In fact, the Newton identities applied to the symmetric polynomials in the $y_i^2$’s show that the knowledge of $p_{2k}$ for $k=1,\dots ,n$ determines $y_1^2,\dots ,y_n^2$ uniquely up to permutation. By our assumption, this means that given $a_1$ there are either none or unique values (up to permutation) of $y_1,\dots y_n$ for which their symmetric polynomials $(a_1,\dots a_n)$ belong to the variety V associated to ${\mathcal {I}}$. Therefore $\#V=2^n$ and the points of V are separated by $a_1$ (they have all distinct first coordinate). Let’s note that in this reasoning we have kept in mind specializations of the $p_{2k}$ to particular values in ${\mathbb {F}}$ corresponding to generic $y_1,\dots y_n$. In fact, what this shows is that as we work with undetermined coefficients, i.e. with $\mathcal I\subset \mathbb {F}(p_2,\dots ,p_{2n})[a_1,\dots ,a_n]$ we have a fortiori $\#V=2^n$, where $V \subset \bigl (\overline{\mathbb {F}(p_2,\dots ,p_{2n})}\bigr )^n$, as well as separation by the first coordinate $a_1$.

Moreover ${\mathcal {I}}$ is a radical ideal: consider again the symmetric polynomials $e_1= y_1^2+\cdots + y_n^2$, ..., $e_n=y_1^2\ldots y_n^2$ in the $y_i^2$’s. We write the identity

$$\begin{aligned} \big (x^2-y_1^2\big )\cdots \big (x^2-y_n^2\big ) = (x-y_1)\cdots (x-y_n)(x+y_1)\cdots (x+y_n) \end{aligned}$$

as

$$\begin{aligned}&x^{2n}-e_1x^{2n-2}+e_2x^{2n-4}+\cdots + (-1)^n e_n \\&\quad = \Big (x^n - a_1 x^{n-1} + a_2 x^{n-2} + \cdots + (-1)^n a_n\Big )\\&\quad \quad \times \, \Big (x^n + a_1 x^{n-1} + a_2 x^{n-2} + \cdots + a_n\Big ) \end{aligned}$$

This gives rise to the following system of n equations

$$\begin{aligned} e_1&= -2a_2 +a_1^2 , \nonumber \\ e_2&= 2a_4-2a_1a_3+a_2^2 , \\ \nonumber e_3&= -2a_6+2a_1a_5-2a_2a_4+a_3^2 , \\ \nonumber&\text {etc.} \end{aligned}$$

(22)

Newton’s identities imply that $\mathbb {F}[p_2,\dots ,p_{2n}]=\mathbb {F}[e_1,\dots ,e_{n}]$ since we are supposing that ${\text {char}} {\mathbb {F}}>n$ and hence the two systems (21) and (22) are equivalent in the sense that the ideals they define are equal in $\mathbb {F}(p_2,\dots ,p_{2n})[a_1,\dots ,a_n] = \mathbb {F}(e_1,\dots ,e_{n})[a_1,\dots ,a_n]$. Looking at ${\mathcal {I}}$ as described by (22), we apply Bézout’s Theorem for hypersurfaces [16, Ch.12.3]: since we already know that the n hyperquadrics (22) intersect in $2^n$ points (the maximum allowed without common components), the multiplicity of intersection at each point is one and therefore by [13, Ch.4, Corollary 2.6] we deduce that ${\mathcal {I}}$ is radical (we don’t need the hypothesis that the field k be algebraically closed if we have already found $V({\mathcal {I}})$).

The Shape Lemma [12, 30] says that under the preceding conditions, the reduced Gröbner basis will look as follows.

$$\begin{aligned} \left[ g_{1}(a_1) , a_2+g_2(a_1), \dots , a_n + g_n(a_1) \right] , \end{aligned}$$

where $g_k\in \mathbb {F}(p_2,\dots ,p_{2n})[a_1]$ with $\deg g_1=2^n$ and $\deg g_k<2^n$ for $k=2,\dots ,n$. This Gröbner basis can be precomputed (it depends only on n) and from its form, given $a_1$, the other $a_k$’s for $k=2,\dots ,n$ can be recovered in a constant number of operations. See Appendix 1 for the expressions of $g_k$ when $n=4$.

Once we know the symmetric polynomials, we can compute the right-hand sides of

$$\begin{aligned} y_1+ \cdots + y_n&= a_1,\\ {y_1^{3}+ \cdots + y_n^{3}}&= {a_1^3} - 3 a_1a_2 + 3 a_3,\\ {y_1^{5}+ \cdots + y_n^{5}}&= {a_1^{5}} - 5 a_1^{3} a_2 + 5 a_1 a_2^{2} + 5 a_1^{2} a_3 - 5 a_2 a_3 - 5 a_1 a_4 + 5 a_5, \\&\vdots \end{aligned}$$

up to $y_1^{2n-1}+ \cdots + y_n^{2n-1}$. Since

$$\begin{aligned} y_1^{2k-1}+ \cdots + y_n^{2k-1} = y_1\cdot y_1^{2k-2} + \cdots + y_n \cdot y_n^{2k-2} \end{aligned}$$

we will get n linear equations in the n variables $y_1, \dots , y_n$, whose matrix is the Vandermonde

$$\begin{aligned} \begin{pmatrix} 1 &{} \cdots &{} 1 \\ y_1^2 &{} \cdots &{} y_n^2 \\ \vdots &{} &{} \vdots \\ y_1^{2n-2} &{} \cdots &{} y_n^{2n-2} \\ \end{pmatrix} \end{aligned}$$

which will be invertible since $y_i^2\ne y_j^2$ for $1\le i<j\le n$ (otherwise not all $2^n$ sums $\pm y_1 \pm \cdots \pm y_n$ would be distinct). We can solve this system by linear algebra in a constant number of operations, thereby concluding the LA decompression. Thus we have proved the following theorem.

Theorem 2

Given a curve $y^2=f(x)$ over a field $\mathbb {F}$ of odd characteristic greater than n and ${\mathbb {F}}$-rational generic points $P_i=(x_i,y_i), i=1,\dots , n$ on it, we can fully LA compress and decompress them by storing $n+1$ field elements.

5 Conclusion

In this paper, we presented novel LA based compression techniques for multiple points on elliptic curves. Four- and five-point compression schemes are first described which extend Khabbazian et al. [20]. We then extend this analysis to deal with n points by generically storing $n+1$ field elements. Using our new algorithms, the compression process requires almost no computational effort and the decompression does not involve solving any quadratic or higher degree equations over finite fields. Hence, the proposed techniques can be employed to reduce the required bandwidth/memory when single point compression is computationally expensive. It is possible to generalise this method to deal with divisors on hyperelliptic curves represented in Mumford form. One aspect that would be interesting to explore is the possibility to design a fully LA algorithm where compression and decompression take comparable amount of time, or even where decompression is fast but compression slower, in contrast with the present algorithm where compression is immediate and decompression is much slower.

Appendices

Appendix 1: Expression of the polynomials $g_i$ when $n=4$

$$\begin{aligned} g_1\left( a_1\right)= & {} a_{1}^{16} + \left( -8 p_{2}\right) a_{1}^{14} + \left( 20 p_{2}^{2} + 8 p_{4}\right) a_{1}^{12} + \left( -\frac{88}{3} p_{2}^{3} + 16 p_{2} p_{4} - \frac{128}{3} p_{6}\right) a_{1}^{10} \\&+\, \left( -\frac{94}{3} p_{2}^{4} + 360 p_{2}^{2} p_{4} - 248 p_{4}^{2} - \frac{1664}{3} p_{2} p_{6} + 544 p_{8}\right) a_{1}^{8} \\&+\, \left( 72 p_{2}^{5} - \frac{1696}{3} p_{2}^{3} p_{4} + 480 p_{2} p_{4}^{2} + 768 p_{2}^{2} p_{6} - \frac{512}{3} p_{4} p_{6} - 640 p_{2} p_{8}\right) a_{1}^{6} \\&+ \,\left( -\frac{428}{9} p_{2}^{6} + \frac{1192}{3} p_{2}^{4} p_{4} - 624 p_{2}^{2} p_{4}^{2} - \frac{4352}{9} p_{2}^{3} p_{6} + 480 p_{4}^{3} \right. \\&\left. \quad +\, \frac{512}{3} p_{2} p_{4} p_{6} + 576 p_{2}^{2} p_{8} + \frac{4096}{9}p_{6}^{2} - 896 p_{4} p_{8}\right) a_{1}^{4} \\&+ \,\left( -\frac{56}{9} p_{2}^{7} + \frac{304}{3} p_{2}^{5} p_{4} - 480 p_{2}^{3} p_{4}^{2} - \frac{896}{9} p_{2}^{4} p_{6} + 320 p_{2} p_{4}^{3}+ \frac{3584}{3} p_{2}^{2} p_{4} p_{6}\right. \\&\left. \quad -\, \frac{128}{3} p_{2}^{3} p_{8} - \,512 p_{4}^{2} p_{6} - \frac{8192}{9} p_{2} p_{6}^{2} - 256 p_{2} p_{4} p_{8} + \frac{2048}{3} p_{6} p_{8}\right) a_{1}^{2} \\&+ \,\frac{25}{9} p_{2}^{8} - 40 p_{2}^{6} p_{4} + \frac{472}{3} p_{2}^{4} p_{4}^{2} + \frac{640}{9} p_{2}^{5} p_{6} - 96 p_{2}^{2} p_{4}^{3}\\&-\, 512 p_{2}^{3} p_{4} p_{6} - \frac{160}{3} p_{2}^{4} p_{8} \\&+ \,16 p_{4}^{4} + \frac{512}{3} p_{2} p_{4}^{2} p_{6} + \frac{4096}{9} p_{2}^{2} p_{6}^{2} + 384 p_{2}^{2} p_{4} p_{8} - 128 p_{4}^{2} p_{8}\\&- \,\frac{2048}{3} p_{2} p_{6} p_{8} + 256 p_{8}^{2} ,\\ g_2(a_1) \,= & {} \, \left( -\frac{1}{2}\right) a_{1}^{2} + \frac{1}{2} p_{2}. \end{aligned}$$

Next, $g_3(a_1)$ equals

$$\begin{aligned}&\quad (3141 p_{2}^{6} - 29916 p_{2}^{4} p_{4} + 73575 p_{2}^{2} p_{4}^{2} + 27288 p_{2}^{3} p_{6} - 22950 p_{4}^{3} \\&\quad -\, 107568 p_{2} p_{4} p_{6} - 9558 p_{2}^{2} p_{8} + 41472 p_{6}^{2} + 24300 p_{4} p_{8}) a_{1}^{15} \\&\quad +\, (-24228 p_{2}^{7} + 229068 p_{2}^{5} p_{4} - 559224 p_{2}^{3} p_{4}^{2} - 203544 p_{2}^{4} p_{6}\\&\quad + \,174528 p_{2} p_{4}^{3} + 788832 p_{2}^{2} p_{4} p_{6}\\&\quad + \,67824 p_{2}^{3} p_{8} + 7776 p_{4}^{2} p_{6} - 290304 p_{2} p_{6}^{2} - 158112 p_{2} p_{4} p_{8} - 31104 p_{6} p_{8}) a_{1}^{13} \\&\quad +\, (56205 p_{2}^{8} - 498654 p_{2}^{6} p_{4} + 1024839 p_{2}^{4} p_{4}^{2} + 438408 p_{2}^{5} p_{6} + 177660 p_{2}^{2} p_{4}^{3}\\&\quad -\, 1425312 p_{2}^{3} p_{4} p_{6} \\&\quad - \,130086 p_{2}^{4} p_{8} - 178092 p_{4}^{4} - 885600 p_{2} p_{4}^{2} p_{6} + 539136 p_{2}^{2} p_{6}^{2} \\&\quad +\, 168696 p_{2}^{2} p_{4} p_{8} + 331776 p_{4} p_{6}^{2} + 166536 p_{4}^{2} p_{8} + 186624 p_{2} p_{6} p_{8} + 23328 p_{8}^{2}) a_{1}^{11} \\&\quad + \,(-78726 p_{2}^{9} + 789120 p_{2}^{7} p_{4} - 2350998 p_{2}^{5} p_{4}^{2} - 722856 p_{2}^{6} p_{6} \\&\quad + \,2106360 p_{2}^{3} p_{4}^{3}+4069584 p_{2}^{4} p_{4} p_{6} \end{aligned}$$

$$\begin{aligned}&\quad + \,169452 p_{2}^{5} p_{8} - 486216 p_{2} p_{4}^{4} - 5601312 p_{2}^{2} p_{4}^{2} p_{6} - 1869312 p_{2}^{3} p_{6}^{2} - 589680 p_{2}^{3} p_{4} p_{8}\nonumber \\&\quad + \,1046592 p_{4}^{3} p_{6} \\&\quad +\, 5612544 p_{2} p_{4} p_{6}^{2} + 907632 p_{2} p_{4}^{2} p_{8} + 252288 p_{2}^{2} p_{6} p_{8} - 1769472 p_{6}^{3}\\&\quad -\, 1306368 p_{4} p_{6} p_{8} - 171072 p_{2} p_{8}^{2}) a_{1}^{9} \\&\quad + \,(-113973 p_{2}^{10} + 2247624 p_{2}^{8} p_{4} - 14414355 p_{2}^{6} p_{4}^{2} - 2873976 p_{2}^{7} p_{6} + 35073162 p_{2}^{4} p_{4}^{3}\\&\quad + \,31435920 p_{2}^{5} p_{4} p_{6} + 2121606 p_{2}^{6} p_{8} - 26740476 p_{2}^{2} p_{4}^{4} - 88583328 p_{2}^{3} p_{4}^{2} p_{6}\\&\quad -\, 17567232 p_{2}^{4} p_{6}^{2} \\&\quad - \,20887092 p_{2}^{4} p_{4} p_{8} + 5739336 p_{4}^{5} + 40201920 p_{2} p_{4}^{3} p_{6} \nonumber \\&\quad + \,78474240 p_{2}^{2} p_{4} p_{6}^{2}+ 51563304 p_{2}^{2} p_{4}^{2} p_{8} \\&\quad +\, 20431872 p_{2}^{3} p_{6} p_{8} - 10616832 p_{4}^{2} p_{6}^{2} - 24772608 p_{2} p_{6}^{3}\\&\quad -\, 18752688 p_{4}^{3} p_{8} - 74428416 p_{2} p_{4} p_{6} p_{8} \\&\quad -\, 4854816 p_{2}^{2} p_{8}^{2} + 23887872 p_{6}^{2} p_{8} + 13421376 p_{4} p_{8}^{2}) a_{1}^{7} \\&\quad +\, (183552 p_{2}^{11} - 3089004 p_{2}^{9} p_{4} + 18070524 p_{2}^{7} p_{4}^{2} + 3134904 p_{2}^{8} p_{6} - 43127352 p_{2}^{5} p_{4}^{3} \\&\quad - \,31349184 p_{2}^{6} p_{4} p_{6} - 1758456 p_{2}^{7} p_{8} + 37337904 p_{2}^{3} p_{4}^{4}\\&\quad +\, 86126976 p_{2}^{4} p_{4}^{2} p_{6} + 13088256 p_{2}^{5} p_{6}^{2} \\&\quad +\, 15252912 p_{2}^{5} p_{4} p_{8} - 8725536 p_{2} p_{4}^{5} - 54885888 p_{2}^{2} p_{4}^{3} p_{6}\\&\quad -\, 52205568 p_{2}^{3} p_{4} p_{6}^{2} - 32713632 p_{2}^{3} p_{4}^{2} p_{8} \end{aligned}$$

$$\begin{aligned}&\quad -\, 9452160 p_{2}^{4} p_{6} p_{8} + 1798272 p_{4}^{4} p_{6} + 22321152 p_{2} p_{4}^{2} p_{6}^{2}\\&\quad + \,7077888 p_{2}^{2} p_{6}^{3} + 12156480 p_{2} p_{4}^{3} p_{8} \\&\quad +\, 15422976 p_{2}^{2} p_{4} p_{6} p_{8} + 1019520 p_{2}^{3} p_{8}^{2} - 7077888 p_{4} p_{6}^{3} + 8805888 p_{4}^{2} p_{6} p_{8} \\&\quad +\, 15925248 p_{2} p_{6}^{2} p_{8} + 4582656 p_{2} p_{4} p_{8}^{2} - 17915904 p_{6} p_{8}^{2}) a_{1}^{5} \\&\quad +\, (-119357 p_{2}^{12} + 2165658 p_{2}^{10} p_{4} - 14673531 p_{2}^{8} p_{4}^{2}\\&\quad -\, 2088552 p_{2}^{9} p_{6} + 46760208 p_{2}^{6} p_{4}^{3} \\&\quad +\, 23773056 p_{2}^{7} p_{4} p_{6} + 1897398 p_{2}^{8} p_{8} - 73942056 p_{2}^{4} p_{4}^{4}\\&\quad -\, 86667456 p_{2}^{5} p_{4}^{2} p_{6} - 9014784 p_{2}^{6} p_{6}^{2} \\&\quad -\, 22437504 p_{2}^{6} p_{4} p_{8} + 57054240 p_{2}^{2} p_{4}^{5} + 117450240 p_{2}^{3} p_{4}^{3} p_{6}\\&\quad + \,43920384 p_{2}^{4} p_{4} p_{6}^{2} + 87558768 p_{2}^{4} p_{4}^{2} p_{8} \\&\quad +\, 17627904 p_{2}^{5} p_{6} p_{8} - 12932784 p_{4}^{6} - 68144256 p_{2} p_{4}^{4} p_{6}\\&\quad -\, 20305920 p_{2}^{2} p_{4}^{2} p_{6}^{2} - 3506176 p_{2}^{3} p_{6}^{3} \\&\quad -\, 124350336 p_{2}^{2} p_{4}^{3} p_{8} - 111430656 p_{2}^{3} p_{4} p_{6} p_{8} - 6348672 p_{2}^{4} p_{8}^{2}\\&\quad + \,8687616 p_{4}^{3} p_{6}^{2} - 46006272 p_{2} p_{4} p_{6}^{3} \\&\quad +\, 45537120 p_{4}^{4} p_{8} + 143926272 p_{2} p_{4}^{2} p_{6} p_{8} + 36790272 p_{2}^{2} p_{6}^{2} p_{8}\\&\quad +\, 41478912 p_{2}^{2} p_{4} p_{8}^{2} + 18874368 p_{6}^{4} \\&\quad - \,23003136 p_{4} p_{6}^{2} p_{8} - 48169728 p_{4}^{2} p_{8}^{2} - 35665920 p_{2} p_{6} p_{8}^{2} + 15303168 p_{8}^{3}) a_{1}^{3} \end{aligned}$$

$$\begin{aligned}&\quad +\, (5186 p_{2}^{13} - 10704 p_{2}^{11} p_{4} - 936990 p_{2}^{9} p_{4}^{2} + 105288 p_{2}^{10} p_{6}\\&\quad +\, 8434128 p_{2}^{7} p_{4}^{3} + 1229136 p_{2}^{8} p_{4} p_{6} \\&\quad -\, 370452 p_{2}^{9} p_{8} - 26146800 p_{2}^{5} p_{4}^{4} - 23498496 p_{2}^{6} p_{4}^{2} p_{6} - 907776 p_{2}^{7} p_{6}^{2}\\&\quad +\, 3779424 p_{2}^{7} p_{4} p_{8} + 28215360 p_{2}^{3} p_{4}^{5} \\&\quad + \,92255232 p_{2}^{4} p_{4}^{3} p_{6} + 26336256 p_{2}^{5} p_{4} p_{6}^{2} - 9767520 p_{2}^{5} p_{4}^{2} p_{8}\\&\quad - \,3057024 p_{2}^{6} p_{6} p_{8} - 7140960 p_{2} p_{4}^{6} \\&\quad -\, 90170496 p_{2}^{2} p_{4}^{4} p_{6} - 132544512 p_{2}^{3} p_{4}^{2} p_{6}^{2} - 8880128 p_{2}^{4} p_{6}^{3}\\&\quad - \,3844224 p_{2}^{3} p_{4}^{3} p_{8} + 9347328 p_{2}^{4} p_{4} p_{6} p_{8} \\&\quad +\, 2239488 p_{2}^{5} p_{8}^{2} + 13130496 p_{4}^{5} p_{6} + 87527424 p_{2} p_{4}^{3} p_{6}^{2}\\&\quad +\, 88473600 p_{2}^{2} p_{4} p_{6}^{3} + 11524032 p_{2} p_{4}^{4} p_{8} \\&\quad +\, 60120576 p_{2}^{2} p_{4}^{2} p_{6} p_{8} - 9338880 p_{2}^{3} p_{6}^{2} p_{8} - 15123456 p_{2}^{3} p_{4} p_{8}^{2}\\&\quad -\, 17694720 p_{4}^{2} p_{6}^{3} - 18874368 p_{2} p_{6}^{4} \\&\quad -\, 36615168 p_{4}^{3} p_{6} p_{8} - 85819392 p_{2} p_{4} p_{6}^{2} p_{8} + 2087424 p_{2} p_{4}^{2} p_{8}^{2}\\&\quad +\, 25436160 p_{2}^{2} p_{6} p_{8}^{2} + 14155776 p_{6}^{3} p_{8} \\&\quad + 28532736 p_{4} p_{6} p_{8}^{2} - 12192768 p_{2} p_{8}^{3}) a_{1} \end{aligned}$$

divided by

$$\begin{aligned}&82560 p_{2}^{12} - 1615872 p_{2}^{10} p_{4} + 11757312 p_{2}^{8} p_{4}^{2} + 1855488 p_{2}^{9} p_{6} - 38739456 p_{2}^{6} p_{4}^{3} \\&\quad -\, 24600576 p_{2}^{7} p_{4} p_{6} - 1230336 p_{2}^{8} p_{8} + 55052928 p_{2}^{4} p_{4}^{4} + 105615360 p_{2}^{5} p_{4}^{2} p_{6} \\&\quad +\, 12435456 p_{2}^{6} p_{6}^{2} + 16137216 p_{2}^{6} p_{4} p_{8} - 26417664 p_{2}^{2} p_{4}^{5} - 150552576 p_{2}^{3} p_{4}^{3} p_{6} \\&\quad - \,92061696 p_{2}^{4} p_{4} p_{6}^{2} - 67834368 p_{2}^{4} p_{4}^{2} p_{8} - 16588800 p_{2}^{5} p_{6} p_{8} + 3995136 p_{4}^{6} \\&\quad + \,41213952 p_{2} p_{4}^{4} p_{6} + 127401984 p_{2}^{2} p_{4}^{2} p_{6}^{2} + \,28311552 p_{2}^{3} p_{6}^{3} + 90740736 p_{2}^{2} p_{4}^{3} p_{8} \\&\quad +\, 120029184 p_{2}^{3} p_{4} p_{6} p_{8} + 6068736 p_{2}^{4} p_{8}^{2} - 5308416 p_{4}^{3} p_{6}^{2} - 28311552 p_{2} p_{4} p_{6}^{3} \\&\quad -\, 24440832 p_{4}^{4} p_{8} - 132710400 p_{2} p_{4}^{2} p_{6} p_{8} - 63700992 p_{2}^{2} p_{6}^{2} p_{8} - 43960320 p_{2}^{2} p_{4} p_{8}^{2} \\&\quad +\, 21233664 p_{4} p_{6}^{2} p_{8} + 38320128 p_{4}^{2} p_{8}^{2} + 55738368 p_{2} p_{6} p_{8}^{2} -\, 17915904 p_{8}^{3}. \end{aligned}$$

The formula for $g_4(a_1)$ is

$$\begin{aligned}&(-180 p_{2}^{3} + 756 p_{2} p_{4} - 648 p_{6}) a_{1}^{14} \\&\quad +\, (1323 p_{2}^{4} - 5382 p_{2}^{2} p_{4} - 459 p_{4}^{2} + 4536 p_{2} p_{6} + 486 p_{8}) a_{1}^{12} \\&\quad + \,(-2682 p_{2}^{5} + 8424 p_{2}^{3} p_{4} + 9918 p_{2} p_{4}^{2} - 7992 p_{2}^{2} p_{6} - 5616 p_{4} p_{6} - 3564 p_{2} p_{8}) a_{1}^{10} \\&\quad +\, (3111 p_{2}^{6} - 13500 p_{2}^{4} p_{4} + 7389 p_{2}^{2} p_{4}^{2} + 15528 p_{2}^{3} p_{6} - 3978 p_{4}^{3} - 45072 p_{2} p_{4} p_{6} \\&\quad + \,7182 p_{2}^{2} p_{8} + 27648 p_{6}^{2} + 4212 p_{4} p_{8}) a_{1}^{8} \\&\quad +\, (8520 p_{2}^{7} - 106788 p_{2}^{5} p_{4} + 340092 p_{2}^{3} p_{4}^{2} + 139368 p_{2}^{4} p_{6} - 190872 p_{2} p_{4}^{3} \\&\quad - 696480 p_{2}^{2} p_{4} p_{6} - 106200 p_{2}^{3} p_{8} + 176544 p_{4}^{2} p_{6} \\&\quad +\, 387072 p_{2} p_{6}^{2} + 419472 p_{2} p_{4} p_{8} - 373248 p_{6} p_{8}) a_{1}^{6} \\&\quad + \,(-8067 p_{2}^{8} + 83322 p_{2}^{6} p_{4} - 209049 p_{2}^{4} p_{4}^{2} - 88728 p_{2}^{5} p_{6} + 11412 p_{2}^{2} p_{4}^{3} \\&\quad + \,347040 p_{2}^{3} p_{4} p_{6} + 26586 p_{2}^{4} p_{8} + 118116 p_{4}^{4} - 9696 p_{2} p_{4}^{2} p_{6} - 119808 p_{2}^{2} p_{6}^{2} \\&\quad +\, 75528 p_{2}^{2} p_{4} p_{8} + 119808 p_{4} p_{6}^{2} - 382104 p_{4}^{2} p_{8} - 235008 p_{2} p_{6} p_{8} + 272160 p_{8}^{2}) a_{1}^{4} \\&\quad +\, (-818 p_{2}^{9} + 16344 p_{2}^{7} p_{4} - 104490 p_{2}^{5} p_{4}^{2} - 14312 p_{2}^{6} p_{6} + 177288 p_{2}^{3} p_{4}^{3} \\&\quad +\, 244944 p_{2}^{4} p_{4} p_{6} - 10188 p_{2}^{5} p_{8} + 66312 p_{2} p_{4}^{4} - 618336 p_{2}^{2} p_{4}^{2} p_{6} - 180224 p_{2}^{3} p_{6}^{2} \\&\quad +\, 5040 p_{2}^{3} p_{4} p_{8} - 115008 p_{4}^{3} p_{6} + 645120 p_{2} p_{4} p_{6}^{2} - 66672 p_{2} p_{4}^{2} p_{8} + 161280 p_{2}^{2} p_{6} p_{8} \\&\quad -\, 294912 p_{6}^{3} + 248832 p_{4} p_{6} p_{8} - 160704 p_{2} p_{8}^{2}) a_{1}^{2} \\&\quad +\, 3809 p_{2}^{10} - 58848 p_{2}^{8} p_{4} + 320919 p_{2}^{6} p_{4}^{2} + 57464 p_{2}^{7} p_{6} - 707514 p_{2}^{4} p_{4}^{3} \\&\quad -\, 565968 p_{2}^{5} p_{4} p_{6} - 33006 p_{2}^{6} p_{8} + 532188 p_{2}^{2} p_{4}^{4} + 1485984 p_{2}^{3} p_{4}^{2} p_{6} + 272384 p_{2}^{4} p_{6}^{2} \\&\quad + \,312660 p_{2}^{4} p_{4} p_{8} - 113832 p_{4}^{5} - 721344 p_{2} p_{4}^{3} p_{6} - 1096704 p_{2}^{2} p_{4} p_{6}^{2} - 749448 p_{2}^{2} p_{4}^{2} p_{8} \\&\quad -\, 296448 p_{2}^{3} p_{6} p_{8} + 165888 p_{4}^{2} p_{6}^{2} + 294912 p_{2} p_{6}^{3} + 331056 p_{4}^{3} p_{8} + 912384 p_{2} p_{4} p_{6} p_{8} \\&\quad +\, 97632 p_{2}^{2} p_{8}^{2} - 221184 p_{6}^{2} p_{8} - 222912 p_{4} p_{8}^{2} \end{aligned}$$

divided by

$$\begin{aligned}&-\,16512 p_{2}^{8} + 204288 p_{2}^{6} p_{4} - 840960 p_{2}^{4} p_{4}^{2} - 159744 p_{2}^{5} p_{6} + 1202688 p_{2}^{2} p_{4}^{3} \\&\quad +\, 1155072 p_{2}^{3} p_{4} p_{6} + 87552 p_{2}^{4} p_{8} - 332928 p_{4}^{4} - 1658880 p_{2} p_{4}^{2} p_{6} - 442368 p_{2}^{2} p_{6}^{2} \\&\quad -\, 635904 p_{2}^{2} p_{4} p_{8} + 442368 p_{4} p_{6}^{2} + 705024 p_{4}^{2} p_{8} + 663552 p_{2} p_{6} p_{8} - 373248 p_{8}^{2} . \end{aligned}$$

These formulas were obtained by running the following commands in SAGE (www.sagemath.org):

Appendix 2: Computational complexity of the decompression for $n = 4$

1.1 All points are decompressed

The calculation of the complexity is based on the principles described in [23], which are as follows.

• Only the square and multiply operations are counted; the computational cost of the addition and subtraction is neglected.

• Multiplication by a constant is neglected as well.

It most cases inversion is computationally costly as compared to multiplication and square operations. For that reason, we will minimize the number of the inversions.

Denote

$$\begin{aligned} B= & {} a_1\big (A^2+a_4^2-a_1^2b_3\big ),\\ C= & {} 2a_1\big (a_1^2a_2-A\big ),\\ D= & {} 2a_1^2a_2A-A^2+a_4^2-a_1^2b_3,\\ E= & {} 2a_1^2\big (a_1^2a_2-A\big ).\\ \end{aligned}$$

Then Eq. (10) yields

$$\begin{aligned} y_i = \frac{B+C\big (a_2y_i^2+y_i^4\big )}{D+Ey_i^2}. \end{aligned}$$

(23)

The computation of $y_1, y_2, y_3, y_4$ separately using the equation above ends up with 4 inversions. For the sake of efficiency, it makes sense to compute $y_i$’s in the following way:

$$\begin{aligned} y_1= & {} \frac{\Big (B+C\big (a_2y_1^2+y_1^4\big )\Big )\big (D+Ey_2^2\big )\big (D+Ey_3^2\big )\big (D+Ey_4^2\big )}{\big (D+Ey_1^2\big )\big (D+Ey_2^2\big )\big (D+Ey_3^2\big )\big (D+Ey_4^2\big )},\\ y_2= & {} \frac{\Big (B+C\big (a_2y_2^2+y_2^4\big )\Big )\big (D+Ey_1^2\big )\big (D+Ey_3^2\big )\big (D+Ey_4^2\big )}{\big (D+Ey_1^2\big )\big (D+Ey_2^2\big )\big (D+Ey_3^2\big )\big (D+Ey_4^2\big )},\\ y_3= & {} \frac{\Big (B+C\big (a_2y_3^2+y_3^4\big )\Big )\big (D+Ey_1^2\big )\big (D+Ey_2^2\big )\big (D+Ey_4^2\big )}{\big (D+Ey_1^2\big )\big (D+Ey_2^2\big )\big (D+Ey_3^2\big )\big (D+Ey_4^2\big )},\\ y_4= & {} \frac{\Big (B+C\big (a_2y_4^2+y_4^4\big )\Big )\big (D+Ey_1^2\big )\big (D+Ey_2^2\big )\big (D+Ey_3^2\big )}{\big (D+Ey_1^2\big )\big (D+Ey_2^2\big )\big (D+Ey_3^2\big )\big (D+Ey_4^2\big )}. \end{aligned}$$

Here all $y_i$’s are converted to the common denominator, which means that only one inversion is needed.

Table 1 shows how the computational complexity is calculated.

Overall, the decompression algorithm require $55M + 11S + 1I$.

Table 1 Computational complexity of the decompression algorithm

1.2 Only one point is decompressed

The complexity of the decompression can be reduced when one has to extract only one $y_i, i \in \{1, 2, 3, 4\},$ and not all of them. Note that in many practical situations only one of the y-coordinates has to be extracted for the archive.

Without loss of generality, suppose we have to recover $y_1$. We will compute $y_1$ using Eq. (23).

Table 2 Computational complexity of the preparation step

Then in Table 1 we can avoid the computation of the following values: $D + E y_2^2$, $D + E y_3^2$, $D + E y_4^2$, $\big (D + E y_1^2\big ) \big (D + E y_2^2\big ) \big (D + E y_3^2\big ) \big (D + E y_4^2\big )$, $B + C\big (a_2 y_2^2 + y_2^4\big )$, $B + C\big (a_2 y_3^2 + y_2^4\big )$, $B + C\big (a_2 y_4^2 + y_2^4\big )$. This saves us $1M + 1M + 1M + 3M + 2M + 2M + 2M = 12M$.

Table 3 Computational complexity of the final computation: all $y_i$’s are retrieved

Table 4 Computational complexity of the final computation: only $y_1$ is retrieved

Instead of inverting $\big (D + E y_1^2\big ) \big (D + E y_2^2\big ) \big (D + E y_3^2\big ) \big (D + E y_4^2\big )$ we will invert $\big (D + E y_1^2\big )$ so we still need 1I.

In the end we needed extra 16M to compute $y_1, y_2, y_3, y_4$ (see the very end of Sect. 1). And now we will need 1M instead: this is the multiplication $\Big (B + C \big (a_2 y_1^2 + y_1^4\big )\Big ) \cdot \big (D + E y_1^2\big )^{-1}$. This saves us 15M.

In total we save $12M + 15M = 27M$ and the overall complexity becomes $(55M + 11S + 1I) - 27M = 28M + 11S + 1I$.

Furthermore, in the case when the decompression algorithm may output the projective coordinates of the point (which is acceptable e.g. when the decompressed point is used for the point addition or point doubling) we can avoid the inversion.

Appendix 3: Computational complexity of the decompression for $n = 5$

1.1 Preparation step

Table 2 shows the cost of computing $y_i^2, b_i$, $i = 1, 2, 3, 4, 5$ as well as C, F, G, H, K, L.

1.2 Final computation of $y_i$

Table 3 demonstrates the cost of the computation of $y_i$, $i = 1, 2, 3, 4, 5$ in the case when the goal is to retrieve the y-coordinates of all five points. Table 4 shows the cost of the computational complexity can be reduced significantly when the goal is to retrieve only one $y_i, i \in \{1, 2, 3, 4, 5\}$.

The overall computational complexity of the decompression algorithm is $120 M + 12 S + I$ in the case when the goal is to retrieve the y-coordinates of all five points. If only one point has to be retrieved the complexity reduces to $64 M + 12 S + I$. Furthermore, when the decompression algorithm may output the projective coordinates we can avoid the inversion.