An Efficient Lattice-Based Proxy Signature with Message Recovery

Abstract

Proxy signature scheme is an important cryptographic primitive in which an entity can delegate its signing rights to another entity, the purpose of proxy signature with message recovery is to shorten the length of proxy signatures which can effectively reduce the communication overhead. Although message recovery proxy signature scheme based on conventional number-theoretic problems has been proposed for a long time, the message recovery technique draws no attention to proxy signature scheme from lattice. In this paper, we firstly propose a proxy signature scheme with message recovery from lattice which is more efficient than previous proxy signature schemes in signature size, time and energy cost, and we prove that in the random oracle, our scheme is secure model under the hardness assumption of SIS. Our proxy signature scheme with message recovery would work well in the quantum age based on the underlying lattice problems.

1 Introduction

Proxy signatures, proposed by Mambo et al. [1], are significant cryptographic systems that are widely used in different situations, such as E-commerce, cloud computing and Electronic election. In a proxy signature scheme, Original signer A delegates his signing power and responsibility to another one which is called proxy signer. According to the hardness of traditional Number Theory problems, the researchers have prosed many effective proxy signature schemes such as integer factoring-based schemes, discrete logarithm schemes and elliptic curve schemes [2, 3]. However, in a long run, all these proxy signature schemes are not secure, because both discrete logarithms and large prime factorization algorithms can be solved in polynomial-time [4] when we take quantum computing into account. For purpose of reducing the threat from the quantum age, many researchers pay their attention to Post-Quantum Cryptography, some proxy signature schemes, like hash-based schemes, MPKC schemes, lattice-based schemes, which are considered as Post-Quantum Cryptography, and many corresponding efficient Post-Quantum proxy signature schemes have been proposed, such as [5,6,7,8,9].

Lattice-based signature occupies a position of particular interest, as it relies on well-studied problems and comes with uniquely strong security guarantees [10]. Organizations and research groups are looking forward for efficient lattice-based cryptography schemes to replace RSA and ECC based schemes, and many creative and constructive results show that properly optimized lattice schemes may be competitive with, or even outperform, classical factoring and discrete logarithm-based cryptography.

The first signature scheme with message recovery was proposed by Nyberg and Rueppel [11]. In a signature scheme with message recovery, we only need to transmit the signature without the signed message, because verifier can easily recover the signed message from the signature. This construction quietly adapts to situations where small signed message to be transmitted or strict bandwidth requirements [12, 13]. The existent proxy signature schemes with such property can be categorized into two different types: discrete logarithm based and RSA based [14,15,16] which efficiently improve the performance of previous signature without message recovery. Although there are many very effective latticed-based proxy signature schemes, based on the hardness assumption of lattice, have been proposed [17,18,19], as far as we know, there are no efficient lattice-based proxy signature schemes with message recovery have been proposed.

In this paper, benefit from the techniques [20, 21], we propose an efficient lattice-based proxy signature scheme with message recovery, and prove that it has existentially security in the random oracle model, in addition, contribution to message recovery technology and mainly multiplication of matrix and vector given in our scheme, our scheme enjoy higher performance when compared with others’ proxy signature scheme, finally, when we take piratical situation into consideration [22], we are surprised to find that this kind of scheme consume less energy even when we add some operations for message recovery, which means our proxy signature schemes are extremely suitable for system with low energy and low bandwidth. As the hardness assumption of lattice problem SIS, our lattice-based message recovery proxy signature scheme would work well in the quantum age.

The remainder of our paper is organized as follow. In Sect. 2, we provide necessary preliminaries of our scheme. In Sect. 3, we describe two models of our lattice-based proxy signature scheme with message recovery:syntax model and security model. In Sect. 4, we propose our efficient message recovery proxy scheme from lattice. In Sect. 5, we present the formal security analysis of our scheme. In Sect. 6, we introduce some necessary criterions, and give detailed comparisons between our scheme and some existing proxy schemes from lattice.

2 Preliminaries

2.1 Notations

In this paper, following notations would be used:

• $x\parallel y$ denotes the connection of two string x and y, and they are effectively recoverable.

• $M^{n\times (k_{1}+k_{2})}=M_{1}^{n\times k_{1}}\parallel M_{2}^{n\times k_{1}}$ denotes the concatenation of Matrices $M_{1},M_{2}$.

