Modifying Compression

Upon receiving the response $\sigma$, the verifier needs to ensure that it is an isogeny $E_A \rightarrow E_2$ of degree $D$, such that the composition with the challenge isogeny is cyclic. To send the response to the verifier, we want to find a compact and efficient representation of $\sigma$ that can be sent to the verifier.

We found that we needed to include an additional bit into the compressed representation $S$ of the response isogeny $\sigma: E_A \to E_2$ to ensure that it is correctly extracted during decompression. This page details the issue we faced and how an additional bit is enough to remove ambiguity.

Additionally, we detail our method of deterministically generating random points, which requires normalisation of the isogeny during compression. As far as we are aware, this does not appear in the SQISign paper, and so we include a few notes for the interested reader.

The page finishes with an overview of the algorithms with python snippets. For the whole implementation of the various sub-algorithms, see compression.py.

Overview of compression

The idea of the compression algorithm is to take an isogeny $\sigma$ and break it into pieces $\sigma = \sigma_v \circ \cdots \circ \sigma_1$ of degree at most $\ell^f$, such that each isogeny has degree dividing the available torsion and can be computed without extending the base field. We then find a canonical torsion basis of $E_A[2^f] = \langle R_1, Q_1 \rangle$ and represent $\ker(\sigma_1) = R_1 + [S_1]Q_1$ for some integer $S_1 < 2^f$. As one can compute the basis deterministically, it is enough to send a user $S_1$, from which the kernel (and hence the isogeny) can then be computed.

We can then iteratively repeat this. By using $Q_2 = \sigma_1(Q_1)$ as one basis element for the kernel of $\sigma_2$, we find an orthogonal $R_2$ though some deterministic method to compute $S_2$ corresponding to $\ker(\sigma_2)$ as above. SQISign additionally suggests that the compression stores a 4-bit value $s_i$ to help the decompression algorithm compute $R_i$ efficiently, i.e., there is some function such that Ri = compute_R(Ei, si).

Putting it all together, the integers $S_i$, $s_i$ can be packaged together in their binary representation to produce a bitstring of length $(f + 4)(v-1) + f$ (we do not need the hint $s_1$, as we compute the canonical torsion basis):

$$ S = S_1 \mathrel{||} s_2 \mathrel{||} S_2 \mathrel{||} \ldots \mathrel{||} s_v \mathrel{||} S_v. $$

Computing the kernel of an isogeny

To compute the kernel, we use the trick discussed on page Meet in the Middle to find $\sigma_i(R_i + [S_i]Q_i) = \OO$ such that $\sigma_i(R_i) = [-S_i] \sigma_i(Q_i)$. Then, all we need to do is to compute the image of the basis elements under the action of the isogeny and compute a discrete log. As the order of the points is $2^f$, this is very fast thanks to the Pohlig-Hellman algorithm. In the implementation, we further improve performance by mapping elliptic curve elements to finite field elements with the Weil pairing, which yields about a 30% improvement when solving the discrete log.

However, given a fixed random basis $E_A[2^f] = \langle R_1, Q_1 \rangle$, we know only that at least one of $\sigma_i(R_1)$ and $\sigma_i(Q_1)$ has order exactly $D$, so there will be isogenies whose kernel cannot be written into the prescribed format. To see why, let us look at how we can generate kernels.

Given $E_A[D] = \langle R, Q \rangle$ we can compute all possible kernels generators $K$ from the following linear combinations:

$$ K = [a]R + [b]Q, \quad a,b \in \mathbb{Z} / D\mathbb{Z}, \quad \gcd(a,b,D) = 1. $$

Note: the condition for at least one of the integers $a,b$ to be coprime with $D$ is to ensure that $K$ has order $D$. For the case when $D = 2^f$, we need at least one of $a,b$ to be odd.

As we are interested in cyclic isogenies, then any two points $K’ = [x]K$ for some integer $x$ such that $\gcd(x, D) = 1$, produce the same isogeny, so allowing $a,b$ to span all values will result in over-counting.

