# On the Non-repudiation of Isogeny Based Signature Scheme

Sookyung Eom, Hyang-Sook Lee, Seongan Lim

► To cite this version:

Sookyung Eom, Hyang-Sook Lee, Seongan Lim. On the Non-repudiation of Isogeny Based Signature Scheme. 12th IFIP International Conference on Information Security Theory and Practice (WISTP), Dec 2018, Brussels, Belgium. pp.63-77, 10.1007/978-3-030-20074-9_6. http-02294595

HAL Id: hal-02294595

https://hal.science/hal-02294595

Submitted on 23 Sep 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
On the Non-repudiation of Isogeny based
Signature Scheme

Sookyung Eom¹, Hyang-Sook Lee² and Seongan Lim¹

¹Institute of Mathematical Sciences,
²Department of Mathematics,
Ewha Womans University, Seoul, Korea
{esk9030, hsl, seongannym}@ewha.ac.kr

*

Abstract

For a digital signature scheme, unforgeability and non-repudiation are
two main security requirements. In 2017, Galbraith, Petit and Silva pre-
sented GPS signature, an efficient isogeny based signature with a proven
unforgeability. In this paper, we present a successful key substitution
attack on GPS signature which threaten the non-repudiation of GPS sig-
nature. We also suggest how to prevent key substitution attack in general
as well as our attack in this paper. We also present an example of our
attack using Sage to illustrate isogenies of elliptic curves and our attack.

**Keywords.** Isogeny-based signature, non-repudiation, Post-quantum cryp-
tography

# 1 Introduction

The essential security goals of digital signatures include integrity of the signed data, authenticity of the signed data and the signer, and non-repudiation of the origin of the signature. The unforgeability of a signature scheme guarantees the integrity and authenticity of the signature scheme. Therefore, unforgeability and non-repudiation are two main security requirements for signature schemes. The forgeability of a signature can be an evidence of the failure of non-repudiation

<footnote>*Sookyung Eom(Corresponding author) was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea Government(No.2016R1C1B2013851). Hyang-Sook Lee was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Science, ICT and Future Planning(No.2018R1A2A1A05079095). Seongan Lim was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea Government(No.2016R1D1A1B01008562).</footnote>
of the signature scheme, and thus, the issue of non-repudiation of a signature
can be addressed only for unforgeable signatures. However, the unforgeability
of a signature may not guarantee the non-repudiation of the signature [6, 1].

It suggests that further analysis on the non-repudiation of unforgeable signa-
ture schemes is necessary, especially for the newly presented signature schemes
such as post-quantum signatures (secure signatures in the presence of quantum
computers). The isogeny-based public key cryptography is widely studied as a
candidates of post-quantum signatures due to short key sizes and compatibil-
ity with the current elliptic curve primitives [10, 3, 4, 15]. In [12], Galbraith,
Petit and Silva presented an efficient isogeny based signature, which we call it
as GPS signature, by applying the Fiat-Shamir transformation [2] to the De
Feo-Jao-Plût identification [10]. GPS signature scheme is proven unforgeable
under the hardness assumptions of some isogeny problems in the random oracle
model [12].

In this paper, we study the non-repudiation of GPS signature scheme. We present a successful key substitution attack, one of the most basic attack which threaten the non-repudiation of a digital signature scheme. Our attack on GPS signature implies that the non-repudiation fails for the current version of GPS signature. Our result is the first key substitution attack on isogeny based sig-nature schemes under the consideration of the non-repudiation of the signature. Since the non-repudiation has not been considered in the current design of isogeny based signatures even though it is one of the main security issues of digital signature schemes, we believe that our result would put forward fur-ther studies on secure design of isogeny based signatures. Our attack on GPS signature uses isomorphisms on the underlying elliptic curves and the fact that isomorphic elliptic curves have the same *j*-invariants. We recommend to restrict different *j*-invariants for each public key to prevent our key substitution attack in this paper. Moreover, we suggest to format the message as specific to each public key, such as *pk||message*, prior to signing according to the analysis of Menezes and Smart [1].

The paper is organized as follows. In Section 2, we give preliminaries on isogeny, non-repudiation of signature and key substitution attack. Section 3 describes our key substitution attack on GPS signature scheme using isomorphism and explain why the non-repudiation fails for GPS signature with an example of our key substitution attack. We also discuss countermeasures of our attack on GPS signature. Section 4 concludes the paper.

## 2 Preliminaries

In this section, we review some concepts and properties of isogenies of elliptic curves and isogeny problems related to GPS signature. We also recall the definition of key substitution attack for digital signature schemes and its impacts on the non-repudiation of signatures.
## 2.1 Elliptic Curves and $j$-invariants

**Definition 2.1.** (Elliptic curve [9]) An elliptic curve over a field $K$ is a smooth projective plane curve of genus one having a specified distinguished point. Projective Weierstrass equation of an elliptic curve over a field $K$ is

$$E(\mathbb{K}) : Y^2Z + a_1XYZ + a_3YZ^2 = X^3 + a_2X^2Z + a_4XZ^2 + a_6Z^3;$$

Affine Weierstrass equation of an elliptic curve over a field $K$ is

$$E(\mathbb{K}) : y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6 \text{ with } \infty;$$

When $\text{char } K \neq 2,3$, we can write

$$E(\mathbb{K}) : y^2 = x^3 + ax + b;$$

with $a,b \in \mathbb{K}$ such that $\Delta = -16(4a^2 + 27b^2) \neq 0$ for smoothness condition.

Standard projective coordinates are used to represent the points of elliptic curve $y^2 = x^3 + ax + b$. In standard projective coordinates, the triple $(X,Y,Z)$ represents the affine point $(x = X/Z, y = Y/Z)$ of the curve. We use the standard projective coordinates in our example in Section 3.2.

**Definition 2.2.** (j-invariant [9]) Let $E$ be the elliptic curve given by $y^2 = x^3 + ax + b$, where $a,b$ are elements of a field $K$ of characteristic not 2 or 3. Define the $j$-invariant of $E$ to be

$$j = j(E) = 1728 \frac{4a^3}{4a^3 + 27b^2}.$$

