Post quantum proxy signature scheme based on the multivariate public key cryptographic signature

Abstract

Proxy signature is a very useful technique which allows the original signer to delegate the signing capability to a proxy signer to perform the signing operation. It finds wide applications especially in the distributed environment where the entities such as the wireless sensors are short of computational power and needed to be convinced to the authenticity of the server. Due to less proxy signature schemes in the post-quantum cryptography aspect, in this article, we investigate the proxy signature in the post-quantum setting so that it can resist against the potential attacks from the quantum adversaries. A general multivariate public key cryptographic proxy scheme based on a multivariate public key cryptographic signature scheme is proposed, and a heuristic security proof is given for our general construction. We show that the construction can reach Existential Unforgeability under an Adaptive Chosen Message Attack with Proxy Key Exposure assuming that the underlying signature is Existential Unforgeability under an Adaptive Chosen Message Attack. We then use our general scheme to construct practical proxy signature schemes for three well-known and promising multivariate public key cryptographic signature schemes. We implement our schemes and compare with several previous constructions to show our efficiency advantage, which further indicates the potential application prospect in the distributed network environment.

Introduction

The characteristic that some specified agents have the capability to proceed with the signing operations on behalf of the original signer turns out to be very attractive in case of the original signers temporal absence, short of computational power, and so on. It has already been shown in many previous researches that the proxy signature can be very helpful especially for application in the environments such as the wireless sensor networks, ¹ Internet of things, ² distributed shared object systems, ³ grid computing, ⁴ global distribution networks, ⁵ and so on. However, most of the previous constructions are based on the hardness of number theory such as the integer factorization and discrete logarithm. According to Shor’s algorithm, ⁶ Rivest–Shamir–Adleman (RSA) and some other algorithms based on the number theory will be broken in polynomial time after the emergence of quantum computers. And as a result, it will eventually lead to the break of most of the traditional cryptosystem.

To deal with the upcoming quantum computers, cryptographic researchers from different countries are beginning to devote themselves to explore the cryptosystems that can resist quantum computer attacks, that is, researching on the post-quantum cryptography. ⁷ Post-quantum cryptography can be divided into five categories: code-based cryptography, lattice-based cryptography, hash-based cryptography, multivariate public key cryptography (MPKC), and isogeny-based cryptography. The National Institute for Standards and Technology (NIST) has announced a formal call for proposals for post-quantum cryptography in fall 2016. ⁸ Thereafter, it formally provided the first round (round 1) submissions of post-quantum cryptographic standard protocols in December 2017.

The security of MPKC is based on solving a set of random quadratic multivariate equations on a finite field. So far, evidence does not reveal that quantum computers could solve this kind of questions effectively. Plus, MPKC schemes are in general much more effective than RSA in computing. But there are two drawbacks that become obstacles to use MPKCs. The first one is the large key sizes. The second drawback is that the security of MPKCs relies both on the multivariate quadratic (MQ) problem and on the Isomorphism of Polynomials (IP) problem, so the schemes in MPKCs are subjected to not only direct attacks but also structural attacks. This makes many MPKCs insecure, such as Matsumoto–Imai scheme, ⁹ balanced Oil, and Vinegar. ¹⁰ Under this situation, a number of attempts have been undertaken in order to tackle these two problems. For example, Courtois ¹¹ studied provable security against key-only attack on Quartz, but the security against the chosen-message attack is unclear. Beyond these techniques, the Unbalanced Oil and Vinegar (UOV) scheme ¹² is a well-known and deeply studied scheme in MPKC, Bulygin et al. ¹³ then presented an idea to reduce the public key size of the UOV signature scheme and provided provable security against direct attacks. Then, Sakumoto et al. ¹⁴ gave provable security of UOV against chosen-message attack, using the idea given in the study by Bellare and Rogaway, ¹⁵ which concatenates a random seed $r$ with the signing message $M$ so as to make the basic trapdoor one-way function of UOV become full domain hash (FDH). In Crypto2011, Sakumoto et al. ¹⁶ proposed provably secure identification/signature schemes based on the MQ problem, which is a great improvement for the security of MPKCs.

According to NIST Computer Security Resource Center (CSRC): Cryptographic Technology Group, ⁸ MPKC is popular for its efficient signature scheme in the post-quantum cryptography (PQC) aspect and signature schemes are promising. As shown in the submission, there are nine signature schemes, named double exponentiation with matrix exponent (DME), ⁸ DualModeMS, ¹⁷ GeMSS, ¹⁸ Gui, ¹⁹ Hi-MQ, lifted unbalanced oil and vinegar scheme (LUOV) ²⁰ (a variant of UOV), multivariate quadratic digital signature scheme (MQDSS), ²¹ Rainbow, ²² TPSig. ²³ Among them, only Rainbow is the old scheme, and others are all published in the recent 5 years and the best scheme is LUOV, which has a combined not more than 20 kB size. However, it is the newest one which need time to confirm its security. Another promising scheme is MQDSS, which is provable secure one and the key size is relatively small. However, its resultant signature is too large compared with the original small message. Also, the running time of two schemes is not fast which in fact is the most advantage of MPKC schemes compared with other PQC schemes. Other schemes such as Rainbow is good at the running time and the security consideration but suffers from large key size.

Also, multivariate signature schemes with special properties, such as proxy signature, ring signature, are proposed. For example, Tang and Xu ²⁴ proposed the first MPKC proxy signature scheme based on the problem of IP. Petzoldt et al. ²⁵ proposed the first provable MPKC threshold ring signature scheme based on the result of Sakumoto et al. ¹⁴ Chen et al. ²⁶ proposed the first online/offline signature based on UOV by utilizing the linear construction of the central map of UOV, so that the proposed scheme can be distributed in the wireless sensor networks. In addition, multivariate sequential aggregate signature scheme by Petzoldt et al. ²⁷ and multivariate blind signature scheme by El Bansarkhani et al. ²⁸ are proposed to enrich this area.

Since proxy signature scheme is widely used as a communication solution in distributed sensor networks, that is, the solution in healthcare wireless sensor networks in Verma et al. ²⁹ In this article, we focus on developing multivariate signature schemes with special properties and investigate how to build an MPKC proxy scheme and then we will use this idea to build a series of MPKC proxy schemes based on current promising MPKCs (UOV, Rainbow, MQDSS). A highlight of our work is the general proxy scheme is formally provable security under the assumption that the basing scheme is secure, so based on the promising MPKC signature shcemes, our practical resultant proxy schemes from the general construction are considered promising proxy MPKC schemes.

This article is structured as follows: First, we introduce how to build a general MPKC proxy scheme, specifically we give a formal proof for the general scheme assuming the underlying MPKC scheme is secure. Then we propose three practical proxy signature schemes: Proxy-UOV, Proxy-Rainbow, and Proxy-MQ. Next, we run some experiments to verify the security and efficiencies of our schemes. Finally, we draw a conclusion.

Preliminaries

In this section, we give the preliminaries of this article.

Proxy signature scheme

A proxy signature protocol allows an entity, called the original signer, to delegate another entity, called a proxy signer, to sign messages on behalf of itself, in case of temporal absence, lack of time or computational power, and so on. The first efficient proxy signature was introduced by Mambo et al. ³⁰ A proxy signature scheme consists of the following algorithms: Setup, KeyGen, Delegate, ProxyKeyGen, ProxySign, ProxyVerify, where the Setup and KeyGen correspond with an ordinary signature scheme $\underset{=}{\Pi }(\mathtt{Setup},\mathrm{KeyGen},\mathrm{Sign},\mathrm{Verify})$ . Assume $(p{k}_A,s{k}_A)$ and $(p{k}_B,s{k}_B)$ generated by KeyGen are the public/private key pairs of the original signer and the proxy signer, respectively. Delegate is a randomized algorithm for the delegation of signing right, that is, $\theta \leftarrow \mathtt{Delegate}(w,s{k}_A,p{k}_A)$ is run by the original signer. The input $w$ can be regarded as a warrant. In general, $w$ includes the original signer’s public key $p{k}_A$ , the proxy signer’s public key $p{k}_B$ , a delegated time period $t$ , and other information. ProxyKeyGen algorithm generates the proxy key $\mathrm{psk}$ for the proxy signer. For a message $m$ , the proxy signer can generate a proxy signature by ProxySign, that is, $\sigma \leftarrow \mathtt{ProxySign}(m,(w,\theta ),\mathrm{psk})$ . Anyone who receives the proxy signature can verify the validity of the signature by ProxyVerify. ProxyVerify outputs 1 if the signature is valid; otherwise, it outputs 0.

MPKC signature scheme

Usually, an MPKC scheme over a finite field $k$ is defined as

$$P=L_1°F°L_2$$

in which $F$ is a set of $m$ quadratic multivariate polynomials in $n$ variables, $L_1$ is an affine transformation from ${\mathbb{F}}_q^m$ to ${\mathbb{F}}_q^m$ , and $L_2$ is an affine transformation from ${\mathbb{F}}_q^n$ to ${\mathbb{F}}_q^n$ .

For an MPKC digital signature scheme, the setup algorithm Setup ( $1^{\lambda }$ ) takes $1^{\lambda }$ as input and then outputs the system parameter $\mathrm{param}$ which mainly contains $(q,n,m)$ , and all the arithmetic operations hereafter are over this finite field.

The key generation algorithm KeyGen( $\mathrm{param}$ ) takes $\mathrm{param}$ as input and then outputs $\mathrm{pk}=P$ and $\mathrm{sk}=(L_1,F,L_2)$ .

The signing algorithm Sign( $M,\mathrm{sk}$ ) is described in Algorithm 1.

Algorithm 1. Sign( $M,\mathrm{sk}$ ).
Input
$M$ : the message;
$\mathrm{sk}$ : $\mathrm{sk}=(L_1,F,L_2)$ , the private key;
Output
$\sigma$ : the signature on message $m$ ;
Begin
Step 1. The signer computes $M_1=L_1^{-1}(M)$ ;
Step 2. The signer computes $M_2=F^{-1}(M_1)$ ;
Step 3. The signer computes $\sigma =L_2^{-1}(M_2)$ ;
Step 4. Return $\sigma$ ;
End

Finally, the verification algorithm Verify( $\sigma$ , $M$ , $P$ ) returns 1 if $P(\sigma )=M$ , otherwise returns 0.

Security model for MPKC signature scheme