• $\Vert v\Vert _{p}$ denotes the $l_{p}$ norm of v.

• ${\mid } x{\mid }$ denotes the quantity of bits of v.

• ${\mid } x{\mid }^{l_{1}}$ denotes the first left $l_{1}$ bits of x.

• ${\mid } x{\mid }_{l_{2}}$ denotes the first right $l_{2}$ bits of x.

2.2 Lattice

Definition 1

A lattice L is a discrete subgroup of some space $\mathbb {R}^{n}$, it is generated by independent vector $v_1,v_2,\cdots ,v_k \in \mathbb {R}^{n}$ through the following way:

$$\begin{aligned} \varLambda =L(v_1,v_2,\cdots ,v_k) = \{\sum _{i=1}^ka_iv_i\mid a_i\in \mathbf {Z}\} \end{aligned}$$

The basis of L are vectors $v_1,v_2,\cdots ,v_n$, lattice’s rank is the integer n where $k<n$ and $a_i$ is coefficient.

Definition 2

Given integers q, m, n and a matrix $A\in Z_{q}^{n\times m}$, for some $S\in Z^{m}$.

$$\begin{aligned} \begin{aligned} \varLambda _{q}(A)=\{x\in Z^{m}:x=A^{T}S=u (mod q) \}\\ \varLambda _{q}^{\perp }(A)=\{x\in Z^{m}:x=A^{T}S=0 (mod q)\} \end{aligned} \end{aligned}$$

From the above definition, these two types of lattices are dual to each other.

2.3 Gaussian on Lattice

In lattice-based signature scheme, Gaussian series are very effective techniques which are widely used, and we have a briefly review of it here.

Definition 3

(Discrete Gaussian distribution). $\sigma \in \mathbb {R}^{m}$ is standard deviation, vector $c\in Z^{m}$ is center, Continuous Gaussian distribution $\rho _{c,\sigma }^{m}(x)$ and Discrete Gaussian distribution $D_{c,\sigma }^{m}(x)$ are defined as follow:

$$\begin{aligned} \begin{aligned} \rho _{c,\sigma }^{m}(x)=(\frac{1}{\sqrt{2\pi \delta ^{2}}})^{m}e^{\frac{-\parallel x-c\parallel ^{2}}{2\sigma ^{2}}}\\ D_{c,\sigma }^{m}(x)=\frac{\rho _{c,\sigma }^{m}(x)}{\sum _{z\in Z^{m}}\rho _{c,\sigma }^{m}(z)} \end{aligned} \end{aligned}$$

(1)

When $c=0$, we can simply write $\rho _{c,\sigma }^{m}(x), D_{c,\sigma }^{m}(x)$ as $\rho _{\sigma }^{m},D_{\sigma }^{m}$, and from [21], an important theorem of Discrete Gaussian distribution is described as follow

Theorem 1

$\forall \sigma >0$ and $m\in Z^{+}$

• (1) P$[x\in D_{\sigma }^{1}:{\mid } x{\mid }>12\sigma ]<2^{-100}$;

• (2) P$[x\in D_{\sigma }^{m}:{\parallel } x {\parallel } > 2\sigma \sqrt{m}]<2^{-m}$.

2.4 RST: Rejection Sampling Technique

For a lattice-based signature scheme, the most important conception of the RST is to eliminate the relationship between signing key and output signature’s distribution [10], the algorithm as follow (Algorithm 1).

2.5 Small Integer Solution (SIS) and its Hardness Assumption

Definition 4

For an integer modular homogeneous scheme $As=0modq$, get a proper solution $s\in Z^{m}$ where q, matrix coefficient, small solution s satisfy $q\in Z^{m}$, $A\in Z_{q}^{n\times m}$ and $\parallel s\parallel \le \beta$ where $\beta$ is a real value.

In reference [10, 23], they proved that for any polynomial-bound $m,\beta$ and any prime p, with small factors and the Gaussian measure, there is no difference between the hardness of some worst-case approximation and average-case harness of SIS. Even the hardness of SIS problem has been proved, there still exist overwhelming probability that anyone can solve some case if the trapdoor of $f=Ax(modq)$ is got.

3 Lattice-Based Proxy Signature Scheme with Message Recovery

Syntax model and security model of our lattice-based proxy signature scheme with message recovery are proposed in this section.

3.1 Syntax

Definition 5

