1 Introduction

Multilinear maps [ 1 ] that provide many applica- tions in cryptography, was proposed as an ex- tension of bilinear maps. Unlike bilinear maps, which are known to be constructed using pairing of elliptic curves, there was no method to construct a multilinear maps before the year 2013. This long-standing open problem was finally solved by Garg et al. [ 2 ]. They proposed the concept of graded encoding schemes, which is an approximate construction of multilinear maps. In their work, ideal lattices are used to build an instantiation of graded encoding schemes which is called GGH13.

Graded encoding schemes are one of the most im- portant cryptographic tools that provide many appli- cations in cryptography such as secret sharing scheme [ 3 ], witness encryption [ 4 ], multipartite key exchange [ 2 ], functional encryption [ 5 ], obfuscation [ 6 , 7 ], aggre- gate signature scheme [ 8 ] and so on. In this paper, we offer another application of graded encoding schemes in signature schemes.

Digital signature schemes [ 9–11 ] are useful crypto- graphic primitives in practice. They provide many uses for data security in a variety of applications, in- cluding authenticity and non-repudiation, securing software updates, the use in secure communication protocols SSL/TLS and more. In one-time digital sig- nature schemes the signer is limited to sign a single message [ 12 ]. These schemes are important crypto- graphic primitives that used as the core of the design of many-time digital signature schemes. One-time sig- nature schemes have other important applications like digital signatures with forward security property [ 13 , 14 ], network routing protocols [ 15 ] and so on.

So far, several techniques have been presented for constructing one-time digital signature schemes, one of the most interesting of which is the Winternitz one-time signature (WOTS) scheme [ 16 ]. One-time signature schemes designed using this technique play important roles in the design of both stateless and stateful many-time signature schemes [ 17–19 ]. For example, if a Merkle signature scheme is built using a WOTS type signature scheme, there is no need to put the public verification key of WOTS scheme in the signature [ 14 ]. In addition, in WOTS type signature schemes, it is possible to make a trade-off between the runtime and the size of signature [ 20–22 ].

Using the concept of “function chain”, we can give a good description of WOTS scheme. A function chain, using a function (family), produces a chain of values starting from a given point. The main idea of WOTS scheme is the use of a limited number of function chains, that are all calculated starting from random values. These values are in fact the private signing key of WOTS scheme. The public verification key is also the final values of each function chain. Finally, to calculate the signature, the message is mapped to one intermediate value of each chain.

1.1 Related Work

Along the years, several different versions of WOTS scheme have been presented for various purposes. The main idea of the WOTS scheme was first presented in [ 16 ]. Using this basic idea, the one-time digital signature schemes [ 23 , 24 ] were designed using an undetectable, collision resistant hash function. Af- terwards, a WOTS type signature scheme was intro- duced that achieve existential unforgeability under adaptive chosen message attacks (EU-CMA) security using a pseudorandom function family [ 25 ].

Under the name WOTS+, Hu¨lsing [ 26 ] later intro- duced a WOTS type signature scheme based on min- imal security requirements i.e. undetectable, second- preimage resistant, one-way hash functions. In this scheme, using the bitmasks, the need for collision re- sistant hash functions has been resolved. The security proof of WOTS+ is tight, which allows the signature size to be reduced compared to the previous WOTS type signature schemes. Therefore, WOTS+ has been given more attention than previous WOTS type sig- nature schemes. For example, the one-time signature which is used in the structure of stateless many-time signature schemes SPHINCS [ 19 ] and SPHINCS+ [ 22 ] is WOTS+. The variations of WOTS scheme that have been described so far are all vulnerable to multi- target attacks. More precisely, if an adversary has several targets to attack them, then the probability of being able to attack at least one of them is more than he can attack exactly one. There is another WOTS type signature scheme which is referred to as WOTS- T [ 20 ]. This scheme is considered as an improved version of WOTS+ that resists against multi-target attacks. The major difference between WOTS-T and WOTS+, which makes WOTS-T resistant to multi- target attacks, is that it uses an addressing scheme. Using this, a new bitmask is produced every time the used hash function is called.

As discussed above, using the concept of func- tion chain, there exists a good description of WOTS scheme. Considering this fact, the difference between all WOTS type signature schemes is in the method that the used function chain is constructed. In the function chain used in each of the WOTS type signa- ture schemes, a function has been used that must be repeated a certain number of times in order to gener- ate the intermediate values of the chains. The total number of production of each intermediate value in the key generation, signature and verification algo- rithms of this signature schemes is two. Thus, reduc- ing the number of required intermediate values, can reduce the number of operations required for these algorithms.

In this work, we propose WOTS-GES, a new vari- ant of the Winternitz one time signature scheme in which the need for computing all of the intermediate values of the chains is eliminated. More precisely, in each key generation, signature and verification algo- rithms of the proposed signature scheme, it is neces- sary to calculate only one intermediate value in each function chain. This significantly reduces the number of required operations needed to calculate these al- gorithms. To achieve this results, we have used the concept of “leveled” multilinear maps which is also referred to as graded encoding schemes. We also show how the used graded encoding scheme can be instan- tiated using GGH13.

The rest of the paper is as follows. In Section 2, we review the required concepts. In Section 3, we give description of the generic WOTS scheme. Sec- tion 4, describes WOTS-GES based on graded en- coding schemes. The security of WOTS-GES is pro- posed in Section 5. In Section 6, the instantiation of WOTS-GES using GGH13 is discussed and finally in Section 7, conclusions are provided.

2 Preliminaries

This section reviews some required concepts which are used throughout this paper. Most of the content in this section is devoted to graded encoding schemes. But first of all, we provide a simple definition of multilinear maps [ 1 ].

Definition 2.1. Suppose G₁, . . . , G_k and G_T be groups of prime order q. Then, a k-multilinear map e : G₁ × . . . × G_k → G_T is a map with the following properties:

(1) Multilinear: For a₁, . . . , a_k ∈ Z*_q and arbitrary elements g₁∈G₁, . . . , g_kG_k, it is hold that $e{\left(g_1^{a_1}\mathrm{,\; ...\; ,}{g}_k^{a_k}\right)=e\left(g_1\mathrm{,\; ...\; ,}{g}_k\right)}^{a_1\mathrm{,\; ...\; ,}{a}_k}.$

