1]Department of Computer Science, University of Calgary, Calgary, Canada
2]Department of Mathematics, National Institute of Technology Jamshedpur,
Jamshedpur, India 3]Department of Mathematics, Indian Institute of Technology
Madras, Chennai, India

#  A new approach to delegate signing rights to proxy signers using isogeny-
based cryptography

Kunal Dey<EMAIL_ADDRESS>Somnath Kumar<EMAIL_ADDRESS>Vikas
Srivastava<EMAIL_ADDRESS>Sumit Kumar Debnath
<EMAIL_ADDRESS>[  [  [

###### Abstract

E-governance is a two-way protocol through which one can use government
services, share data and request information. It refers to the use of
communication and information technologies to provide government services to
public in an efficient and fast manner. In addition, any document submitted to
the e-Government system must be authenticated by a government officer using a
digital signature scheme. In the context of digital signatures, the proxy
signature is an important cryptographic primitive that allows the original
signer to delegate signing authority to another signer (proxy signer). The
proxy signature has a number of important applications in the e-government
system. There are now a large amount of proxy signature schemes. The security
of most of them relies on the following hard problems: the discrete logarithm
problem and the factorization of integers problem. However, a large-scale
quantum computer can solve them in polynomial time due to Shor’s algorithm. As
a consequence, there is a need for a quantum computer-resistant proxy
signature to secure e-governance system from quantum adversaries. In this
work, we propose the first post-quantum isogeny based proxy signature scheme
CSI-PS (commutative supersingular isogeny proxy signature). Our construction
is proven to be uf-cma secure under the hardness of the group action inverse
problem (GAIP) based on isogeny.

###### keywords:

E-governance, isogeny-based public-key cryptography; post-quantum
cryptography; proxy signature; elliptic curve cryptography.

##  1 Introduction

Electronic governance often abbreviated as e-governance is an application of
information and communication technologies to facilitate the direct
interaction between government and other entities like citizens, businesses
and employees. In other words, e-governance aims to use technology to achieve
the objective of governance. The basic goals of e-governance are to increase
individual’s access to information, connect with business and industry, and
make government more accountable, transparent, and effective. Essentially, it
performs government functions through information, communication, and
technology. In e-governance, there are four types of government interactions:
government-to-citizen (G2C), government-to-government (G2G), government-to-
business (G2B), and government-to-employee (G2E). In e-governance initiatives
worldwide, various security measures are implemented to protect the data of
residents. Each department’s representatives are provided with digital
signature certificates, allowing them to digitally sign documents for
authentication purposes. However, a dilemma arises as to how the government
representative can sign a paper when he is on leave. That is where proxy
signatures come in. A Proxy signature is a type of digital signature, where a
participant (original signer) makes some representative (proxy signer) able to
sign a message on behalf of the original signer. Given the context of the
situation, the proxy signature can be employed by the government official to
solve the problem. By making use of such a scheme, he can transfer the signing
authority to a proxy signer who can sign on behalf of the government official
for a limited time.We demonstrate the above in Figure 1.

Figure 1: Proxy signature in e-governance

The proxy signature idea was developed by Mambo et al. [1] in 1996. A proxy
signature should attain the below-mentioned security features [2]:

  1. 1.

Unforgeability: No one but the proxy signer, not even the original signer,
should be able to generate a correct proxy signature.

  2. 2.

Identifiability: The proxy signer should be identified after observing the
proxy signature by anyone having the authority to access the signature.

  3. 3.

Undeniability: After a proxy signer generates a valid proxy signature for the
original signer, they cannot later deny having created it.

  4. 4.

Verifiability: The verifier can be convinced of the original singer’s
agreement from the proxy signature.

  5. 5.

Distinguishability: In polynomial time, the original signer’s valid signature
can be distinguished from a valid proxy signature.

  6. 6.

Secrecy: Any information about the secret key of the original signer cannot be
determined at any stage during proxy signature.

  7. 7.

Prevention of misuse: Proxy signer will not be able to sign a message with
some proxy key that is not defined in its warrant. Otherwise, it will be
identified from its warrant.

  8. 8.

Revocability: The proxy signer’s signing authority will be disabled
automatically on completion of the validity of the period. Then any proxy
signature produced by the proxy signer will not be valid.

In addition to applications in e-governance, proxy signature find applications
in other real-life situations like global distribution networks [3, 4], mobile
agent applications [5, 6, 7], etc. The majority of the currently used proxy
signature schemes [8, 9, 10, 11, 12, 13] are based on hard problems like the
_discrete logarithm problem_ and the _integer factorization problem_. However,
they are not protected against attacks by quantum computers since Shor’s
algorithm [14] can efficiently solve them. Consequently, post-quantum
cryptography (PQC) is considered a promising alternative believed to offer
security against quantum adversaries. There are several candidates of PQC,
such as Lattice-based cryptography [15], Multivariate cryptography [16],
Isogeny-based cryptography [17], Hash-based cryptography [18], Code-based
cryptography [19]. Isogeny-based cryptography (IBC) is a relatively new area
within post-quantum cryptography (PQC) that offers small public key sizes
compared to other PQC candidates. The concept of IBC was first introduced by
Couveignes [20] in 1997. That work was based on ordinary elliptic curves for
which the endomorphism ring is an order of some imaginary quadratic field
(IQF). In 2006, Rostovtsev and Stolbunov [21] rediscovered the idea and
proposed a Diffie-Hellman [22] like key exchange (KE) protocol. In 2018,
Castryck et al. [23] developed an efficient key agreement protocol ${\sf
Commutative~{}supersingular~{}Isogeny~{}Diffie-Hellman~{}(CSIDH)}$ which uses
supersingular elliptic curves defined over a prime finite field. However,
instead of the full endomorphism ring, they worked with the
$\mathbb{F}_{p}$-rational endomorphism ring, which is an order of IQF and
hence commutative. Throughout the literature, the emphasis is on isogeny-based
protocols relying on class group action [17]. Research shows that there are
many advantages [24, 25] in isogeny-based cryptography, such as the size of
the signatures and public keys, which are almost the same as existing
practical schemes. Another major advantage is its sufficiently low
communication cost. In the literature, there are some efficient isogeny based
digital signatures like ‘SeaSign’ [26], ‘CSI-Fish’[27], ‘SQISign’ [28] which
are based on the ‘Fiat-Shamir’ technique. Additionally, there are isogeny-
based identity based signature scheme (IBS) [29], Group signature [30, 31] and
Ring signature [30] and Signcryption [32, 33]. However, there is a lack of
proxy signatures based on IBC. Consequently, designing a secure and efficient
isogeny-based proxy signature is an interesting open challenge.

###  1.1 Our contribution

The major contributions of the paper are outlined below.

  * •

To the extent of our knowledge, there has been no construction of proxy
signature in the context of isogeny-based cryptography. In this paper, we
addressed this open challenge by designing the first isogeny-based post-
quantum secure proxy signature CSI-PS (Commutative Supersingular Isogeny Proxy
Signature).

  * •

The security of our proposed design CSI-PS is based on hardness assumption of
the group action inverse problem ($\sf{GAIP}$). In particular, we show that
CSI-PS achieves uf-cma security under the random oracle model. Moreover, CSI-
PS also meets the other security requirements, such as identifiability,
undeniability, and verifiability.

  * •

We observe that the public keys of original signer and proxy signer are of
sizes $L_{0}\left\lceil{log(p)}\right\rceil$ bits, original signer’s and proxy
signer’s secret key sizes are $L_{0}\left\lceil{nlog(2I_{0}+1)}\right\rceil$
bits each, sizes of proxy share and proxy signature become
$M_{1}M_{2}\left\lceil{log(L_{1}+1)}\right\rceil$ \+
$M_{1}M_{2}\left\lceil{nlog(2I_{1}+1)}\right\rceil$ bits each.

  * •

To determine the most optimal size for the proxy signature, we perform
calculations for different parameter choices. We conclude that our proxy
signature achieves a size of 3052B with parameters set to
$(16,8,8,2,65535,255)$. A concrete instantiation of CSI-PS for the parameters
set $(16,8,8,2,65535,255)$ is provided in Section 6. We demonstrate how an
original signer can use our proposed CSI-PS design to create a proxy signer
with signing authority, and how the proxy signer can then generate a valid
proxy signature on a document.

  * •

The only cost intensive operation in our design is class group computation. We
computed the cost of class group computation in terms of field
multiplications. In addition, we calculated the exact number of field
multiplications required for public key generation, proxy share generation,
and proxy signature. Moreover, we also estimated the time complexity of CSI-
PS. The results are summarized in Table 3.

###  1.2 Organization of the paper

The structure of the paper is outlined as follows: Section 2 covers the
preliminaries to aid readers in understanding our scheme. Section 3 introduces
our scheme, CSI-PS. Security analysis is discussed in Section 4, while
communication complexities are examined in Section 5. A concrete instantiation
illustrating the CSI-PS flow is provided in Section 6. Finally, we conclude
our discussion in Section 7.

##  2 Preliminaries

Notations. Given a finite set $X$, $|X|$ stands for its cardinality.
$\mathbb{F}_{q}$ denotes the finite field of order $q$, where $q$ is a power
of some prime $p$. Closure of a field $\mathbb{F}_{q}$ is denoted by
$\overline{\mathbb{F}}_{q}$. $[a,b]$ denotes the set of integers $z$ such that
$a\leq z\leq b$.

######  Definition 1.

Negligible function:
A function $\epsilon:\mathbb{N}\longrightarrow\mathbb{R}$ is called a
negligible function, if for every polynomial poly(x) in $x$, there exists a
positive integer $N$ such that $\epsilon(x)<\frac{1}{poly(x)}$ $\forall$ $x>N$
.

###  2.1 Elliptic curves and isogenies [17]

An elliptic curve over a field $\mathbb{F}_{q}$ is a smooth projective curve
of genus $1$ having at least one $\mathbb{F}_{q}$-rational point. For
char$(\mathbb{F}_{q})\not=2,3$, the short Weierstrass affine equation for an
elliptic curve over $\mathbb{F}_{q}$ is $y^{2}=x^{3}+cx+d$, where the point at
infinity is $(0:1:0)$, and $c,d\in\mathbb{F}_{q}$ with $4c^{3}+27d^{2}\not=0$.
Throughout the paper, elliptic curves are assumed to be defined over
$\mathbb{F}_{p}$. According to Hasse’s theorem [34], the cardinality
$|E(\mathbb{F}_{p})|$ of $E(\mathbb{F}_{p})$ satisfies
$|E(\mathbb{F}_{p})|=p+1-t$ with $|t|\leq 2\sqrt{p}$.

An isogeny $\chi:E_{1}\rightarrow E_{2}$ is an onto morphism inducing a group
homomorphism from $E_{1}(\overline{\mathbb{F}}_{q})$ to
$E_{2}(\overline{\mathbb{F}_{q}})$. Here $E_{1}$ and $E_{2}$ are called
isogenous. Indeed, $E_{1}$ and $E_{2}$ having same number of points assure
that there exist an isogeny between them. An isogeny sends the identity
element $\Theta$ of $E_{1}$ to identity element $\Theta^{\prime}$ of $E_{2}$.
An endomorphism is a morphism from $E$ to itself that fixes the distinguished
point $\Theta$. The set of all endomorphisms on $E$ is denoted by $End(E)$.
One should say that the set of all endomorphisms is actually a ring. The
Frobenius endomorphism is an endomorphism on $E$ over $\mathbb{F}_{q}$ and it
is defined as $\pi_{E}:(x:y:z)\longmapsto(x^{q}:y^{q}:z^{q})$. Another example
of endomorphism is the multiplication-by-$n$ map, defined as
$[n]:P\longmapsto[n]P$. Its kernel is called the $n$-th torsion subgroup
$E[n]$.

The standard form of isogeny $\chi$ over $\mathbb{F}_{q}$ is given by
$\chi(x,y)=\left(\frac{\alpha(x)}{\beta(x)},\frac{\gamma(x)}{\delta(x)}y\right)$,
where $\alpha,\beta,\gamma,\delta\in\mathbb{F}_{q}[x]$, $\alpha$ is co-prime
to $\beta$ and $\gamma$ is co-prime to $\delta$ in $\mathbb{F}_{q}[x]$. The
degree of $\chi$ is denoted by $deg(\chi)$ and defined by
$deg(\chi)=max\\{deg(\alpha),deg(\beta)\\}$. If
$\left(\frac{\alpha(x)}{\beta(x)}\right)^{\prime}\neq 0$ then $\chi$ is called
separable; otherwise, it is called inseparable. Note that the Frobenius
endomorphism over $\mathbb{F}_{p}$ is an inseparable isogeny. The endomorphism
$[m]$ for an elliptic curve $E/\mathbb{F}_{p}$ is separable if and only if $m$
and $p$ are co-prime. The $j$-invariant of $y^{2}=x^{3}+cx+d$ is defined by
$j(E)=1728\frac{4c^{3}}{4c^{3}+27d^{2}}$. Two elliptic curves over
$\overline{\mathbb{F}_{q}}$ with same $j$-invariant are called isomorphic. The
torsion subgroup $E[p]$ is isomorphic to either $\mathbb{Z}/p\mathbb{Z}$ or 0.
E is called ordinary in the first case, while $E$ is called a supersingular
elliptic curve in the second case. If $E$ is supersingular over a finite field
of characteristic $p$, then $j(E)$ lies in $\mathbb{F}_{p^{2}}$.

###  2.2 Endomorphism algebra and ideal class group [17]

A quaternion algebra over $\mathbb{F}_{q}$ is a $\mathbb{F}_{q}$-algebra with
$\mathbb{F}_{q}$ basis $\\{1,\alpha,\beta,\alpha\beta\\}$, where
$\alpha\beta=-\beta\alpha$ and
$\alpha^{2},\beta^{2}\in\mathbb{F}_{q}-\\{0\\}$. Let $A$, $B$ be two rings and
$f:A\rightarrow B$ be a ring homomorphism. An $A$-module structure on $B$ is
defined by the scalar multiplication $a.b=f(a)b$. If $B$ has a ring structure
along with an $A$-module structure via $f$ then $B$ is called an algebra. The
endomorphism algebra of $E$ is denoted by
$End^{0}(E):=End(E)\otimes_{\mathbb{Z}}\mathbb{Q}$, where $End^{0}(E)$ is a
$\mathbb{Q}$-algebra. $End(E)$ is a free $\mathbb{Z}$-module of rank $r$. Note
that $r=1$ implies that $End^{0}(E)$ isomorphic to $\mathbb{Q}$, $r=2$ implies
that $End^{0}(E)$ is isomorphic to an imaginary quadratic field and $r=4$
implies that $End^{0}(E)$ is isomorphic to a quaternion algebra. Note that if
$E$ is defined over a finite field, the case $r=1$ can not happen. An order
$\vartheta$ of a $\mathbb{Q}$-algebra is a $\mathbb{Z}$-lattices of the
$\mathbb{Q}$-algebra, which is also a subring. For any number field $K$, the
ring of integers $\vartheta_{K}$ is the unique maximal order. The orders in
imaginary quadratic number fields are defined by
$\vartheta=\mathbb{Z}+f\vartheta_{K}$, where $f$ is an integer which is called
the conductor of $\vartheta$.

The Frobenius endomorphism $\pi$ for an elliptic curve $E/\mathbb{F}_{q}$
satisfies the equation $\pi^{2}-t\pi+q=0$ with $|t|\leq 2\sqrt{q}$. Here $t$
is called trace of $\pi$ and $\Delta_{\pi}=t^{2}-4q$ is discriminant of $\pi$.
Therefore, the discriminant $\Delta_{\pi}=t^{2}-4q$ of $\pi$ is negative and
we have $\pi\in\mathbb{Q}(\sqrt{\Delta_{\pi}})$ which is an imaginary
quadratic field.

######  Definition 2.

Let $G$ be a finite commutative group that acts freely and transitively on
some set H. A hard homogeneous space (HHS) [20] consists of the sets $G$ and
$H$, where the following computational problems are required to be easy:

  1. 1.

Computation of the group action in $G$.

  2. 2.

Random selection of an element from $G$ with uniform distribution.

  3. 3.

Deciding validity and equality of a representation of H’s elements.

  4. 4.

Computation of the group action of $g\in G$ on some $h\in H$.

and the following problems are assumed to be hard:

  1. 1.

Given $h,k\in H$, finding $g\in G$ such that $k=gh$.

  2. 2.

Given $h,k,w\in H$ with $k=gh$, finding $k^{\prime}=gw$

Let $\vartheta$ be the order of a number field $K$. With the help of an
$\vartheta$-ideal $L$, we can define a fractional $\vartheta$\- ideal as
$L^{\prime}=\omega L=\\{\omega\alpha:\alpha\in L\\}$ for some $\omega\in
K^{*}$. A fractioal $\vartheta$-ideal $L^{\prime}$ is called invertible if
there exists a fractional $\vartheta$-ideal $L^{\prime\prime}$ such that
$L^{\prime}L^{\prime\prime}=\vartheta$. Collection of invertible fractional
$\vartheta$-ideals forms a group with respect to multiplication of fractional
$\vartheta$-ideals which is defined as
$L^{\prime}N^{\prime}=\omega\omega^{\prime}LN$ for two fractional
$\vartheta$-ideals $L^{\prime}=\omega L$ and $N^{\prime}=\omega^{\prime}N$.
Let $I$ represents the group of invertible fractional $\vartheta$-ideals and
$P$ denotes the subgroup of $I$ consisting of principal fractional
$\vartheta$-ideals. The ideal class group is defined by the quotient group
$cl(\vartheta)=\frac{I}{P}$. The $\mathbb{F}_{p}$-rational endomorphism ring
$End_{p}(E)$ for a supersingular elliptic curve $E$ over $\mathbb{F}_{p}$ is
an order in an imaginary quadratic field. Suppose $E_{p}$ is the set of
isomorphism classes of elliptic curves over $\mathbb{F}_{p}$ whose
$\mathbb{F}_{p}$-rational endomorphism ring is isomorphic to $\vartheta$.
Then, we have a group action of $Cl(\vartheta)$ on $E_{p}$ which is free and
transitive. As a consequence, $E_{p}$ is $Cl(\vartheta)$-torsor or principal
homogeneous space (PHS).

######  Theorem 1.

Let $E$ be a supersingular elliptic curve defined over $\mathbb{F}_{p}$ with
the Frobenius endomorphism $\pi$, where $p\equiv 3\ (\textrm{mod}\ 4)$ and
$p>3$. The necessary and sufficient condition for $End_{p}(E)=\mathbb{Z}[\pi]$
is that there exists a unique $e\in\mathbb{F}_{p}$ so that $E$ is
$\mathbb{F}_{p}$ isomorphic to a Montgomery curve: $y^{2}=x^{3}+ex^{2}+x$,
where $\mathbb{Z}[\pi]$ is a subring of $\mathbb{Q}(\sqrt{-p})$.

Algorithm 1 The class-group action on a Montgomery curve

1:A Montgomery curve $E:y^{2}=x^{3}+ex^{2}+x$, $e\in\mathbb{F}_{p}$,
$p=4l_{1}\cdots l_{n}-1$ and a set of integers $(a_{1},\cdots,a_{n})$.

2:while some $a_{i}\neq 0$ do

3: Sample $x\in\mathbb{F}_{p}$.

4: Set $w\longleftarrow 1$ if $x^{3}+ex^{2}+x$ is a square in
$\mathbb{F}_{p}$, else set $w\longleftarrow-1$.

5: Suppose $W=\\{i:a_{i}\neq 0,sign(a_{i})=w\\}$.

6: if $W=\emptyset$ then

7: Start from step 2.

8: end if

9: Set $f\longleftarrow\prod_{i\in W}l_{i}$.

10: Evaluate $Q\longleftarrow[(p+1)/f]P$, where $P$ is a point of order
$l_{i}$ in E.

11: for each $i\in W$ do

12: Calculate $R\longleftarrow[f/l_{i}]Q$.

13: if $R=\infty$ then

14: skip

15: end if

16: Compute the isogeny $\phi:E\longrightarrow E^{\prime}$ with
$E^{\prime}:y^{2}=x^{3}+Bx^{2}+x$ and $ker(\phi)=R$.

17: Set $Q\longleftarrow\phi(Q)$, $f\longleftarrow f/l_{i}$, $a_{i}=a_{i}-w$

18: end for

19:end while

20:$B$.

###  2.3 Commutative supersingular isogeny Diffie-Hellman (CSIDH) [23]

If $E$ is a supersingular curve over $\mathbb{F}_{p}$ then its ring of
$\mathbb{F}_{p}$-rational endomorphism is an imaginary quadratic order
$\vartheta\subseteq\mathbb{Q}(\sqrt{-p})$ which is denoted by $End_{p}(E)$. In
CSIDH [23], we fix $E_{0}:y^{2}=x^{3}+x$ over $\mathbb{F}_{p}$ for the prime
$p=4l_{1}\cdots l_{n}-1$, where $l_{1},\cdots,l_{n}$ are small distinct odd
primes. As $p\equiv(-1)(\bmod~{}4)$, we can say that $E_{0}$ is supersingular.
Hence $|E_{0}(\mathbb{F}_{p})|=p+1\equiv 0(\bmod~{}l_{i})$ and we can
decompose $l_{i}\vartheta=J_{i}\overline{J_{i}}$, where $J_{i}=(l_{i},\pi-1)$
and $\overline{J_{i}}=(l_{i},\pi+1)$. Now we have to assume that $J_{i}$’s are
evenly distributed in the class group and we expect that an ideal is of the
form $J_{1}^{a_{1}}\cdots J_{n}^{a_{n}}$ with $(a_{1},\cdots a_{n})$ randomly
chosen from $[-s,s]^{n}$ for some natural number $s$. Thereby, we may
represent the ideal $J_{1}^{a_{1}}\cdots J_{n}^{a_{n}}$ as
$(a_{1},\cdots,a_{n})$. It has been observed that it is sufficient to choose
$m$ such that $2s+1\geq\sqrt[n]{|cl(\vartheta)}$. As the trace of Frobenius
endomorphism is zero for supersingular elliptic curve over $\mathbb{F}_{p}$,
its characteristic equation is $\pi^{2}+p=0$ yielding $\pi=\sqrt{-p}$. Thus,
$End_{p}(E_{0})=\mathbb{Z}[\sqrt{-p}]=\mathbb{Z}[{\pi}]$. In other words,
$E_{0}$ is $\mathbb{F}_{p}$ rational isomorphic to a Montgomery curve
$E_{A}:y^{2}=x^{3}+ex^{2}+x$, which is represented by its coefficient $e$ by
theorem 1.
To generate the key, Alice randomly chooses a n-tuple secret key
$\textbf{a}=(a_{1},\cdots,a_{n})$ randomly form $[-s,s]^{n}$ and computes
$[\textbf{a}]=[J_{1}^{a_{1}}\cdots J_{n}^{a_{n}}]\in\mathbb{Z}[\pi]$. She then
computes the group action $[\textbf{a}]E_{0}$ using Algorithm 1, which is
isomorphic to some Montgomery curve $E_{A}$ with a coefficient $f$ (public
key) by Theorem 1. Here, Alice’s secret key - public key pair is
$([\textbf{a}],f)$. Similarly Bob chooses his key pairs as $([\textbf{b}],g)$.
Next, Alice evaluates $[\textbf{a}]E_{B}=[\textbf{a}]([\textbf{b}]E_{0})$ and
Bob computes $[\textbf{b}]E_{A}=[\textbf{b}]([\textbf{a}]E_{0})$. At the end
of the protocol, they will share the same key
$[\textbf{a}][\textbf{b}]E_{0}=[\textbf{b}][\textbf{a}]E_{0}$ due to the
commutative property of imaginary quadratic field.

###  2.4 Rejection sampling [29]

In order to prevent any leakage of information of the secret key, we can apply
rejection sampling. Let there be two parties P and Q. P selects a secret
vector $\textbf{a}=(a_{1},\cdots,a_{n})$ $\in$ $[-I,I]^{n}$, where
$I\in\mathbb{N}$ so that $\prod_{t=1}^{n}J_{t}^{a_{t}}$ covers almost all the
ideal classes in order to make the output distribution uniform. In addition, P
chooses another random vector $\textbf{a}^{\prime}$ $\in$ [-($\delta$ \+ 1)$I$
, ($\delta$ \+ 1)$I$]n where $\delta\in\mathbb{N}$. After that, Q randomly
chooses a bit $b$ and sends it to P. In the following, P evaluates
${\gamma}=\textbf{a}^{\prime}-\textbf{a}$ if ${b}=1$ and otherwise,
$\gamma=\textbf{a}^{\prime}$. As a consequence, we can filter $\gamma$ as
$|\gamma|\leq\delta I$ to prevent any leakage of the secret key. Here the
output vector $\gamma$ is uniformly distributed and as a result it is
independent of a.

###  2.5 Hardness assumption

######  Definition 3.

Group Action Inverse Problem ($\sf{GAIP}$) [26]:
Given two elliptic curves $E$ and $E^{\prime}$ over a same field with
$E^{\prime}=[\textbf{a}]E$ for $[\textbf{a}]\in cl(\mathbb{Z}[\pi_{E}])$, it
is hard to find $[\textbf{a}]$. Here $\pi_{E}$ stands for the Frobenius
endomorphism on $E$.

###  2.6 SeaSign [26]

The signature scheme SeaSign [26] consists of three algorithms ${\sf
Key~{}generation}$, ${\sf Signature}$ and ${\sf Verification}$ which are
discussed below.

$({PK},{SK})\leftarrow{\sf Key~{}generation}(1^{\lambda}):$ Consider a
supersingular elliptic curve $E_{0}:y^{2}=x^{3}+x$ over $\mathbb{F}_{p}$ where
$p$ is a prime. On input of a security parameter $\lambda$, the signer
randomly chooses a=$(a_{1},\cdots,a_{n})$ $\in$ $[-I_{0},I_{0}]^{n}$ and
evaluates $E_{1}=[\textbf{a}]E_{0}$. The public key-secret key pair of the
signer is $({PK,SK})=(E_{1},\textbf{a})$.

$(\sigma)\leftarrow{\sf Signature}(m,{SK},{PK}):$ On input of a message $m$,
the signer performs the following steps:

  1. 1.

chooses $\textbf{x}^{i}\in_{R}[-(I_{0}+I_{1}),(I_{0}+I_{1})]^{n}$ and
evaluates $X_{i}=[\textbf{x}^{i}]E_{0}$ for $i=1,2,\ldots,t$,

  2. 2.

calculates $H(X_{1},\cdots,X_{t},m)=b_{1}\parallel\cdots\parallel b_{t}$,
where $H:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{t}$ is a cryptographically secure
collision resistant hash function,

  3. 3.

sets $\textbf{z}^{k}=\textbf{x}^{k}$ if $b_{k}=0$ and
$\textbf{z}^{k}=\textbf{x}^{k}-\textbf{a}$ otherwise by ensuring the fact that
$\textbf{z}^{k}\in[-I_{1},I_{1}]^{n}$,

  4. 4.

outputs the signature as
$\sigma=(z_{1},z_{2},\cdots,z_{t},b_{1},b_{2},\cdots,b_{t})$.

$(1~{}\mbox{or}~{}0)\leftarrow{\sf Verification}(m,\sigma,{PK}):$ On receiving
a signature $\sigma$ from the sender, a verifier executes the following
operations:

  1. 1.

computes

$X^{\prime}_{k}=\left.\begin{cases}[z_{k}]\mathcal{E},&\text{if }b_{k}=0\\\
[z_{k}]\mathcal{E}_{1},&\text{if }b_{k}=1\par\end{cases}\right\\},$

  2. 2.

evaluates
$H(X^{\prime}_{1},\cdots,X^{\prime}_{t},m)=b^{\prime}_{1}\parallel\cdots\parallel
b^{\prime}_{t}$ ,

  3. 3.

outputs 1 if the equality $b_{1}\parallel\cdots\parallel
b_{t}=b^{\prime}_{1}\parallel\cdots\parallel b^{\prime}_{t}$ holds, else
outputs 0.

######  Theorem 2.

[26] The above signature scheme is unforgeable under chosen-message attack
(uf-cma) relying on the hard problem $\sf{GAIP}$ in the random oracle model.

###  2.7 Notion of a proxy signature scheme [9]

In general, a proxy signature involves two entities A (original signer) and B
(proxy signer) with the following five algorithms:

(pp) $\leftarrow$ ${\sf Setup}$ $(1^{\lambda})$:- On input the security
parameter $\lambda\in\mathbb{N}$, this algorithm outputs the collection of
public parameters pp which are published in a public platform like a bulletin
board.

${((PK_{A},SK_{A}),(PK_{B},SK_{B}))}$ $\leftarrow$ ${\sf Key~{}generation}$
(pp):- In this algorithm, A and B generate their key pairs $(PK_{A},SK_{A})$
and $(PK_{B},SK_{B})$ respectively.

(${z_{B}}$) $\leftarrow$ ${\sf Proxy~{}share~{}generation}$
${(SK_{A},d_{B})}$:- Let $d_{B}$ be the attribute of B consisting of the
necessary information like DOB, id card number, etc. Then A generates a proxy
share $z_{B}$ with the help of $SK_{A}$ in favor of B and publishes
$(d_{B},z_{B})$ as a warrant in the bulletin board.

(0 or 1) $\leftarrow$ ${\sf Proxy~{}share~{}verification}$
$(PK_{A},d_{B},z_{B})$:- B runs this algorithm to check the validity of the
warrant $(d_{B},z_{B})$. The algorithm outputs 1 if the warrant is valid;
otherwise, it outputs 0.

($\sigma$) $\leftarrow$ ${\sf Proxy~{}signature}$ $(m,SK_{B},d_{B},z_{B})$:-
The proxy signer B holding a valid warrant, outputs a signature $\sigma$ on
some message using its secret key $SK_{B}$.

(0 or 1) $\leftarrow$ ${\sf Proxy~{}signature~{}verification}$
$(m,\sigma,PK_{A},PK_{B},d_{B},z_{B})$:- Given a message-signature pair
$(m,\sigma)$ along with a warrant $(d_{B},z_{B})$ of the proxy signer B, the
verifier checks the validity of the warrant $(d_{B},z_{B})$. If the warrant is
valid, the verifier checks the correctness of $(m,\sigma)$ using $PK_{B}$. It
then outputs a deterministic value of 1 if the verification is done correctly;
else, it outputs 0.

###  2.8 Existential unforgeability under chosen-message attack (uf-cma)

Let us consider a proxy signature scheme consisting of the algorithms: Setup,
Key generation, Proxy share generation, Proxy share verification, Proxy
signature, Proxy signature verification. The uf-cma security for the proxy
signature scheme is defined by a game between an adversary ($\mathcal{A}$) and
a challenger ($\mathcal{C}$) for a particular proxy signer with attribute $d$.
Once $d$ is chosen, it remains unchanged throughout the game. In this game
$\mathcal{C}$ generates the key pair for original signer and the proxy signer.
In the following, $\mathcal{C}$ responds to the queries made by $\mathcal{A}$
over some messages polynomial number of times with $d^{\prime}$. Finally, the
$\mathcal{A}$ has to output a valid message-signature pair
$(m^{\star},\sigma^{\star})$ to win the game, where the message $m^{\star}$
should not be queried before. We denote this experiment by $Exp^{uf-
cma}_{proxy(1^{\lambda})}$ which is described below in detail.

Setup: $\mathcal{C}$ runs the Key generation algorithm on input pp to generate
a new public key-secret key pairs $(PK_{O},SK_{O})$ for original signer and
$(PK_{P},SK_{P})$ for proxy signer on input of security parameter $\lambda$.

Sign-query: In this phase, $\mathcal{A}$ queries to $\mathcal{C}$ of proxy
signature for a message m with the attribute $d$ of the proxy signer.
$\mathcal{C}$ first recognizes the warrant $(d,z)$ for $d$ from the bulletin
board and runs the algorithm Proxy signature to generate a proxy signature
$\sigma$ which is sent to $\mathcal{A}$. $\mathcal{A}$ can query polynomial
number of times.

Forgery: $\mathcal{A}$ outputs a forge signature $\sigma^{\star}$ for a
message $m^{\star}$ which has not been previously queried. $\mathcal{A}$
succeeds if it can impersonate the proxy signer i.e., Proxy signature
verification outputs 1 on input
$(m^{\star},\sigma^{\star},PK_{O},PK_{P},d,z)$.

The advantage of $\mathcal{A}$ is defined as $Adv_{\mathcal{A}}^{Exp^{uf-
cma}_{proxy(1^{\lambda})}}$ = Prob[$Exp^{uf-cma}_{proxy(1^{\lambda})}$ = 1] =
Prob[$\mathcal{A}$ wins the game].

######  Definition 4.

A prosy signature scheme is said to be uf-cma secure if for any probabilistic
polynomial time adversary $\mathcal{A}$,

$Adv_{\mathcal{A}}^{Exp^{uf-cma}_{proxy(1^{\lambda})}}\leq\epsilon(\lambda)$

where $\epsilon(\lambda)$ is a negligible function of $\lambda$.

##  3 Proposed isogeny based proxy signature

In this section, we describe our proposed scheme CSI-PS, where the original
signer (A) delegates its signing authority to the proxy signer (B). Our
approach consists of six algorithms: Setup, key generation, Proxy share
generation, Proxy share verification, Proxy signature, Proxy signature
verification. During the ${\sf Setup}$ phase, the original signer generates
the public parameters. Key generation algorithm enables A and B to generate
their public key-secret key pairs. During the Proxy share generation phase, A
will generate a proxy share $z_{B}$ for B by using its secret key and B’s
attribute $d_{B}$ consisting of identity and other necessary information, like
DOB, identity card number, etc. of B. On receiving a proxy share $z_{B}$ from
A, the proxy signer B checks the validity of the warrant $(d_{B},z_{B})$ by
implementing the algorithm Proxy share verification. During the Proxy
signature algorithm, B generates a signature on a message $m$ with its secret
key and proxy share $z_{B}$. The verifier verifies the correctness of the
warrant and validity of the message-signature pair during the Proxy signature
verification phase. A comprehensive description is provided below:

(pp) $\leftarrow$ ${\sf Setup}$ $(1^{\lambda})$:- On input of security
parameter $1^{\lambda}$, original signer A selects suitable CSIDH (see 2.3)
parameters including one basic elliptic curve $E_{0}:y^{2}=x^{3}+x$, one
exponent interval $[-I_{0},I_{0}]$, $I_{0}\in$ $\mathbb{N}$, and parameters
$\alpha_{0}$, $\gamma_{0}$, $\gamma_{1}$, $M_{1}$, $M_{2}$ from $\mathbb{Z}$ .
Then A computes one exponent interval $I_{1}=\alpha_{0}I_{0}$, two branch
integers $L_{0}=2^{\gamma_{0}}-1$, $L_{1}=2^{\gamma_{1}}-1$ and publishes
$pp=(E_{0},\alpha_{0},\gamma_{0},\gamma_{1}M_{1},M_{2},I_{0},I_{1},L_{0},L_{1})$

${((PK_{A},SK_{A}),(PK_{B},SK_{B}))}$ $\leftarrow$ ${\sf Key~{}generation}$
(pp):- A does the following operations for $i=1,2,\cdots,L_{0}$:

  1. 1.

Randomly chooses $\textbf{a}^{(i)}$=$(a_{1}^{(i)},\cdots,a_{n}^{(i)})$ $\in$
$[-I_{0},I_{0}]^{n}$.

  2. 2.

Computes $E_{i}=[\textbf{a}^{(i)}]E_{0}.$

  3. 3.

Publishes the public key $PK_{A}={(E_{i})}^{L_{0}}_{i=1}$ and keeps the secret
key $SK_{A}={(\textbf{a}^{(i)})}^{L_{0}}_{i=1}.$

On the other hand, B executes the following for $i=1,2,\cdots,L_{0}$:

  1. 1.

Randomly selects $\textbf{b}^{(i)}$=$(b_{1}^{(i)},\cdots,b_{n}^{(i)})$ $\in$
$[-I_{0},I_{0}]^{n}$.

  2. 2.

Evaluates $\hat{E_{i}}=[\textbf{b}^{(i)}]E_{0}$.

  3. 3.

Sets the public key as $PK_{B}={(\hat{E_{i}})}^{L_{0}}_{i=1}$ and the secret
key as $SK_{B}={(\textbf{b}^{(i)})}^{L_{0}}_{i=1}$.

Algorithm 2 Key generation (original signer)

1:pp

2:for each $i\in 1,\cdots,L_{0}$ do

3: $\textbf{a}^{(i)}$=$(a_{1}^{(i)},\cdots,a_{n}^{(i)})$ $\in_{R}$
$[-I_{0},I_{0}]^{n}$.

4: Evaluate $E_{i}=[\textbf{a}^{(i)}]E_{0}$.

5:end for

6:$PK_{A}={(E_{i})}^{L_{0}}_{i=1}$,
$SK_{A}={(\textbf{a}^{(i)})}^{L_{0}}_{i=1}$.

Algorithm 3 Key generation (proxy signer)

1:pp

2:for each $i\in 1,2,\cdots,L_{0}$ do

3: $\textbf{b}^{(i)}$=$(b_{1}^{(i)},\cdots,b_{n}^{(i)})$ $\in_{R}$
$[-I_{0},I_{0}]^{n}$.

4: Evaluate $\hat{E_{i}}=[\textbf{b}^{(i)}]E_{0}$.

5:end for

6:$PK_{B}={(\hat{E_{i})}}^{L_{0}}_{i=1}$,
$SK_{B}={(\textbf{b}^{(i)})}^{L_{0}}_{i=1}$.

(${z_{B}}$) $\leftarrow$ ${\sf Proxy~{}share~{}generation}$
${(SK_{A},d_{B})}$:- The original signer A executes the following steps to
generate a proxy share $z_{B}$ on input $SK_{A}$ and B’s attribute $d_{B}$. To
do that, A performs the following tasks.

  1. 1.

Computes $h=H_{1}(d_{B},pp)$, where
$H_{1}:\\{{0,1}\\}^{*}\rightarrow(\mathbb{Z}_{{L_{0}}+1})^{M_{1}}$ is a
cryptographically secure collision resistant hash function and parses $h$ as
integer $\\{h_{i}\\}_{i=1}^{M_{1}}$.

  2. 2.

For $i=1,\cdots,M_{1}$ and $j=1,\cdots,M_{2}$ chooses
$\textbf{x}^{(i,j)}\in_{R}[-(I_{0}+I_{1}),(I_{0}+I_{1})]^{n}$ and evaluates,
$X_{ij}=[\textbf{x}^{(i,j)}]E_{h_{i}}$.

  3. 3.

Determines $C=H_{2}(d_{B},pp,\\{{X}_{ij}\\}_{i=1j=1}^{M_{1}M_{2}})$ for
cryptographically secure collision resistant hash function
$H_{2}:\\{{0,1}\\}^{*}\rightarrow(\mathbb{Z}_{{L_{1}}+1})^{M_{1}M_{2}}$ and
parses it to integers $\\{C_{(i,j)}\\}_{i=1j=1}^{M_{1}M_{2}}$.

  4. 4.

For $i=1,\cdots,M_{1}$ and $j=1,\cdots,M_{2}$, sets
$\textbf{y}^{(i,j)}=\begin{cases}\textbf{x}^{(i,j)},&\text{if
$C_{(i,j)}=0$}\\\
\textbf{x}^{(i,j)}+\textbf{a}^{(h_{i})},&\text{otherwise}\end{cases}$

  5. 5.

If $\textbf{y}^{(i,j)}\in[-I_{1},I_{1}]^{n}$ then performs the next step;
otherwise, starts from step 2.

  6. 6.

Outputs the proxy share as
$z_{B}=(C,\\{\mathbf{y}^{(i,j)}\\}^{M_{1},M_{2}}_{i=1j=1})$ which is delivered
to B and publishes $(d_{B},z_{B})$ as warrant on the bulletin board.

Algorithm 4 Proxy share generation

1:${(SK_{A},d_{B})}$, $d_{B}$ is some attributes of $B$.

2:Computes $h=H_{1}(d_{B},pp)$.
$H_{1}:\\{{0,1}\\}^{*}\rightarrow(\mathbb{Z}_{{L_{0}}+1})^{M_{1}}$ is a hash
function.

3:Parses $h$ as integer $\\{h_{i}\\}_{i=1}^{M_{1}}$.

4:for each $i=1,\cdots,M_{1}$ and $j=1,\cdots,M_{2}$ do

5: Chooses $\textbf{x}^{(i,j)}\in_{R}[-(I_{0}+I_{1}),(I_{0}+I_{1})]^{n}$.

6: Evaluates $X_{ij}=[\textbf{x}^{(i,j)}]E_{h_{i}}$.

7:end for

8:$C=H_{2}(d_{B},pp,\\{{X}_{ij}\\}_{i=1j=1}^{M_{1}M_{2}})$ for a
cryptographically secure collision resistant hash function
$H_{2}:\\{{0,1}\\}^{*}\rightarrow(\mathbb{Z}_{{L_{1}}+1})^{M_{1}M_{2}}$.

9:Parses $C$ to a integer set $\\{C_{(i,j)}\\}_{i=1j=1}^{M_{1}M_{2}}$.

10:for each $i=1,\cdots,M_{1}$ and $j=1,\cdots,M_{2}$ do

11: if $C_{(i,j)}=0$ then

12: $\textbf{y}^{(i,j)}=\textbf{x}^{(i,j)}$

13: else

14: $\textbf{y}^{(i,j)}=\textbf{x}^{(i,j)}+\textbf{a}^{(h_{i})}$

15: end if

16: if $\textbf{y}^{(i,j)}\in[-I_{1},I_{1}]^{n}$ then

17: Perform the next step.

18: else

19: Start from Step 3.

20: end if

21:end for

22:$z_{B}=(C,\\{\mathbf{y}^{(i,j)}\\}^{M_{1},M_{2}}_{i=1j=1})$ and publishes
$(d_{B},z_{B})$ as the warrant.

(0 or 1) $\leftarrow$ ${\sf Proxy~{}share~{}verification}$
$(PK_{A},d_{B},z_{B})$:- On input $(PK_{A},d_{B},z_{B})$, the proxy signer B
performs the following tasks to check whether the warrant $(d_{B},z_{B})$ is
valid or not:

  1. 1.

Determines $h=H_{1}(d_{B},pp)$, and parses $h$ and $C$ into integers as
$\\{h_{i}\\}_{i=1}^{M_{1}}$ with $0\leq h_{i}\leq L_{0}$ and
$\\{C_{(i,j)}\\}_{i=1j=1}^{M_{1}M_{2}}$ with $0\leq C_{(i,j)}\leq L_{1}$
respectively.

  2. 2.

For $i=1,\cdots,M_{1}$ and $j=1,\cdots,M_{2}$ sets
$\overline{X}_{ij}=\begin{cases}[\textbf{y}^{(i,j)}]E_{h_{i}},&\text{if
$C_{(i,j)}=0$}\\\ [\textbf{y}^{(i,j)}]E_{0},&\text{otherwise}\end{cases}$

  3. 3.

Determines
$C^{\prime}=H_{2}(d_{B},pp,\\{\overline{X}_{ij}\\}_{i=1j=1}^{M_{1}M_{2}})$.

  4. 4.

If $C=C^{\prime}$, outputs 1 and gets the assurance of signing authority on
behalf of the original signer A; otherwise, outputs 0.

Algorithm 5 Proxy share verification

1:$(PK_{A},d_{B},z_{B})$.

2:Evaluate $h=H_{1}(d_{B},pp)$.

3:Parses $h$ as integers $\\{h_{i}\\}_{i=1}^{M_{1}}$, $0\leq h_{i}\leq L_{0}$.

4:Parses $C$ as integers $\\{C_{(i,j)}\\}_{i=1j=1}^{M_{1}M_{2}}$, $0\leq
C_{(i,j)}\leq L_{1}$.

5:for each $i=1,\cdots,M_{1}$ and $j=1,\cdots,M_{2}$ do

6: if $C_{(i,j)}=0$ then

7: $\overline{X}_{ij}=[\textbf{y}^{(i,j)}]E_{h_{i}}$

8: else

9: $\overline{X}_{ij}=[\textbf{y}^{(i,j)}]E_{0}$

10: end if

11:
$C^{\prime}=H_{2}(d_{B},pp,\\{\overline{X}_{ij}\\}_{i=1j=1}^{M_{1}M_{2}})$.

12: if $C=C^{\prime}$ then

13: True.

14: else

15: False.

16: end if

17:end for

18:True/False.

($\sigma$) $\leftarrow$ ${\sf Proxy~{}signature}$ $(m,SK_{B},d_{B},z_{B})$:-
On input of a message $m\in\\{0,1\\}^{\star}$, $SK_{B}$, $d_{B}$ and $z_{B}$,
B executes the following steps to generate a proxy signature $\sigma$ for $m$.

  1. 1.

Computes $h^{\prime}={H_{1}}(z_{B},pp)$ and parses $h^{\prime}$ as integers
$\\{h_{i}^{\prime}\\}_{i=1}^{M_{1}}$ for $0\leq h_{i}^{\prime}\leq L_{0}$.

  2. 2.

For $i=1,\cdots,M_{1}$ and $j=1,\cdots,M_{2}$, chooses
$\boldsymbol{\xi}^{(i,j)}\in_{R}[-(I_{0}+I_{1}),(I_{0}+I_{1})]^{n}$ and
evaluates $Y_{(i,j)}=[\boldsymbol{\xi}^{(i,j)}]{\hat{E}_{h_{i}^{\prime}}}$.

  3. 3.

Determines $D={H_{2}}(z_{B},pp,m,\\{{Y}_{ij}\\}_{i=1j=1}^{M_{1}M_{2}})$ and
parses it to integers $\\{D_{(i,j)}\\}_{i=1j=1}^{M_{1}M_{2}}$ with $0\leq
D_{(i,j)}\leq L_{1}$.

  4. 4.

For $i=1,\cdots,M_{1}$ and $j=1,\cdots,M_{2}$ sets
$\boldsymbol{\eta}^{(i,j)}=\begin{cases}\boldsymbol{\xi}^{(i,j)},&\text{if
$D_{(i,j)}=0$}\\\
\boldsymbol{\xi}^{(i,j)}+\textbf{b}^{(h^{\prime}_{i})},&\text{otherwise}\end{cases}$

  5. 5.

If $\boldsymbol{\eta}^{(i,j)}\in[-I_{1},I_{1}]^{n}$ then performs the next
step; otherwise, starts from step 2.

  6. 6.

Outputs the signature as
${\sigma=\\{D,{\\{\boldsymbol{\eta}}^{(i,j)}\\}_{i=1j=1}^{M_{1}M_{2}}}\\}$.

Algorithm 6 Proxy signature

1:$(m,SK_{B},d_{B},z_{B})$, $m\in\\{0,1\\}^{\star}$

2:Computes $h^{\prime}={H_{1}}(z_{B},pp)$.

3:$h^{\prime}=\\{h_{i}^{\prime}\\}_{i=1}^{M_{1}}$, $h_{i}^{\prime}$’s are
integers with $0\leq h_{i}^{\prime}\leq L_{0}$.

4:for each $i=1,\cdots,M_{1}$ and $j=1,\cdots,M_{2}$ do

5: Chooses
$\boldsymbol{\xi}^{(i,j)}\in_{R}[-(I_{0}+I_{1}),(I_{0}+I_{1})]^{n}$.

6: Evaluates $Y_{(i,j)}=[\boldsymbol{\xi}^{(i,j)}]{\hat{E}_{h_{i}^{\prime}}}$.

7:end for

8:$D={H_{2}}(z_{B},pp,m,\\{{Y}_{ij}\\}_{i=1j=1}^{M_{1}M_{2}})$.

9:Parses $D$ to a integer set $\\{D_{(i,j)}\\}_{i=1j=1}^{M_{1}M_{2}}$ with
$0\leq D_{(i,j)}\leq L_{1}$.

10:for each $i=1,2,\ldots,M_{1}$ and $j=1,2,\ldots,M_{2}$ do

11: if $D_{(i,j)}=0$ then

12: $\boldsymbol{\eta}^{(i,j)}=\boldsymbol{\xi}^{(i,j)}$

13: else

14:
$\boldsymbol{\eta}^{(i,j)}=\boldsymbol{\xi}^{(i,j)}+\textbf{b}^{(h^{\prime}_{i})}$

15: end if

16: if $\boldsymbol{\eta}^{(i,j)}\in[-I_{1},I_{1}]^{n}$ then

17: Perform the next step.

18: else

19: Start from Step 3.

20: end if

21:end for

22:${\sigma=\\{D,{\\{\boldsymbol{\eta}}^{(i,j)}\\}_{i=1j=1}^{M_{1}M_{2}}}\\}$.

(0 or 1) $\leftarrow$ ${\sf Proxy~{}signature~{}verification}$
$(m,\sigma,PK_{A},PK_{B},d_{B},z_{B})$:- Using $(PK_{A},d_{B},z_{B})$, the
verifier initially checks the validity of the warrant $(d_{B},z_{B})$ of B
using the similar approach as discussed in proxy share verification. If the
verification fails it outputs $0$; otherwise, does the following:

  1. 1.

Computes $h^{\prime}={H_{1}}(z_{B},pp)$, and parses $h^{\prime}$ and $D$ into
integers as $\\{h_{i}^{\prime}\\}_{i=1}^{M_{1}}$ with $0\leq
h_{i}^{\prime}\leq L_{0}$ and $\\{D_{(i,j)}\\}_{i=1j=1}^{M_{1}M_{2}}$ with
$0\leq D_{(i,j)}\leq L_{1}$, respectively.

  2. 2.

For $i=1,\cdots,M_{1}$ and $j=1,\cdots,M_{2}$ , sets
$\overline{Y}_{(i,j)}=\begin{cases}[{\boldsymbol{\eta}}^{(i,j)}]{\hat{E}_{h_{i}^{\prime}}},&\text{if
$D_{(i,j)}=0$}\\\
[{\boldsymbol{\eta}}^{(i,j)}]{{E}_{0}},&\text{otherwise}\end{cases}$

  3. 3.

Evaluates
$D^{\prime}={H_{2}}(z_{B},pp,m,\\{{\overline{Y}}_{ij}\\}_{i=1j=1}^{M_{1}M_{2}})$.

  4. 4.

If $D=D^{\prime}$, outputs 1; otherwise, outputs 0.

Algorithm 7 Proxy signature verification

1:$(m,\sigma,PK_{A},PK_{B},d_{B},z_{B})$.

2:Evaluate $h=H_{1}(d_{B},pp)$.

3:Parses $h$ as integers $\\{h_{i}\\}_{i=1}^{M_{1}}$, $0\leq h_{i}\leq L_{0}$.

4:Parses $C$ as integers $\\{C_{(i,j)}\\}_{i=1j=1}^{M_{1}M_{2}}$, $0\leq
C_{(i,j)}\leq L_{1}$.

5:for each $i=1,\cdots,M_{1}$ and $j=1,\cdots,M_{2}$ do

6: if $C_{(i,j)}=0$ then

7: $\overline{X}_{ij}=[\textbf{y}^{(i,j)}]E_{h_{i}}$

8: else

9: $\overline{X}_{ij}=[\textbf{y}^{(i,j)}]E_{0}$

10: end if

11:
$C^{\prime}=H_{2}(d_{B},pp,\\{\overline{X}_{ij}\\}_{i=1j=1}^{M_{1}M_{2}})$.

12: if $C=C^{\prime}$ then

13: Determines $h^{\prime}={H_{1}}(z_{B},pp)$.

14: Parses $h^{\prime}$ as $\\{h_{i}^{\prime}\\}_{i=1}^{M_{1}}$, where
$h_{i}^{\prime}$’s are integers with $0\leq h_{i}^{\prime}\leq L_{0}$.

15: Parses $D$ as integers $\\{D_{(i,j)}\\}_{i=1j=1}^{M_{1}M_{2}}$ with $0\leq
D_{(i,j)}\leq L_{1}$.

16: for each $i=1,\cdots,M_{1}$ and $j=1,\cdots,M_{2}$ do

17: if $D_{(i,j)}=0$ then

18:
$\overline{Y}_{(i,j)}=[{\boldsymbol{\eta}}^{(i,j)}]{\hat{E}_{h_{i}{\prime}}}$

19: else

20: $\overline{Y}_{(i,j)}=[{\boldsymbol{\eta}}^{(i,j)}]{{E}_{0}}$

21: end if

22:
$D^{\prime}={H_{2}}(z_{B},pp,m,\\{{\overline{Y}}_{ij}\\}_{i=1j=1}^{M_{1}M_{2}})$.

23: if $D=D^{\prime}$ then

24: True.

25: else

26: False.

27: end if

28: end for

29: else

30: False

31: end if

32:end for

33:True/False.

###  3.1 Correctness

To check the correctness of the proxy share and the proxy signature, we need
to check the correctness of the equalities, $C=C^{\prime}$ and $D=D^{\prime}$,
respectively.

$C=C^{\prime}$ will hold if and only if ${X_{ij}}=\overline{X}_{ij}$ for
$1\leq i\leq M_{1}$, $1\leq j\leq M_{2}$.
Note that $X_{ij}=[\textbf{x}^{(i,j)}]E_{h_{i}}$ and
$\overline{X}_{ij}=\begin{cases}[\textbf{y}^{(i,j)}]E_{h_{i}},&\text{if
$C_{(i,j)}=0$}\\\ [\textbf{y}^{(i,j)}]E_{0},&\text{otherwise.}\end{cases}$

For $C_{(i,j)}=0$, $\textbf{y}^{(i,j)}=\textbf{x}^{(i,j)}$ which implies
$\overline{X}_{ij}=[\textbf{y}^{(i,j)}]E_{h_{i}}=[\textbf{x}^{(i,j)}]E_{h_{i}}$.
On the other hand, if $C_{(i,j)}\neq 0$ then
$\textbf{y}^{(i,j)}=\textbf{x}^{(i,j)}+\textbf{a}^{(h_{i})}$, which implies
$\overline{X}_{ij}=[\textbf{y}^{(i,j)}]E_{0}=[\textbf{x}^{(i,j)}+\textbf{a}^{(h_{i})}]E_{0}=[\textbf{x}^{(i,j)}]E_{h_{i}}$.
Thus, the equality $C=C^{\prime}$ holds. Similarly, it can be proved that the
equality $D=D^{\prime}$ holds.

##  4 Security Analysis

In this section, we discuss the security of our proposed scheme.

  * •

Unforgeability of proxy signature: We now prove that our proposed isogeny
based proxy signature scheme CSI-PS is uf-cma secure under the hardness of the
group action inverse problem of isogeny. $H_{1}$ and $H_{2}$ are considered as
random oracles. We show this by contradiction. If possible let there be an
adversary $\mathcal{A}$ with non-negligible advantage in the uf-cma game. Then
we are going to show that using $\mathcal{A}$ an oracle machine
$O^{\mathcal{A}}$ can be designed to break the isogeny problem by utilizing
the outputs of $H_{1}$ and $H_{2}$. In order to do that, we present a series
of games $Game^{0}$, $Game^{1}$, $Game^{2}$, $Game^{3}$, where $Game^{i}$
slightly modifies $Game^{i-1}$ for $i=1,2,3$. Let us denote the success
probability of $\mathcal{A}$ in $Game^{i}$ as Prob[$Game^{i}$].

    1. 1.

$\textbf{Game}^{0}$: $Game^{0}$ is exactly same as uf-cma game for proxy
signature. Therefore, $Adv_{\mathcal{A}}^{Exp^{uf-cma}_{proxy(1^{\lambda})}}$
= Prob[$Exp^{uf-cma}_{proxy(1^{\lambda})}$ = 1] = Prob[$Game^{0}$].

    2. 2.

$\textbf{Game}^{1}$: It is similar to $Game^{0}$, except that
$O^{\mathcal{A}}$ replaces output of the the hash function $H_{1}$ on
$(z_{B},pp)$ by a random string of length $M_{1}$ from
$(\mathbb{Z}_{{L_{0}}+1})^{M_{1}}$. If $|Prob(Game^{1})-Prob(Game^{0})|$ is
non-negligible then $\mathcal{A}$ will be able to distinguish the output
distribution of $H_{1}$ which is impossible since $H_{1}$ is chosen as random
oracle. Hence $|Prob(Game^{1})-Prob(Game^{0})|$ should be negligible, say
bounded by $\epsilon_{1}(\lambda)$.

    3. 3.

$\textbf{Game}^{2}$: $Game^{2}$ is similar to $Game^{1}$, except that
$O^{\mathcal{A}}$ substitutes output of the hash function $H_{2}$ by a random
string chosen from $(\mathbb{Z}_{{L_{1}}+1})^{M_{1}M_{2}}$. By a similar
argument as discussed in $Game^{1}$, $|Prob(Game^{2})-Prob(Game^{1})|$ $\leq$
$\epsilon_{2}(\lambda)$ (negligible).

    4. 4.

$\textbf{Game}^{3}$: This is similar to $Game^{2}$, except that during the
challenge phase when $\mathcal{A}$ tries to forge a signature of a message
$m^{*}$, $O^{\mathcal{A}}$ substitutes $H_{1}$ output by a random tuple from
$(\mathbb{Z}_{{L_{0}}+1})^{M_{1}}$ and substitute $H_{2}$ by a random tuple
from $(\mathbb{Z}_{{L_{1}}+1})^{M_{1}M_{2}}$. Using the similar argument as
discussed in $Game^{1}$, we may conclude that
$|Prob(Game^{3})-Prob(Game^{2})|$ $\leq$ $\epsilon_{3}(\lambda)$ (negligible).

Now $|Prob(Game^{3})-Adv_{\mathcal{A}}^{Exp^{uf-cma}_{\textit{CSI-
PS}(1^{\lambda})}}|$= $|Prob(Game^{3})-Prob(Game^{0})|$
$\leq$ $|Prob(Game^{3})-Prob(Game^{2})|$+$|Prob(Game^{2})-Prob(Game^{1})|$\+
$|Prob(Game^{1})-Prob(Game^{0})|$ $\leq$
$\epsilon_{1}(\lambda)$+$\epsilon_{2}(\lambda)$+$\epsilon_{3}(\lambda)$=$\epsilon(\lambda)$
(say).

Therefore, the success probability of $\mathcal{A}$ in $Game^{3}$ is close to
$Adv_{AD}^{Exp^{uf-cma}_{\textit{CSI-PS}(1^{\lambda})}}$. Since we have
assumed that $Adv_{\mathcal{A}}^{Exp^{uf-cma}_{\textit{CSI-PS}(1^{\lambda})}}$
is non-negligible we can ensure that $Prob(Game^{3})$ is also non-negligible.
Thereby, with the held of $\mathcal{A}$ and controlling $H_{1}$, $H_{2}$, the
oracle machine $O^{\mathcal{A}}$ can generate two valid transcripts
$(\\{{Y}_{ij}\\}$, $D^{(1)}$, ${\boldsymbol{\eta}_{1}^{(i,j)}})$ and
$(\\{{Y}_{ij}\\},D^{(2)},{\boldsymbol{\eta}_{2}^{(i,j)}})$ where
$D^{(1)}_{(i,j)}=0$ and $D^{(2)}_{(i,j)}\neq 0$ $\forall$ $i$, $j$. Note that
$\boldsymbol{\eta}_{1}^{(i,j)}=\boldsymbol{\xi}^{(i,j)}$ since
$D^{(1)}_{(i,j)}=0$ and
$\boldsymbol{\eta}_{2}^{(i,j)}=\boldsymbol{\xi}^{(i,j)}+\textbf{b}^{\left(h^{\prime}_{i}\right)}$
since $D^{(2)}_{(i,j)}\neq 0$. Utilizing $\boldsymbol{\eta}_{1}^{(i,j)}$ and
$\boldsymbol{\eta}_{2}^{(i,j)}$, $O^{\mathcal{A}}$ can easily extract the
secret $SK_{B}=\\{B^{i}\\}_{i=1}^{L_{0}}$. Therefore, the group action inverse
problem ($\sf{GAIP}$) between two elliptic curves is broken which leads to a
contradiction. Thus, the advantage of $\mathcal{A}$ in the uf-cma game can not
be non-negligible. In other words, our scheme CSI-PS is uf-cma secure.
We now discuss the other security properties of our proposed design CSI-PS.

  * •

Identifiability: Given a signature $\sigma$ with the proxy share $z_{B}$, the
verifier finds $(d_{B},z_{B})$ from the bulletin board and verifies the
correctness of $z_{B}$. If it is valid, then from $d_{B}$, the identity of the
proxy signer is detected.

  * •

Undeniability: At the stage of the verification process of the proxy
signature, the proxy signer cannot deny their generation of the proxy
signature. Here, the proxy signature contains
${\\{\mathbf{\eta}}^{(i,j)}\\}_{i=1j=1}^{M_{1}L_{1}}$, which is constructed by
using secret-key of the proxy signer. Hence, after generating the proxy
signature, the proxy signer can not disagree with their signature generation.

  * •

Verifiability: In the verification process, the verifier has to be convinced
about the agreement of the original signature and the proxy signer from the
proxy signature. To generate the warrant $z_{B}$, the secret key of the
original signer has been used. Thus, by verifying the correctness of $z_{B}$
using $PK_{A}$, the verifier is convinced about the agreement.

  * •

Distinguishability: Anyone authorized to verify a signature can distinguish
between a proxy signature and a normal signature. In the isogeny-based
signature scheme Seasign [26], the signer generates a signature on a message
using their own secret key, and the verifier confirms the signature using the
signer’s public key. On the other hand, in a proxy signature scheme, the proxy
signer uses their own proxy share $z_{B}$ (generated by the original signer)
and own secret key. The verifier then checks the signature using the proxy
share and the public information of both the original signer and the proxy
signer. Therefore, the proxy signature and the ordinary signature are
distinguishable due to their different structures.

  * •

Secrecy: Given the proxy share $z_{B}$, it is impossible to derive the
original signer’s secret key. Deriving the secret key from the warrant would
require solving the GAIP problem (see Definition 3) for the instances
$(X_{ij},E_{h_{i}})$, where $i=1,2,\ldots,M_{1}$ and $j=1,2,\ldots,M_{2}$.
Thus, extracting the original signer’s secret key is computationally hard.
Similarly, it is difficult to extract the proxy signer’s secret key from a
proxy signature.

  * •

Prevention of misuse: The proxy signer can sign a message using the warrant
$(d_{B},z_{B})$ assigned specifically to them. This warrant includes their
identity and other necessary information. Therefore, any misuse of the proxy
signature can be traced back to the proxy signer through the warrant.

  * •

Revocability: Once the time period involved in the warrant $(d_{B},z_{B})$ is
over, automatically the signing authority of the proxy signer is removed.
Besides, the original signer can broadcast the announcement of invalidation of
the warrant $(d_{B},z_{B})$ by putting a signed message on the bulletin board.

##  5 Complexity Analysis of CSI-PS

We describe below the communication and computation complexity of our proposed
CSI-PS. The public key sizes of the original signer and the proxy signer, the
proxy share size, and the proxy signature size all contribute to the scheme’s
communication costs. Each signer’s public key is made up of $L_{0}$ number of
elliptic curves. According to Theorem 1, any elliptic curve can be represented
by a single coefficient in $\mathbb{F}_{p}$ after class group action.
Additionally, proxy share generation and proxy signature generation both
contains one hash output and $M_{1}M_{2}$ vectors from $[-I_{1},I_{1}]^{n}$.
In our scheme, we have two hash functions $H_{1}$ and $H_{2}$. In proxy share
generation and proxy signature generation algorithms four hash outputs
$h,h^{\prime}$, $C$ and $D$ have been used. The lengths of $h$ and
$h^{\prime}$ are $M_{1}\left\lceil{log(L_{0}+1)}\right\rceil$ bits. The
lengths of $C$ and $D$ are $M_{1}M_{2}\left\lceil{log(L_{1}+1)}\right\rceil$
bits. The communication complexity of our proposed scheme CSI-PS is given in
Table 1.
To achieve $\lambda$ bits of security we may take
$M_{1}\left\lceil{log(L_{0}+1)}\right\rceil\geq\lambda$ and
$M_{1}M_{2}\left\lceil{log(L_{1}+1)}\right\rceil\geq\lambda$. Since
$L_{0}=2^{\gamma_{0}}-1$ and $L_{1}=2^{\gamma_{1}}-1$, we conclude that
$M_{1}{\gamma_{0}}\geq\lambda$ and $M_{1}M_{2}{\gamma_{1}}\geq\lambda$. In
particular, we select our own parameters $M_{1}$ and $M_{2}$ as
$M_{1}\gamma_{0}=\lambda$, $M_{1}M_{2}\gamma_{1}=\lambda$. Hence,
$M_{1}=\frac{\lambda}{\gamma_{0}}$, $M_{1}M_{2}=\frac{\lambda}{\gamma_{1}}$
and $M_{2}=\frac{\gamma_{0}}{\gamma_{1}}$. We choose $\alpha_{0}=nM_{1}L_{1}$.
Castryck et al. [23] proposed parameters for CSIDH-512 to achieve AES-128 bit
security. CSIDH-512 includes the prime of the form $p=4l_{1}l_{2}\ldots
l_{n}-1$ where, $n=74$, $I_{73}=373$ and $I_{74}=587$, the key bound $m$ is
taken as 5 (See subsection 2.3 for details of the parameters). In our scheme
$n=74$, $I_{0}=5$. In order to calculate the sizes of the keys, proxy share
and proxy signature, we rely on the different choices of parameters
$(\gamma_{0},\gamma_{1}M_{1},M_{2},L_{0},L_{1})$ as proposed in [29] for
$\lambda=128$-bit security level. For some choices of parameters the results
are documented in Table 2.

Table 1: The sizes of public keys, secret keys, proxy share, and proxy signature. Data | Size (bits)
---|---
$PK_{A}$ | $L_{0}\left\lceil{log(p)}\right\rceil$
$SK_{A}$ | $L_{0}\left\lceil{nlog(2I_{0}+1)}\right\rceil$
$PK_{B}$ | $L_{0}\left\lceil{log(p)}\right\rceil$
$SK_{B}$ | $L_{0}\left\lceil{nlog(2I_{0}+1)}\right\rceil$
Proxy share($z_{B}$) |  $M_{1}M_{2}\left\lceil{log(L_{1}+1)}\right\rceil$ \+ $M_{1}M_{2}\left\lceil{nlog(2I_{1}+1)}\right\rceil$
Proxy Signature($\sigma$) |  $M_{1}M_{2}\left\lceil{log(L_{1}+1)}\right\rceil$ \+ $M_{1}M_{2}\left\lceil{nlog(2I_{1}+1)}\right\rceil$
Table 2: Communication cost and secret key size for different parameters for 128 bit security parameters $(\gamma_{0},\gamma_{1},M_{1},M_{2},L_{0},L_{1})$ | Public key size | Secret key size | Proxy share or signature size
---|---|---|---
(1, 1, 128, 1, 1, 1) | 63.75B | 32B | 19584B
(1, 8, 16, 1, 1, 255) | 63.75B | 32B | 3198B
(8, 16, 16, 1, 255, 65535) | 16256.25B | 8160B | 4402B
(16, 8, 8, 2, 65535, 255) | 4177856.25B | 2097120B | 3052B

##  6 Concrete Instantiation

In this section, we discuss and analyze a concrete instantiation of CSI-PS for
$128$-bit security level with parameter set $(16,8,8,2,65535,255)$ Suppose a
government officer A (original signer) is the only person authorized to sign a
specific document. In case $A$ is on the leave, they must appoint a
representative officer B (proxy signer) to delegate the signing authority. We
demonstrate how B will obtain signing rights from A using a toy example.

  * •

Here $I_{0}=5$, $n=74$, $\gamma_{0}=16$, $\gamma_{1}=8$, $M_{1}=8$, $M_{2}=2$,
$L_{0}=2^{16}-1=65535$, $L_{1}=2^{8}-1=255$, $I_{1}=754800$

  * •

A selects the vectors $\textbf{a}^{1},\cdots,\textbf{a}^{65535}$ randomly from
$[-5,5]^{74}$.

  * •

A computes $E_{1},\cdots,E_{65535}$, where $E_{i}=[\textbf{a}^{(i)}]E_{0}$,
$i=1,\cdots,65535$.

  * •

B selects the vectors $\textbf{b}^{1},\cdots,\textbf{b}^{65535}$ randomly from
$[-5,5]^{74}$.

  * •

B computes $\hat{E_{1}},\cdots,\hat{E}_{65535}$, where
$\hat{E_{i}}=[\textbf{b}^{(i)}]E_{0}$, $i=1,\cdots,65535$.

$SK_{A}=\textbf{a}^{1},\cdots,\textbf{a}^{65535}$,
$PK_{A}=E_{1},\cdots,E_{65535}$ and
$SK_{B}=\textbf{b}^{1},\cdots,\textbf{b}^{65535}$,
$PK_{B}=\hat{E_{1}},\cdots,\hat{E}_{65535}$. The original signer will now
perform the following actions.

  * •

$h=H_{1}(d_{B},pp)={h_{1},\cdots,h_{8}}$, where
$h_{1},\cdots,h_{8}\in\mathbb{Z}_{65536}$.

  * •

Randomly selects,
$\textbf{x}^{(1,1)},\textbf{x}^{(1,2)},\textbf{x}^{(2,1)},\textbf{x}^{(2,2)},\cdots,\textbf{x}^{(8,1)},\textbf{x}^{(8,2)}$
from $[754795,754805]^{74}$

  * •

Evaluates $X_{11}=[\textbf{x}^{(1,1)}]E_{h_{1}}$,
$X_{12}=[\textbf{x}^{(1,2)}]E_{h_{1}}$,
$X_{21}=[\textbf{x}^{(2,1)}]E_{h_{2}}$,
$X_{22}=[\textbf{x}^{(2,2)}]E_{h_{2}}$, $\cdots$,
$X_{81}=[\textbf{x}^{(8,1)}]E_{h_{8}}$,
$X_{ij}=[\textbf{x}^{(8,2)}]E_{h_{8}}$.

  * •

$C=H_{2}(d_{B},pp,\\{{X}_{ij}\\}_{i=1j=1}^{8~{}~{}2})$=
$\\{C_{(1,1)},C_{(1,2)},C_{(2,1)},C_{(2,2)},\cdots,C_{(8,1)},C_{(8,2)}\\}\subset\mathbb{Z}_{256}$.

  * •

Computes
$\textbf{y}^{(1,1)},\textbf{y}^{(1,2)},\textbf{y}^{(2,1)},\textbf{y}^{(2,2)},\cdots,\textbf{y}^{(8,1)},\textbf{y}^{(8,2)}$
according to Algorithm 4.

Therefore the proxy share is
$z_{B}=(C,\\{\mathbf{y}^{(i,j)}\\}^{8~{}~{}2}_{i=1j=1})$. Using Algorithm 5,
the representative proxy signer can validate the proxy share using its own
credentials. In the following, signing rights of the original signer might be
assigned to the representative signer B. B can now use the signing rights to
sign the respective documents on the behalf of the original signer A. We now
demonstrate how the representative officer can sign a document.

  * •

Evaluates
$h^{\prime}={H_{1}}(z_{B},pp)=\\{h_{1}^{\prime},\cdots,h_{8}^{\prime}\\}$,
where $h_{1}^{\prime},\cdots,h_{8}^{\prime}\in\mathbb{Z}_{65536}$.

  * •

Randomly selects,
$\boldsymbol{\xi}^{(1,1)},\boldsymbol{\xi}^{(1,2)},\boldsymbol{\xi}^{(2,1)},\boldsymbol{\xi}^{(2,2)},\cdots,\boldsymbol{\xi}^{(8,1)},\boldsymbol{\xi}^{(8,2)}$
from $[754795,754805]^{74}$.

  * •

Computes the following elliptic curves,
$Y_{11}=[\textbf{x}^{(1,1)}]\hat{E}_{h_{1}^{\prime}}$,
$Y_{12}=[\boldsymbol{\xi}^{(1,2)}]\hat{E}_{h_{1}^{\prime}}$,
$Y_{21}=[\boldsymbol{\xi}^{(2,1)}]\hat{E}_{h_{2}^{\prime}}$,
$Y_{22}=[\boldsymbol{\xi}^{(2,2)}]\hat{E}_{h_{2}^{\prime}}$, $\cdots$,
$Y_{81}=[\boldsymbol{\xi}^{(8,1)}]\hat{E}_{h_{8}^{\prime}}$,
$Y_{ij}=[\boldsymbol{\xi}^{(8,2)}]\hat{E}_{h_{8}^{\prime}}$.

  * •

Assume that $m$ represents the content of the document that the representative
officer wishes to sign. To proceed further he calculates the hash value,
$D=H_{2}(z_{B},pp,m,\\{{Y}_{ij}\\}_{i=1j=1}^{8~{}~{}2})$=
$\\{D_{(1,1)},D_{(1,2)},D_{(2,1)},D_{(2,2)},\cdots,D_{(8,1)},D_{(8,2)}\\}\subset\mathbb{Z}_{256}$.

  * •

Computes
$\boldsymbol{\eta}^{(1,1)},\boldsymbol{\eta}^{(1,2)},\boldsymbol{\eta}^{(2,1)},\boldsymbol{\eta}^{(2,2)},\cdots,\boldsymbol{\eta}^{(8,1)},\boldsymbol{\eta}^{(8,2)}$
by the method given in Algorithm 6 and checks whether
$\boldsymbol{\eta}^{(1,1)},\boldsymbol{\eta}^{(1,2)},\boldsymbol{\eta}^{(2,1)},\boldsymbol{\eta}^{(2,2)},\cdots,\boldsymbol{\eta}^{(8,1)},\boldsymbol{\eta}^{(8,2)}\in[-754800,754800]^{74}$.

Finally the proxy signer outputs the proxy signature
${\sigma=\\{D,{\\{\boldsymbol{\eta}}^{(i,j)}\\}_{i=1j=1}^{8~{}~{}2}}\\}$. The
designated verifier can verify the proxy signature using the Algorithm 7.
We now discuss the computation complexity of CSI-PS for $128$-bit security
level corresponding to aforementioned parameter set. The most computational
intensive operation in CSI-PS is the class group computation. In the first
step, we estimated the cost of one class group computation in terms of field
multiplications. In the following, we compute the computational complexity of
public key generation, proxy share generation, and proxy signature generation
in terms of total number of field multiplications required. We also calculated
the time complexity of CSI-PS by estimating the run time and cpu clock cycles
for public key generation, proxy share generation, and proxy signature
generation. We ran the C script111https://yx7.cc/code/csidh/csidh-
latest.tar.xz on a workstation having Intel Core i5-8700 2.40GHz processor
with 8GB of RAM and Linux Lite v5.2 OS. The results of our experiments are
summarized in Table 3.

Table 3: Computation complexity and time complexity of CSI-PS for 128 bit security level | Clock cycle | Time (in seconds) | Field multiplications
---|---|---|---
CSIDH-512 (one class group computation) | $45.7\times 10^{6}$ | $0.021624$ | $282,424$
Public Key | $29.94\times 10^{11}$ | $1422.12$ | $18,508,656,840$
Proxy Share | $73.12\times 10^{8}$ | $0.3472$ | $4,518,784$
Proxy Signature | $73.12\times 10^{8}$ | $0.3472$ | $4,518,784$

##  7 Conclusion

This paper presents a promising approach to delegate the signing rights of an
original signer to proxy signers using isogeny-based cryptography. The
isogeny-based signature scheme SeaSign [26] serves as the fundamental building
block for our scheme. Our proposed scheme achieves uf-cma security under the
assumption that the group action inverse problem ($\sf{GAIP}$) between two
elliptic curves is hard. Additionally, our scheme satisfies other security
properties of a proxy signature. In our design, the proxy signature is
$M_{1}M_{2}\left\lceil{\log(L_{1}+1)}\right\rceil$ \+
$M_{1}M_{2}\left\lceil{n\log(2I_{1}+1)}\right\rceil$ bits in size. Through
calculations, we conclude that the proxy signature size is 3052B for a 128-bit
security level with a certain parameter choice. Constructing the proxy
signature requires 16 class group operations or 4,518,784 field
multiplications. In particular, our proposed proxy signature scheme, CSI-PS,
is the first of its kind using isogeny-based cryptography.

## Declarations

#### Funding Details

This work was supported by the “International Mathematical Union (IMU) and the
Graduate Assistantships in Developing Countries (GRAID) Program”.

#### Conflict of interest

The authors state that they have not known competing financial interests or
personal connections that may seem to have influenced the work described in
this study.

#### Data availability

Data sharing is not applicable to this article as no new data were generated
or analyzed to support this research.

## References

  *   * Mambo et al. [1996] Mambo, M., Usuda, K., Okamoto, E.: Proxy signatures: Delegation of the power to sign messages. IEICE transactions on fundamentals of electronics, communications and computer sciences 79(9), 1338–1354 (1996)
  * Debnath et al. [2021] Debnath, S.K., Choudhury, T., Stanica, P., Dey, K., Kundu, N.: Delegating signing rights in a multivariate proxy signature scheme. American Institute of Mathematical Sciences: Advances in Mathematics of Communications (2021)
  * Bakker et al. [2001] Bakker, A., Van Steen, M., Tanenbaum, A.S.: A law-abiding peer-to-peer network for free-software distribution. In: Proceedings IEEE International Symposium on Network Computing and Applications. NCA 2001, pp. 60–67 (2001). IEEE
  * Neuman [1993] Neuman, B.C.: Proxy-based authorization and accounting for distributed systems. In: [1993] Proceedings. The 13th International Conference on Distributed Computing Systems, pp. 283–291 (1993). IEEE
  * Kim et al. [2001] Kim, H., Baek, J., Lee, B., Kim, K.: Secret computation with secrets for mobile agent using one-time proxy signature. Cryptography and information security 2001, 845–850 (2001)
  * Bamasak and Zhang [2004] Bamasak, O., Zhang, N.: A secure method for signature delegation to mobile agents. In: Proceedings of the 2004 ACM Symposium on Applied Computing, pp. 813–818 (2004)
  * Romao and da Silva [2001] Romao, A., Silva, M.M.: Secure mobile agent digital signatures with proxy certificates. In: E-Commerce Agents: Marketplace Solutions, Security Issues, and Supply and Demand, pp. 206–220. Springer, ??? (2001)
  * Lee et al. [2001] Lee, B., Kim, H., Kim, K.: Strong proxy signature and its applications. In: Proceedings of SCIS, vol. 2001, pp. 603–608 (2001)
  * Boldyreva et al. [2012] Boldyreva, A., Palacio, A., Warinschi, B.: Secure signature schemes for delegation of signing rights. Journal of Cryptology 25(1), 57–115 (2012)
  * Li et al. [2003] Li, L.-H., Tzeng, S.-F., Hwang, M.-S.: Generalization of proxy signature-based on discrete logarithms. Computers & Security 22(3), 245–255 (2003)
  * Shao [2003] Shao, Z.: Proxy signature schemes based on factoring. Information Processing Letters 85(3), 137–143 (2003)
  * Lee et al. [2011] Lee, C.-C., Lin, T.-C., Tzeng, S.-F., Hwang, M.-S.: Generalization of proxy signature based on factorization. International Journal of Innovative Computing, Information and Control 7(3), 1039–1054 (2011)
  * Awasthi and Lal [2003] Awasthi, A.K., Lal, S.: Proxy blind signature scheme. Cryptology EPrint Archive (2003)
  * Shor [1999] Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review 41(2), 303–332 (1999)
  * Ravi et al. [2021] Ravi, P., Howe, J., Chattopadhyay, A., Bhasin, S.: Lattice-based key-sharing schemes: A survey. ACM Computing Surveys (CSUR) 54(1), 1–39 (2021)
  * Ding and Yang [2009] Ding, J., Yang, B.-Y.: Multivariate public key cryptography. Post-quantum cryptography, 193–241 (2009)
  * De Feo [2017] De Feo, L.: Mathematics of isogeny based cryptography. arXiv preprint arXiv:1711.04062 12 (2017)
  * Srivastava et al. [2023] Srivastava, V., Baksi, A., Debnath, S.K.: An overview of hash based signatures. Cryptology ePrint Archive (2023)
  * Weger et al. [2022] Weger, V., Gassner, N., Rosenthal, J.: A survey on code-based cryptography. arXiv preprint arXiv:2201.07119 (2022)
  * Couveignes [2006] Couveignes, J.-M.: Hard homogeneous spaces. Cryptology ePrint Archive (2006)
  * Rostovtsev and Stolbunov [2006] Rostovtsev, A., Stolbunov, A.: Public-key cryptosystem based on isogenies. Cryptology ePrint Archive (2006)
  * Diffie and Hellman [1976] Diffie, W., Hellman, M.: New directions in cryptography. IEEE transactions on Information Theory 22(6), 644–654 (1976)
  * Castryck et al. [2018] Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: Csidh: an efficient post-quantum commutative group action. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 395–427 (2018). Springer
  * Peng et al. [2019] Peng, C., Chen, J., Zeadally, S., He, D.: Isogeny-based cryptography: a promising post-quantum technique. IT Professional 21(6), 27–32 (2019)
  * [25] Martindale, C., Panny, L.: Isogeny-based cryptography
  * De Feo and Galbraith [2019] De Feo, L., Galbraith, S.D.: Seasign: Compact isogeny signatures from class group actions. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 759–789 (2019). Springer
  * Beullens et al. [2019] Beullens, W., Kleinjung, T., Vercauteren, F.: Csi-fish: Efficient isogeny based signatures through class group computations. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 227–247 (2019). Springer
  * De Feo et al. [2020] De Feo, L., Kohel, D., Leroux, A., Petit, C., Wesolowski, B.: Sqisign: compact post-quantum signatures from quaternions and isogenies. In: Advances in Cryptology–ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part I 26, pp. 64–93 (2020). Springer
  * Peng et al. [2020] Peng, C., Chen, J., Zhou, L., Choo, K.-K.R., He, D.: Csiibs: A post-quantum identity-based signature scheme based on isogenies. Journal of Information Security and Applications 54, 102504 (2020)
  * Chung et al. [2021] Chung, K.-M., Hsieh, Y.-C., Huang, M.-Y., Huang, Y.-H., Lange, T., Yang, B.-Y.: Isogeny-based group signatures and accountable ring signatures in qrom. arXiv preprint arXiv:2110.04795 (2021)
  * Beullens et al. [2022] Beullens, W., Dobson, S., Katsumata, S., Lai, Y.-F., Pintore, F.: Group signatures and more from isogenies and lattices: Generic, simple, and efficient. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 95–126 (2022). Springer
  * Dey et al. [2022] Dey, K., Debnath, S.K., Stănică, P., Srivastava, V.: A post-quantum signcryption scheme using isogeny based cryptography. Journal of Information Security and Applications 69, 103280 (2022)
  * Shaw and Dutta [2023] Shaw, S., Dutta, R.: A quantum resistant multi-user signcryption scheme featuring key invisibility for internet of things. Journal of Information Security and Applications 76, 103549 (2023)
  * Silverman [2009] Silverman, J.H.: The Arithmetic of Elliptic Curves vol. 106. Springer, ??? (2009)