Given an elliptic curve $E$, its $j$-invariant can be found in polynomial-time; moreover, given a $j$-invariant $j^* \in \mathbb{K}$, one can find a curve $E$ with $j(E) = j^*$ in polynomial time. As the name suggests, the $j$-invariant is invariant under $\overline{\mathbb{K}}$-isomorphisms of algebraic sets, and so a $j$-invariant uniquely identifies a $\overline{\mathbb{K}}$-isomorphism class of elliptic curves over $\mathbb{K}$.

**Theorem 2.3.** [9] Let $E_1(\mathbb{K}) = \{(x_1, y_1)|y_1^2 = x_1^3 + a_1x_1 + b_1\}$ and $E_2(\mathbb{K}) = \{(x_2, y_2)|y_2^2 = x_2^3 + a_1x_2 + b_1\}$ be two elliptic curves over the field $\mathbb{K}$ with the $j$-invariants $j_1$ and $j_2$, respectively. If $j_1 = j_2$, then there exists $\mu \neq 0$ in the algebraic closure $\overline{\mathbb{K}}$ such that $a_2 = \mu^4a_1$, $b_2 = \mu^6b_1$. The transformation $x_2 = \mu^2x_1$, $y_2 = \mu^3y_1$ takes one equation to the other.

## 2.2 Isogeny

**Definition 2.4.** (Isogeny [9]) Let $E$ and $E'$ be elliptic curves defined over a field $K$. An isogeny from $E$ to $E'$ is a non constant morphism $\phi : E \to E'$ that maps the neutral element into the neutral element.
An isogeny $\phi : E \to E'$ over a finite field $\mathbb{F}_q$ can be represented as a rational map whose coefficients belong to $\mathbb{F}_q$. An isogeny of degree $m$, when it is considered as a rational map, is called an $m$-isogeny. If $\phi$ is a separable isogeny, then $\deg\phi = |ker\phi|$ [10]. If there is a separable isogeny between two curves, we say that they are isogenous. A theorem of Tate in [7] says that if $E$ and $E'$ are defined over a finite field $\mathbb{F}_q$, then $E$ and $E'$ are isogenous over $\mathbb{F}_q$ if and only if $|E(\mathbb{F}_q')| = |E'(\mathbb{F}_q')|$ for every finite extension $\mathbb{F}_q'$ of $\mathbb{F}_q$. In [8], it has been shown that $E'$ is isogenous to $E$ over $\mathbb{F}_q$ if and only if $E$ is isogenous to $E'$ over $\mathbb{F}_q$. The isogeny class of a curve $E$ over $\mathbb{F}_q$ is defined to be the set of all curves $E'$ which are isogenous to $E$, up to $\mathbb{F}_q$-isomorphism. Since any algebraic morphism of curves is either constant or surjective [11], if $\phi : E \to E'$ is a nontrivial isogeny, then $\phi(E) = E'$.

An isogeny $\phi : E \to E'$ such that $E = E'$ is called an endomorphism. The set of endomorphisms of an elliptic curve $E$ denote $End(E)$. For a finite field $\mathbb{F}$, this set $End(E)$ is a $\mathbb{Z}$ module of rank 2 or 4. We say that $E$ is supersingular if the rank of $End(E)$ as a $\mathbb{Z}$ module is 4, and ordinary otherwise. Any supersingular elliptic curve $E$ is defined over $\mathbb{F}_{p^2}$ for some prime $p$, and for each prime $m \neq p$ there are $m + 1$ isogenies of degree $m$ with domain $E$ (though not all of them are defined over $\mathbb{F}_{p^2}$, in general)[10]. These isogenies of degree $m$ are in one-to-one correspondence with the subgroups of $E$ of order $m$; moreover, each such subgroup $\Phi \subset E$ is the kernel of a unique isogeny $\phi$, and we write $\phi(E) = E/\Phi$ [8]. That is, an isogeny can be identified with its kernel [14]. Hence to specify an isogeny it suffices to specify its kernel, and conversely given a subgroup $\Phi$ of $E$ we can construct the isogeny $\phi$ whose kernel is $\Phi$, using Velu's formulae [13].

If we have two isogenies $\phi : E \to E'$ and $\phi' : E' \to E$ such that $\phi \cdot \phi'$ and $\phi' \cdot \phi$ are the identity maps, we say that $\phi, \phi'$ are isomorphisms and $E$ and $E'$ are isomorphic. The isomorphic elliptic curves over finite field can be named with their $j$-invariant.

## 2.3 Computational Isogeny Problems relating to GPS signature

There are several hard problem candidates related to supersingular elliptic curves, we present the problems related to the security of GPS signature scheme. The GPS signature scheme is based on De Feo-Jao-Plût identification protocol [10] which uses *isogeny smooth prime* defined as follows.

**Definition 2.5.** (*isogeny smooth prime*[10]) A prime $p$ is called isogeny smooth prime if $p = \ell_1^{e_1} \ell_2^{e_2} f \pm 1$ where $\ell_1$ and $\ell_2$ are two distinct small primes, and $e_1, e_2$ and $f$ are positive integers.

The security of GPS signature scheme relies on Computational Supersingular Isogeny (CSSI) and Decisional Supersingular Product (DSSP) problems from [10]. Let $E_0$ and $E_1$ be supersingular elliptic curves over $\mathbb{F}_{p^2}$ for an isogeny smooth prime $p$, that is, $p = \ell_1^{e_1} \ell_2^{e_2} f \pm 1$. Let $\{R_1, S_1\}$ and $\{R_2, S_2\}$ be bases for $E_0[\ell_1^{e_1}]$ and $E_0[\ell_2^{e_2}]$, respectively.
**Problem 2.6. (Computational Supersingular Isogeny - CSSI)**

Let $\phi_1: E_0 \to E'$ be an isogeny with kernel $\langle[m_1]R_1 + [n_1]S_1\rangle$, where $m_1, n_1$ are chosen uniformly at random from $\mathbb{Z}/\ell_1^{e_1}\mathbb{Z}$, and not both divisible by $\ell_1$. The problem is, given $(E', (\phi_1(R_2), \phi_1(S_2)))$, to find a generator of $\langle[m_1]R_1 + [n_1]S_1\rangle$.