(2) Non-degenerate: If g_i ∈ G_i, 1 ≤ i ≤ k be a generator of G_i, then e(g₁, . . . , g_k) is also a generator of G_T .

(3) Computable: For arbitrary elements g₁ ∈ G₁ , . . . , g_k ∈ G_k , the resulting e(g₁ , . . . , g_k) can be computed efficiently.

2.1 Graded Encoding Schemes

Garg et al. [ 2 ] proposed the concept of graded encod- ing schemes, which is an approximate construction of multilinear maps as follows:

Definition 2.2. For the family of sets $S=\{S_i^{\mathrm{(\alpha )}}\subset {\left\{\mathrm{0,1}\right\}}^{*}|0\le i\le k,\alpha \in R\}$ in which R is a ring, assume that for each constant 0 ≤ i ≤ k, $\{S_i^{\mathrm{(\alpha )}}\alpha \in R\}$ the sets be disjoint. Using this assumption, a k-graded encoding scheme GES(R; S) can be defined with the following procedures:

● InstGen(1^λ, k) : The inputs of randomized "instance-generation" procedure are a security parameter λ and also multilinearity parameter k. The corresponding output is (params; P_zt) in which P_zt and params are a zero-test parameter and description of the k-graded encoding scheme, respectively.

● Samp(params) : The input of randomized "ring sampler" procedure is params. The output of this procedure is $a\in S_0^{\mathrm{(\alpha )}}$ that is a "level-zero encoding" (Here α ∈ R is a random and nearly uniform element).

● Enc(params, i, a) : The inputs of (possibly randomized) "encoding" procedure are params, an index i ≤ k and also a "level-zero" encoding $a\in S_0^{\mathrm{(\alpha )}}$. The corresponding output is $u\in S_i^{\mathrm{(\alpha )}}$ that is a "level-i" encoding for the same element α ∈ R.

Obviously for 1 ≤ i ≤ k, in order to obtain a level-i encoding, we first get a level-0 encoding of α using the ring sampler procedure and then get a level-i encoding of α using the encoding procedure.

● Add(params, i, u₁, u₂) : The inputs of "addition" procedure are params, an index i ≤ k and two level-i encodings $u_1\in S_i^{\left({\alpha }_1\right)}$ and $u_2\in S_i^{\left({\alpha }_2\right)}$ . This procedure computes Add(params, i, u₁, u₂) = u₁ + u₂ ∈ $S_i^{({\alpha }_1+{\alpha }_2)}$ in which α₁ + α₂ is addition in the ring R.

More generally, for a collection of encodings $u_j\in S_i^{\left({\alpha }_j\right)}$ where j = 1, ... , h, it is hold that u₁ + ... + u_h ∈ $S_i^{({\alpha }_1+\mathrm{...}+{\alpha }_h)}$.

● Neg(params, i, u₁) : The inputs of "negation" procedure are params, an index i ≤ k and a level-i encodings $u_1\in S_i^{\left({\alpha }_1\right)}$. This procedure computes Neg(params, i, u₁) = -u₁ ∈ ${\mathrm{-u}}_1\in S_i^{\left({\mathrm{-\alpha }}_1\right)}$ in which -α₁ is negation in the ring R.

● Mul(params, i₁, u₁, i₂, u₂) : The inputs of "multiplication" procedure are params, indices i₁, i₂ with i₁ + i₂ ≤ k, a level-i₁ encoding $u_1\in S_{\mathrm{i1}}^{\left({\alpha }_1\right)}$ and also a level-i₂ encoding $u_2\in S_{\mathrm{i2}}^{\left({\alpha }_2\right)}$ . The output of this procedure is Mul(params, i₁, u₁, i₂, u₂) = u₁ × $u_2\in S_{i_1+i_2}^{\left({\alpha }_1.{\alpha }_2\right)}$ in which α₁ . α₂ is multiplication in the ring R and i₁ + i₂ is integer addition.

More generally, for a collection of h encodings $u_j\in S_{\mathrm{ij}}^{\left({\alpha }_j\right)}$ with Ph ${\sum }_{\mathrm{j=1}}^h{i}_j\le k$ , it is hold that $u_1\times u_2\in S_{i_1\mathrm{+\; ...\; +}{i}_h}^{\left({\Pi }_{\mathrm{j=1}}^h{\alpha }_j\right)}$.

● isZero(params, P_zt, u) : The inputs of "zero-test" procedure are params, P_zt and u. The output of this procedure is 1 if $u\in S_k^{\left(0\right)}$ and 0 otherwise.

● Ext(params, P_zt, u) : The inputs of "extraction" procedure are params, P_zt and $u\in S_k^{\left(\alpha \right)}$ , The output of this procedure is s ∈ {0,1}^λ with the following properties:

a)For every α ∈ R and two level-k encodings u₁, $u_2\in S_k^{\left(\alpha \right)}$ , it is hold that

Ext(params, P_zt, u₁) = Ext(params, P_zt, u₂) (1)

b) The following distribution over {0,1}^λ is nearly uniform (λ is the security parameter):

$\left\{\mathrm{Ext}\right(\mathrm{params,}{P}_{\mathrm{zt}},u\left)\right|u\in S_k^{\left(\alpha \right)},\alpha \in R\}$

Garg et al. proposed GGH13 which is a k-graded encoding scheme that is parameterized by λ and the multilinearity parameter k ≤ poly(λ). GGH13 is a realization of a k-graded encoding scheme with several changes to the above definition. The important change relevant to our signature scheme is in the extraction procedure: the probability that the output of the extraction procedure of GGH13 is the same for two different level-k encodings of α is not 1. Thus, the property a) of the extraction procedure is replaced by a weaker requirement:

a') Suppose that a ← Samp(params) with $a\in S_0^{\left(\alpha \right)}$ . Then, if the (randomized) encoding procedure is run twice on a to obtain two level-k encodings $u_1,u_2\in S_k^{\left(\alpha \right)}$ :

Pr[Ext(params, P_zt, u₁) = Ext(params, P_zt, u₂)] ≥ 1 - negl(λ)