In such lattice-based proxy signature scheme with message recovery scheme, there are three participants: An original signer with $ID_{o}$, a proxy signer: $ID_{p}$, and a verifier, and this scheme is consists of six PPT algorithm (Setup, KeyGen, DelGen, DelVer, Psign, Pver), where:

• 1. Setup: Given a security parameters n, and select appropriate parameters and functions. $(par,n)\leftarrow Setup$.

• 2. KeyGen: Given a security parameters n, this algorithm output the secret and public key of original signer and proxy signer: Original signer’s = ($PK_{o},SK_{o})$, Proxy signer’ = ($PK_{p},SK_{p})$.$(PK_{o},SK_{o},PK_{p},SK_{p})\leftarrow KeyGen(n,M)$.

• 3. DelGen: Given the original signer’s public key $PK_{o}$ and secret key $SK_{o}$ hash function $H_{i}$, proxy signer’s $ID_{p}$, this algorithm output the Delegation Key $(PK_{D},SK_{D})$ for original signer, original signer sends this pair to proxy signer in security channel. $(PK_{D},SK_{D})\leftarrow DelGen(H_{i},ID_{p},PK_{D},SK_{D})$.

• 4. DelVer: Given the original signer’s public key $PK_{o}$ and Delegation Key $( PK_{D},$ $SK_{D})$, and check $DelVer (PK_{o},PK_{D}, SK_{D})$ = 1 or not. If it outputs 1, it’s a valid delegation of original signer. $\{0, 1\}\leftarrow DelVer(PK_{o},PK_{D},SK_{D})$.

• 5. Psign: Given the secret delegation key $SK_{D}$, proxy signer’s secret key $SK_{p}$ and the message $u=u_{1}\parallel u_{2}$, output the proxy signature$\theta$, that is $\theta \leftarrow Psign(u,SK_{D},SK_{p})$.

• 6. Pver: Given the public key $PK_{o}$ of original signer, public key $PK_{o}$ of proxy signer, public delegation key $PK_{D}$, proxy signer’s $ID_{p}$, hash function $H_{i}$, partial message $u_{2}$, and proxy signature $\theta$, if the proxy signature is valid, output 1, otherwise, output 0, that is $(m,\{0,1\})\leftarrow Pver(PK_{o}, PK_{o},PK_{D}, ID_{p}, H_{i}, \theta , u_{2})$.

Remark 1

For consistency requirements, partial message $u_{2}$, the proxy signature $\theta$ of secret Delegation Key $SK_{D}$ and proxy signer’s secret key $SK_{P}$ must hold with overwhelming probability with following equation Verify $(Sign( SK_{D}, SK_{P}, u), u_{2}, PK_{D}, SK_{D})$ = 1.

3.2 Security Model

In a lattice-based proxy signature scheme with message recovery, the properties of Unforgeability, Verifiability, Strong identifiability, Strong undeniability and Key dependence are satisfied naturally. Therefore, we consider in this lattice-based proxy signature scheme under adaptive chosen message and identity attack. To have a formal security definition for this scheme, the security model is an security game played between a adversary A and a challenger C:

• 1. Setup: In this game, the challenger C firstly run the algorithm Setup(n), get the necessary parameters and send them to the adversary A.

• 2. Queries: In such query-game, following types of queries can be adaptively issued by adversary A within polynomial bound number of questions.

  • KeyGen-query: The adversary A can issue a query on the ID which he want to get the secret key, and the challenger run the algorithm KeyGen, and return A with $SK_{ID}$ in response.

  • DelGen-query: To get the delegation key $SK_D$, the adversary A input two secret key corresponding to the identity $ID_{o}$ and ID p, in response, the challenger C run the algorithm DelGen, and return A with $SK_D$.

  • Psign-query: When adversary issues such on $ID_p$ with message u, the challenger C run the algorithm Psign, and return A with signature.