**Problem 2.7. (Decisional Supersingular Product - DSSP)**

Let $\phi: E_0 \to E_1$ be an isogeny of degree $\ell_1^{e_1}$. The problem is, given

$$((E_0, E_1), (R_2, S_2, \phi(R_2), \phi(S_2)), (E_2, E_3)),$$

to determine from which distribution the pair $(E_2, E_3)$ is sampled;

* $(E_2, E_3)$ such that there is a cyclic group $G \subseteq E_0[\ell_2^{e_2}]$ of order $\ell_2^{e_2}$ and $E_2 \cong E_0/G$ and $E_3 \cong E_1/\phi(G)$.

* $(E_2, E_3)$ where $E_2$ is chosen at random among the curves having the same cardinality as $E_0$, and $\phi: E_2 \to E_3$ is a random $\ell_1^{e_1}$-isogeny.

As discussed in [10] and [12], the problems CSSI and DSSP are non-standard isogeny problems since they use special primes as isogeny smooth prime, use somewhat small isogeny degrees, and reveal auxiliary points. In general, the problems CSSI and DSSP are proven to be exponentially hard even under quantum attack [10], but it is known that revealing auxiliary points may be dangerous in certain context. Even with such concern on the underlying computational problems CSSI and DSSP, GPS signature is simple to describe and easy to implement which could be very important advantages in practice.

## 2.4 Non-repudiation of Signature Scheme and Key Substitution Attack

A digital signature scheme consists of three polynomial time algorithms

(KeyGen, Sign, Verify)

which are defined as follows:

* **KeyGen(1^λ):** On a given security parameter $\lambda$, the algorithm KeyGen outputs a pair $(pk, sk)$ of keys, where $pk$ is a public key for signature verification and $sk$ is a private key for signature generation. The private key $sk$ is kept secret by the owner of the public key $pk$.

* **Sign(sk, m ∈ {0, 1}^*):** On a given message $m \in \{0, 1\}^*$ and a private key $sk$, the algorithm Sign outputs a signature $\sigma_m$.

* **Verify(m, σ_m, pk):** On a given input $((m, σ_m), pk)$, the algorithm Verify outputs $1(= \text{valid})$ or $0(= \text{invalid})$.

We say that a digital signature is correct if

$$\text{Verify}(m, \text{Sign}(sk, m \in \{0, 1\}^*), pk) = 1$$
for any $(pk, sk) \leftarrow KeyGen(1^{\lambda})$ and message $m$. The existential unforgeability (EUF) of a signature requires that it is infeasible for anyone to compute a valid signature under a public key $pk$ without knowing the private key $sk$. Generally, a secure signature scheme means EUF-CMA (existential unforgeable against chosen message attack) secure which is defined as follows.

**Definition 2.8. (EUF-CMA)**

A digital signature scheme (KeyGen, Sign, Verify) is EUF-CMA secure if for all probabilistic polynomial-time algorithm $\mathcal{A}$ with access to a signing oracle $\text{Sign}(\cdot, sk)$, there is a negligible function $\epsilon(\cdot)$ such that:

$$ \Pr \left[ \begin{array}{l} \left( pk, sk \right) \leftarrow \text{KeyGen}(1^{\lambda}) \\ \left( m^*, \sigma^* \right) \leftarrow \mathcal{A}^{\text{Sign}(\cdot, sk)}(pk) \quad : \left( m^* \notin Q \right) \land (\text{Verify}(m^*, \sigma^*, pk) = 1) \end{array} \right] \le \epsilon(\lambda), $$

where $Q$ is the set of queries which $\mathcal{A}$ has accessed to the signing oracle.

The non-repudiation of a signature requires that it is infeasible for the signer to repudiate his/her signing on a valid signature under the public key $pk$ of the signer. For a digital signature scheme, unforgeability and non-repudiation are two main security requirements which seem to be closely related. The existence of a forged signature of a signature scheme lets the signer to claim his/her signed signature as a forged signature. Therefore, issue of non-repudiation of a signature is to be considered only for EUF-CMA secure signatures. It is known that unforgeability of signature may not guarantee the non-repudiation of the signature [1, 6].

We focus on the non-repudiation of digital signatures in this paper. The most basic attack for the non-repudiation is the public key substitution attack. The goal of public key substitution attack is to compute a new public key $pk'$ where a valid signature $\sigma$ on a message $m$ under a public key $pk$ can be also validated under $pk'$. Therefore, any signer can repudiate his/her signing on a signature $\sigma$ on a message by using the existence of a successful key substitution attack. More precisely, the signer, the owner of public key $pk$, computes $pk'$ by using a key substitution attack and claims that the signature $\sigma$ is signed by the owner of $pk'$, not himself/herself. The key substitution attack has been formalized as follows.

**Definition 2.9. (Key Substitution Attack) [6]**

Given a signature scheme (KeyGen, Sign, Verify), a key substitution attack is a probabilistic polynomial-time algorithm $\mathcal{A}$ which on input of valid domain parameters outputs two valid public keys $pk$ and $pk'$ and a message/signature pair $(m, \sigma)$ where Verify($m, \sigma, pk$) and Verify($m, \sigma, pk'$) each return $1(= \text{valid})$. A digital signature scheme is key substitution secure if it is secure against key substitution attacks.

Since the potential attacker for the non-repudiation of a signature scheme is the original signer, one can assume that the key substitution attacker for the non-repudiation of a signature knows the private key of the original signature
and the private information, such as nonce, used during signing process. And this contrasts the potential attackers against the unforgeability of a signature scheme.

# 3 Results

## 3.1 GPS Signature Scheme