We quantify the security of MPKC signature scheme from the idea in Bellare and Rogaway. ¹⁵ A signature scheme is said to be $(ϵ,t,q_s)-\mathrm{secure}$ if an attacker, given the public key, allowed to run in time $t$ , and allowed a chosen-message attack in which he or she can get $q_s$ legitimate message–signature pairs, can be successful in forging the signature of a new message with probability at most $ϵ$ .

Definition 1

We say that the MPKC signature scheme is $(ϵ,t,q_s)-\mathrm{secure}$ if there is no forger $\mathcal{A}$ who takes a public key generated through $(\mathrm{pk},·)\leftarrow \mathrm{KeyGen}(1^{\lambda })$ , after at most $q_s$ signature queries, and $t$ processing time, then outputs a valid signature with probability at least $ϵ$ .

UOV and Rainbow

The UOV scheme is one of the earliest MPKC signature scheme. Even though its construction is very simple, it turns out to be one of the most secure MPKC scheme so far. However, Rainbow is one of the most popular schemes in MPKC schemes and rapid development in recent years. It could be regarded as an extension of UOV and has obvious advantages over efficiency and key size.

The central map $F$ of UOV is composed of a set of so-called Oil–Vinegar polynomials which have the following form

$$\sum _{i=1}^o\sum _{j=1}^v{a}_{\mathrm{ij}}{x}_{i}x{\prime }_j+\sum _{i=1}^v\sum _{j=1}^v{b}_{\mathrm{ij}}x{\prime }_{i}x{\prime }_j+\sum _{i=1}^o{c}_i{x}_i+\sum _{j=1}^v{d}_{j}x{\prime }_j+e$$ (1)

In this polynomial, there are two kinds of variables: Oil variables ( $x_i$ ) and Vinegar variables ( $x{\prime }_j$ ). Once we assign a set of random values for Vinegar variables, the central map becomes a set of linear polynomials and can be easily inverted. When $v>o$ , this scheme is called UOV scheme, the construction of a UOV scheme is as follows

$$P=F°T$$ (2)

where $T$ is an affine translation from ${\mathbb{F}}_q^n$ to ${\mathbb{F}}_q^n$ . The construction does not have to compose an invertible affine transformation on the left.

In the case of Rainbow, Rainbow is an extension of UOV scheme. It could be viewed as a multi-layer UOV scheme. Each layer is an independent UOV and each layer’s variables (including Oil variables and Vinegar variables) are Vinegar variables of the next layer. Specifically, let us assume a Rainbow has $l$ layers. We use $v_i$ to represent the number of Vinegar variables of the ith layer and $o_i$ to represent the number of Oil variables of the ith layer. Then we have $v_{i+1}=o_i+v_i$ and $v_{l+1}=n$ . Each layer’s Vinegar variables set and Oil variables set are represented as $\{x_1,...,x_{v_i}\},\{{x_{v_i}}_{+1},...,{x_{v_i}}_{+o_i}\}$ and the ith layer’s polynomials have the form of

$$\sum _{i=1}^{v_i}\sum _{j=v_i+1}^{v_i+o_i}{a}_{\mathrm{ij}}{x}_i{x}_j+\sum _{i=1}^{v_i}\sum _{j=1}^{v_i}{b}_{\mathrm{ij}}{x}_i{x}_j+\sum _{i=1}^{v_i+o_i}{c}_i{x}_i+d$$ (3)

We can see that the above polynomial has the basic Oil–Vinegar polynomial form. Finally, the construction of a Rainbow scheme is given as follows

$$P=L_1°F°L_2$$ (4)

The MQ-based signature scheme

At CRYPTO 2011 Sakumoto et al. ¹⁶ presented a new identification scheme whose security is solely based on the MQ problem. In the scheme, every user chooses a vector $\mathbf{s}\in {\mathbb{F}}_q^n$ as his secret key and computes his public key as $\mathbf{v}=F(\mathbf{s})\in {\mathbb{F}}_q^m$ . To identify himself to a verifier, he or she has to show that he or she indeed knows $\mathbf{s}$ (without revealing any information about $\mathbf{s}$ ). Thus, to create a zero-knowledge proof of the vector $\mathbf{s}$ , we need the polar form of the multivariate system $F$ , which is defined as

$$G(\mathbf{x},\mathbf{y})=F(\mathbf{x}+\mathbf{y})-F(\mathbf{x})-F(\mathbf{y})$$

Note that $G(\mathbf{x},\mathbf{y})$ is bilinear in $\mathbf{x}$ and $\mathbf{y}$ , the knowledge of $\mathbf{s}$ is equivalent to knowing a tuple $({\mathbf{r}}_0,{\mathbf{r}}_1,{\mathbf{t}}_0,{\mathbf{t}}_1,{\mathbf{e}}_0,{\mathbf{e}}_1)$ satisfying

$$G({\mathbf{t}}_0,{\mathbf{r}}_1)+{\mathbf{e}}_0=\mathbf{v}-F({\mathbf{r}}_1)-G({\mathbf{t}}_1,{\mathbf{r}}_1)-{\mathbf{e}}_1$$

and $({\mathbf{t}}_0,{\mathbf{e}}_1)=({\mathbf{r}}_0-{\mathbf{t}}_1,F({\mathbf{r}}_0)-{\mathbf{e}}_1)$ . The five-pass identification scheme between a prover and a verifier is as follows

1. The prover chooses randomly ${\mathbf{t}}_0,{\mathbf{r}}_0{\in }_R{\mathbb{F}}_q^n,{\mathbf{e}}_0{\in }_R{\mathbb{F}}_q^m$ , set ${\mathbf{r}}_1=\mathbf{s}-{\mathbf{r}}_0$ and computes commitments $c_0=\mathrm{Com}({\mathbf{r}}_0,{\mathbf{t}}_0,{\mathbf{e}}_0),c_1=\mathrm{Com}({\mathbf{r}}_1,G({\mathbf{t}}_0,{\mathbf{r}}_1)+{\mathbf{e}}_0)$ and then sends $(c_0,c_1)$ to the verifier.

2. The verifier chooses randomly a choice $\alpha {\in }_R{\mathbb{F}}_q$ and sends $\alpha$ to the prover.

3. After receive $\alpha$ , the prover computes ${\mathbf{t}}_1=\alpha {\mathbf{r}}_0-{\mathbf{t}}_0,{\mathbf{e}}_1=\alpha F({\mathbf{r}}_0)$ and then sends $({\mathbf{t}}_1,{\mathbf{e}}_1)$ to the verifier.

4. The verifier chooses randomly the challenge $\mathrm{Ch}{\in }_R\{0,1\}$ and sends $\mathrm{Ch}$ to the prover.

5. If $\mathrm{Ch}=0$ , the prover sends $\mathrm{Rsp}={\mathbf{r}}_0$ back; if $\mathrm{Ch}=1$ , the prover sends $\mathrm{Rsp}={\mathbf{r}}_1$ back.

6. If the verifier chooses 0 as the challenge $\mathrm{Ch}$ , he or she checks whether $c_0=\mathrm{Com}({\mathbf{r}}_0,\alpha {\mathbf{r}}_0-{\mathbf{t}}_0,\alpha F({\mathbf{r}}_0)-{\mathbf{e}}_1)$ hold. If the verifier chooses 1 as the challenge $\mathrm{Ch}$ , he or she checks whether $c_1=\mathrm{Com}({\mathbf{r}}_1,\alpha \mathbf{v}-F({\mathbf{r}}_1)-G({\mathbf{t}}_1,{\mathbf{r}}_1)-{\mathbf{e}}_1)$ holds.

This scheme has a cheating probability per round of 3/4 when $q=2$ . Therefore, one needs at least 133 rounds to reduce the impersonation probability to less than $2^{-80}$ . Sakumoto et al. ¹⁶ propose for their five-pass schemes that $q=2,n=80,m=80$ to achieve a security level of 80 bits.

Using the Fiat–Shamir paradigm, ³¹ anyone can transform the MQ identification scheme into a signature scheme, and a good example is the MQDSS ²¹ which is transformed from five-pass MQ identification scheme. Below we give a short description of the MQ signature scheme. For the full description of the MQ scheme, we recommend to read. ²¹ The setup and key generation process for the signature scheme work just the same as the identification scheme.

To generate a signature for a message $m$ , the signer gathers the commitments for all rounds, creates the commitments $c_0^{(1)},c_1^{(1)},...c_0^{(\mathrm{round})},c_1^{(\mathrm{round})}$ , and then uses a hash function $\mathcal{H}$ to produce the challenge vector $\mathrm{Ch}$ and compute the according responses $\mathrm{Rs}{p}^{(1)},...,\mathrm{Rs}{p}^{(\mathrm{round})}$ . Finally, the signature is $\sigma =(c_0^{(1)}||c_1^{(1)}||...c_0^{(\mathrm{round})}||c_1^{(\mathrm{round})})||\mathrm{Rs}{p}^{(1)}||...||\mathrm{Rs}{p}^{(\mathrm{round})}$ .

To verify the authenticity of a signature, the verifier parses $\sigma$ , computes the challenge vector $\mathrm{Ch}$ , and tests for each $i\in 1,...,\mathrm{round}$ if $\mathrm{Rs}{p}^i$ is a correct response to $C{h}_i$ according to $c_0^{(i)},c_1^{(i)}$ .

Security model for proxy signature

Schuldt et al. ³² presented the security notion Existential Unforgeability under an Adaptive Chosen Message Attack with Proxy Key Exposure (ps-uf-pke) for multilevel proxy signature scheme. Later, Tang and Xu ²⁴ modified this notion to single-level proxy signature scheme and adopted as the security model for a proxy signature. In the analysis of our proxy scheme, we also use this model, and we recommend to read more information about this model in Tang and Xu. ²⁴ We summarize the security model for a proxy signature in the following.

In our security model for proxy signature, the definition is the same as that in Tang and Xu. ²⁴ In the security model in Tang and Xu, ²⁴ it uses only one list $\mathrm{psklist}$ to store the proxy key which generated by $\mathcal{C}$ , but it does not use lists to store the original signature query and the proxy query, this is ambiguous for someone to calculate the number and kinds of query oracle. So, in our security model, we use three initialized empty lists: $\mathrm{OSList}$ , $\mathrm{delList}(w)$ , $\mathrm{pskList}(w)$ which are maintained by a challenger $\mathcal{C}$ . The $\mathrm{OSList}$ stores all the signatures which are queried by the original signature query, and the $\mathrm{delList}(w)$ stores the submitted warrants and the corresponding delegation. The $\mathrm{pskList}(w)$ stores all the proxy key which is generated by $\mathcal{C}$ from the warrants in the $\mathrm{delList}(w)$ . Using these three lists, we can follow the security proof more clearly. More precisely, by calculating the list $\mathrm{OSList}$ , we can know how many times of ordinary signature oracle have been queried, and from $\mathrm{delList}(w)$ , we can know the number of query of proxy signature oracle. The security model is based on the following game which is played between a challenger $\mathcal{C}$ and an adversary $\mathcal{A}$ :