In this paper, we work with the Definition 2.2, in which the probability that the output of the extraction procedure is the same λ bit string for two different level-k encodings of α is 1. If we want to use the extraction procedure of GGH13, we must consider the negligible probability that Ext(params, P_zt, u₁) 6= Ext(params, P_zt, u₂). Thus, for every α ∈ R, we can use Ext(params, P_zt, $S_k^{\left(\alpha \right)}$ ) to denote this λ bit string.

Remark 2.1. We can assume that a level 1 encoding of 1 ∈ R is published as part of the instancegeneration procedure, namely an element y ∈ $S_1^{\left(1\right)}$ [27].

2.1.1 Graded Discrete-Logarithm (GDL) Problem

The analog of discrete logarithm problem in a k-graded encoding scheme GES(R, S) can be defined as the following: consider a level-i encoding $u_i\in S_i^{\left(\alpha \right)}$ in which 1 ≤ i ≤ k and α ∈ R, it must be hard to output a level-j encoding u_j$u_j\in S_j^{\left(\alpha \right)}$ , where j < i. Here, the value i is chosen uniformly at random from the interval [1, k].

More formally, the following experiment can be defined between a challenger C and an adversary B:

Experiment${\mathrm{Exp}}_{\mathrm{GES}}^{\mathrm{GDL}}$ (B, λ):

(1) Using λ and also the multilinearity parameter k, the challenger C runs (params, P_zt) ← InstGen(1^λ, k) to get description of a k-graded encoding scheme.

(2) Now, C firstly runs $a\in S_0^{\left(\alpha \right)}$ ← Samp(params) to get a level-zero encoding of a random and nearly uniform element α ∈ R. The challenger C also runs u_i ← Enc(params, i, a) to get a level-i encoding $u_i\in S_i^{\left(\alpha \right)}$ . Next, C sends (params, P_zt, u_i) to the adversary B.

(3) Finally, B outputs a value u_j.

(4) The output is defined to be 1 iff $u_j\in S_j^{\left(\alpha \right)}$ and j < i.