• 3. By the above queries, the adversary A generate a valid proxy signature $\theta ^{'}$ on message $u^{*}$ under the identity $ID'$, if the following holds, Adversary A wins the game: (i) $Vfy(Sign( SK_{D}, SK_{P}, m), PK_{D}, SK_{D},par)$ = 1; (ii) $u^{*}$ has never been send to the Psign-query; (iii) all identities which is related to $ID'$ have never been sent to KeyGen-query.

An lattice-based proxy signature scheme with message recovery is considered as existential unforgeable if the advantage of Adversary A wins the above query game in polynomial time is negligible.

4 Our Lattice-Based Proxy Signature Scheme with Message Recovery

We gave a detailed account of our efficient message recovery proxy signature scheme from lattice in this section. Like the traditional signature systems, our scheme have three participants: an original signer with $ID_{o}$, a proxy signer with identity $ID_{p}$, and a verifier, and this scheme is consists of six probabilistic polynomial time (PPT) algorithm (Setup, KeyGen, DelGen, DelVer, Psign, Pver), where:

• 1. Setup: Given the security parameter n of this system, we select $l_{1}, l_{2}, k_{1}, k_{2}, m, q \in N$, where q is a prime, select five hash function: $H_{1}=Z_{q}^{n}\rightarrow \{0,1\}^{l_{1}+l_{2}}$, $H_{2}=\{0,1\}^{*}\rightarrow \{0,1\}^{k_{1}+k_{2}}$, $H_{3}=ID \rightarrow \{-1,0,1\}^{k_{1}\times k_{2}}$, $F_{1}=\{0,1\}^{l_{2}}\rightarrow \{0,1\}^{l_1}$, $F_{2}=\{0,1\}^{l_{1}}\rightarrow \{0,1\}^{l_{2}}$. $H_{1},H_{2}$are seen as a random oracle.

• 2. KeyGen: On input security parameter n, randomly choose $A\in Z_{q}^{n\times m}$ together with two secret matrix basis $S_{1},S_{2}\in \{-d,\cdots , 0, \cdots , d\}^{m\times k_{1}}$. Original signer computes $T_{1}=AS_{1}mod q$, and keep $PK_{o}=(A,T_{1})$ as his own public key, $SK_{o}=S_{1}$ as secret key. Proxy signer computes $T_{2}=AS_{2}mod q$, and keep $PK_{p}=(A,T_{2})$ as his own public key, $SK_{p}=S_{2}$ as secret key.

• 3. DelGen: Original signer computes $t=H_{3}(ID_{p})$, $S_{3}=S_{1}t\in Z^{m\times k_{2}}$, $T_{3}=T_{1}t\in Z^{n\times k_{2}}$, and send $(S_{3},T_{3})$ to Proxy signer via an safe authenticated channel, Proxy signer keep the delegation key $PK_{D}=S_{3}$, proxy signer can use it to generate valid proxy signatures stand for original signer, and the corresponding public key is $PK_{D}=T_{3}$.

• 4. DelVer: The Proxy signer receives $(S_{3},T_{3})$ from original signer, and checks if $AS_{3}=T_{1}t$ holds, where $t=H_{3}(ID_{p})$.

• 5. Psign: The Proxy signer with identity $ID_{p}$ do the following:

  • Divide the message u into two parts $u=u_{1}\parallel u_{2}$ where $\mid u_{1}\mid =l_{2}$, if$\mid u\mid <l_{2}$, let $u_{2}=\perp$.

  • Select a random $y\in D_{\sigma }^{m}$, and compute $\alpha =H_{1}(Ay)$.

  • Let $u_{1}^{'}=F_{1}(u_{1})\parallel (F_{2}(F_{1}(u_{1}))\bigoplus u_{1})$, $r=\alpha \bigoplus u_{1}^{'}$.

  • Compute $C=H_{2}(r,u_{2})$.

  • Compute $Z=(S_{2}\Vert S_{3})C+y\in Z_{q}^{m}$.

  • The proxy signature on the message u is $(r,Z,u_{2})$ with probability $min(\frac{D_{\sigma }^{m}(Z)}{MD_{(S_{2}\Vert S_{3})_{C,\sigma }}(Z)},1)$.

• 6. Pver: Given $(r,Z,u_{2})$, a verifier does as explained in the succeeding text:

  • Compute $\alpha =H_{1}(AZ-(T_{2}\parallel T_{3}) H_{2}(r,u_{2}))$.

  • Compute $u_{1}^{'}=r\bigoplus \sigma$, $u_{1}=|u_{1}^{'}|_{l_{2}}\bigoplus F_{2}(|u_{1}^{'}|^{l_{1}})$, and then recover message $u=u_{1}\parallel u_{2}$.

  • Check if $\Vert Z\Vert <2\sigma \sqrt{m}$ and $F_{1}(u_{1})=|u_{1}^{'}|^{l_{1}}$ hold at same time, if so, accept signature from the proxy signer, otherwise, reject it.

Theorem 2

Our lattice-based proxy signature scheme with message recovery is correctness.

Proof

From the above detailed construction, we can easily have following equations where u message

$$\begin{aligned}&AZ-(T_{2}\parallel T_{3}) H_{2}(r,u_{2})\\&=A((S_{2}\Vert S_{3})C+y)-(T_{2}\parallel T_{3}) H_{2}(r,u_{2})\\&=Ay \end{aligned}$$

the distribution of $(S_{2}\Vert S_{3})C+y$ is statically closed to the distribution $D_{\sigma }^{m}$, and from the Theorem 1, $\parallel (S_{2}\Vert S_{3})C+y\parallel \le 2\sigma \sqrt{m}$ with probability at least $1-2^{-m}$. On the other hand, $u_{1}^{'}=F_{1}(u_{1})\parallel (F_{2}(F_{1}(u_{1}))\bigoplus u_{1})$, we can recover $u_{1}=|u_{1}^{'}|_{l_{2}}\bigoplus F_{2}(|u_{1}^{'}|^{l_{1}})$ with $F_{1}(u_{1})=|u_{1}^{'}|^{l_{1}}$ hold.

5 Security Analysis

As a signature scheme, security is the most important factor, we prove that our lattice-based proxy signature scheme with message recovery is secure enough (unforceability) under the hardness assumption of SIS in this section.

When we proving the unforceability of proxy signature scheme with message recovery, we should take two types adversary into consideration:

$\mathbf {Type(\text {i})}$ Adversary A can not only have the public key $PK_{o}$ of original signer and public key $PK_{p}$ of proxy signer, but also have the original signer’s secret key $SK_{o}$.

$\mathbf {Type(\text {ii})}$ Adversary A has neither the original signer’s secret key $SK_{O}$ nor the proxy signer’s secret key $SK_{P}$.

It’s obvious that adversary in $\mathbf {Type(\text {i})}$ knows more information than the adversary in $\mathbf {Type(\text {ii})}$, so we only need to take $\mathbf {Type(\text {i})}$ adversary into consideration. We suppose there is a polynomial time, adversary A forge a valid proxy signature by at most $q_{H_{1}}$times $H_{1}$ query, $q_{H_{2}}$times $H_{2}$ query, $q_{F_{1}}$times $F_{1}$ query, $q_{F_{2}}$times $F_{2}$ query, and $q_{s}$ times signature query with non-negligible probability, it means there exist an algorithm C (Challenger C) which can solve a $SIS_{q,n,m,C}$ problem “with the help of” Adversary A in polynomial time. Algorithm C (Challenger C) has a game with A, the following is the simulation. $\mathbf {Queries.}$ The adversary A issues the following types of queries adaptively, A has random oracle $H_{1}-query$ before any other queries.

• $H_{3}-query$. Challenger C maintains a list $L_{0}=(ID_{p_{i}},PK_{p_{i}},SK_{p_{i}})$, and the initial value is null, when adversary A issues a query on $ID_{p_{i}}$, Challenger C search it in list first, if there exist corresponding tuple $(ID_{p_{i}},PK_{p_{i}},SK_{p_{i}})$, return $PK_{p_{i}}$; otherwise, Challenger C randomly chooses matrix $S\in Z_{q}^{m\times k_{2}}$, then Challenger C computes $PK=AS$, Update the list $L_{0}$ as $L_{0}=(L_{0}, (ID,PK,SK))$, return PK.

• $KeyGen-query$. When adversary A issues a query on $ID_p$, Challenger C look it up in $L_0$, find a match tuple (ID, PK, SK), and output SK as response.

• $DelGen-query$. On receiving the secret key $SK_{P}$, Challenger C outputs $SK_{D}$ as response.

• $H_{1}-query$. Challenger C maintains a list $L_{1}=(Ay,\alpha _{i})$, and the initial value is null. When the adversary A issue a query for Aymodq, Challenger C search it in list first, if there exist corresponding tuple $(Ay,\alpha )$, return $\alpha$; otherwise, randomly chooses $\alpha \in \{0,1\}^{k_{1}+k_{2}}$. Update the list $L_{1}$ as $L_{1}=(L_{1}, (Ay,\alpha ))$, then return $\alpha$.

• $F_{1}-query$. Challenger C maintains a list $L_{2}=(u_{1},F_{1}(u_{1}))$, and the initial value is null. When the adversary A issue a query for $u_{1}$, Challenger C search it in list first, if there exist corresponding tuple $(u_{1},F_{1}(u_{1}))$, return $F_{1}(u_{1})$, otherwise, randomly chooses $F_{1}(u_{1})\in \{0,1\}^{l_{1}}$, Update the list $L_{2}=(L_{2}, (u_{1},F_{1}(u_{1})))$.

• $F_{2}-query$. Challenger C maintains a list $L_{3}=(F_{1}(u_{1}),F_{2}(F_{1}(u_{1}))$, and the initial value is null. When the adversary A issue a query for $F_{1}(u_{1})$, Challenger C search it in list first, if there exist corresponding tuple $(F_{1}(u_{1}),F_{2}(F_{1}(u_{1}))$, return $F_{2}(F_{1}(u_{1})$, otherwise, randomly chooses $F_{2}(F_{1}(u_{1})\in \{0,1\}^{l_{2}}$, Update the list $L_{3}=(L_{3}, (F_{1}(u_{1}),F_{2}(F_{1}(u_{1}))$.

• $H_{2}-query$. Challenger C maintains a list $L_{4}=(r_{i},u_{i},z_{i},c_{i})$. When the adversary A issues a query for $(r,u=u_{1}\parallel u_{2})$, the Challenger C search it in list first, if there exist corresponding tuple (r, u, c, z), return C; otherwise, randomly chooses vector $Z\in D_{\sigma }^{m}, C\in \{v:v\in \{-1,0,1\}^{m}\}$, $H_{1}-query$ $AZ-(T_{2}\parallel T_{3})modq$ for $\alpha$, let $u_{1}^{'}=\alpha \bigoplus r$, and according to $u_{1}^{'}=F_{1}(u_{1})\parallel (F_{2}(F_{1}(u_{1}))\bigoplus u_{1})$, and Update $L_{3}=(L_{3}, (F_{1}(u_{1}),F_{2}(F_{1}(u_{1}))\bigoplus u_{1})$, $L_{2}=(L_{2}, (u_{1},F_{1}(u_{1})))$. Update $L_1=(r,u,c,z)$ where r, u satisfied $H_{2}(r,u_{2})=C$, then return C.

• $Psign-query$. To obtain a proxy signature on message u, adversary search it in $L_{4}$, if Challenger C find a match tuple(r, u, c, z), then output(r,z) as a response; otherwise, randomly choose vector $C\in \{-1,0,1\}^{k_{1}+k_{2}}$, $Z \in D_{\sigma } ^{m}$, adversary A $H_{1}-query$ $AZ-T_{2}\parallel T_{3}C$ for $\alpha$, $F_1$-query and $F_2$-query for $(u_1,F_{1}(u_{1}))$ and $(F_{1}(u_{1}),(F_{2}(F_{1}(u_{1}))\bigoplus u_{1}))$, let $r=\alpha \bigoplus u_{1}^{'}$. Update $L_1=(L_1,(r,u,c,z))$ where $H(r,u_{2})=C$. then return $(r, u_{2})$ and $u_{2}$.

$\mathbf {Forgery.}$ The adversary finally outputs a valid forgery $(r,z,u_{2}^{*})$ on message $u^{*}=u_{1}^{*}\parallel u_{2}^{*}$.

The specific example SIS problem: In order to solve SIS problem, adversary A should find a small vector $x\in \varLambda _{q}^{\perp }(A)$, Challenger responses to adversary A with different results when adversary A repeats his queries. According to General Forking Lemma [24], adversary A finally gets a valid forgery $(r^{\#},Z^{\#},u_{2}^{*})$ on same message $u^{*}=u_{1}^{*}\parallel u_{2}^{*}$ with non-negligible probability, and the following equation satisfied, where $C^{\#}=H_{2}(r^{\#},u_{2}^{*}), H_{2}(r^{*},u_{2}^{*})=C^{*}$.

According to the above construction, we can see that for any message u:

• $H_{2}(r^{\#},u_{2}^{*})\ne H_{2}(r^{*},u_{2}^{*})$

• $AZ^{\#}-(T_{2}\parallel T_{3}) H_{2}(r^{\#},u_{2}^{*})-(AZ^{*}-(T_{2}\parallel T_{3}) H_{2}(r^{*},u_{2}^{*}))$=$A(Z^{\#}-Z^{*}-(S_{2}\parallel S_{3})C^{\#}+(S_{2}\parallel S_{3})C^{*})$

• $\parallel Z^{\#}\parallel \le 2\sigma \sqrt{m},\parallel Z^{*}\parallel \le 2\sigma \sqrt{m}$,$\parallel (S_{2}\parallel S_{3})C^{\#}\parallel \le d_{k_{1}+k_{2}}\sqrt{m}$, and $\parallel (S_{2}\parallel S+_{3})C^{*}\parallel d_{k_{1}+k_{2}}\sqrt{m}$

• $\parallel Z^{\#}-Z^{*}-(S_{2}\parallel S+_{3})C^{\#}+(S_{2}\parallel S+_{3})C^{*}\parallel \le (4\delta +2d_{k_{1}+k_{2}})\sqrt{m}$

According to [21], $Z^{\#}-Z^{*}+(S_{2}\parallel S_{3}C^{\#}-S_{2}\parallel S_{3})C^{*}\ne 0$ with probability at least 1/2, so $Z^{\#}-Z^{*}+((S_{2}\parallel S_{3})C^{\#}-(S_{2}\parallel S_{3})C^{*})\ne 0$ with non-negligible ability. Our lattice-based proxy signature scheme with message recovery is Unforgeability.

6 Efficiency Analysis

When we have a efficiency analysis of our scheme, We take signature size, computation time and energy cost into consideration. In this section, we analyse our scheme’s efficiency by comparing it with some existing proxy signature schemes from the length of secret delegation key, proxy signature message and total time cost. In order to simplify the presentation, We define R = Rejection sampling algorithm computation cost, T = TrapGen algorithm computation cost, S = SamplePre algorithm computation cost, B = BasisDel algorithm computation cost, E = ExtBasis algorithm computation cost, M = Multiplication of matrix, M = Multiplication of vector, M= $m=O(n\log n)$, $q=O(n^{2})$, $M=\omega (\sqrt{\log m})$, $S_{1},S_{2}\in \{-1,\cdots , 0,\cdots , 1\}^{m\times k_{1}}$, $\sigma =12k_{2}\sqrt{m}$. Table 1 are given the detailed sizes and time of the comparison.

Table 1. Comparison of related proxy signature schemes

From Table 1, it is obvious that the total length (signed message and signature) of our message recovery scheme is less than other proposed schemes which is the foremost advantage of a lattice-based proxy signature scheme with message recovery, besides, we can find that in proxy signature [17, 18], they mainly use TrapGen algorithm, SamplePre algorithm, BasisDel algorithm and ExtBasis algorithm which are very time consuming, while in our scheme and [14], based on Lyubashevsky’s rejection sampling algorithm, we mainly use the multiplication of matrix and vector, and due to different technique used in verification, we are almost twice as fast as [14].

When we let $k+l=l_1+l_2$ and take security parameters mentioned in [21] into consideration $(n=512,q=2^{57},d=1)$, we can have a direct comparison with [19] as following

$$\begin{aligned} \triangle _{Length of Proxy Signature and Message}\approx l_2+mlog(12\delta )=(l_2+163000) bits \end{aligned}$$

(2)

Refer to the comparison proposed in [22], 1 bit transmission cost more energy than 32 bits simple operation, in that case, even we increase simple computation (like hash and XOR) in message recovery technology, our scheme still cost much less energy than [19]’s in pracRef1tical situation. According to the above analysis, our message recovery proxy signature scheme is more efficient than these existing schemes in signature size, time and energy cost.

7 Conclusion

With the development of quantum computers, constructing an efficient quantum-secure proxy signature scheme enjoys priority. Lattice-based signature occupies a position of particular interest, as it relies on well-studied problems and comes with uniquely strong security guarantees, such as worst-case to average case reductions. In this work, we proposed an efficient lattice-based proxy signature with message recovery which is possible to be the first proxy signature scheme with message recovery that can resist known quantum attack, and we give a formal proof of it’s security in the random oracle model. In addition, compared with some existing proxy signature schemes, our scheme is more efficient than others in signature length, signature time and energy cost. Contribution to rich theoretical foundation of Lattice Cryptography, we will design more efficient lattice-based signature schemes with message recovery in the future.