This section recalls a signature scheme in [12], which we call it as GPS signature. Let $p$ be a large isogeny smooth prime, that is, $p = \ell_1^{e_1} \ell_2^{e_2} \cdot f \pm 1$, where $\ell_1, \ell_2$ are small primes (typically $\ell_1 = 2$ and $\ell_2 = 3$). We define a supersingular elliptic curve $E_0$ over $\mathbb{F}_{p^2}$ with $|E_0(\mathbb{F}_{p^2})| = \ell_1^{e_1} \ell_2^{e_2} \cdot f$ and a primitive $\ell_1^{e_1}$-torsion point $P_1 \in E_0$. Define $E_1 = E_0/\langle P_1 \rangle$ and denote the corresponding $\ell_1^{e_1}$-isogeny by $\phi: E_0 \to E_1$. In [12], Galbraith, Petit and Silva apply the Fiat-Shamir transform [2] to the De Feo-Jao-Pl\'ut identification scheme, and construct GPS signature which is described as follows.

**KeyGen(1^λ):** On input a security parameter $\lambda$, the algorithm proceeds the following steps:

* generate a prime $p = \ell_A^{e_1} \ell_B^{e_2} \cdot f \pm 1$ with at least $4\lambda$ bits for small $\ell_1, \ell_2, f$ (ideally $f = 1, \ell_1 = 2, \ell_2 = 3$) and $\ell_1^{e_1} \approx \ell_2^{e_2}$.

* choose a supersingular elliptic curve $E_0$ with $j$-invariant $j_0$.

* compute points $R_2, S_2 \in E_0(\mathbb{F}_{p^2})[\ell_2^{e_2}]$ and a random primitive $\ell_1^{e_1}$-torsion point $P_1 \in E_0[\ell_1^{e_1}]$.

* compute an isogeny $\phi: E_0 \to E_1$ with kernel generated by $P_1$, and let $j_1$ be the $j$-invariant of the image curve.

* set $R'_2 = \phi(R_2), S'_2 = \phi(S_2)$.

* choose a hash function $H$ with $t = t(\lambda)$ bits of output.

* output

$$pk = (p, j_0, j_1, R_2, S_2, R'_2, S'_2, H), sk = P_1.$$

**Sign(sk = $P_1, m \in \{0, 1\}^*$):** On the given input, the algorithm proceeds the following steps:

* for $i = 1, \dots, t$,

- choose random integers $0 \le \alpha_i < \ell_2^{e_2}$.

- compute an isogeny $\psi_i: E_0 \to E_{2,i}$ with the kernel generated by $R_2 + [\alpha_i]S_2$ and let $j_{2,i} = j(E_{2,i})$.

- compute an isogeny $\psi'_i: E_1 \to E_{3,i}$ with the kernel generated by $R'_2 + [\alpha_i]S'_2$ and let $j_{3,i} = j(E_{3,i})$.

- compute

$$h = H(m, j_{2,1}, \dots, j_{2,t}, j_{3,1}, \dots, j_{3,t}) = b_1 b_2 \cdots b_t \in \{0, 1\}^t.$$
* for $i = 1, \dots, t$,

- if $b_i = 0$ then set $z_i = \alpha_i$.

- if $b_i = 1$ then compute $\psi_i(P_1)$ and set $z_i = (j_{2,i}, \psi_i'')$ where $\psi_i'' : E_{2,i} \to E_{3,i}$ is an isogeny with the kernel generated by $\psi_i(P_1)$.

* output

$$ \sigma_m = (h = b_1 b_2 \cdots b_t, z_1, \dots, z_t) $$

Verify($m, \sigma_m, pk$): On the given input,

* from $pk$, recover the parameters $p, E_0, E_1$.

* for each $1 \le i \le t$, using the information provided by $z_i$, one recompute the $j$-invariants $j'_{2,i}$ and $j'_{3,i}$.

- in the case $b_i = 0$ this is done by using $z_i = \alpha_i$ and computing $j'_{2,i}$ from the isogeny with kernel generated by $R_2 + [\alpha_i]S_2 \in E_0$ and $j'_{3,i}$ from the isogeny with the kernel generated by $R_2 + [\alpha_i]S_2 \in E_1$.

- when $b_i = 1$ then the value $j_{2,i}$ and a description of the isogeny $\psi_i'' : E_{2,i} \to E_{3,i}$ is provided in $z_i$. The verifier computes $j'_{2,i} = j_{2,i}$ and $j'_{3,i}$ as the $j$-invariant of the image curve of $\psi_i''$ which means that $j'_{3,i} = j(E_{2,i}/\text{Ker}(\psi_i'')) = j(E_{3,i})$.

* compute $h' = H(m, j'_{2,1}, \dots, j'_{2,t}, j'_{3,1}, \dots, j'_{3,t})$.

* output $1(= \text{valid})$ if and only if $h' = h$.

**Theorem 3.1 ([12]).** If the problems CSSI (Computational Supersingular Isogeny) and DSSP (Decisional Supersingular Product) are computationally hard then the signature above, GPS signature, is secure in the random oracle model under a chosen message attack.

## 3.2 Our Attack on the Non-repudiation of GPS Signature

Now we show that GPS signature fails to provide non-repudiation of the signature. In particular, we present a key substitution attack on GPS signature for a signer to repudiate his/her signature. We describe our attack in general and present an example.

### 3.2.1 A description of Our Key Substitution Attack

Our attack uses isomorphism of elliptic curves. A legal but malicious user $U$ creates two public keys

$$ pk = (p, j_0, j_1, R_2, S_2, R'_2, S'_2, H), \quad \text{and} \quad pk' = (p, j_0, j_1, \tilde{R}_2, \tilde{S}_2, \tilde{R}'_2, \tilde{S}'_2, H) \quad (1) $$

$$ \bullet \eta_0(\tilde{P}_1) = P_1, \eta_0(\tilde{R}_2) = R_2, \eta_0(\tilde{S}_2) = S_2 \text{ and} $$
$$ \bullet \eta_1^{-1} \cdot \phi \cdot \eta_0(\tilde{R}_2) = \tilde{R}_2', \eta_1^{-1} \cdot \phi \cdot \eta_0(\tilde{S}_2) = \tilde{S}_2' $$

for some isomorphisms $\eta_0 : E'_0 \to E_0$ and $\eta_1 : E'_1 \to E_1$ with the inverses
$\eta_0^{-1} : E_0 \to E'_0$ and $\eta_1^{-1} : E_1 \to E'_1$, respectively.