• Setup. The challenger $\mathcal{C}$ runs Setup with input $1^k$ and generates $(p{k}^{*},s{k}^{*})$ for $u^{*}$ by running the KeyGen ( $1^k$ ) of an ordinary signature scheme. After that, $\mathcal{C}$ sends $p{k}^{*}$ to the adversary $\mathcal{A}$ and stores $s{k}^{*}$ .

• Queries. The adversary $\mathcal{A}$ can adaptively access to any of the following queries which are answered by $\mathcal{C}$ :

• Delegation to $u^{*}$ . $\mathcal{A}$ transmits $w$ to $\mathcal{C}$ , $\mathcal{C}$ interacts with $\mathcal{A}$ through the Delegate and the ProxyKeyGen with $(p{k}^{*},s{k}^{*})$ . After the process finished, $\mathcal{C}$ will obtain a delegation of signing right with $\theta \leftarrow \mathrm{Delegate}(w,s{k}^{*},p{k}^{*})$ and a proxy key $s{k}_p$ . Then, $\mathcal{C}$ adds $(w,\theta )$ and $(w,s{k}_p)$ to the $\mathrm{delList}(w)$ list and the $\mathrm{pskList}(w)$ list, respectively.

• Delegation from $u^{*}$ .

• Self-delegation: $\mathcal{C}$ interacts with itself through Delegate and ProxyKeyGen on input $w$ . $\mathcal{C}$ generates a delegation of signing right $\theta$ and a proxy key $s{k}_p$ , adds $(w,\theta )$ and $(w,s{k}_p)$ to the $\mathrm{delList}(w)$ list and the $\mathrm{pskList}(w)\mathrm{list}$ , respectively. Then $\mathcal{C}$ sends $\theta$ to $\mathcal{A}$ .

• Proxy key exposure. $\mathcal{A}$ transmits w to $\mathcal{C}$ , $\mathcal{C}$ returns the proxy key $s{k}_p$ to $\mathcal{A}$ if such a key exists in $\mathrm{pskList}(w)$ . Otherwise, returns ⊥ to $\mathcal{A}$ .

Forgery. The successful forgery of $\mathcal{A}$ can be one of the following forms:

Forge an ordinary signature of $u^{*}$ . $\mathcal{A}$ outputs $(m,\sigma )$ which can be verified by Verify and $m$ has not been submitted in an ordinary signature query.

Forge a proxy signature of $u^{*}$ . $\mathcal{A}$ outputs $(m,(w,\theta ),\sigma )$ where the $\sigma$ corresponds to the public key $p{k}^{*}$ . This forgery is said to be valid if it can be verified by ProxyVerify with $(m,(w,\theta ))$ has not been queried and $w$ has not been queried.

Self-proxy signature on behalf of $u^{*}$ . $\mathcal{A}$ outputs $(m,(w,\theta ),\sigma )$ where $\sigma$ corresponds to the public key $p{k}_p$ . This forgery is said to be valid if it can be verified by ProxyVerify with $w$ has not been queried.

If one of the above cases happens, the game returns 1. Otherwise, it returns 0.

Definition 2

An adversary $\mathcal{A}$ is said to be a $({ϵ}^{\prime },t^{\prime },{q^{\prime }}_d,{q^{\prime }}_s)$ -forger of a proxy signature scheme if $\mathcal{A}$ has advantage at least $ϵ\prime$ in the above game, runs in time at most $t$ , and makes at most $q{\prime }_d$ and $q{\prime }_s$ delegation and signing queries to the challenger. A proxy signature scheme is said to be $(ϵ\prime ,t\prime ,q{\prime }_d,q{\prime }_s)$ -secure if no $(ϵ\prime ,t\prime ,q{\prime }_d,q{\prime }_s)$ -forger exists.

The general construction of MPKC proxy signature scheme

General proxy signature scheme

Assume we have an above MPKC signature scheme, we now describe our general proxy signature scheme as follows.

Setup: Let $n$ and $m$ be two positive integers, ${\mathbb{F}}_q$ is a finite field and all the arithmetic operations hereafter are over this finite field. $\mathcal{H}:\{0,1{\}}^{*}\to {\mathbb{F}}_q^n$ is a cryptographic hash function.

KeyGen: This algorithm generates the public key and the private key of a user. The detail process is the same as that of the key generation of an MPKC signature scheme. After this algorithm, we set the private key of user $A$ is $s{k}_A=(L_{1A},L_{2A},F_A)$ , and the public key $p{k}_A=P_A$ , where $P_A=L_{1A}°F_A°L_{2A}$ . Similarly, the private key and public key of user $B$ are $s{k}_B=(L_{1B},L_{2B},F_B)$ and $p{k}_B=P_B$ , respectively.

Delegate: On input a warrant $w$ where $w=(p{k}_A,p{k}_B,t)$ , this algorithm is performed by user $A$ and generates a delegation of signing right to user $B$ .

1. Randomly choose two invertible affine transformations $L{\prime }_1$ and $L{\prime }_2$ , which in the forms of $L_{1A}$ and $L_{2A}$ , respectively. Then, compute $L_1=L{\prime }_1°L_{1A}^{-1}$ , $L_2=L_{2A}^{-1}°L{\prime }_2$ , and

   $$P_A\prime =L_1°P_A°L_2$$ (5)

2. Compute $\theta =\mathtt{Sign}(\mathcal{H}(w||P_A\prime ),s{k}_A)$ .

3. Send $(L_1,L_2,P_A\prime )$ and the warrant $(w,\theta )$ to user $B$ through an authenticated channel.

ProxyKeyGen: This algorithm generates a proxy key for the proxy signer with input $(L_1,L_2,P_A\prime ,w,\theta )$ . It is performed by user $B$ as follows:

1. Verify the validity of $P_A\prime$ and $\theta$ . If they are true, goto the next step. Otherwise, output 0.

2. Select two random invertible affine transformations ${L″}_1$ and ${L″}_2$ , respectively, compute

$$L_{1p}=L_1°L_{1B}^{-1}°{{L″}_1}^{-1}$$ (6)

$$L_{2p}={{L″}_2}^{-1}°L_{2B}^{-1}°L_2$$ (7)

and

$$F_p={L″}_1°L_{1B}°P_A°L_{2B}°{L″}_2$$ (8)

• 3. Compute a signature on $(w,\theta ,F_p)$ through running Sign with $s{k}_B$ , that is, ${\sigma }_{\mathrm{prx}}=\mathtt{Sign}(\mathcal{H}(w||\theta ||P{\prime }_A),s{k}_B)$ .

• 4. Output $s{k}_p=(L_{1p},L_{2p},F_p)$ as a proxy key of user $B$ which uses to generate proxy signatures on behalf of user $A$ , and the corresponding public key is $p{k}_p=P{\prime }_A$ .

Remark 1

Note that since $F_p={L″}_1°L_{1B}°P_A°L_{2B}°{L″}_2$ , to invert $F_p$ , we do not need the secret key $F_A$ of user A, but the public key $P_A$ of user $A$ , what we need to choose is the linear transformations such that the map $F_p$ can still be easily inverted. This is the key point in the construction; otherwise, the construction cannot work. In some cases of MPKCs, the linear transformations are totally random, such as our proxy signature for MQ-based signature shown in section “Proxy-MQ: our MQ-based proxy signature scheme,” and the proxy signature in Tang and Xu. ²⁴ In some cases of MPKCs, we need to choose some special linear transformations, for example, in section “Practical implementations for these two schemes,” we will show how to choose the linear transformations in the practical implementation of our proposed proxy schemes for UOV and Rainbow.

ProxySign: Suppose $M$ is the message to be signed. This algorithm generates a proxy signature on the message $M$ by user $B$ .

User $B$ applies $L_{1p}$ , $L_{2p}$ , and the central map $F_p$ to the basic MPKC signature algorithm described in Algorithm 1 to generate the signature $\sigma$ on $M$

$$\sigma =\mathtt{Sign}(\mathcal{H}(M),s{k}_p)$$ (9)

Then the proxy signature on message $M$ by user $B$ is $(\sigma ,(w,\theta ,P_A\prime ,{\sigma }_{\mathrm{prx}}))$ .

ProxyVerify: On input $(M,\sigma ,(w,\theta ,P{\prime }_A,{\sigma }_{\mathrm{prx}}))$ , anyone can verify the validity of the proxy signature by executing this algorithm. This algorithm includes the following steps:

1. Check the validity of $\theta$ on $w$ by running Verify with $p{k}_A$ : $\mathtt{Verify}((w,P{\prime }_A),\theta ,p{k}_A){=}^{?}\mathrm{true}$ . If it is ture, goto the next step. Otherwise, output 0.

2. Check the validity of ${\sigma }_{\mathrm{prx}}$ on $(w,\theta ,P{\prime }_A)$ by running Verify with $p{k}_B$ : $\mathtt{Verify}((w,\theta ,P{\prime }_A),{\sigma }_{\mathrm{prx}},p{k}_B){=}^{?}\mathrm{true}$ . If it is true, goto the next step. Otherwise, output 0.

3. Check the validity of $\sigma$ on message $M$ by running Verify with $P{\prime }_A$ : $\mathtt{Verify}(M,\sigma ,P{\prime }_A){=}^{?}\mathrm{true}$ . If it is true, output 1. Otherwise, output 0.

The verifier accepts the proxy signature if and only if the three conditions of ProxySign are all true. Otherwise, the verifier rejects the proxy signature.

Security analysis of the general proxy signature scheme

Theorem 1

If the basic MPKC signature scheme is $(ϵ,t,q_s)$ secure, then the general proxy signature scheme is $(ϵ\prime ,t\prime ,q{\prime }_d,q{\prime }_s)$ secure, where $ϵ\ge \epsilon \prime /2q{\prime }_d$ , $t=t\prime$ and $q_s=q{\prime }_s+q{\prime }_d$ .

Proof