The success probability of an adversary B in the experiment ${\mathrm{Exp}}_{\mathrm{GES}}^{\mathrm{GDL}}$ (B, λ can be defined as follows.

${\mathrm{Succ}}_{\mathrm{GES}}^{\mathrm{GDL}}\left(\mathrm{B,}\lambda \right)=\mathrm{Pr}\left[{\mathrm{Exp}}_{\mathrm{GES}}^{\mathrm{GDL}}\right(\mathrm{B,}\lambda )=1]$

We say that the GDL problem is hard, if for each polynomial time adversary B running in time ≤ t, ${\mathrm{Succ}}_{\mathrm{GES}}^{\mathrm{GDL}}\left(\mathrm{B,}\lambda \right)$ is a negligible function of λ. In other words,

${\mathrm{InSec}}^{\mathrm{GDL}}\left(\mathrm{GES,}\mathrm{t,}\lambda \right):=\underset{B}{\max }\left\{{\mathrm{Succ}}_{\mathrm{GES}}^{\mathrm{GDL}}\right(\mathrm{B,}\lambda \left)\right\}$ (2)

= negl(λ). (3)

Note that according to the Remark 2.1, the adversary B can simply get a level-j´ encoding $u_{\mathrm{j´}}\in S_{\mathrm{j´}}^{\left(\alpha \right)}$ in the above experiment, by running the multiplication procedure

$u_{\mathrm{j´}}:=u_i\times \underset{\underset{\mathrm{j´}-i\mathrm{times}}{⏟}}{y\times \mathrm{...}\times y}\in S_{\mathrm{j´}}^{\left(\alpha \right)},$ where i < j´

2.2 Digital Signature Schemes

Here, we give some required preliminaries about digital signature schemes and also security of these schemes. In the remainder of the paper, we fix some notation in order to simplify the explanation: We denote by $x\stackrel{\$}{\leftarrow }X$, if x is chosen randomly from the set X. We also write log for log₂.

Definition 2.3. Considering a message space M, a digital signature scheme Dss can be defined using the probabilistic polynomial time (PPT) algorithms (Kg, Sign, Vf):

(1) Key generation algorithm Kg(1ⁿ) takes n as the security parameter and outputs a private signing key sk and a public verification key pk.

(2) Signature algorithm Sign(sk,M) takes as input a message M and also the private signing key sk. Then, if M ∈ M, the algorithm outputs a signature σ for M under sk.

(3) Verification algorithm Vf(pk, σ,M) takes as input the message M, the signature σ and the public verification key pk. The algorithm outputs 1 iff σ is a valid signature on M under pk.

In a Dss = (Kg, Sign, Vf), for every sk; pk which are outputs of Kg(1ⁿ) and every M ∈ M, the following correctness condition must be satisfied:

Vf(M, Sign(sk,M), pk) = 1

2.2.1 EU-CMA Security

We now define "existential unforgeability under adaptive chosen message attacks (EU-CMA)" which is the standard security notion for any digital signature scheme Dss = (Kg, Sign, Vf). EU-CMA security can be defined using the following experiment between a challenger C and an adversary A. In the following, we use the notation Dss(1ⁿ) for a Dss = (Kg, Sign, Vf) with the security parameter n.

Experiment ${\mathrm{Exp}}_{\mathrm{Dss}\left(1^n\right)}^{\mathrm{EU-CMA}}$ (A):

(1) C runs the key generation algorithm Kg(1ⁿ) to generate a key pair (sk, pk) and sends the public verification key pk to A.

(2) Suppose that Sign(sk, ^.) be an oracle which for every message M ∈ M, returns the signature Sign(sk,M). Here, we denote by A^Sign(sk,.) the oracle access to Sign(sk, ^.) for A. Let also that ${\left\{\right(M_i,{\sigma }_i\left)\right\}}_{\mathrm{i=1}}^q$ be the query-answer pairs of Sign(sk, ^.).

(3) The adversary then outputs (M*, σ*).

(4) The output of ${\mathrm{Exp}}_{\mathrm{EU-CMA}}^{\mathrm{Dss}\left(1^n\right)}\left(A\right)$ is defined to be 1 iff Vf(M*, σ*, pk) = 1 and (M* ∉ ${\left\{M_i\right\}}_{\mathrm{i=1}}^q$.

We define the success probability of A in the experiment ${\mathrm{Exp}}_{\mathrm{EU-CMA}}^{\mathrm{Dss}\left(1^n\right)}\left(A\right)$ as

${\mathrm{Succ}}_{\mathrm{EU-CMA}}^{\mathrm{Dss}\left(1^n\right)}\left(A\right)\mathrm{Pr}\left[{\mathrm{Exp}}_{\mathrm{EU-CMA}}^{\mathrm{Dss}\left(1^n\right)}\right(A)=1]$ .

Now, we give the definition of EU-CMA security as follows.

Definition 2.4. Let n, t, q ∈ N and t, q = Poly(n). We say that a signature scheme Dss = (Kg, Sign, Vf) is EU-CMA-secure, if for all PPT adversaries A^Sign(sk,.) running in time at most t and making at most q queries, the maximum success probability InSec^EU-CMA(Dss(1ⁿ); t, q) is a negligible function of n:

${\mathrm{InSec}}^{\mathrm{EU-CMA}}\left(\mathrm{Dss}\right(1^n\left);\mathrm{t,\; q}\right):=\underset{A}{\max }\left\{{\mathrm{Succ}}_{\mathrm{EU-CMA}}^{\mathrm{Dss}\left(1^n\right)}\right(A\left)\right\}$ (4)

$=\mathrm{negl}\left(n\right)$ . (5)

Note that for any one-time signature (OTS) scheme, the number of oracle queries of A in the above experiment is restricted to one, i.e. q = 1.

3 Description of the Generic WOTS

Here, we give description of the generic WOTS scheme. Before defining WOTS, we first recall the definition of function chain.

Definition 3.1. Let n ∈ N, D and K be the security parameter, domain and key space, respectively such that the length of every X ∈ D and ck ∈ K be polynomial in n. A function chain C = (I, ε) consists of the following PPT algorithms:

• The initialization algorithm I(1ⁿ, λ) takes as input a chain length parameter λ ∈ N and also the security parameter n and outputs a public value ck ∈ K which is called "chain key".

• The evaluation algorithm ${\epsilon }_{\mathrm{ck}}^{\mathrm{i,j}}\left(X\right)$ takes as input a public chain key ck, an interval i, j ∈ N, 0 ≤ i < j ≤ λ, and a value X ∈ D which is the ith value of the chain and outputs Y ∈ D, the jth value of the chain.

For every n, λ ∈ N, every ck ∈ K which is output of I(1ⁿ, λ), every i, j, m ∈ N such that 0 ≤ i ≤ j ≤ m ≤ λ and every X ∈ D, it must hold that

${\epsilon }_{\mathrm{ck}}^{\mathrm{j,m}}\left({\epsilon }_{\mathrm{ck}}^{\mathrm{i,j}}\right(X\left)\right)={\epsilon }_{\mathrm{ck}}^{\mathrm{i,m}}\left(X\right)$

We now describe the generic W-OTS using a function chain C = (I, ε). This digital signature is parameterized by

• m : the binary message length.

• n : the security parameter.

• w > 1 : the Winternitz parameter. This parameter determines the time-memory trade-off.

• l: the number of elements in aW-OTS signature, public verification key and private signing key, which is computed as

$l_1=⸢\frac{m}{\log \left(w\right)}⸣$, $l_2=⸤\frac{\log (l_1\stackrel{.}{(}w-1))}{\log \left(w\right)}⸥+1$, l = l₁ + l₂

Key Generation Algorithm (Kg(1ⁿ)): On input of the security parameter n, this algorithm chooses the private signing key sk = (sk₁, . . . , sk_l) $\stackrel{\$}{\leftarrow }$D^l. Next, a public chain key ck is obtained using the initialization algorithm I(1ⁿ, λ) of the function chain. Finally, the public verification key pk can be computed as

$\mathrm{pk}=\left({\mathrm{pk}}_0,{\mathrm{pk}}_1\mathrm{,\; .\; .\; .\; ,}{\mathrm{pk}}_l\right)=\left(\mathrm{ck,}{\epsilon }_{\mathrm{ck}}^{\mathrm{0,w-1}}\right({\mathrm{sk}}_l\left)\mathrm{,\; .\; .\; .\; ,}{\epsilon }_{\mathrm{ck}}^{\mathrm{0,w-1}}\right({\mathrm{sk}}_l\left)\right)$

Signature Algorithm (Sign(sk,M)): This algorithm takes as input a message M ∈ {0, 1}ⁿ and the private signing key sk. Firstly, the base w representation of M is computed, i.e. M = (b₁, . . . , b_l1 ) such that b_i ∈ {0, . . . , w - 1}. Next, the checksum

$C=\underset{\mathrm{i=1}}{\overset{l_1}{\Sigma }}(w-1-b_i)$

and also its base w representation C = (b_l1+1, . . . , b_l) such that b_i ∈ {0, . . . , w - 1}, is computed (Note that C ≤ l₁(w - 1)). Now, the signature is computed as

$\sigma =\left({\sigma }_1\mathrm{,\; .\; .\; .\; ,}{\sigma }_l\right)=\left({\epsilon }_{\mathrm{ck}}^{\mathrm{0,}{b}_1}\right({\mathrm{sk}}_l\left)\mathrm{,\; .\; .\; .\; ,}{\epsilon }_{\mathrm{ck}}^{\mathrm{0,}{b}_l}\right({\mathrm{sk}}_l\left)\right)$

Verification Algorithm (Vf(pk, σ,M)): This algorithm takes as input the message M, the signature σ and also the public verification key pk. Firstly, the b_i, 1 ≤ i ≤ l are computed as above. Next, if the following comparison holds, the verification algorithm returns true and false otherwise:

$\left({\mathrm{pk}}_1\mathrm{,\; .\; .\; .\; ,}{\mathrm{pk}}_l\right)\stackrel{?}{=}\left({\epsilon }_{\mathrm{ck}}^{b_1\mathrm{,\; w-1}}\right({\sigma }_1\left)\mathrm{,\; .\; .\; .\; ,}{\epsilon }_{\mathrm{ck}}^{b_l\mathrm{,\; w-1}}\right({\sigma }_l\left)\right)$

4 WOTS-GES

Here, we propose our digital signature scheme WOTS-GES(k,m) based on a k-graded encoding scheme GES(R, S) with the security parameter λ. As mentioned before, this signature scheme is a new variant of WOTS scheme. Like other versions of WOTS, WOTS-GES(k,m) is parameterized by

• m : the binary message length.

• w > 1 : the Winternitz parameter. Here we suppose that w-1 is equal to the multilinearity parameter k of the k-graded encoding scheme, i.e. w-11 = k.

• l: This parameter is calculated using the parameters m and w, as described in the previous section.

Please note that according to the Remark 2.1, we can consider that there is a level 1 encoding of 1, i.e. $1_1\in S_i^{\mathrm{(1)}}$ . It is assumed that in the pre-computation phase, the encoding procedure Enc(params, i, 1₁) is run to obtain the level-i encoding $1_i\in S_i^{\mathrm{(1)}}$, where 2 ≤ i ≤ k.

Key Generation Algorithm (Kg(GES(R, S))): This algorithm takes as input the description of the k-graded encoding scheme GES(R, S). Then, the randomized ring sampler procedure Samp(params) is run to obtain l level-zero encodings $a_j\in S_0^{\left({\alpha }_j\right)}$, where α₁, . . . , α_l ∈ R are random and nearly uniform elements and 1 ≤ j ≤ l. The private signing key sk = (a₁, . . . , a_l) consists of this level-zero encodings.

Next for 1 ≤ j ≤ l, the key generation algorithm runs the encoding procedure Enc(params, k, a_j) to get l level-k encodings $u_{\mathrm{jk}}\in S_k^{\left({\alpha }_j\right)}$. Finally, the extraction procedure is run to obtain pk_j = Ext(params, P_zt, u_jk). Now, the public verification key pk is defined as pk = (pk₁, . . . , pk_l). The key generation algorithm is shown in Figure 1.

Figure 1. A schematic representation of key generation algorithm

Signature Algorithm (Sign(sk,M)): This algorithm takes as input a message M ∈ {0,1}ⁿ and also the private signing key sk = (a₁, . . . , a_l). Firstly, the base w representation of M is computed, i.e. M = (b₁; : : : ; b_l1 ) such that b_i ∈ {0, . . . ,w-1}. Next, the checksum

$C=\underset{\mathrm{i=1}}{\overset{l_1}{\Sigma }}(w-1-b_i)$

and also its base w representation C = (b_l1+1, . . . , b_l) such that b_i ∈ {0, . . . ,w-1}, is computed. Afterwards for 1 ≤ j ≤ l, the signature algorithm runs the encoding procedure Enc(params, b_i , a_i) to get the level-b_i encodings $u_{j{b}_j}\in S_{b_j}^{\left({\alpha }_j\right)}$. Now, the signature σ is defined as

$\sigma =\left({\sigma }_1\mathrm{,\; ...\; ,}{\sigma }_l\right)=\left(u_{1b_1}\mathrm{,\; ...\; ,}{u}_{l{b}_l}\right)$

The signature algorithm is shown in Figure 2. Let B = M||C, then we can conclude from the checksum that if M´ ≠ M be any other message, the corresponding B´ consists of at least one b´_j < b_j , where 1 ≤ j ≤ l.

Figure 2. A schematic representation of signature algorithm

Verification Algorithm (Vf(pk, σ, M)): This algorithm which is shown in Figure 3, takes as input the message M, the signature σ and also the public verification key pk. In this algorithm for 1 ≤ j ≤ l.

(1) Firstly, the b_js are computed as described above.

(2) Then, the verification algorithm runs the multiplication procedure Mul(params, b_j , u_jbj , k - b_j, 1_k-bj ) to compute the level-k encoding ${\mathrm{u´}}_{\mathrm{jk}}\in S_k^{\left({\alpha }_j\right)}$.

(3) Finally, the extraction procedure is run to obtain pk´_j = Ext(params, P_zt, u´_jk).

Now, if the following comparison holds, the verification algorithm returns true and false otherwise:

$\left({\mathrm{pk}}_1\mathrm{,\; ...\; ,}{\mathrm{pk}}_l\right)\stackrel{?}{=}\left({\mathrm{pk´}}_1\mathrm{,\; ...\; ,}{\mathrm{pk´}}_l\right)$

Figure 3. A schematic representation of verification algorithm

5 Security of WOTS-GES

Here, we prove the security of WOTS-GES. We explain how an adversary for WOTS-GES can be used to construct an adversary to solve the GDL problem. More formally, the GDL problem is reduced to the EU-CMA security of WOTS-GES.

Lemma 1.Let k,m ∈ N. Then, if there is any PPT adversary A who can break the proposed digital sig- nature scheme WOTS-GES(k,m), then there exists a PPT adversary B that is a solver for the GDL prob- lem such that

${\mathrm{Succ}}_{\mathrm{Dss}\left(1^n\right)}^{\mathrm{EU-CMA}}\left(A\right)\le \mathrm{kl}.{\mathrm{Succ}}_{\mathrm{Dss}}^{\mathrm{EU-CMA}}\left(\mathrm{B,\; \lambda }\right)\le \mathrm{kl}.$ (6)

Proof. Consider a PPT adversary A which acts according to the Experiment ${\mathrm{Exp}}_{\mathrm{Dss}\left(1^n\right)}^{\mathrm{EU-CMA}}\left(A\right)$ against the security of WOTS-GES(k,m), such that his success probability ${\mathrm{Succ}}_{\mathrm{Dss}\left(1^n\right)}^{\mathrm{EU-CMA}}\left(A\right)={\epsilon }_A$ is non-negligible. In the rest of the proof, we will define an adversary B which acts according to the Experiment ${\mathrm{Exp}}_{\mathrm{GES}}^{\mathrm{GDL}}\left(\mathrm{B,\; \lambda }\right)$ to solve the GDL problem in polynomial time with a non-negligible success probability SuccGDL ${\mathrm{Succ}}_{\mathrm{GES}}^{\mathrm{GDL}}\left(\mathrm{B,\; \lambda }\right)={\epsilon }_B$ and uses A as a sub-routine (Note that we have n = λ):

(1) Based on λ and the multilinearity parameter k, the challenger of the Experiment ${\mathrm{Exp}}_{\mathrm{GES}}^{\mathrm{GDL}}\left(\mathrm{B,\; \lambda }\right)$ (that is C) runs (params, P_zt) InstGen(1^λ, k) to get an explanation of a k-graded encoding scheme GES(R, S). Now, the challenger C firstly runs a ← Samp(params) to obtain a level-zero encoding $a\in S_0^{\mathrm{(\alpha )}}$, where α ∈ R is a random and nearly uniform element. Then, C runs u_i Enc(params, i, a) to get a level-i encoding $u_i\in S_i^{\mathrm{(\alpha )}}$. Next, C sends (params, P_zt, u_zi) to the adversary B.

(2) Now, B is used as a challenger for A in the Experiment ${\mathrm{Exp}}_{\mathrm{Dss}\left(1^n\right)}^{\mathrm{EU-CMA}}\left(A\right)$. So, B executes the WOTS-GES key generation algorithm Kg(GES(R, S)) to obtain a private signing key sk = (a₁, . . . , a_l), where $a_j\in S_0^{\left({\alpha }_j\right)}$ are l level-zero encodings and α₁, . . . , α_l ∈ R are random and nearly uniform elements and also a public verification key pk = (pk₁, . . . , pk_l). Suppose that (M, α) be the query-answer pair of Sign(sk, ^.) in the Step 2 of the experiment ${\mathrm{Exp}}_{\mathrm{Dss}\left(1^n\right)}^{\mathrm{EU-CMA}}\left(A\right)$and B = M∥C = (b₁, . . . , b_l). Let also that (M*, σ*) be the output of the adversary A in the Step 3 of this experiment and B* = M*∥C* = (b₁*, . . . , b_l*). Because of the checksum, the corresponding B* of the successful forgery (M*, σ*) must contain at least one b_γ* < b_γ, where 1 ≤ γ ≤ l. More precisely, the γ-th components of σ = (σ₁, . . . , σ_l) and σ* = (σ₁*, . . . , σ_l*) i.e. σ_γ and σ_γ* are a level-b_γ encoding ${\sigma }_{\gamma }\in S_{b_{\gamma }}^{\left({\alpha }_{\gamma }\right)}$ and a level-b_γ* encoding ${{\sigma }^{*}}_{\gamma }\in S_{{b^{*}}_{\gamma }}^{\left({\alpha }_{\gamma }\right)}$, respectively, where 1 ≤ γ ≤ l. In the following, the adversary B tries to conjecture the location of σ_γ and place the level-i encoding $u_i\in S_i^{\left(\alpha \right)}$ there. Hence, he will reply the signature query and finally extract a level-j encoding $u_j\in S_j^{\left(\alpha \right)}$ using the successful forgery σ*, where 0 ≤ j < i:

(a) The adversary B selects the position of a component of the private signing key sk = (a₁, . . . , a_l) choosing the index 1 ≤ 0 ≤ l uniformly at random.

(b) B considers the level-i encoding $u_i\in S_i^{\left(\alpha \right)}$ challenge as the level-i encoding of an unknown level-zero encoding ${\mathrm{a´}}_{\mathrm{\gamma ´}}=a$. Next, B runs the multiplication procedure Mul(params, i, u_i, k-i , 1_k-i) to compute the level-k encoding $u_k\in S_k^{\left(\alpha \right)}$. Afterwards, B runs the extraction procedure to compute pk´_γ´ = Ext(params, P_zt, u_k) Consequently, the manipulated public verification key pk´ is obtained as pk´ = (pk₁, . . . , pk´_γ´ , . . . , pk_l). Note that the private signing key is also changed as sk = (a₁, . . . , a´_γ´ , . . . , a_l), where a´_γ´ is unknown. Now, B sends the manipulated public verification key pk´ to A (the start of the Experiment ${\mathrm{Exp}}_{\mathrm{Dss}\left(1^n\right)}^{\mathrm{EU-CMA}}\left(A\right)$).

(c) Note that B only knows the level-j´ encodings $u_{\mathrm{j´}}\in S_{\mathrm{j´}}^{\left(\alpha \right)}$, where i ≤ j´ ≤ k as he can run the multiplication procedure Mul(params, i, u_i, j´ - i , 1_{j´ - i}) to compute the level-j´ encoding $u_{\mathrm{j´}}\in S_{\mathrm{j´}}^{\left(\alpha \right)}$. So, B can only answer the A's query M, if i ≤ b_γ´ .

(d) Also, the successful forgery (M*, σ*) is only helpful if b*_γ´ < i. In this case, the adversary B announces the level-b*_γ´ encoding $u_{{b^{*}}_{\mathrm{\gamma ´}}}\in S_{{b^{*}}_{\mathrm{\gamma ´}}}^{\left(\alpha \right)}$ as its output (Step 3 of the Experiment ${\mathrm{Exp}}_{\mathrm{GES}}^{\mathrm{GDL}}\left(\mathrm{B,\; \lambda }\right)$.

In the following, the success probability of the adversary B is calculated: As we saw in Step 2c, B can only answer the A's query M, if i ≤ b_γ´. To make computation of the success probability easier, we only consider a certain success case, i.e. i = b_γ´ . As i was selected randomly with uniform distribution from the interval [1, k], the case happens with probability k^-1.

We also pointed out that the corresponding B* of the successful forgery (M*, σ*) must contain at least one b*_γ < b_γ , where 1 ≤ γ ≤ l. This happens for γ = γ´ with probability l^-1 . Thus we have b*_γ´ < b_γ´ . Consequently, we conclude that b*_γ´ < i with probability (kl)^-1 and therefore the condition in Step 2d is fulfilled. Hence, the success probability of the adversary A can be bounded as follows:

${\epsilon }_A\le \mathrm{kl}.{\epsilon }_B$

Note that because of the Equation 1 of the extraction procedure, changing the public verification key generation method to place our challenge, does not change the public verification key. More precisely, if we choose either the key generation algorithm of WOTS-GES(k,m) or the method which is used in the proof to produce public verification key, we obtain an equal value for this key. Thus, the proof is completed.

We now conclude the following theorem using Lemma 1:

Theorem 1.Suppose that k,m ∈ N. Then, we can bound the insecurity of WOTS-GES against an EU-CMA attack by

${\mathrm{InSec}}^{\mathrm{EU-CMA}}\left(\mathrm{WOTS-GES}\right(\mathrm{k,\; m}\left)\mathrm{;\; t,\; 1}\right)\le \mathrm{kl}.{\mathrm{InSec}}^{\mathrm{GDL}}\left(\mathrm{GES;\; t´,\; \lambda }\right)$ . (7)

with t´ = t + 5l.

Proof. Firstly note that the Equation 7 can be simply derived from Equation 6 and also from Definitions 2 and 5. The time t´ = t + 5l is also the maximum runtime required by the adversary A (which behaves according to the Definition 2.4) plus the time required to execute the three algorithms of WOTS-GES once (follow the proof of Lemma 1).

6 Instantiation using GGH13

To use WOTS-GES, graded encoding scheme GES(R, S) must be instantiated. In this section, we discuss how GES(R, S) can be instantiated using GGH13.

The graded encoding scheme GGH13 is parameterized by λ and also multilinearity parameter k ≤ poly(λ). Using these parameters, consider the cyclotomic ring $R=\frac{Z}{<X^n+1>}$, in which n = $\tilde{O}$ (kλ²) is a power of 2. Also, let that the modulus q = 2^kλ defines the quotient ring $R_q=\frac{R}{\mathrm{qR}}$. Finally, consider the quotient ring $\mathrm{QR}=\frac{R}{I}$ in which I =< g > is a principal prime ideal and g is a secret short vector drawn from the discrete Gaussian distribution $q\leftarrow D_{Z^n\mathrm{,\; \sigma }}$ in which $\sigma =\tilde{O}\left(\sqrt{n}\right)$. There is also another secret vector z ∈ R_q, that selected uniformly at random.

In the graded encoding scheme GGH13, the quotient ring $\mathrm{QR}=\frac{R}{I}$ plays the role of ring R in Definition 2.2. More precisely, elements of QR are what are encoded.

A level-zero encoding of an arbitrary cost r+I ∈ QR is a short vector of r + I. It can be proved that the size of level-zero encodings is bounded by λn² (with high probability) [27]. On the other hand, the private signing key sk = (a₁, . . . , a_l) of the signature scheme WOTS-GES consists of l level-zero encodings. Consequently, the size of private signing key sk is bounded by lλn².

Also, a level-i encoding of a cost r+I ∈ QR, where 1 ≤ i ≤ k, is a vector of the form $\frac{c}{z^i}\in R_q$ in which c ∈ r + I and $\parallel c\parallel <q^{\frac{1}{8}}$. Thus, the size of $\frac{c}{z^i}\in R_q$ is bounded by qn. On the other hand, we know that the signature σ = (σ₁, . . . , σ_l) of a given message M using WOTS-GES, consists of l level-i encodings, where 0 ≤ i ≤ k. Therefore, signature σ consists of l level-i encodings which size of each is at most either λn² or qn.

Finally, as described in Definition 2.2, the output of the extraction procedure is a λ bit string. On the other hand, the public verification key pk = (pk₁, . . . , pk_l) is made up of l extraction procedure outputs. Thus, the size of the public verification key is lλ bits.

In [28], GGHLite, an efficient version of GGH13 is presented in which the size of some parameters has been improved. Thus, instantiating the used graded encoding scheme of WOTS-GES using GGHLite can improve the efficiency of WOTS-GES.

7 Conclusion

Here, we provide a comparison for the number of operations required by the key generation, signature and verification algorithms of WOTS-GES scheme and other WOTS scheme variants in the literature [16, 20, 23-26]. We have summarized the results in Table 1.

Table 1. Comparison of the computational complexities

$\begin{array}{ccc}\mathrm{Step}& \mathrm{WOTS\; schemes\; [16,\; 20,\; 23-26]}& \mathrm{proposed\; scheme}\\ \mathrm{Public\; verification\; key\; generation}& \mathrm{lk}.T_{\mathrm{fc}}& l.(T_{\mathrm{enc}}+T_{\mathrm{ext}})\\ \mathrm{Signature\; algorithm}& \left({\Sigma }_{\mathrm{i=1}}^l{b}_i\right).T_{\mathrm{fc}}& l.T_{\mathrm{enc}}\\ \mathrm{Verification\; algorithm}& \left({\Sigma }_{\mathrm{i=1}}^l\right(k-b_i\left)\right).T_{\mathrm{fc}}& l.(T_{\mathrm{mul}}+T_{\mathrm{ext}})\end{array}$

In this table, we have assumed that the Winternitz parameter minus one is equal to the multilinearity parameter k of the used k-graded encoding scheme, i.e. w-1 = k. We have also used the following notations to analyze the complexities of the proposed scheme:

• T_fc: The time required to execute one iteration of the used function chain.

• T_enc: The time required to execute the encoding procedure of the used k-graded encoding scheme.

• T_ext: The time required to execute the extraction procedure of the used k-graded encoding scheme.

• T_mul: The time required to execute the multiplication procedure of the used k-graded encoding scheme.

From the comparison in the table, we can see that the number of operations required by the three algorithms of WOTS-GES is less than that of other WOTS scheme variants. In [29], the first practical implementation of graded encoding schemes is presented in which the efficiency of GGHLite has also been improved. Using our results along with the practical implementations of graded encoding schemes, we can obtain an efficient one-time digital signature scheme for various applications [13-15].

References

1. Dan Boneh and Alice Silverberg. Applications of multilinear forms to cryptography. Contem- porary Mathematics, 324(1):71–90, 2003.
2. Sanjam Garg, Craig Gentry, and Shai Halevi. Candidate multilinear maps from ideal lattices. In Annual International Conference on the The- ory and Applications of Cryptographic Tech-niques, pages 1–17. Springer, 2013.
3. Massoud Hadian Dehkordi and Hossein Oraei. How to construct a verifiable multi-secret sharing scheme based on graded encoding schemes. IET Information Security, 13(4):343–351, 2019..
4. Sanjam Garg, Craig Gentry, Shai Halevi, and Daniel Wichs. On the implausibility of differing-inputs obfuscation and extractable witness en- cryption with auxiliary input. Algorithmica, 79(4):1353–1373, 2017.
5. Huijia Lin and Stefano Tessaro. Indistinguisha- bility obfuscation from trilinear maps and block- wise local prgs. In Annual International Cryptol- ogy Conference, pages 630–660. Springer, 2017.
6. Sanjam Garg, Craig Gentry, Shai Halevi, Mar- iana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM Jour- nal on Computing, 45(3):882–929, 2016.
7. Prabhanjan Ananth, Aayush Jain, and Amit Sa- hai. Robust transforming combiners from indis- tinguishability obfuscation to functional encryp- tion. In Annual International Conference on the Theory and Applications of Cryptographic Tech- niques, pages 91–121. Springer, 2017.
8. Susan Hohenberger, Amit Sahai, and Brent Wa- ters. Full domain hash from (leveled) multilinear maps and identity-based aggregate signatures. In Annual Cryptology Conference, pages 494–512. Springer, 2013.
9. Jia Yu, Hui Xia, Huawei Zhao, Rong Hao, Zhangjie Fu, and Xiangguo Cheng. Forward- secure identity-based signature scheme in un-trusted update environments. Wireless Personal Communications, 86(3):1467–1491, 2016.
10. O¨ zgu¨r Dagdelen, David Galindo, Pascal V´eron, Sidi Mohamed El Yousfi Alaoui, and Pierre-Louis Cayrel. Extended security arguments for signa- ture schemes. Designs, Codes and Cryptography, 78(2):441–461, 2016.
11. Daofeng Li, Haiqiang Chen, Cheng Zhong, Taoshen Li, and Feng Wang. A new self-certified signature scheme based on ntrus ing for smart mobile communications. Wireless Personal Com- munications, 96(3):4263–4278, 2017.
12. Leslie Lamport. Constructing digital signatures from a one-way function. Technical report, Cite- seer, 1979.
13. Tal Malkin, Daniele Micciancio, and Sara Miner. Efficient generic forward-secure signatures with an unbounded number of time periods. In In- ternational Conference on the Theory and Appli- cations of Cryptographic Techniques, pages 400–417. Springer, 2002.
14. Johannes Buchmann, Erik Dahmen, and An- dreas Hu¨lsing. Xmss-a practical forward secure signature scheme based on minimal security as- sumptions. In International Workshop on Post- Quantum Cryptography, pages 117–129. Springer, 2011.
15. Ralf Hauser, Tony Przygienda, and Gene Tsudik. Reducing the cost of security in link-state rout- ing. In Proceedings of SNDSS’97: Internet Soci- ety 1997 Symposium on Network and Distributed System Security, pages 93–99. IEEE, 1997.
16. Ralph C Merkle. A certified digital signature. In Conference on the Theory and Application of Cryptology, pages 218–238. Springer, 1989.
17. Andreas Hu¨lsing, Christoph Busold, and Jo- hannes Buchmann. Forward secure signatures on smart cards. In International Conference on Selected Areas in Cryptography, pages 66–80. Springer, 2012.
18. Andreas Hu¨lsing, Lea Rausch, and Johannes Buchmann. Optimal parameters for xmss mt. In International Conference on Availability, Re- liability, and Security, pages 194–208. Springer, 2013.
19. Daniel J Bernstein, Daira Hopwood, Andreas Hu¨lsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko Wilcox-O’Hearn. Sphincs: practical stateless hash-based signa- tures. In Annual international conference on the theory and applications of cryptographic tech- niques, pages 368–397. Springer, 2015.
20. Andreas Hu¨lsing, Joost Rijneveld, and Fang Song. Mitigating multi-target attacks in hash- based signatures. In Public-Key Cryptography–PKC 2016, pages 387–416. Springer, 2016.
21. Jean-Philippe Aumasson and Guillaume Endig- noux. Improving stateless hash-based signatures. In Cryptographers’ Track at the RSA Conference, pages 219–242. Springer, 2018.
22. Jean-Philippe Aumasson, Daniel J Bernstein, Christoph Dobraunig, Maria Eichlseder, Scott Fluhrer, Stefan-Lukas Gazdag, Andreas Hu¨lsing, Panos Kampanakis, Stefan K¨olbl, Tanja Lange, et al. Sphincs+. 2019.
23. Alejandro Hevia and Daniele Micciancio. The provable security of graph-based one-time sig- natures and extensions to algebraic signature schemes. In International Conference on the Theory and Application of Cryptology and Infor- mation Security, pages 379–396. Springer, 2002.
24. Chris Dods, Nigel P Smart, and Martijn Stam. Hash based digital signature schemes. In IMA International Conference on Cryptography and Coding, pages 96–115. Springer, 2005.
25. Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas Hu¨lsing, and Markus Ru¨ckert. On the security of the winternitz one-time signature scheme. In International conference on cryptol- ogy in Africa, pages 363–378. Springer, 2011.
26. Andreas Hu¨lsing. W-ots+–shorter signatures for hash-based signature schemes. In International Conference on Cryptology in Africa, pages 173–188. Springer, 2013.
27. Sanjam Garg. Candidate Multilinear Maps. PhD thesis, University of California Los Angeles, 2013.
28. Adeline Langlois, Damien Stehl´e, and Ron Ste- infeld. Gghlite: More efficient multilinear maps from ideal lattices. In Annual International Con-ference on the Theory and Applications of Cryp- tographic Techniques, pages 239–256. Springer, 2014.
29. Martin R Albrecht, Catalin Cocis, Fabien Laguil- laumie, and Adeline Langlois. Implementing can- didate graded encoding schemes from ideal lat- tices. In International Conference on the Theory and Application of Cryptology and Information Security, pages 752–775. Springer, 2015.