The public key $pk'$ is correctly formulated by using the isogeny $\eta_1^{-1} \cdot \phi \cdot \eta_0 : E'_0 \to E'_1$ with kernel generated by $\tilde{P}_1$. We set $\tilde{\phi} = \eta_1^{-1} \cdot \phi \cdot \eta_0$.

The following commutative diagram explains the relations between $pk$ and $pk'$.

<figure><img src="image_2.png" /></figure>

Now we prove that the user with the public key $pk'$ succeed a key substitution attack on GPS signature scheme.

**Theorem 3.2.** Let the public keys $pk = (p, j_0, j_1, R_2, S_2, R'_2, S'_2, H)$ and $pk' = (p, j_0, j_1, \tilde{R}_2, \tilde{S}_2, \tilde{R}'_2, \tilde{S}'_2, H)$ of GPS signature be given as in Equation 1. For any valid signature $\sigma_m = (h = b_1b_2\cdots b_t, z_1, \dots, z_t)$ on a message $m \in \{0,1\}^*$ under the public key $pk$, $\sigma_m$ is a valid signature on the message $m \in \{0,1\}^*$ under the public key $pk'$.

*Proof.* From the validity of $\sigma_m = (h = b_1b_2\cdots b_t, z_1, \dots, z_t)$ as a signature on the message $m \in \{0,1\}^*$ under the public key $pk$, the followings hold,

* for the $i = 1, \dots, t$ with $b_i = 0$, which implies that $z_i = \alpha_i$,
  $-j_{2,i} = j(E_0/\langle R_2 + [\alpha_i]S_2 \rangle)$ and $j_{3,i} = j(E_0/\langle R'_2 + [\alpha_i]S'_2 \rangle)$.

* for the $i = 1, \dots, t$ with $b_i = 1$, which implies that $z_i = (j_{2,i}, \psi_i' : E_{2,i} \to E'_{3,i})$, $j_{3,i} = j(E_{2,i}/\langle Ker(\psi_i'') \rangle) = j(E'_{3,i})$.

* $h = b_1b_2\cdots b_t = H(m, j_{2,1}, \dots, j_{2,t}, j_{3,1}, \dots, j_{3,t})$.

Now we show that $\sigma_m$ is also a valid signature on $m$ under $pk'$. From $(m, \sigma_m)$, anyone can verify the validity of $\sigma_m$ as a signature on $m$ under $pk'$ as follows:

* If $b_i = 0$, that is, $z_i = \alpha_i$, any verifier computes $(j'_{2,i}, j'_{3,i})$ as follows by using $pk'$ which turns out $(j'_{2,i}, j'_{3,i}) = (j_{2,i}, j_{3,i})$:
- The verifier computes $j'_{2,i} = j(E'_0/\langle \tilde{R}_2 + [\alpha_i]\tilde{S}_2 \rangle)$ from an isogeny $\tilde{\psi}_i : E'_0 \to E'_{2,i}$ whose kernel is generated by $\tilde{R}_2 + [\alpha_i]\tilde{S}_2$. We want to show that $j'_{2,i} = j_{2,i}$. Since $\eta_0 : E_0 \to E'_0$ is an isomorphism, we have

$$j'_{2,i} = j(E'_0/\langle Ker(\tilde{\psi}_i) \rangle) = j(E_0/\langle Ker(\tilde{\psi}_i \cdot \eta_0^{-1}) \rangle).$$

We also have that $Ker(\tilde{\psi}_i \cdot \eta_0^{-1}) = \langle R_2 + [\alpha_i]S_2 \rangle$ from the fact

$$\eta_0^{-1}(R_2 + [\alpha_i]S_2) = \eta_0^{-1}(R_2) + [\alpha_i]\eta_0^{-1}(S_2) = \tilde{R}_2 + [\alpha_i]\tilde{S}_2.$$

Therefore, $j'_{2,i} = j(E_0/Ker(\tilde{\psi}_i \cdot \eta_0^{-1})) = j(E_0/\langle R_2 + [\alpha_i]S_2 \rangle) = j_{2,i}$

- The verifier computes $j'_{3,i} = j(E'_1/\langle \tilde{R}'_2 + [\alpha_i]\tilde{S}'_2 \rangle)$ from an isogeny $\tilde{\psi}'_i : E'_1 \to E'_{3,i}$ whose kernel is generated by $\tilde{R}'_2 + [\alpha_i]\tilde{S}'_2$. We want to show that $j'_{3,i} = j_{3,i}$. Since $\eta_1 : E_1 \to E'_1$ is an isomorphism, we have

$$j'_{3,i} = j(E'_1/\langle Ker(\tilde{\psi}_i) \rangle) = j(E_1/\langle Ker(\tilde{\psi}_i \cdot \eta_1^{-1}) \rangle).$$

We also have that $Ker(\tilde{\psi}_i \cdot \eta_1^{-1}) = \langle R'_2 + [\alpha_i]S'_2 \rangle$ from the fact

$$\eta_1^{-1}(R'_2 + [\alpha_i]S'_2) = \eta_1^{-1}(R'_2) + [\alpha_i]\eta_1^{-1}(S'_2) = \tilde{R}'_2 + [\alpha_i]\tilde{S}'_2.$$

Therefore, $j'_{3,i} = j(E_1/\langle Ker(\tilde{\psi}_i \cdot \eta_1^{-1}) \rangle) = j(E_1/\langle R'_2 + [\alpha_i]S'_2 \rangle) = j_{3,i}$.