Let $\mathcal{A}$ be an adversary who can $(ϵ\prime ,t\prime ,q{\prime }_d,q{\prime }_s)$ break our proxy signature scheme, then there exists an attacker $\mathcal{C}$ who can $(ϵ,t,q_s)$ break the corresponding MPKC signature scheme using $\mathcal{A}$ . Assume that $\mathcal{C}$ receives a random public key $\mathrm{pk}\prime =P\prime$ of MPKC signature scheme and has the right to access to an MPKC signing oracle $\mathrm{Oracl}{e}_{\mathrm{sig}}(m,\mathrm{sk})$ . Before beginning the security game, the attacker $\mathcal{C}$ flips a uniform coin $c$ . The result of $c$ is hidden from $\mathcal{A}$ , unless the security game aborts. If $c=0$ , $\mathcal{C}$ sets $p{k}^{*}=\mathrm{pk}\prime$ , and $s{k}^{*}=Ø$ , where Ø means empty set. Otherwise, $\mathcal{C}$ generates a fresh key pair $(p{k}^{*},s{k}^{*})\leftarrow \mathtt{KeyGen}$ where $p{k}^{*}=(P^{*})$ , and chooses $i^{*}\in \{1,2,\dots ,q{\prime }_d\}$ .

As the challenger in the security game, $\mathcal{C}$ will maintain three lists $\mathrm{OSList}$ , $\mathrm{delList}(w)$ , $\mathrm{pskList}(w)$ . Here, the $\mathrm{delList}$ list stores the intermediate result which will be considered in the following. Furthermore, $\mathcal{A}$ is allowed to make $q{\prime }_s$ ordinary signature queries and $q{\prime }_d$ delegation queries which $\mathcal{C}$ will answer in the security game as follows:

• Ordinary signature. On input $m$ from $\mathcal{A}$ , if $c=0$ , $\mathcal{C}$ simply makes query to the MPKC signing oracle and obtains an answer $\sigma$ ; if $c=1$ , $\beta$ generates a signature $\sigma$ by running $\mathtt{Sign}(m,s{k}^{*})$ . $\mathcal{C}$ adds $(m,\sigma )$ to the $\mathrm{OSList}$ list and sends $\sigma$ to $\mathcal{A}$ .

• Delegation to $u^{*}$ . $\mathcal{A}$ transmits a delegation message $(w,\theta ,L_{1d}^{\prime },L_{2d}^{\prime },P{\prime }_d)$ where $w=(p{k}_d,p{k}^{*},t)$ . $\mathcal{C}$ verifies whether both $P{\prime }_d=L_{1d}^{\prime }°P_d°L_{2d}^{\prime }$ and $\theta =\mathtt{Sign}(\mathcal{H}(w||P{\prime }_d),s{k}_d)$ are correct. If $c=0$ , $\mathcal{C}$ chooses randomly two invertible affine transformations $L{\prime }_1$ and $L{\prime }_2$ , and computes $L_{1p}=L{\prime }_{1d}°L_1{\prime }^{-1}$ , $L_{2p}=L{{\prime }_2}^{-1}°L{\prime }_{2d}$ , and $F_{p{u}^{*}}=L{\prime }_1{P}_d°L{\prime }_2$ . Let $p{k}_p=P{\prime }_d$ and $s{k}_p=(L_{1p},L_{2p},F_{p{u}^{*}})$ . makes a query to the MPKC signing oracle for $(w,\theta ,P{\prime }_d,p{k}_p)$ and obtains a signature ${\sigma }_{\mathrm{prx}}$ . In this case, ${\sigma }_{\mathrm{prx}}$ would be added to the $\mathrm{OSList}$ list. If $c=1$ and this is not the $i^{*}\mathrm{th}$ query, $\mathcal{C}$ similarly chooses randomly two invertible affine transformations $L_1$ and $L_2$ , and computes $L_{1p}=L{\prime }_{1d}°L_1^{-1}$ , $L_{2p}=L_2^{-1}°L{\prime }_{2d}$ , and $F_{p{u}^{*}}=L_1°P_d°L_2$ . Let $p{k}_p=P{\prime }_d$ and $s{k}_p=(L_{1p},L_{2p},F_{p{u}^{*}})$ . Then $\mathcal{C}$ runs ${\sigma }_{\mathrm{prx}}=\mathtt{Sign}(\mathcal{H}(w||\theta ||p{k}_p),s{k}^{*})$ . If $c=1$ and this is the $i^{*}\mathrm{th}$ query, $\mathcal{C}$ directly lets $p{k}_p=\mathrm{pk}\prime$ , $s{k}_p=\varphi$ and runs ${\sigma }_{\mathrm{prx}}=\mathtt{Sign}(\mathcal{H}(w||\theta ||p{k}_p),s{k}^{*})$ . Finally, $\mathcal{C}$ stores $(w,\theta ,P{\prime }_d)$ and $(w,s{k}_p)$ to the $\mathrm{delList}(w)$ and $\mathrm{pskList}(w)$ , respectively.

• Delegation from $u^{*}$ .

• Self-delegation. $\mathcal{C}$ interacts with itself with $w=(p{k}^{*},p{k}^{*},t)$ which submitted by $\mathcal{A}$ . If $c=0$ or $c=1$ and this is not the $i^{*}\mathrm{th}$ query, $\mathcal{C}$ chooses randomly two invertible affine transformations $(L_{1p},L_{2p})$ , computes $P^{*\prime }=L_{1p}°P^{*}°L_{2p}$ , makes a query to the MPKC signing oracle, and obtains a signature $\theta$ on $w||P^{*\prime }$ with $P^{*}$ . Then, $\mathcal{C}$ also makes a query to the MPKC signing oracle for $(w,\theta ,P^{*\prime })$ and obtains a signature ${\sigma }_{\mathrm{prx}}$ . If $c=1$ and this is the $i^{*}\mathrm{th}$ query, $\mathcal{C}$ directly lets $p{k}_p=\mathrm{pk}\prime$ and computes ${\sigma }_{\mathrm{prx}}=\mathtt{Sign}(\mathcal{H}(w||\theta ||p{k}_p),s{k}^{*})$ . Finally, $\mathcal{C}$ adds $(w,\theta ,p{k}_p)$ to the $\mathrm{delList}(w)$ and $(w,s{k}_p)$ to the $\mathrm{pskList}(w)$ . If the $\theta$ is obtained by the MPKC signing oracle, $\mathcal{C}$ also adds it to the $\mathrm{OSList}$ list.

Proxy signature. Once receiving $(m,(w,\theta ))$ submitted by $\mathcal{A}$ , $\mathcal{C}$ finds the relevant information with $w$ from $\mathrm{delList}(w)$ and $\mathrm{pskList}(w)$ . $\mathcal{C}$ parses $p{k}_p$ and the proxy key as $s{k}_p$ . Then, $\mathcal{C}$ makes a query to the MPKC signing oracle for $m$ and obtains a signature $\sigma$ if $c=0$ . Otherwise, $\mathcal{C}$ computes $\sigma \leftarrow \mathtt{Sign}(\mathcal{H}(m),s{k}_p)$ . Then $\mathcal{C}$ sends $(m,\sigma ,(w,\theta ,p{k}_p,{\sigma }_{\mathrm{prx}}))$ to $\mathcal{A}$ .