When we have $D = \ell^k$ for a prime power, we can always divide out by the coprime element to get one of two simple representations:

$$ \begin{aligned} K &= R + [b] Q, \qquad & &b \in \mathbb{Z} / \ell^k \mathbb{Z} \\ K &= [\ell a] R + Q, \qquad & &a \in \mathbb{Z} / \ell^{k-1} \mathbb{Z} \end{aligned} $$

Looking at this, we see that the SQISign method of writing $K_i = R_i + [S_i] Q_i$ will not capture every kernel, and there are isogenies $\sigma_i$ whose kernels cannot be compressed into a single integer $S_i$.

Specifically, the kernels which we cannot capture are those generated by elements which have an $\ell$-multiply of $R$. Take for example the point $K = [\ell]R + Q$. Looking at the image of $R,Q$ under the isogeny generated by $K$, we have: $\sigma(Q) = [-\ell]\sigma(R)$ and so $\sigma(Q)$ will only have order $\ell^{k-1}$.

When the order of $\sigma(Q)$ is smaller than the order of $\sigma(R)$, we will have no solution to the discrete logarithm and thus no integer $S_i$ to include in the compressed representation. So, how do we encode isogenies which are generated by these points?

The option we have chosen is to compute $R_1, Q_1$ canonically and then check if $\sigma(Q_1)$ has full order. When it does not, we simply swap $R_1, Q_1 = Q_1, R_1$ and we know our new $Q_1$ has full order. When this swap is performed, we set a swap bit $s_0 = \texttt{1}$ and $s_0 = \texttt{0}$ otherwise. By appending this single swap bit to our compressed bitstring, then the user decompressing knows to swap the order of the canonical torsion basis and all kernel generators in $E[D]$ can be represented.

We do not need to worry about storing a swap bit for any other isogeny in the chain. This is because we pick $K_i = R_i + [S_i]Q_i$ such that $Q_i$ is always orthogonal to $R_i$ and hence also to $K_i$. As $Q_i$ is orthogonal to $\ker(\sigma_i)$, $\sigma_i(Q_i)$ will always have full order and there will always be a solution to the discrete log for the next step.

With this method, we have a compressed representation of the response isogeny of length $(f + 4)(v-1) + f + 1$:

$$ S = s_0 \mathrel{||} S_1 \mathrel{||} s_2 \mathrel{||} S_2 \mathrel{||} \ldots \mathrel{||} s_v \mathrel{||} S_v. $$

Computing deterministic orthogonal points

The second part of the compression algorithm which requires careful attention is the deterministic generation of the orthogonal points $R_i \in E_i$.

In compression, we have an isogeny $\sigma_i$, and from this we compute a kernel $R_i + [S_i]Q_i$. In decompression, the user receives the domain $E_i$ and $S_i$. The basis for the kernel is deterministically generated and, from this, $\sigma_i’$ is computed from $K_i$.

However, although these isogenies have the same kernel generators, the isogenies $\sigma_i$ and $\sigma_i’$ only agree on a codomain up to isomorphism. This is no problem for computing the isogeny walk itself, but it is an issue for deterministically generating random points.

For compression, we expect the user to take the curve $E_i$, with the point $Q_i$ and to randomly sample points $P \in E_i$ until a point orthogonal to $Q_i$ is found, which we name $R_i$. The hint $s_i$ tells the decompression algorithm to take the $s_i^{\text{th}}$ point, which avoids computing expensive checks. As $s_i$ has only four bits allocated to it, if we require more than 15 samples, all $s_i$ can communicate is “skip the first 15 samples and check each point after that”. In practice, we usually find $R_i$ in much less than 15 queries.

However, if one naively computes $S_i$ and sends this to be decompressed, then the compressor samples random points on $E_{i+1}$, where as the decompressor samples from points on $E_{i+1}’$, where we have $E_{i+1} \cong E_{i+1}’$, but not necessarily equality. As a result, the points $R_i$ obtained from compression will not align with points $R_i’$ sampled during decompression.