* If $b_i = 1$, that is, $z_i = (j_{2,i}, \psi_i'' : E_{2,i} \to E'_{3,i})$, then any verifier computes $j'_{3,i}$ as follows

$$j'_{3,i} = j(E_{2,i}/\langle Ker(\psi_i'') \rangle) = j_{3,i}.$$

* Since the verifier computes $(j'_{2,i}, j'_{3,i})$ such that $(j'_{2,i}, j'_{3,i}) = (j_{2,i}, j_{3,i})$ for all $i$, it is clear to see that

$$H(m, j'_{2,1}, \dots, j'_{2,t}, j'_{3,1}, \dots, j'_{3,t}) = H(m, j_{2,1}, \dots, j_{2,t}, j_{3,1}, \dots, j_{3,t}) = h.$$

Therefore, $\sigma_m = (h, z_1, \dots, z_t)$ is a valid signature on $m \in \{0, 1\}^*$ under the public key $pk' = (p, j_0, j_1, \tilde{R}_2, \tilde{S}_2, \tilde{R}'_2, \tilde{S}'_2, H)$. $\square$

Theorem 3.2 implies that the signer $U$ whose public key is $pk$ can repudiate his/her signing of $\sigma_m$ on $m$ whenever he/she wants by submitting $pk'$ as another public key that validates the signature $\sigma_m$ on $m$. Moreover, we note that the public key $pk'$ can be computed independently to any valid pair (message, signature) under $pk$, the owner $U$ of $pk$ can register $pk'$ as another legal user in the system a priori to prepare his/her future malicious actions. This concludes that GPS signature scheme does not provide the non-repudiation property.
**Remark 3.3.** Unruh [5] has given a transform that converts a secure interactive identification scheme into a signature scheme that is secure against a quantum adversary. In [12] the authors presented a post-quantum version of GPS signature using the Unruh transform and prove that it is existentially unforgeable in the quantum random oracle model if CSSI and DSSP are computationally hard for a quantum computer. It is easy to see that our key substitution attack on the (classic) GPS signature scheme works exactly the same for the post-quantum version of GPS signature scheme, too. Therefore, we see that the post-quantum version of GPS signature scheme does not provide the non-repudiation property, too.

### 3.2.2 An Example

In this section, we present a simple example of our key substitution attack on GPS signature for a clear view of isogenies and our attack. We compute our example using Sage with a small prime $p$ for simplicity. We also use the hash function MD5 in our example, but our attack succeeds independently the underlying hash function.

**( A Valid Key Generation )**

* $p = 2^4 \cdot 3^3 \cdot 2 - 1 = 863$;

* $E_0 : y^2 = x^3 + x$, an elliptic curve over a finite field $\mathbb{F}_{p^2}$;

* $a$ is generator of finite field $\mathbb{F}_{p^2}$;

* Choose points $P_1, R_2, S_2 \in E_0$ as follows:

$$P_1 = (197a + 648 : 758a + 405 : 1),$$

$$R_2 = (422a + 27 : 548a + 682 : 1), S_2 = (164a + 7 : 478a + 586 : 1)$$

* Compute an isogeny $\phi : E_0 \to E_1$ of degree 16 with the kernel $\langle P_1 \rangle$ where $E_1 : y^2 = x^3 + (155a + 756)x + (18a + 470)$ and the isogeny $\phi$ is defined as follows:
$$ \phi = \left( \frac{q_1(x)}{q_2(x)}, \frac{r_1(x, y)}{r_2(x)} \right) $$

$$ q_1(x) = x^{16} + (-36a - 343)x^{15} + (169a + 373)x^{14} + (312a + 388)x^{13} \\ + (284a + 400)x^{12} + (-398a + 78)x^{11} + (330a - 125)x^{10} - (41a - 139)x^9 \\ + (-295a - 193)x^8 + (249a - 353)x^7 + (-321a - 224)x^6 + (-199a + 165)x^5 \\ + (-182a + 265)x^4 + (352a + 127)x^3 + (-31a + 257)x^2 + (-239a + 77)x \\ + (174a + 150) $$

$$ q_2(x) = x^{15} + (-36a - 343)x^{14} + (200a - 339)x^{13} + (143a + 351)x^{12} \\ + (-65a - 311)x^{11} + (195a - 81)x^{10} + (23a + 395)x^9 + (-25a + 252)x^8 \\ + (340a - 422)x^7 + (329a - 325)x^6 + (-24a + 201)x^5 + 307a - 158)x^4 \\ + (242a - 368)x^3 + (-118a - 163)x^2 + (147a - 20)x + (48a + 133) $$

$$ r_1(x, y) = x^{23}y + (-286a + 33)x^{22}y + (215a + 131)x^{21}y + (203a - 75)x^{20}y \\ + (202a - 238)x^{19}y + (203a + 273)x^{18}y + (-348a - 351)x^{17}y \\ + (-31a - 269)x^{16}y + (412a + 373)x^{15}y + (117a + 414)x^{14}y \\ + (204a + 157)x^{13}y + (-203a - 363)x^{12}y + (290a - 250)x^{11}y \\ + (-59a - 49)x^{10}y + (-189a + 349)x^9y + (-391a - 360)x^8y \\ + (385a - 231)x^7y + (328a - 189)x^6y + (-142a - 283)x^5y \\ + (76a + 398)x^4y + (-303a + 129)x^3y + (352a + 62)x^2y \\ + (-16a - 397)xy + (366a + 237)y $$

$$ r_2(x) = x^{23} + (-286a + 33)x^{22} + (184a - 20)x^{21} + (-60a - 208)x^{20} \\ + (-235a + 431)x^{19} + (428a - 178)x^{18} + (-a + 378)x^{17} + (327a + 338)x^{16} \\ + (-27a - 356)x^{15} + (77a + 351)x^{14} + (-385a - 137)x^{13} + (425a - 63)x^{12} \\ + (226a + 372)x^{11} + (95a + 156)x^{10} + (118a - 425)x^9 + (-128a + 248)x^8 \\ + (344a + 299)x^7 + (310a - 417)x^6 + (184a + 337)x^5 + (371a - 154)x^4 \\ + (-105a + 307)x^3 + (11a + 243)x^2 + (79a + 327)x + (409a - 149) $$

* Compute $j$-invariants $j_0 = j(E_0) = 2$, $j_1 = j(E_1) = 465a + 831$.

* Compute $R'_2, S'_2 \in E_1$ as follows:

$$ R'_2 = \phi(R_2) = (347a + 480 : 357a + 737 : 1), $$

$$ S'_2 = \phi(S_2) = (712a + 662 : 268a + 204 : 1) $$