Proxy key exposure. On input $w$ from $\mathcal{A}$ , $\mathcal{C}$ finds relevant information from $\mathrm{delList}(w)$ and $\mathrm{pskList}(w)$ and parses it as $(s{k}_p,(w,\theta ,p{k}_p,{\sigma }_{\mathrm{prx}})$ . If $s{k}_p=\varphi$ , $\mathcal{C}$ aborts the game. Otherwise, $\mathcal{C}$ returns $(s{k}_p,(w,\theta ,p{k}_p,{\sigma }_{\mathrm{prx}}))$ to $\mathcal{A}$ .

If the above game is not forced to abort by $\mathcal{C}$ , $\mathcal{A}$ will eventually output a forgery. The forgeries are classified into two different cases:

• Case 1: $\mathcal{A}$ forges (1) a valid MPKC signature $(m,\sigma )$ or (2) a valid proxy signature $(m,(w,\theta ,p{k}_p,{\sigma }_{\mathrm{prx}}),\sigma )$ which the corresponding public key $p{k}_p$ was not generated by $\mathcal{C}$ , or (3) a valid proxy signature $(m,(w,\theta ,p{k}_p,{\sigma }_{\mathrm{prx}}),\sigma )$ where $w$ was not submitted to the ordinary signature query.

• Case 2: $\mathcal{A}$ forges a valid signature which is not in case 1.

In the case $c=0$ , $\mathcal{C}$ sets $p{k}^{*}=\mathrm{pk}\prime$ . If $\mathcal{A}$ constructs a valid forgery in case 2, $\mathcal{C}$ will abort the game. Otherwise, if $\mathcal{A}$ constructs a valid forgery in case 1, then

• If the forgery is of type 1, that is, $(m,\sigma )$ , it shows that $\mathcal{A}$ has not requested a signature on $m$ . Then, $\mathcal{C}$ will not have submitted $m$ to an MPKC signature oracle. That is, $\sigma$ is a valid forgery of an MPKC signature under the public key $\mathrm{pk}\prime$ .

• If the forgery is of type 2, that is, $(m,(w,\theta ,p{k}_p,{\sigma }_{\mathrm{prx}}),\sigma )$ is a valid signature for $(w,\theta ,p{k}_p)$ under the public key $p{k}_p=p{k}^{\prime }$ , then $\mathcal{C}$ will not have submitted $(w,\theta ,p{k}_p)$ to MPKC signing oracle. Therefore, ${\sigma }_{\mathrm{prx}}$ will be a valid MPKC signature forgery under the public key $\mathrm{pk}\prime$ .

• If the forgery is of type 3, that is, $(m,(w,\theta ,p{k}_p,{\sigma }_{\mathrm{prx}}),\sigma )$ derives that $\theta$ is a valid forgery for $w$ , and $\mathcal{C}$ will therefore not have submitted $w$ to the signing oracle. Hence $\theta$ is a valid forgery of an MPKC signature under the public key $\mathrm{pk}\prime$ .

Now, let us consider the case $c=1$ where $\mathcal{C}$ inserts $\mathrm{pk}\prime$ as a proxy public key. In this case, if the forgery is in case 1, then $\mathcal{C}$ will abort the game. However, if the forgery is in case 2 which forgery $(m,(w,\theta ,p{k}_p,{\sigma }_{\mathrm{prx}}),\sigma )$ where $p{k}_p=\mathrm{pk}\prime$ , then $\mathcal{C}$ outputs $(m,\sigma )$ as a valid forgery for signature scheme. Otherwise, $\mathcal{C}$ aborts. Note that if $\mathcal{A}$ constructs such a forgery, then $\mathcal{A}$ will not have queried the proxy key $(w,\theta ,p{k}_p,{\sigma }_{\mathrm{prx}})$ with $p{k}_p$ .

We define the following events associated with the above security game: $E_1$ be the event that $\mathcal{A}$ constructs a forgery in case 1, $E_2$ be the event that $\mathcal{A}$ . constructs a forgery in case 2, and $E_3$ denotes that $\mathcal{A}$ guesses the correct value of $i^{*}$ in a forgery for case 2. The success probability of $\mathcal{A}$ is $\mathrm{Pr}[E_1]+\mathrm{Pr}[E_2]$ . Then the success probability of $\mathcal{C}$ can be

$$\begin{array}{c}\multicolumn{1}{c}{ϵ=\mathrm{Pr}[c=0\wedge E_1]+\mathrm{Pr}[c=1\wedge E_2\wedge E_3]}\\ \multicolumn{1}{c}{=1/2·\mathrm{Pr}[E_1]+\mathrm{Pr}[E_3|c=1\wedge E_2]·}\\ \multicolumn{1}{c}{\mathrm{Pr}[c=1|E_2]·\mathrm{Pr}[E_2]}\\ \multicolumn{1}{c}{=1/2·\mathrm{Pr}[E_1]+1/q{\prime }_d·1/2·\mathrm{Pr}[E_2]}\\ \multicolumn{1}{c}{\ge \frac{\epsilon \prime }{2{q_d}^{\prime }}.}\end{array}$$

Remark 2

Note that the above proof is only a heuristic security proof, since the underlying signature schemes in the area of MPKC are mostly not provable secure, more discussion will be done next, and we propose the additional analysis in section “Practical implementations for these two schemes” for our practical implementation.

Furthermore, we can obtain that anyone can determine the proxy signer by the verification of the warrant $w$ and the signature ${\sigma }_{\mathrm{prx}}$ . Then, the proxy signer is required to sign $\theta$ and the public key of the proxy signature. Under the assumption that the underlying signature scheme is secure, we can conclude that any proxy signer cannot deny the proxy signature he or she created due to the existence of ${\sigma }_{\mathrm{prx}}$ . At the same time, the private key of the original signer is only directly used to sign the warrant $w$ . And no one can obtain the private key of the original signer from the proxy key because of the selected random transformations in Delegate. The above discussions show that our scheme meets all the security properties of a proxy signature scheme.

The proposed MPKC proxy signature schemes

In this section, we will propose three proxy schemes based on three well-known MPKC schemes: UOV, ¹² Rainbow ²² and MQ-based scheme. ¹⁶

Proxy-UOV: proxy scheme based on UOV

Now we describe the process of our proxy scheme based on UOV using our general construction.

• Setup: Let $n$ and $m$ be two positive integers, $k$ is a finite field and all the arithmetic operations hereafter are over this finite field. $\mathcal{H}:\{0,1{\}}^{*}\to k^n$ is a cryptographic hash function.

• KeyGen: This algorithm generates the public key and the private key of a user. The detail process is the same as that of the key generation of an MPKC signature scheme. After this algorithm, we set the private key of user A is $s{k}_A=(F_A,T_A)$ , and the public key $p{k}_A=P_A$ , where $P_A=F_A°T_A$ . Similarly, the private key and public key of user $B$ are: $s{k}_B=(F_B,T_B)$ , $p{k}_B=P_B$ , respectively.

• Delegate: $A$ randomly chooses a bijective affine transformation $T$ , then computes $T_A\prime =T°T_A$ , $F_A\prime =F_A°T$ and $P_A\prime =F_A\prime °T_A\prime$ .

The affine $T$ should be kept secret by $A$ . $A$ sends $(T_A\prime ,F_A\prime ,P_A\prime )$ and the warrant $(w,\theta )$ to $B$ through an authenticated channel, where $w=(p{k}_A,p{k}_B,t)$ , $t$ is a time period which denotes that $w$ is valid in time $t$ and $\theta$ is a signature on $w$ generated by $A$ using our proposed signing algorithm, that is, $\theta =\mathtt{Sign}(\mathcal{H}(w),s{k}_A)$ .

• ProxyKeyGen: After receiving $(T_A\prime ,F_A\prime ,P_A\prime ,w,\theta )$ , $B$ first checks the validity of $P_A\prime ,\theta$ by checking if $P_A\prime =F_A\prime °T{\prime }_A$ and $\mathtt{Verify}(w,\theta ,p{k}_A)=1$ . Then $B$ selects a random bijective affine transformation $T\prime$ and computes $T_p=T{\prime }^{-1}°T_A\prime$ , and $F_p=F{\prime }_A°T\prime$ . Let $s{k}_p=(F_p,T_p)$ , and $p{k}_p=P_A\prime$ . Then $s{k}_p$ is a private key for ordinary signature, and the corresponding public key is $p{k}_p$ , that is because the following equality holds

$$\begin{array}{c}\multicolumn{1}{c}{F_p°T_p=F{\prime }_A°T\prime °T{\prime }^{-1}°T°T_A}\\ \multicolumn{1}{c}{=F{\prime }_A°T°T_A=F_A\prime °T_A\prime =P_A\prime }\end{array}$$ (10)

Then $B$ computes a signature ${\sigma }_{\mathrm{prx}}$ by running

$${\sigma }_{\mathrm{prx}}=\mathtt{Sign}((\mathcal{H}(w,\theta ,P{\prime }_A),s{k}_B)$$ (11)

and sets $s{k}_p$ as the proxy signing key that $B$ uses to generate proxy signatures on behalf of $A$ and sets $p{k}_p$ and $(w,\theta ,P{\prime }_A,{\sigma }_{\mathrm{prx}})$ as the proxy verifying key.

• ProxySign: Suppose $M$ is the message to be signed. This algorithm generates a proxy signature on the message $M$ by user $B$ .

User $B$ applies $T_p$ and the central map $F_p$ to the basic MPKC signature algorithm described in Algorithm 1 to generate the signature $\sigma$ on $M$

$$\sigma =\mathtt{Sign}(\mathcal{H}(M),s{k}_p)$$ (12)

Then the proxy signature on message $M$ by user $B$ is $(\sigma ,(w,\theta ,P_{A^{\prime }},{\sigma }_{prx}))$ .

• ProxyVerify: On input $(M,\sigma ,(w,\theta ,P{\prime }_A,{\sigma }_{\mathrm{prx}}))$ , anyone can verify the validity of the proxy signature by executing this algorithm. This algorithm includes the following steps:

• Check the validity of ${\sigma }_{\mathrm{prx}}$ on $(w,\theta ,P{\prime }_A)$ by running Verify with $p{k}_B$ : $\mathtt{Verify}((w,\theta ,P{\prime }_A),{\sigma }_{\mathrm{prx}},p{k}_B){=}^{?}\mathrm{true}$ . If it is true, go to the next step. Otherwise, output 0.

• Check the validity of $\sigma$ on message $M$ by running Verify with $P{\prime }_A$ : $\mathtt{Verify}(M,\sigma ,P{\prime }_A){=}^{?}\mathrm{true}$ . If it is true, output 1. Otherwise, output 0.

The verifier accepts the proxy signature if and only if the three conditions of ProxySign are all true. Otherwise, the verifier rejects the proxy signature.

Proxy-Rainbow: proxy scheme based on Rainbow

Since the main difference of this proxy signature schemes lies on the Delegate step and ProxyKeyGen process compared to the general construction, we just only describe the processes Delegate step and ProxyKeyGen.

• Setup: Let $n$ and $m$ be two positive integers, $k$ is a finite field, and all the arithmetic operations hereafter are over this finite field. $\mathcal{H}:\{0,1{\}}^{*}\to k^n$ is a cryptographic hash function.

• KeyGen: This algorithm generates the public key and the private key of a user. The detail process is the same as that of the key generation of an MPKC signature scheme. After this algorithm, we set the private key of user $A$ is $s{k}_A=(L_{1A},L_{2A},F_A)$ , and the public key $p{k}_A=P_A$ , where $P_A=L_{1A}°F_A°L_{2A}$ . Similarly, the private key and public key of user $B$ are $s{k}_B=(L_{1B},L_{2B},F_B)$ and $p{k}_B=P_B$ , respectively.

• Delegate: $A$ randomly chooses two invertible affine transformations $L{\prime }_1$ and $L{\prime }_2$ respectively, then computes $L_1=L_{1A}°L{\prime }_1$ , $L_2=L{\prime }_2°L_{2A}$ and $F{\prime }_A=L{\prime }_1°F_A°L_2\prime$ . $P_A\prime =L_1°F_A\prime °L_2$ . The affine $L{\prime }_1$ and $L{\prime }_2$ should be kept secret by $A$ . $A$ sends $(L_1,L_2,F{\prime }_A,P_A\prime )$ and the warrant $(w,\theta )$ to $B$ through an authenticated channel, where $w=(p{k}_A,p{k}_B,t)$ , $t$ is a time period which denotes that $w$ is valid in time $t$ and θ is a signature on $w$ generated by $A$ using Rainbow signing algorithm, that is, $\theta =\mathtt{Sign}(w,s{k}_A)$ .

• ProxyKeyGen: After receiving $(L_1,L_2,F{\prime }_A,P_A\prime ,w,\theta )$ , $B$ randomly chooses two invertible affine transformations ${L″}_1$ and ${L″}_2$ , respectively, and computes $L_{1p}=L_1°L\prime {{\prime }_1}^{-1}$ , $L_{2p}={{L″}_2}^{-1}°L_2$ , and $F_p={L″}_1°P_A°{L″}_2$ . Let $s{k}_p=(L_{1p},F_p,L_{2p})$ , and $p{k}_p=P_A\prime$ . Then $s{k}_p$ is a private key for ordinary signature, and the corresponding public key is $p{k}_p$ , that is, because the following equality holds

$$\begin{array}{c}\multicolumn{1}{c}{L_{1p}°F_p°L_{2p}=L_1°{{L″}_1}^{-1}°{L″}_1°P_A°{L″}_2}\\ \multicolumn{1}{c}{°{{L″}_2}^{-1}°L_2=L_1°F{\prime }_A°L_2=P_A\prime }\end{array}$$ (13)

Then $B$ computes a signature ${\sigma }_{\mathrm{prx}}$ by running

$${\sigma }_{\mathrm{prx}}=\mathtt{Sign}((w,\theta ,p{k}_p),s{k}_B)$$ (14)

and sets $s{k}_p$ as the proxy signing key that $B$ uses to generate proxy signatures on behalf of $A$ , and sets $p{k}_p$ and $(w,\theta ,\mathrm{pkp},{\sigma }_{\mathrm{prx}})$ as the proxy verifying key.

Practical implementations for these two schemes

In Petzoldt et al., ³³ the result indicates that $q=2^8,m=26,v=52$ has security level higher than $2^{80}$ for UOV scheme, where $q$ is the order of the finite field, $m$ is the number of polynomials and is equal to the number of Oil variate, and $v$ is the number of Vinegar variate. We will choose this parameter set.

Next, also the extremely important setting of our construction, we should choose appropriate affine transformations that could preserve the special structure of UOV scheme. Specifically, after composing an affine transformation, the polynomials in the new central map, the public key should still stay in the form of Oil–Vinegar polynomials. If we represent a UOV scheme’s central polynomial by its corresponding matrix, then the matrices of the polynomials in central map should be in the form of following.

Next, also the extremely important setting of our construction, we should choose appropriate affine transformations that could preserve the special structure of UOV scheme. Specifically, after composing an affine transformation, the polynomials in the new central map, the public key should still stay in the form of Oil–Vinegar polynomials. If we represent a UOV scheme’s central polynomial by its corresponding matrix, the Vinegar variables are denoted by its first $v=52$ variables. Then the matrices of the polynomials in central map should be in the form of Figure 1. In Figure 1, the gray areas represent the random entries while blank areas denote zero entries. The rest part of this article follows the same rules. Thereby, our problem is transformed to choose an affine transformation that could keep the shape of the above matrix of central equation. To achieve that goal, we could pick the invertible affine transformations of the form as shown in Figure 2.

Figure 1.

Oil–Vinegar scheme corresponding matrix.

Figure 2.

The affine transformation form for Proxy-UOV.

Once $T$ and $T\prime$ are choosing in this form, we will get that $F_p=F_A°T°T\prime$ , which means that the matrices form of central map $F_p$ is

$$\begin{array}{c}\multicolumn{1}{c}{F_p=\left[\begin{array}{cc}{*}_{v\times v}\hfill & {*}_{v\times o}\hfill \\ \multicolumn{1}{c}{{*}_{o\times v}}& 0_{o\times o}\hfill \end{array}\right]\left[\begin{array}{cc}{*}_{v\times v}\hfill & 0_{v\times o}\hfill \\ \multicolumn{1}{c}{{*}_{o\times v}}& {*}_{o\times o}\hfill \end{array}\right]\left[\begin{array}{cc}{*}_{v\times v}\hfill & {*}_{0\times o}\hfill \\ \multicolumn{1}{c}{{*}_{o\times v}}& {*}_{o\times o}\hfill \end{array}\right]}\\ \multicolumn{1}{c}{=\left[\begin{array}{cc}{*}_{v\times v}\hfill & {*}_{v\times o}\hfill \\ \multicolumn{1}{c}{{*}_{o\times v}}& 0_{o\times o}\hfill \end{array}\right]}\end{array}$$

Thus, this will make sure that the map $F_p$ can still be easily inverted.

Currently, the Rainbow prevails now is two-layer based and layer structure (18,12,12) and $\mathrm{GF}(2^8)$ is enough to resist all the attacks mentioned above (security level is greater than $2^{80}$ ). ³⁴ Thereby, we plan to use this parameter set of Rainbow for our Proxy-Rainbow scheme. The Rainbow’s corresponding matrices have the following forms in Figure 3.

Figure 3.

Rainbow scheme corresponding matrix.

Moreover, to keep the multi-layer structure of central equation, the structure of the left affine transformation $L_1$ and $L{\prime }_1$ should have the shapes as shown below. By choosing these structures, we can make sure that the map $F_p$ of Proxy-Rainbow can still be easily inverted (Figures 4 and 5).

Figure 4.

The left affine transformation form for Proxy-Rainbow.

Figure 5.

The right affine transformation form for Proxy-Rainbow.

Proxy-MQ: our MQ-based proxy signature scheme

Using our general method to propose a proxy signature scheme based on the basic MQ-based signature scheme described in section “The general construction of MPKC proxy signature scheme,” we need to make some changes in the key generation phase KeyGen.

Below is the full description of our proxy signature for the MQ scheme.

• Setup: Let $n$ and $m$ be two positive integers, ${\mathbb{F}}_q$ is a finite field and all the arithmetic operations hereafter are over this finite field. $\mathcal{H}:\{0,1{\}}^{*}\to {\mathbb{F}}_q^n$ is a cryptographic hash function.

• KeyGen: Let $\mathbf{e}$ be a vector from ${\mathbb{F}}_q^n$ that every element is randomly chosen in $k$ (i.e. $\mathbf{e}=\{1,...,1{\}}^{\mathrm{T}}$ , the superscript T denotes transposition), to get $A\mathrm{s}$ private key, A first randomly chooses a bijective affine transformation $T_A$ , and its private key ${\mathbf{s}}_A$ is calculated by ${\mathbf{s}}_A=T_A(\mathbf{e})$ , then the corresponding public key $p{k}_A$ is $(F_A,{\mathbf{v}}_A)$ that satisfies ${\mathbf{v}}_A=F_A({\mathbf{s}}_A)$ . Similarly, B’s private key $s{k}_B$ is calculated by ${\mathbf{s}}_B=T_B(\mathbf{e})$ where $T_B$ is a randomly bijective affine transformation, and the corresponding public key $p{k}_B$ is $(F_B,{\mathbf{v}}_B)$ that satisfies ${\mathbf{v}}_B=F_B({\mathbf{s}}_B)$ . Then $\mathbf{e}$ , $p{k}_A=(F_A,{\mathbf{v}}_A)$ and $p{k}_B=(F_B,{\mathbf{v}}_B)$ , are published to the public bulletin board.

• Delegate: Let ${\mathbf{s}}_A=T_A(\mathbf{e})$ , $A$ randomly chooses a bijective affine transformation $T$ , then computes

$$T_A\prime =T°T_A$$

$$F_A\prime =F_A°T$$

$${\mathbf{v}}_A\prime =F_A\prime °T_A\prime (\mathbf{e})$$

The affine $T$ should be kept secret by $A$ . $A$ sends $(T_A\prime ,F_A\prime ,{\mathbf{v}}_A\prime )$ and the warrant $(w,\theta )$ to $B$ through an authenticated channel, where $w=(p{k}_A,p{k}_B,t)$ and $t$ is a time period which denotes that $w$ is valid in time $t$ , and $\theta$ is a signature on $w$ generated by $A$ using our proposed signing algorithm, that is, $\theta =\mathtt{Sign}(w,s{k}_A)$ .

• ProxyKeyGen: Let ${\mathbf{s}}_B=T_B(\mathbf{e})$ , after receiving $(T_A\prime ,F_A\prime ,{\mathbf{v}}_A\prime ,w,\theta )$ , $B$ selects a random bijective affine transformation $T\prime$ and computes

$${\mathbf{s}}_p=T{\prime }^{-1}°T_A\prime (\mathbf{e})$$

$$F_p=F_A\prime °T\prime$$

$${\mathbf{v}}_p={\mathbf{v}}_A\prime$$

Let $p{k}_p=(F_p,{\mathbf{v}}_p),s{k}_p={\mathbf{s}}_p$ . Then $s{k}_p$ is a private key for ordinary signature, and the corresponding public key is $p{k}_p$ , that is because the following equality holds

$$\begin{array}{c}{F}_p({\mathbf{s}}_p)=F_A\prime °T\prime °T{\prime }^{-1}°T_A\prime (\mathbf{e})\hfill \\ =F{\prime }_A°T°T_A(\mathbf{e})\hfill \\ ={\mathbf{v}}_A\prime ={\mathbf{v}}_p\hfill \end{array}$$

Then $B$ computes a signature ${\sigma }_{\mathrm{prx}}$ by running

$${\sigma }_{\mathrm{prx}}=\mathtt{Sign}((w,\theta ,p{k}_p),s{k}_B)$$ (15)

and sets $s{k}_p$ as the proxy signing key that $B$ uses to generate proxy signatures on behalf of $A$ , and sets $p{k}_p$ and $(w,\theta ,p{k}_p,{\sigma }_{\mathrm{prx}})$ as the proxy verifying key.

• ProxySign: Suppose $M$ is the message to be signed. This algorithm generates a proxy signature on the message $M$ by user $B$ .

User $B$ applies $L_{1p}$ , $L_{2p}$ and the central map $F_p$ to the basic MPKC signature algorithm described in Algorithm 1 to generate the signature $\sigma$ on $M$

$$\sigma =\mathtt{Sign}(\mathcal{H}(M),s{k}_p)$$ (16)

Then the proxy signature on message $M$ by user $B$ is $(\sigma ,(w,\theta ,P_A\prime ,{\sigma }_{\mathrm{prx}}))$ .

• ProxyVerify: On input $(M,\sigma ,(w,\theta ,P{\prime }_A,{\sigma }_{\mathrm{prx}}))$ , anyone can verify the validity of the proxy signature by executing this algorithm. This algorithm includes the following steps:

• Check the validity of ${\sigma }_{\mathrm{prx}}$ on $(w,\theta ,P{\prime }_A)$ by running Verify with $p{k}_B$ : $\mathtt{Verify}((w,\theta ,P{\prime }_A),{\sigma }_{\mathrm{prx}},p{k}_B){=}^{?}\mathrm{true}$ . If it is true, goto the next step. Otherwise, output 0.

• Check the validity of $\sigma$ on message $M$ by running Verify with $P{\prime }_A$ : $\mathtt{Verify}(M,\sigma ,P{\prime }_A){=}^{?}\mathrm{true}$ . If it is true, output 1. Otherwise, output 0.

The verifier accepts the proxy signature if and only if the three conditions of ProxySign are all true. Otherwise, the verifier rejects the proxy signature.

Practical implementation for Proxy-MQ

After the changes, it is easy to see that we modify the randomly selected vector into an invertible transformation and a public known random vector, so the scheme is based not only on MQ problem, but also on IP problem. In contrast to Sakumoto et al., ¹⁶ we suggest to use a determined system for the MQ-based signature scheme (i.e. $m=n$ ). The reason for this is that a greater number of variables does not increase the security of this scheme. ³⁵ And we propose for the scheme the parameters $k=\mathrm{GF}(2),(m,n)=(84,84),r=193$ , where $r$ is the number of the signer gathers the commitments in our modified MQ signature scheme.

A toy example and deployment in real distributed scenario

To illustrate how our proxy signature scheme works, we propose a toy example for Proxy-UOV in this section (others are similar). The following example comes from our running test on Magma. ³⁶

In our toy example, we choose the parameter of Proxy-UOV as $q=2^2,m=2,n=4,o=2,v=2$ .

First, we set the private key of user $A$ is $s{k}_A=(F_A,T_A)$ , the public key $p{k}_A=P_A$ , the private key and public key of user $B$ are $s{k}_B=(F_B,T_B)$ and $p{k}_B=P_B$ , respectively

$$F_A=\left(\begin{array}{c}{x}_1{x}_3+a^2{x}_2{x}_4+x_3^2+x_4^2\hfill \\ \multicolumn{1}{c}{a^2{x}_1{x}_4+x_3{x}_4+x_4^2}\end{array}\right)$$

$$T_A(x_1,x_2,x_3,x_4)=\left(\begin{array}{cccc}1\hfill & \alpha \hfill & {\alpha }^2\hfill & 0\hfill \\ \multicolumn{1}{c}{{\alpha }^2}& {\alpha }^2\hfill & \alpha \hfill & 1\hfill \\ \multicolumn{1}{c}{{\alpha }^2}& 0\hfill & {\alpha }^2\hfill & \alpha \hfill \\ \multicolumn{1}{c}{\alpha }& 0\hfill & 1\hfill & 1\hfill \end{array}\right)\left(\begin{array}{c}{x}_1\hfill \\ \multicolumn{1}{c}{x_2}\\ \multicolumn{1}{c}{x_3}\\ \multicolumn{1}{c}{x_4}\end{array}\right)$$

$$P_A=\left(\begin{array}{c}{x}_1^2+\alpha x_1{x}_2+x_1{x}_3+x_1{x}_4+{\alpha }^2{x}_2{x}_3\hfill \\ \multicolumn{1}{c}{+x_2{x}_4+{\alpha }^2{x}_3{x}_4+x_4^2}\\ \multicolumn{1}{c}{{\alpha }^2{x}_1^2+\alpha x_1{x}_2+\alpha x_1{x}_3+{\alpha }^2{x}_1{x}_4+x_2{x}_3}\\ \multicolumn{1}{c}{+x_2{x}_4+{\alpha }^2{x}_3{x}_4+{\alpha }^2{x}_4^2}\end{array}\right)$$

$$F_B=\left(\begin{array}{c}\alpha x_1{x}_3+\alpha x_2{x}_4+x_2{x}_3+\alpha x_3^2+x_3{x}_4+x_4^2\hfill \\ \multicolumn{1}{c}{x_1{x}_4+{\alpha }^2{x}_2{x}_3+x_3{x}_4}\end{array}\right)$$

$$T_B(x_1,x_2,x_3,x_4)=\left(\begin{array}{cccc}\alpha \hfill & 1\hfill & \alpha \hfill & \alpha \hfill \\ \multicolumn{1}{c}{{\alpha }^2}& \alpha \hfill & 0\hfill & 1\hfill \\ \multicolumn{1}{c}{0}& \alpha \hfill & 0\hfill & \alpha \hfill \\ \multicolumn{1}{c}{1}& {\alpha }^2\hfill & 0\hfill & 1\hfill \end{array}\right)\left(\begin{array}{c}{x}_1\hfill \\ \multicolumn{1}{c}{x_2}\\ \multicolumn{1}{c}{x_3}\\ \multicolumn{1}{c}{x_4}\end{array}\right)$$

$$P_B=\left(\begin{array}{c}{x}_1^2+\alpha x_1{x}_2+{\alpha }^2{x}_1{x}_3+\alpha x_1{x}_4+{\alpha }^2{x}_2^2\hfill \\ \multicolumn{1}{c}{+\alpha x_2{x}_3+\alpha x_3{x}_4+x_4^2}\\ \multicolumn{1}{c}{\alpha x_1^2+x_1{x}_2+\alpha x_1{x}_3+x_1{x}_4+x_2{x}_3}\\ \multicolumn{1}{c}{+\alpha x_3{x}_4+x_4^2}\end{array}\right)$$

where $P_A=F_A°T_A$ , $P_B=F_B°T_B$ .

• Delegate: $A$ randomly chooses a bijective affine transformation $T$ as follows

$$T(x_1,x_2,x_3,x_4)=\left(\begin{array}{cccc}0\hfill & \alpha \hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{\alpha }& \alpha \hfill & 1\hfill & 1\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & {\alpha }^2\hfill & \alpha \hfill \\ \multicolumn{1}{c}{0}& 0\hfill & \alpha \hfill & 0\hfill \end{array}\right)\left(\begin{array}{c}{x}_1\hfill \\ \multicolumn{1}{c}{x_2}\\ \multicolumn{1}{c}{x_3}\\ \multicolumn{1}{c}{x_4}\end{array}\right)$$

Then $A$ computes $T_A\prime =T°T_A$ , $F_A\prime =F_A°T_A\prime$ , and $P_A\prime =F_A\prime °T_A\prime$ . The results are

$$T{\prime }_A(x_1,x_2,x_3,x_4)=\left(\begin{array}{cccc}1\hfill & 1\hfill & {\alpha }^2\hfill & \alpha \hfill \\ \multicolumn{1}{c}{\alpha }& \alpha \hfill & 0\hfill & 1\hfill \\ \multicolumn{1}{c}{1}& 0\hfill & 0\hfill & {\alpha }^2\hfill \\ \multicolumn{1}{c}{1}& 0\hfill & 1\hfill & {\alpha }^2\hfill \end{array}\right)\left(\begin{array}{c}{x}_1\hfill \\ \multicolumn{1}{c}{x_2}\\ \multicolumn{1}{c}{x_3}\\ \multicolumn{1}{c}{x_4}\end{array}\right)$$

$$F{\prime }_A=\left(\begin{array}{c}\alpha x_1{x}_3+{\alpha }^2{x}_2{x}_3+{\alpha }^2{x}_2{x}_4+x_3{x}_4+{\alpha }^2{x}_4^2\hfill \\ \multicolumn{1}{c}{\alpha x_2{x}_3+\alpha x_3^2+{\alpha }^2{x}_3{x}_4}\end{array}\right)$$

$$P{\prime }_A=\left(\begin{array}{c}\alpha x_1{x}_2+x_1{x}_3+\alpha x_1{x}_4+x_2{x}_3+x_2{x}_4\hfill \\ \multicolumn{1}{c}{+{\alpha }^2{x}_3^2+{\alpha }^2{x}_3{x}_4+x_4^2}\\ \multicolumn{1}{c}{\alpha x_1^2+{\alpha }^2{x}_1{x}_2+{\alpha }^2{x}_1{x}_3+\alpha x_3{x}_4+{\alpha }^2{x}_4^2}\end{array}\right)$$

In addition, $A$ generates a warrant $w=(p{k}_A,p{k}_B,t)$ (assume that $\mathcal{H}(w)=(0,\alpha )$ ), signs it using the regular UOV signing algorithm, and gets $\theta =\mathtt{Sign}(\mathcal{H}(w),s{k}_A)=(0,0,\alpha ,1)$ ,

Finally, $A$ sends $(T_A\prime ,F_A\prime ,P_A\prime )$ and the warrant $(w,\theta )$ to $B$ through an authenticated channel.

• ProxyKeyGen: Afterreceiving $(T_A\prime ,F_A\prime ,P_A\prime ,w,\theta$ , $B$ first checks the validity of $P_A\prime ,\theta$ by checking $P{\prime }_A=F{\prime }_A°T{\prime }_A$ and $\mathtt{Verify}(w,\theta ,p{k}_A)=P_A(0,0,\alpha ,1)=(0,\alpha )$ . Then $B$ selects a random bijective affine transformation $T\prime$ and computes $T_p=T{\prime }^{-1}°T_A\prime$ , and $F_p=F_A\prime °T\prime$ , where

$$T\prime (x_1,x_2,x_3,x_4)=\left(\begin{array}{cccc}1\hfill & \alpha \hfill & {\alpha }^2\hfill & 1\hfill \\ \multicolumn{1}{c}{{\alpha }^2}& {\alpha }^2\hfill & 0\hfill & {\alpha }^2\hfill \\ \multicolumn{1}{c}{0}& 0\hfill & 0\hfill & \alpha \hfill \\ \multicolumn{1}{c}{0}& 0\hfill & \alpha \hfill & {\alpha }^2\hfill \end{array}\right)\left(\begin{array}{c}{x}_1\hfill \\ \multicolumn{1}{c}{x_2}\\ \multicolumn{1}{c}{x_3}\\ \multicolumn{1}{c}{x_4}\end{array}\right)$$

$$T_p(x_1,x_2,x_3,x_4)=\left(\begin{array}{cccc}1\hfill & 0\hfill & \alpha \hfill & 1\hfill \\ \multicolumn{1}{c}{1}& {\alpha }^2\hfill & \alpha \hfill & 1\hfill \\ \multicolumn{1}{c}{\alpha }& 0\hfill & {\alpha }^2\hfill & 1\hfill \\ \multicolumn{1}{c}{{\alpha }^2}& 0\hfill & 0\hfill & \alpha \hfill \end{array}\right)\left(\begin{array}{c}{x}_1\hfill \\ \multicolumn{1}{c}{x_2}\\ \multicolumn{1}{c}{x_3}\\ \multicolumn{1}{c}{x_4}\end{array}\right)$$

$$F_p=\left(\begin{array}{c}\alpha x_1{x}_3+x_1{x}_4+{\alpha }^2{x}_2{x}_4+\alpha x_3^2+\alpha x_3{x}_4+x_4^2\hfill \\ \multicolumn{1}{c}{\alpha x_1{x}_4+\alpha x_2{x}_4+\alpha x_3{x}_4}\end{array}\right)$$

$$P{\prime }_A=\left(\begin{array}{c}\alpha x_1{x}_2+x_1{x}_3+\alpha x_1{x}_4+x_2{x}_3+x_2{x}_4\hfill \\ \multicolumn{1}{c}{+{\alpha }^2{x}_3^2+{\alpha }^2{x}_3{x}_4+x_4^2}\\ \multicolumn{1}{c}{\alpha x_1^2+{\alpha }^2{x}_1{x}_2+{\alpha }^2{x}_1{x}_3\alpha x_3{x}_4+{\alpha }^2{x}_4^2}\end{array}\right)$$

Let $s{k}_p=(F_p,T_p)$ , and $p{k}_p=P_A\prime$ . Then $s{k}_p$ is a private key for ordinary signature, and the corresponding public key is $p{k}_p$ .

Assume the hash value of $(w,\theta ,P{\prime }_A)$ is $(\alpha ,\alpha )$ , $B$ computes a signature ${\sigma }_{\mathrm{prx}}$ by running

$${\sigma }_{\mathrm{prx}}=\mathtt{Sign}(\mathcal{H}(w,\theta ,P{\prime }_A),s{k}_B)=(1,1,1,\alpha )$$

and sets $s{k}_p$ as the proxy signing key that $B$ uses to generate proxy signatures on behalf of $A$ , and sets $p{k}_p$ and $(w,\theta ,P{\prime }_A,{\sigma }_{\mathrm{prx}})$ as the proxy verifying key.

• ProxySign: Suppose $\mathcal{H}(M)=(0,{\alpha }^2)$ is the message to be signed.

User $B$ generates the signature $\sigma$ on $M$ using the proxy key $s{k}_p$

$$\sigma =\mathtt{Sign}(\mathcal{H}(M),s{k}_p)=({\alpha }^2,0,\alpha ,\alpha )$$

Then the proxy signature on message $M$ by user $B$ is $(\sigma ,(w,\theta ,P_A\prime ,{\sigma }_{\mathrm{prx}}))$ .

• ProxyVerify: On input $(M,\sigma ,(w,\theta ,P{\prime }_A,{\sigma }_{\mathrm{prx}}))$ , a verifier $V$ can verify the validity of the proxy signature by executing this algorithm. This algorithm includes the following steps:

• 2. Compute $P_B({\sigma }_{\mathrm{prx}})=(\alpha ,\alpha )$ and check whether it is equal to $\mathcal{H}(w,\theta ,P{\prime }_A)$ . Since it is true, go to the next step.

• 3. Compute $P{\prime }_A(\sigma )=(0,{\alpha }^2)$ and check whether it is equal to $\mathcal{H}(M)$ . Since it is also valid, the algorithm outputs 1.

In addition, let us consider a communication scenario in a distributed sensor network and see how we can deploy our proxy scheme into this scenario. To develop a secure communication in a distributed sensor network, sensors digitally sign the data (i.e. the message $M$ ) and communicate to a server. It is expected that the server must be convinced to the authenticity of the sender (i.e. sensor deployed in the distributed network) and the sender (i.e. sensor) must also be convinced to the authenticity of the receiver (i.e. server). To develop such authentication method, a designated receiver delegation method is the most promising. In this method, the deploying authority (DA) (server administrator or network developer) delegates its signing power to sensor and also designates the trained professional as a receiver. Thus, DA is original signer, sensor is a proxy signer and the server is designated receiver. As shown in the above toy example, in this scenario, the DA is acting as $A$ , the sensors are acting as $B$ , and finally, it can generate a proxy signature on message $M$ as $(\sigma ,(w,\theta ,P_A\prime ,{\sigma }_{\mathrm{prx}}))$ . Finally, the server is acting as a verifier $V$ and thus can convince to the authenticity of the sensors.

Performance and comparisons of our proxy signature schemes

The complexity and running time of each procedure of our proxy signature schemes, and comparison with Tang’s scheme ²⁴ (the only proxy scheme of MPKC we have known) and Mambo’s scheme ³⁰ (the first proxy scheme), Hu–Zhang (HZ) scheme ³⁷ (an improved efficient secure proxy scheme) is shown in Table 1. We set the parameters in HZ scheme ³⁷ with $(n=2,t=1)$ . From Table 1, we can see that the proxy signature generation and the proxy signature verification of our schemes are more efficient than Tang’s schemes in Table 1. According to recent research result, the time of generating a large prime is more than 20 times than that of generating a system of polynomials, and an exponentiation evaluation costs about half times than an evaluation operation, while choosing proper parameters with security level more than 80 bits. So, in this situation, all our schemes and Tang’s scheme ²⁴ have better initialization time and verify process time than that of Mambo’s scheme ³⁰ and HZ scheme. ³⁷

Table 1.

Computing complexity requirements by ours and compared with other schemes.

	Proxy-UOV	Proxy-Rainbow	Proxy-MQ
Initialization	$\mathcal{O}(2n^2+2m{n}^2)$	$\begin{array}{c}\mathcal{O}(2m^2+2n^2+\hfill \\ 2m{n}^2)\hfill \end{array}$	$\mathcal{O}(2n^2+2m{n}^2)$
Proxy share generation	$\mathcal{O}(3n^3+2m{n}^2+n^2+S)$	$\begin{array}{c}\mathcal{O}(3m^3+4n^3+\hfill \\ 4m{n}^2+2\mathrm{uS})\hfill \end{array}$	$\begin{array}{c}\mathcal{O}(2n^3+3m{n}^2+\hfill \\ 2\mathrm{round}·m{n}^3)\hfill \end{array}$
Proxy signature generation	$\mathcal{O}(n^3+n^2+S)$	$\begin{array}{c}\mathcal{O}(m^3+n^3+n^2+\hfill \\ \mathrm{uS})\hfill \end{array}$	$\mathcal{O}(\mathrm{round}·m{n}^3)$
Signature verify	$\mathcal{O}(3n)$	$\mathcal{O}(3n)$	$\mathcal{O}(3\mathrm{round}·m{n}^3)$
	Tang’s scheme 24	Mambo’s scheme 30	HZ scheme 37
Initialization	$\mathcal{O}(2m^2+2n^2+2m{n}^2)$	$\begin{array}{c}2T_p+T_e+T_m\approx \hfill \\ \mathcal{O}(2\log (n_r)+\hfill \\ n_{\mathrm{rsa}}\log (n_r)+n_r^2)\hfill \end{array}$	$\begin{array}{c}2T_p+5T_e+2T_m\approx \hfill \\ \mathcal{O}(2\log (n_r)+\hfill \\ 5n_{\mathrm{rsa}}\log (n_r)+\hfill \\ 2n_r^2)\hfill \end{array}$
Proxy share generation	$\begin{array}{c}\mathcal{O}(5m^3+5n^3+\hfill \\ 5m{n}^3+3\mathrm{qm}{n}^3)\hfill \end{array}$	$T_e+T_m\approx \mathcal{O}(n_r\log (n_r)+n_r^2)$	$6T_e+4T_m+T_H\approx \mathcal{O}(6n_r\log (n_r)+4n_r^2+\log (n_h))$
Proxy signature generation	$\mathcal{O}(\mathrm{qm}{n}^3)$	$T_e\approx \mathcal{O}(n_r\log (n_r))$	$4T_e+6T_m+2T_H\approx \mathcal{O}(4n_r\log (n_r)+6n_r^2+2\log (n_h))$
Signature verify	$\mathcal{O}(3\mathrm{qm}{n}^3)$	$2T_e+T_m\approx \mathcal{O}(2n_r\log (n_r)+n_r^2)$	$5T_e+3T_m+2T_H\approx \mathcal{O}(5n_r\log (n_r)+3n_r^2+2\log (n_h)$

UOV: Unbalanced Oil and Vinegar; MQ: multivariate quadratic; RSA: Rivest–Shamir–Adleman; HZ: Hu–Zhang.

Notation for Table 1: $u,m,n$ : the number of layers, polynomials, and variables in a scheme, respectively; $S$ : average time required by a Gaussian Elimination function to solve linear equations; $q$ : the length of output bits of the hash function for Tang scheme; ²⁴ $\mathrm{round}$ : the iterative rounds for MQ-based signature; $T_p,T_e,T_m,T_H$ : the time for generating a large prime, one exponentiation computation, one modular multiplication computation, and hash function computation, respectively; $n_r,n_h$ : the size of the public key in a secure RSA scheme and the size of a secure hash function, respectively.The running time of our proposed Proxy-UOV and Proxy-Rainbow schemes (using our suggested parameters) compared with Mambo’s scheme ³⁰ and HZ scheme ³⁷ (2048 bits) is shown in Table 2. From the experiments’ results, we can see that our schemes’ proxy signature generation time is between RSA and elliptic curve cryptography (ECC), while the initialization and verifying time are much faster than both of them. Consequently, even though our scheme is a bit slower than the proxy share generation time, but it is applicable in real life.

Table 2.

Running time requirements by Proxy-UOV and Proxy-Rainbow and compared with other schemes.

	Proxy-UOV	Proxy-Rainbow	Mambo scheme	HZ scheme
Initialization (ms)	$19,376$	$11,912$	$404,277$	$443,885$
Proxy share generation (ms)	$52,301$	$30,691$	$141$	$10,245$
Proxy signature generation (ms)	$187$	$61$	$47$	$4502$
Signature verify (ms)	$31$	$16$	$249$	$3646$

UOV: Unbalanced Oil and Vinegar; HZ: Hu–Zhang.

While running in Magma, the memory will be overflowed when using the suggested parameters of Proxy-MQ and Tang’s scheme in Tang and Xu, ²⁴ we have to modify the parameter to formulate the running time ( $(n=42,m=42,q=2,\mathrm{round}=2)$ for Proxy-MQ, $(n=42,m=42,q=2,\mathrm{round}=2)$ for Tang’s scheme), and the result is shown in Table 3.

Table 3.

Running time requirements by Proxy-MQ and compared with Tang scheme.

	Proxy-MQ	Tang’s scheme
Initialization (ms)	$24,043$	$24,328$
Proxy share generation (ms)	$92,008$	$122,873$
Proxy signature generation (ms)	$30,521$	$48,642$
Signature verify (ms)	$74,215$	$75,832$

MQ: multivariate quadratic.

From the result shows, the proxy signature scheme based on MQ is slightly more efficient than Tang’s scheme ²⁴ and is a promising proxy scheme by taking into account its post-quantum property in multivariate cryptography.

Conclusion

A general proxy signature scheme based on MPKC signature scheme is proposed, which invokes three number of times of the underlying signature scheme, and can satisfy all the security requirement of a proxy scheme. Through formal security analysis, our general scheme is proved to be cured on Existential Unforgeability under an Adaptive Chosen Message Attack with Proxy Key Exposure assuming that the underlying MPKC signature is Existential Unforgeability under an Adaptive Chosen Message Attack. Thereafter, we propose three practical proxy schemes based on three promising MPKC schemes: UOV, Rainbow, and MQ-based scheme. Although the security of the underlying MPKC is still an open problem, the method to construct our proxy scheme and the method to formally prove the security of our proxy scheme are good exploration in the area of MPKC.

In the future work, we plan to construct other primitives based on multivariate signature scheme, such as identity-based signature, forward secure signature, and so on.