To fix this issue, we normalise the isogeny chain during compression by computing additional isogenies. The trick is to take $\sigma_i$ and compute $S_i$ such that $K_i = R_i + [S_i]Q_i$. Then we compute a new isogeny $\sigma_i’ : E_{i} \to E_{i} / \langle K_i \rangle = E_{i+1}’$, which is the isogeny that the decompression will obtain. Then $Q_{i+1} = \sigma_i’(Q_i)$ is computed. Finally, we have to alter $\sigma_{i+1}$ with an isomorphism so that its domain matches the codomain of the newly derived $\sigma_{i}’$. This makes compression more expensive (we must compute $v$ additional isogenies after computing the kernel), but it ensures that decompression will generate $R_i \in E_i$ which match precisely with those sampled during compression.

Practically, we find random points which can be obtained from a hint $s_i$ by seeding the random number generator of SageMath. We also have to be careful to pick the same result from the lift as SageMath returns $P,-P$ with equal probability.

def generate_random_point(E, seed=None):
    """
    E.random_point() returns either P
    or -P with equal probability.

    We always select the element with
    smaller y-coordinate to make this
    deterministic.
    """
    # Allow a setting of the seed to
    # ensure the same point is always returned
    if seed is not None:
        set_random_seed(seed)

    P = E.random_element()
    return min(P, -P)

Compression

With the swap bit addressed and the isogeny chain normalised to ensure the correct points $R_i$ are sampled, we can now implement the compression algorithm as described in the SQISign paper. We outline it below for completeness.

Split an isogeny $\sigma$ into $v$ pieces: $\sigma = \sigma_v \circ \cdots \circ \sigma_1$, where each isogeny has degree dividing $2^f$. In practice only $\sigma_v$ will have degree less than or equal to $2^f$.
Compute the canonical torsion basis $E_A[2^f] = \langle R_1, Q_1 \rangle$.
If $\sigma_1(Q_1)$ has order less than $2^f$, then set $R_1,Q_1 = Q_1,R_1$ and set the sign bit $s_0 = \texttt{1}$, otherwise set $s_0 = \texttt{0}$. Add $s_0$ to the bitstring $S$.
Compute a generator of $\ker(\sigma_i)$ as $K_1 = R_1 + [S_1]Q_1$. Add $S_1$ to $S$ as a bitstring of length $f$.
Compute $\sigma_1’ : E_A \to E_A / \langle K_1 \rangle$. Set $Q_2 = \sigma_1’(Q_1)$.
Loop for $i \in \{ 2,\ldots,v \}$:
1. Using an isomorphism, ensure the domain of $\sigma_{i}$ is equal to the codomain of $\sigma_{i-1}$ (the curve $Q_i$ is defined on). Set $E_i$ as this curve.
2. Compute a point $R_i \in E_i$ orthogonal to $Q_i$. Add the hint $s_i$ to $S$ to represent how many points were searched before finding $R_i$. If 15 or more curves were checked, set $s_i = \texttt{1111}$.
3. Compute a generator $K_i$ of $\ker(\sigma_i) = \langle R_i + [S_i] Q_i \rangle$. Add $S_i$ to $S$.
4. Compute $\sigma_i’ : E_i \to E_{i} / \langle K_i \rangle$ and set $Q_{i+1} = \sigma_i’(Q_i)$.
Output the bitstring: $$ S = s_0 \mathrel{||} S_1 \mathrel{||} s_2 \mathrel{||} S_2 \mathrel{||} \ldots \mathrel{||} s_v \mathrel{||} S_v. $$

A SageMath implementation of the above is as follows:

def compression(E, σ, l, f):
    """
    Given an isogeny σ of degree l^e = l^vf compute a
    compressed representation of the isogeny as a bitstring
    in the form:

    S = swap_bit || S1 || s2 || S2 || ... || sv || Sv

    Note: swap_bit denotes when the torsion basis of the first
    step must be swapped: R, Q = Q, R to ensure a solution to
    the discrete log. This bit is needed to communicate to decom.
    to do the same swap.
    """
    S = ""

    # Split σ into v isogenies of degree f
    σ_chain = isogeny_into_blocks(σ, l**f)
    assert E == σ_chain[0].domain(), "Supplied curve is incorrect"


    # Compute a canonical torsion basis
    σ1 = σ_chain[0]
    D = σ1.degree()
    R1, Q1 = torsion_basis(E, D, canonical=True)

    # Solve the discrete log and compute the image of σ1(Q1)
    S1, Qi, swap_bit = compute_S_and_next_Q(σ1, R1, Q1, f, first_step=True)

    # Add the swap bit, as well as the dlog solution 
    S += str(swap_bit)
    S += S1

    # For the remaining steps, we can use Qi as one
    # basis element so we only need to compute some
    # Ri linearly independent to Qi. There will always
    # be a solution to the dlog as Qi has order D.
    for σi in σ_chain[1:]:
        # We need to align the next step in the chain
        # with σ_new computed previously, which means
        # mapping the domain of the next step with the
        # codomain of the last step.
        Ei = Qi.curve()
        iso = Ei.isomorphism_to(σi.domain())
        σi = σi * iso
        assert Ei == σi.domain()

        D = σi.degree()
        # The last element of the chain has degree D | l^f
        # So we can ensure Qi ∈ E[D] by multiplying by a
        # cofactor
        if D != l**f:
            cofactor = l**f // D
            Qi = cofactor * Qi

        # Add hint to compression to help decompression
        # recover Ri
        Ri, hint = compute_R(Ei, Qi, D)
        S += hint_to_bitstring(hint)

        # Add dlog to compression and derive next Qi
        Si, Qi, _ = compute_S_and_next_Q(σi, Ri, Qi, f)
        S += Si

    # Our compressed rep. is 1 bit longer as we encode the swap bit
    v = len(σ_chain)
    assert len(S) == (v - 1) * (f + 4) + f + 1

    return S

Decompression

With the additional sign-bit and normalisation which we applied during compression, the process of decompression follows the algorithm given in the SQISign paper pretty closely. We repeat it here for completeness.

Take the given bitstring $S$ and compute the swap bit $s_0$, the integers $S_i$ to compute the kernels and the integers $s_i$ to compute orthogonal points.
Given the public key $E_A$, compute a torsion basis $E_A[2^f] = \langle R_1, Q_1 \rangle$. If $s_0 = 1$, set $R_1, Q_1 = Q_1, R_1$.
Loop for $i \in \{ 1,\ldots,v-1 \}$:
1. Compute the kernel $K_i = R_i + [S_i] Q_i$ and compute the isogeny $\sigma_i : E_i \to E_i / \langle K_i \rangle$.
2. Compute $Q_{i+1} = \sigma_i(Q_i)$, which by construction is orthogonal to $K_i$ and has order $2^f$.
3. Using the hint $s_i$ compute the point $R_{i+1}$ orthogonal to $Q_{i+1}$.
Correct the order of the last step: given the step length and degree of $\sigma$, compute the length of the final step. Ensure that $R_v, Q_v$ have the correct order by clearing the cofactor.
Compute $K_v = R_v + [S_v]Q_v$ and the corresponding isogeny $\sigma_v$.
Compute the composition $\sigma = \sigma_v \circ \cdots \circ \sigma_1$.
Compute the isomorphism from the codomain of $\sigma$ to $E_2$. Post compose with this isomorphism to ensure that $\sigma : E_A \to E_2$.

As we have encoded the swap in $s_0$ and computed all the isomorphisms during compression, then there are no additional checks or worries. This isogeny can now be processed and verified to complete SQISign.