* Hash function $H = \text{MD5}: \{0,1\}^* \rightarrow \{0,1\}^{128}$

* Output

$$ pk = (p, j_0, j_1, R_2, S_2, R'_2, S'_2, H), sk = P_1. $$

( A Key Generation for Key Substitution Attack )

* For the given $E_0$ from the valid key generation, compute an isomorphism $\zeta_0: E_0 \rightarrow E'_0$ defined by $\zeta_0(x, y) = (557x, (842a + 442)y)$ for the elliptic curve $E'_0: y^2 = x^3 + 2x$. Compute $\eta_0 = \zeta_0^{-1}: E'_0 \rightarrow E_0$, then $\eta_0^{-1} = \zeta_0$. Note that $\eta_0(x, y) = (251x, (677a + 93)y)$ and $j(E'_0) = j(E_0) = j_0$.
* For the given $E_1$ from the valid key generation, compute an isomorphism $\zeta_1: E_1 \to E_1'$ defined by $\zeta_1(x, y) = (406x, (385a+239)y)$ for $E_1: y^2 = x^3 + (465a+542)x + (349a+291)$. Compute $\eta_1 = \zeta_1^{-1}: E_1' \to E_1$, then $\eta_1^{-1} = \zeta_1$. Note that $\eta_1(x, y) = (423x, (779a+42)y)$ and $j(E_1') = j(E_1) = j_1$.

* Compute

$$ - \widetilde{P}_1 = \eta_0^{-1}(P_1) = (256a + 404 : 23a + 425 : 1) $$

$$ - \widetilde{S}_2 = \eta_0^{-1}(S_2) = (603a + 31 : 164a + 224 : 1) $$

$$ - \widetilde{R}_2 = \eta_0^{-1}(R_2) = (636a + 736 : 825a + 34 : 1) $$

* Compute the isogeny $\tilde{\phi} = \eta_1^{-1} \cdot \phi \cdot \eta_0: E_0' \to E_1'$. Note that the kernel of $\tilde{\phi}$ is $\langle \widetilde{P}_1 \rangle$. Set

$$ - \widetilde{S}_2' = \tilde{\phi}(\widetilde{S}_2) = (830a + 379 : 680a + 602 : 1) $$

$$ - \widetilde{R}_2' = \tilde{\phi}(\widetilde{R}_2) = (213a + 705 : 795a + 677 : 1) $$

* Output

$$ pk' = (p, j_0, j_1, \widetilde{R}_2, \widetilde{S}_2, \widetilde{R}_2', \widetilde{S}_2', H), sk = \widetilde{P}_1 $$

### (A Signature Generation using sk on a message m = message)

A signature $\sigma_m$ on the message $m = \text{message}$ is computed as follows: First we compute the first part $h$ of the signature as follows: For a randomly chosen $[\alpha_i]_{1 \le i \le t} = [15, 5, 6, 18, 2, \dots]$, compute the following isogenies and $j$-invariants for each $i$:

* $\psi_i: E_0 \to E_{2,i}$ with the kernel $\langle R_2 + [\alpha_i]S_2 \rangle$ and $j_{2,i} = j(E_0/\langle R_2 + [\alpha_i]S_2 \rangle)$:

$$ j_2 = [j_{2,1}, j_{2,2}, j_{2,3}, j_{2,4}, \dots] = [515a+716, 473a+144, 473a+144, 451a+551, \dots] $$

* $\psi'_i: E_1 \to E_{3,i}$ with the kernel $\langle R'_2 + [\alpha_i]S'_2 \rangle$ and $j_{3,i} = j(E_1/\langle R'_2 + [\alpha_i]S'_2 \rangle)$:

$$ j_3 = [j_{3,1}, j_{3,2}, j_{3,3}, j_{3,4}, \dots] = [232a+541, 657a+665, 657a+665, 590a+114, \dots] $$

For the two sequences $j_2$ and $j_3$ of $j$-invariants, compute the hash value

$$ h = b_1b_2b_3\cdots = H(\text{message}, j_2, j_3) = 10111011\dots $$

Now we compute the second part $(z_i)$'s of the signature as follows:

* From the fact $b_1 = 1$, set $z_1 = (j_{2,1} = 515a + 716, \psi_1'')$, where

$$ - \psi_1'': E_{2,1} \to E_{3,1}' \text{ is an isogeny with the kernel generated by } \psi_1(P_1) \text{ for the elliptic curves } E_{2,1}: y^2 = x^3 + (285a + 129)x + (507a + 262) \text{ and } E_{3,1}': y^2 = x^3 + (713a + 733)x + (70a + 235). $$
* $b_2 = 0$, and set $z_2 = \alpha_2 = 5$.

Finally, we have a sequence $z = [z_1, z_2, z_3, \dots] = [(515a + 716, \psi_1''), 5, (473a + 144, \psi_3''), \dots]$, and the computed signature is $\sigma = ((h, z), \text{message})$. This signature $\sigma_m = ((h, z), \text{message})$ can be verified as a valid signature on message under the public key $pk$.

### (Key Substitution Attack on $\sigma_m$ using the public key $pk'$)

Note that $pk' = (p, j_0, j_1, \tilde{R}_2, \tilde{S}_2, \tilde{R}_2', \tilde{S}_2', H)$. Suppose that a valid signature $\sigma = ((h, z), \text{message})$ under $pk$ is given as follows:

* $h = H(\text{message}, j_2, j_3) = 10111011\dots$

* $z = [z_1, z_2, z_3, \dots] = [(515a+716, \psi_1''), 5, (473a+144, \psi_3''), \dots] = [(j_{2,1}, \psi_1' : E_{2,1} \to E'_{3,1}), \alpha_2, (j_{2,3}, \psi_3' : E_{2,3} \to E'_{3,3}), \dots]$

For the verification, anyone compute the values of $j$-invariants $(j'_2 = [j'_{2,1}, j'_{2,2}, \dots], j'_3 = [j'_{3,1}, j'_{3,2}, \dots])$ for the $pk'$ as follows:

From $b_1 = 1$ and $z_1 = (j_{2,1}, \psi_1'') = (515a + 716, \psi_1'' : E_{2,1} \to E'_{3,1})$:

* set $j'_{2,1} = j_{2,1}$ and

* compute the $j$-invariant $j'_{3,1} = j(E'_{3,1}) = 232a + 541$, which turns out $j'_{3,1} = j_{3,1}$.

From $b_2 = 0$, that is, $z_2 = \alpha_2 = 5$:

* The verifier computes an isogeny $\tilde{\psi}_2 : E'_0 \to E'_{2,2}$ with the kernel $\tilde{R}_2 + 5\tilde{S}_2$ and the $j$-invariant $j'_{2,2} = j(E'_0/(\tilde{R}_2 + 5\tilde{S}_2)) = 473a + 144$, which turns out $j'_{2,2} = j_{2,2}$.

* The verifier computes an isogeny $\tilde{\psi}'_2 : E'_1 \to E'_{3,2}$ with the kernel $\tilde{R}'_2 + 5\tilde{S}'_2$ and the $j$-invariant $j'_{3,2} = j(E'_1/(\tilde{R}'_2 + 5\tilde{S}'_2)) = 657a + 665$, which turns out $j'_{3,2} = j_{3,2}$.

Similarly, the values of $j$-invariants $j'_2, j'_3$ for the $pk'$ such that $j_2 = j'_2, j_3 = j'_3$ are computed. Clearly, $h = H(\text{message}, j_2, j_3) = H(\text{message}, j'_2, j'_3)$, therefore, the signature $\sigma = ((h, z), \text{message})$ is valid under $pk'$.

## 3.3 How to prevent Our Attack

Our attack on GPS signature uses isomorphisms of the underlying elliptic curves and isomorphic elliptic curves have the same $j$-invariants. Therefore, if one restricts distinct $j$-invariants $(j_0, j_1)$ for each public key, our key substitution attack can be prevented. However, our result is the first key substitution attack on isogeny based signature schemes under the consideration of the non-repudiation
of the signature and one could expect a more advanced key substitution attack
on isogeny based signature.

In general, there are two ways to prevent key substitution attacks on digital signature schemes. One is that the certificate authority (CA) for public keys requires that users to prove possession of user's private key before issuing certificates. This prevents the adversary mounts key substitution attacks without knowing the corresponding private key. However, this counter-measure is not suitable to prevent key substitution attack under consideration of non-repudiation, since the original signer is considered as a potential attacker and the original signer knows the related private keys. Another way to prevent key substitution attack is proposed by Menezes and Smart. They formalize the key substitution security as a security of signature schemes in multi-user setting and formatting messages specific to each public key, such as including the signer's public key to the message in some unambiguous way prior to signing (e.g., $pk||message$) guarantees the key substitution security if the original signature scheme is proven unforgeable [1].

# 4 Conclusion

GPS signature [12] is an efficient isogeny based signature scheme which is proven
EUF-CMA secure in the random oracle model under the assumption that the
problems CSSI (Computational Supersingular Isogeny) and DSSP(Decisional
Supersingular Product) are infeasible. In this paper, we show that the current
version of GPS signature fails to provide non-repudiation by presenting a pub-
lic key substitution attack on GPS signature. In [12], they also presented a
post-quantum version of GPS signature which is proven EUF-CMA secure in
the quantum random oracle model based on the hardness of CSSI and DSSP.
It is easy to see that our key substitution attack on the (classic) GPS signa-
ture scheme works exactly the same against the post-quantum version of GPS
signature scheme, too. We recommend to use distinct $j$-invariants ($j_0, j_1$) for
each public key of GPS signature scheme to prevent our key substitution attack.
Moreover, we suggest to format messages as specific to each public key, such as
$pk||message$, prior to signing according to the analysis of Menezes and Smart
[1].

# References

[1] Alfred M, Nigel S (2004) Security of signature schemes in a multiuser setting. Designs Codes and Cryptography, vol 23, pp 261-274.

[2] Amos F, Adi S (1986) How to prove yourself: Practical solutions to identification and signature problems. CRYPTO 1986, LNCS, vol 263, pp 186-194.
[3] David J, Luca De F (2011) Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. PQCrypto 2011, LNCS, vol 7071, pp 19-34.

[4] David J, Vladimir S (2014) Isogeny-based quantum-resistant undeniable signatures. PQCrypto 2014, LNCS, vol 8772, pp 160-179.

[5] Dominique U (2015) Non-interactive zero-knowledge proofs in the quantum random oracle model. EUROCRYPT 2015, LNCS, vol 9057, pp 755-784.

[6] Jens-Matthias B, Stefan R, Rainer S (2006) Key substitution attacks revisited: Taking into account malicious signers. International Journal of Information Security, vol 5, pp 30-36.

[7] John T (1966) Endomorphisms of Abelian Varieties Over Finite Fields. Inventiones math, vol 2, pp 134-144.

[8] Joseph H S (2009) The Arithmetic Elliptic Curves, Graduate Texts in Mathematics, Springer-Verlag, New York, ISBN:9780387962030.

[9] Lawrence C W (2008) Elliptic Curves: Number Theory and Cryptography, 2 ed., CRC Press, United Kingdom, ISBN:978-1420071467.

[10] Luca De F, David J, and Jérôme P (2014) Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. Journal of Mathematical Cryptology, vol 8, pp 209-247.

[11] Robin H (1977) Algebraic Geometry, Number 52, Graduate Texts in Mathematics, Springer-Verlag, New York.

[12] Steven G, Christophe P, Javier S (2017) Signature scheme based on supersingular isogeny problems. ASIACRYPT 2017, LNCS, vol 10624, pp 3-33.

[13] Velu J (1971) Isogenies Entre Courbes Elliptiques. Communications de Academie royale des Sciences de Paris, pp 305-347.

[14] William C W (1969) Abelian varieties over finite fields. Annales scientifiques de l'É.N.S., pp 521-560.

[15] Xi S, Haibo T, Yumin Wang (2014) Toward quantum-resistant strong designated verifier signature from isogenies. International Journal of Grid and Utility Computing, vol 5, pp 80-86.