# Winternitz Signature Scheme Using Nonadjacent Forms.

1. IntroductionRecent research progress on quantum computers has brought postquantum cryptography to the forefront to protect against attacks by quantum computers. Once quantum computers are developed, most modern cryptographic systems will become insecure. Particularly, it would cause catastrophic damage to public key cryptography. Most modern public key cryptographic algorithms are secure under the assumption that the integer factorization and the discrete logarithm problem are computationally infeasible. However, quantum computers can solve these problems using Shor's algorithm [1] in polynomial time. Therefore, the advent of quantum computers will make modern public key cryptographic systems insecure.

In this situation, cryptographic society put spurs to develop postquantum cryptography. The NIST (National Institute of Standards and Technology) started a process to standardize postquantum cryptographic algorithms. Moreover, the NSA (National Security Agency) has announced preliminary plans for transitioning algorithms approved for protecting the classified and unclassified national security systems of the United States to quantum-resistant algorithms.

The leading fields of postquantum cryptography are lattice-based cryptography, code-based cryptography, multivariate cryptography, and hash-based digital signatures. In this paper, we propose a new technique that could increase the efficiency of hash-based digital signatures. Hash-based digital signatures are slower than digital signatures that are based on a lattice, code, and multivariate polynomials. However, hash-based digital signatures provide stronger security guarantees than those of other categories because hash-based digital signatures are secure under only one assumption that the underlying hash functions are secure. Therefore, hash-based signatures are considered to be the most promising alternative in the short-term. Hash-based digital signatures have been researched continuously since the Lamport digital signature [2] such as LMS [3] and SPHINCS [4].

All hash-based digital signatures use binary representations to generate signatures up to now. In this paper, we propose using the nonadjacent form (NAF) representation when generating signatures. Specifically, this paper proposes WSS-N by applying the NAF to W-OTS+ [5]. W-OTS+ is a Winternitz-type one-time signature scheme (the Winternitz signature is a one-time digital signature that can be used as a component of recent hash-based digital signatures that are capable of signing many messages. Particularly, the Winternitz signature is used as a building block of XMSS, SPHINCS, etc.) [6] that was proposed by Hulsing in 2013. It allows reducing the signature size more than previous Winternitz-type one-time signature schemes and is proven to be strongly unforgeable under chosen message attacks in the standard model.

We prove that WSS-N is existentially unforgeable under adaptive chosen message attacks, if the used hash function family is second preimage-resistant, undetectable, and one-way. And we also analyze the performance of WSS-N and compare it with WSS-B.

The NAF uses signed digits 0,1, and -1 while the binary representation uses bits 0 and 1. While the binary representation has a uniform distribution, the NAF representation has a biased distribution. It makes the Winternitz signature scheme require less hash function calls when generating a signature. For a specific parameter with a 256-bit security, the Winternitz signature using the NAF requires 8% less hash function calls (thus generates signatures 8% faster) than that using the binary representation. However, the key generation and signature verification time of the Winternitz signature using the NAF become longer than that using the binary representation. We analyzed these trade-offs in detail.

Figure 1 gives the intuition of WSS-N showing better signature generation performance than WSS-B. Concretely, the graph shows the number of blocks by the number of hash function calls when WSS-B and WSS-N, each having a hashed message length of 256 bits and a block length of 4 bits, generate a signature. That is, the point (x, y) of the graph means that when WSS-B or WSS-N generates signatures for [2.sup.256] hashed messages, the total number of blocks that call the hash function x times is y. In addition, the blue and red vertical dotted lines of the graph represent the number of hash function evaluations that each block calls on average when WSS-B and WSS-N generate signatures, respectively. As can be seen from the graph, the maximum number of hash function calls of the WSS-N block is larger than that of WSSB. However, in the case of WSS-N, since the number of blocks making a small number of hash function calls is larger than that of WSS-B, on average, WSS-N requires less hash function calls than WSS-B. So, WSS-N generates signatures faster than WSS-B on average.

Now let us look at the usage and the meaning of WSS-N. Basically, WSS-N can be used when signature generation time is more important than key generation time. Generally, the bottleneck of a one-time digital signature is not the signature generation time but the key generation time, but there will certainly be a situation where the signature generation time is more critical. Devices that sense data that do not happen frequently but need a quick response, such as seismic sensors, fire sensors, and so forth, should generate a signature as soon as possible if an event occurs. They can generate a key pair in the wait time. Also, in situations where we need to send measurement data on a regular basis (e.g., every 5 minutes), we will be able to generate a key pair between data measurements and wait for signature generation. Note that efforts to reduce signature generation time have been around for a long time [7, 8]. And the most important contribution of the paper is that it shows the possibility of a numeral system that can provide better performance than a binary representation.

The rest of this paper is organized as follows. Section 2 presents some preliminaries. In Section 3, the properties of the NAF that are required to analyze the efficiency of the Winternitz signature using the NAF are given and proven. In Section 4, we present WSS-N, the Winternitz signature using the NAF, and prove that it is existentially unforgeable under chosen message attacks in the standard model. We compare the efficiency of the Winternitz signatures using the NAF and the binary representation in Section 5. And we give implementation results comparing WSS-N and WSS-B in Section 6. Finally, we conclude the paper in Section 7.

2. Preliminaries

This section gives some notation and formal definitions. We follow the notation of [5]. From now on, the notation x [??] X means that x is randomly chosen from the set X using the uniform distribution. We will denote by [U.sub.n] the uniform distribution over [{0, 1}.sup.n]. We follow the definition of a digital signatures scheme DSS = (Kg, Sign, Vf) in [5]. Let DSS([1.sup.n]) denote a signature scheme with a security parameter [1.sup.n]. We also adopt the definitions of the EU-CMA security of [mathematical expression not reproducible] in [5].

Using this, we define EU-CMA in the following way.

Definition1 (EU-CMA [5]). Let DSS([1.sup.n]) be a digital signature scheme with a security parameter [1.sup.n]. DSS([1.sup.n]) is (t, q, [epsilon])-existentially unforgeable under an adaptive chosen message attack if [InSec.sup.EU-CMA](DSS([1.sup.n]); t, q), the maximum success probability of all possibly probabilistic f-time adversaries A making at most q queries to Sign in the above experiment, is at most [epsilon];

[mathematical expression not reproducible]. (1)

WSS-N uses a family of functions [F.sub.n] : {[f.sub.k] : [{0, 1}.sup.n] [right arrow] [{0, 1}.sup.n] | k [member of] [K.sub.n]} with a key space [K.sub.n]. It can be viewed as a cryptographic hash function family that is noncompressing. Using [F.sub.n], we define the following chaining function.

For [c.sup.i.sub.k](x, r) [5], for given a value x [member of] [{0, 1}.sup.n], an iteration counter i [member of] N, a key k [member of] [K.sub.n], and randomization elements r = ([r.sub.1], ..., [r.sub.j]) [member of] [{0, 1}.sup.nxj] with j [greater than or equal to] i, the chaining function works in the following way. In case i = 0, c returns x ([c.sup.0.sub.k](x, r) = x). For i > 0, we define c recursively as

[c.sup.i.sub.k] (x, r) = [f.sub.k] ([c.sup.i-1.sub.k] (x, r) [direct sum] [r.sub.i]). (2)

The subset [r.sub.a], ..., [r.sub.b] of r will be denoted by [r.sub.a,b]. When b < a, we define [r.sub.a,b] to be the empty string. It is assumed that the function family [F.sub.n] is publicly known.

Throughout the paper, we measure all runtimes by counting the number of the evaluations of elements from [F.sub.n]. In what follows, we use the (distinguishing) advantage of an adversary [5].

Functions [5]. We use three properties for families of functions. The first two of them are the one-wayness and the second preimage resistance of the family [F.sub.n] and the success probability of adversaries against them are defined as [mathematical expression not reproducible] [5].

To define the other property, undetectability, consider the two distributions, [mathematical expression not reproducible] is obtained by sampling [mathematical expression not reproducible] is obtained by sampling k [??] [K.sub.n] and then evaluating [f.sub.k] on a uniformly random n-bit string, that is, u [left arrow] [f.sub.k]([U.sub.n]). The advantage of an adversary A against the undetectability of [F.sub.n] is as follows:

[mathematical expression not reproducible]. (3)

Using this, we define the undetectability as follows.

Definition 2 (undetectability (UD) [5]). Let n [member of] N and [F.sub.n] be a family of functions as described above. [F.sub.n] is [epsilon]-undetectable if the advantage of any t-time adversary A against the undetectability of [F.sub.n] is at most e:

[mathematical expression not reproducible]. (4)

Now we provide some more notation and formal definitions regarding the NAF. First, we give the formal definition of the NAF and related definitions that are useful to describe our results.

Definition 3. Let c be an integer. A signed binary representation of c is an equation of the form c = [[summation].sup.l-1.sub.i=0] [c.sub.i][2.sup.i], where [c.sub.i] [member of] {0, 1, -1} for all i. A signed binary representation ([c.sub.l-1], ..., [c.sub.0]) of an integer c is said to be in nonadjacent form provided that no two consecutive [c.sub.i]'s are nonzero. Such a representation is denoted as a NAF representation.

Note that the NAF representation of an integer is unique.

Definition 4. Let [P.sub.n] be a set of all the NAFs, which consists of n signed digits and N(n) = [absolute value of [P.sub.n]] for n [greater than or equal to] 1. And let [P.sub.0] = 0 and N(0) = 1. Furthermore, let N(-1) = 1 and N(-2) = 0.

Proposition 5 shows the explicit formula for N(n) and a recurrence relation of N(n).

Proposition 5. [greater than or equal to] -2, N(n) = {[2.sup.n+2]-[(-1).sup.n]}/3 and N(n + 2) = N(n + 1) + 2N(n).

The functions defined in the following definition give an order on [P.sub.n].

Definition 6. We define five functions on [P.sub.n] which give orders on [P.sub.n].

(1) Let [o.sub.n] : [P.sub.n] [right arrow] Z be an injective function such that

[mathematical expression not reproducible]. (5)

(2) Let [u.sub.n] : [P.sub.n] [right arrow] [Z.sub.N(n)] be a bijective function such that [u.sub.n]([R.sub.1]) [less than or equal to] [u.sub.n]([R.sub.2]) if [o.sub.n]([R.sub.1]) [[less than or equal to].sub.n] [o.sub.n]), where [R.sub.1], [R.sub.2] [member of] [P.sub.n]

(3) Let [v.sub.n] : [P.sub.n] [right arrow] [Z.sub.N(n)] be a bijective function such that

[mathematical expression not reproducible] (6)

(4) Let [mathematical expression not reproducible] be an injective function such that

[mathematical expression not reproducible]. (7)

(5) Let [v'.sub.n] : [P.sub.n] [right arrow] [Z.sub.N(n)] be an injective function such that

[mathematical expression not reproducible]. (8)

3. Properties of the NAF

In this section, we give some properties of the NAF. They will have a crucial role in analyzing the efficiency of WSS-N.

Let s and w be positive integers such that w divides s. For r [member of] [{0, 1}.sup.s], let ([r.sub.s], ..., [r.sub.0]) be the NAF of r. Here, we assume that [r.sub.-1] is always equal to 0. And let

(i) [mathematical expression not reproducible];

(ii) [mathematical expression not reproducible]

for ([p.sub.w-1], ..., [p.sub.0]) [member of] [P.sub.w].

We compute the numbers of the elements in [mathematical expression not reproducible]. First, the numbers of the elements in [mathematical expression not reproducible] are as follows.

Lemma 7. For all ([p.sub.w-1], ..., [p.sub.0]) [member of] [P.sub.w]

(1) [mathematical expression not reproducible].

(2) [mathematical expression not reproducible].

Proof. First, suppose that [p.sub.w-1] = -1. Because [r.sub.s-w-1] should Be 0 for r [mathematical expression not reproducible]. Additionally, because [r.sub.s-w-1] = [+ or -]1 and [r.sub.s-w-2] = 0 for r [member of] [mathematical expression not reproducible].

Next, suppose that [p.sub.w-1] = -1. If there is an element [mathematical expression not reproducible] should be 0. Then r represents a negative integer. This contradicts our assumption. Hence, [mathematical expression not reproducible]. In the same manner, we can see that [mathematical expression not reproducible].

We are now in a position to calculate the numbers of the elements in [mathematical expression not reproducible].

Theorem 8. For all 0 [less than or equal to] i < s/w - 1 and ([p.sub.w-1], ..., [p.sub.0]) [member of] [P.sub.w],

(1) [mathematical expression not reproducible].

(2) [mathematical expression not reproducible].

Proof. See Appendix A.

4. Winternitz Signature Scheme Using the NAF

In this section, we propose WSS-N, a Winternitz signature scheme that uses the NAF representation. WSS-N is parameterized by the security parameter n [member of] N, the message length m, and the Winternitz parameter 1 < w [member of] N. And let

[mathematical expression not reproducible]. (9)

Algorithms 1-3 describe the key generation, signature generation, and signature verification algorithms of WSS-N.

Note that distinct messages will yield distinct [b.sub.i] values and that the checksum guarantees that given [mathematical expression not reproducible] corresponding to a message, [mathematical expression not reproducible] corresponding to another message include at least one 1 [less than or equal to] i [less than or equal to] [t.sub.w] such that [b'.sub.i] < [b.sub.i].

The following theorem shows that WSS-N is existentially unforgeable under chosen message attacks, provided that a second preimage-resistant and undetectable one-way function family is used.

Algorithm 1: WSS-N key generation algorithm Kg. Input: security parameter [1.sup.n] Output: secret key sk and public key pk 1. choose [mathematical expression not reproducible] uniformly at random. 2. set [mathematical expression not reproducible]. 3. choose [r.sub.1], ..., [r.sub.N(w)-1] [??] [{0, 1}.sup.n] uniformly at random. 4. setr = ([r.sub.1], ..., [r.sub.N(w)-1]). 5. choose a function key k [??] [K.sub.n] uniformly at random. 6. set [pk.sub.0] = (r, k). 7. compute [mathematical expression not reproducible]. 8. for i = 2 to [??]m/w[??], compute [pk.sub.i] = [c.sub.N(w)-1.sub.k]([sk.sub.i], r). 9. for [mathematical expression not reproducible]. 10. [mathematical expression not reproducible]. 11. return (sk, pk).

Theorem 9. Let n, w, m [member of] N, w, m = poly(n), and [F.sub.n] : {[f.sub.k] : [{0, 1}.sup.n] [right arrow] [{0, 1}.sup.n] | k [member of] [K.sub.n]} be a second preimage-resistant and undetectable one-way function family. Then, [InSec.sup.EU-CMA](WSS-N([1.sup.n], w, m); t, 1), the insecurity of WSS-N against an EU-CMA attack, is bounded by

[mathematical expression not reproducible]. (10)

Proof. It may be proven in much the same way as Theorem 1 in [5]. The only difference between them is that the heights of the chains to compute public keys of WSS-N and W-[OTS.sup.+] [5] are different. Since the heights of the chains in WSS-N are not constant, the proof becomes a bit more complicated. However, the main idea of the proof does not change. For the detailed proof, we refer the reader to Appendix B.

Remark 10. The length of the signatures of the WSS-N can be reduced by using a secure pseudorandom generator. For example, a 2n-bit seed of a secret key can be used to generate the [nt.sub.w]-bit secret key using the pseudorandom generator based on an AES counter mode. Naturally, the length of the signatures of the WSS-B can be reduced in a similar way.

5. Comparisons

In this section, we compare the Winternitz signature using the NAF with that using the binary representation. When n [member of] N is the security parameter, m [member of] N is the message length and 1 < w [member of] N is the Winternitz parameter; let WSS-N([1.sup.n], w, m) and WSS-B([1.sup.n], w, m) denote the Winternitz signatures using the NAF and the binary representation, respectively. We compare WSS-N with WSS-B in terms of efficiency.

Algorithm 2: WSS-N signature generation algorithm Sign. Input: message M, secret key sk and randomization elements r Output: signature [sigma] 1. compute the NAF representation ([x.sub.m], [x.sub.m-1], ..., [x.sub.0]) of M. 2. split ([x.sub.m-1], ..., [x.sub.0]) into [??]m/w[??] blocks [c.sub.1], ..., [c.sub.[??]m/w[??]] of length w, padding ([x.sub.m-1], ..., [x.sub.0]) with zeros from the left if required. 3. for i = 1 to [??]m/w[??], set [d.sub.i] be a block of length (w - 1) obtained by dropping the least significant signed digit of [c.sub.i]. 4. compute [mathematical expression not reproducible]. 5. for i = 2 to i = [??]m/w[??] - 1, compute [mathematical expression not reproducible]. 6. compute [mathematical expression not reproducible]. 7 compute the checksum [mathematical expression not reproducible] 8. split the binary representation of [mathematical expression not reproducible] of length w, padding C with zeros from the left if required. 9. for i = [??]m/w[??] + 1 to i = [t.sub.w], set [b.sub.i] be the integer encoded by the block [c.sub.i]. 10. set [mathematical expression not reproducible]. 11. for [mathematical expression not reproducible]. 12. set [mathematical expression not reproducible]. 13. return a. Algorithm 3: WSS-N signature verification algorithm Vf. Input: message M, signature a and public key pk Output: valid or invalid 1. compute B as in Sign. 2. [mathematical expression not reproducible] then return valid, else return invalid.

First, we compare the number of hash function calls that are needed to generate a WSS-N signature and a WSS-B signature. We show that WSS-N([1.sup.n], w, m) needs less hash function calls than WSS-B([1.sup.n], w, m) to generate a signature when m [greater than or equal to] 15w and w [greater than or equal to] 2. For the ease of the analysis, we only consider the case where w divides m in this section.

Before counting the numbers of the hash function calls that are needed in the signature generation steps, we give a lemma concerning the lengths of the count fields.

Lemma 11. Let n be the security parameter, let m be the message length, and let w be the bit length of the block, the Winternitz parameter. And suppose that w divides m. The difference between the block length of the count field of WSS-B([1.sup.n], w, m) and that of WSS-N([1.sup.n], w, m) is less than or equal to 1 when w [greater than or equal to] 2.

Proof. The block length of the count field of WSS-B([1.sup.n], w, m) is

[??][log.sub.2] (m([2.sup.w] - 1)/w)/w [??]+ 1 (11)

And the block length of the count field of WSS-N([1.sup.n], w, m) is

[??][log.sub.2] ([2.sup.w] - 1 + (m/w - 1) (N (w) - 1))/w[??] + 1 (12)

Thus, it is enough to show that

[mathematical expression not reproducible]. (13)

It is equivalent to

(m/w - 1)(N(w) - 1) [less than or equal to] (2m/w)([2.sup.w] - 1). (14)

Because N(w) - 1 = ([2.sup.w+2] - [(-1).sup.w])/3 [less than or equal to] [2.sup.w+1] - 2 when w [greater than or equal to] 2, we can see that

(m/w - 1)(N(w) - 1) [less than or equal to] (2m/w - 1)([2.sup.w] - 1), (15)

when w [greater than or equal to] 2. This completes the proof.

Now we count the numbers of hash function calls that are needed in the signature generation steps of the Winternitz signature schemes using the binary representation and the NAF representation.

Theorem 12. Let [beta]([1.sup.n], w, m) and v([1.sup.n], w, m) be the numbers of hash function calls that are needed to generate a WSS-B([1.sup.n], w, m) signature and a WSS-N([1.sup.n], w, m) signature on average, respectively, where n is the security parameter, w is the Winternitz parameter, and m is the message length. And suppose that w divides m. Then v([1.sup.n], w, m) [less than or equal to] p([1.sup.n], w, m) when m [greater than or equal to] 15w and w [greater than or equal to] 2.

Proof. First, we compute [beta]([1.sup.n], w, m).

[mathematical expression not reproducible] (16)

The first and second terms correspond to the numbers of the hash function calls that are needed for the message and count fields, respectively.

Next, we compute v([1.sup.n], w, m).

[mathematical expression not reproducible] (17)

The first six and the last terms correspond to the numbers of hash calls that are needed for the message and count fields, respectively.

Applying Lemma 11 yields

[mathematical expression not reproducible]. (18)

We shall have established the theorem if we prove that the right-hand side of the above inequality is greater than or equal to 0 when m [greater than or equal to] 15w and w [greater than or equal to] 2. The right-hand side can be rewritten as

[mathematical expression not reproducible] (19)

Because m [greater than or equal to] 15w and w [greater than or equal to] 2, we can show that the right-hand side is greater than or equal to 0. This finishes the proof, and the detailed verification of the right-hand side being greater than or equal to 0 is left to the reader.

The above theorem states that WSS-N([1.sup.n], w, m) needs less hash function calls to generate a signature than WSSB([1.sup.n], w, m) on average when m [greater than or equal to] 15w and w [greater than or equal to] 2. Note that [beta]([1.sup.n], w, m) = v([1.sup.n], w, m) when m = w.

We proceed to show the numbers of hash function calls that are needed in the key generation steps of WSSB([1.sup.n], w, m) and WSS-N([1.sup.n], w, m). It is easily seen that

([2.sup.w] - 1) (m/w + [??][log.sub.2] (m([2.sup.w] - 1)/w)/w[??] + 1) (20)

hash function calls are needed to generate a WSS-B([1.sup.n], w, m) key pair. Similarly, we see that

[mathematical expression not reproducible] (21)

hash function calls are needed to generate a WSS-N([1.sup.n], w, m) key pair.

What is left is to count the numbers of hash function calls that are required to verify a WSS-B([1.sup.n], w, m) signature and a WSS-N([1.sup.n], w, m) signature. An analysis similar to that in the proof of Theorem 12 shows that

1/2([2.sup.w] - 1) (m/w + [??][log.sub.2] (m([2.sup.w] - 1)/w)/w[??] + 1) + 1 (22)

hash function calls are needed to verify a WSS-B([1.sup.n], w, m) signature. Similarly, we obtain that

[mathematical expression not reproducible] (23)

hash function calls are needed to verify a WSS-N([1.sup.n], w, m) signature.

Now, we give the concrete result of the efficiency analysis (Table 1) that compares WSS-N([1.sup.256], 4,256) and WSS-B([1.sup.256], 4,256). The numbers in the public key, secret key, and signature columns are byte lengths and those in the key generation, signature generation, and signature verification columns are the number of hash function calls. Additionally, the numbers with the dagger mark are average values. Table 1 shows that the number of hash function calls to generate a Winternitz signature is reduced by about 8% when using the NAF representation compared to that with the binary representation. However, generating a key pair and verifying a signature need more hash function calls when using the NAF compared to the binary representation.

Remark 13. WSS-N needs less hash function calls when generating a signature than that of WSS-B. By giving the other orders on [P.sub.W], one can make the Winternitz signature scheme need less hash function calls when verifying a signature. However, we will not cover this feature in this paper.

6. Benchmarks and Comparison

In this section, we provide benchmarking results of WSS-N and WSS-B. Concretely, we implement WSS-N([1.sup.256], 4, 256) and WSS-B([1.sup.256], 4, 256) and compare their software performances. The specific parameters and functions are summarized in Table 2. We use SHA-256 in OpenSSL [9].

Table 3 shows implementation results of WSS-N and WSS-B. It gives the average clock cycle counts of 1,000,000 runs for key generation, signing, and verification. All results in Table 3 were obtained on an Intel Core i7-6700 running at 3.40 GHz. We used the compiler gcc-5.4.0 with the options O3," "-march=broadwell," and "-mtune=generic" to compile our C program.

We can see that WSS-N generates signatures faster than WSS-B by about 8% on a general desktop computer. However, the key generation and the signature verification of WSS-N are slower than those of WSS-B as expected. The source code that benchmarks WSS-N and WSS-B can be found in the supplementary materials (available here).

7. Conclusions

In this paper, we proposed a hash-based signature using the NAF, WSS-N. It is existentially unforgeable under chosen message attacks in the standard model. And we proved that WSS-N requires less hash function calls than WSS-B when generating a signature on average. In a concrete example, WSS-N([1.sup.256], 4, 256) makes the signature generation time 8% shorter than that of the WSS-B([1.sup.256], 4, 256). And we also gave benchmarking results on a regular desktop computer and it could be seen that the signature generation of WSS-N can be implemented faster than that of WSS-B. However, it takes longer to generate the keys and verify the signatures.

WSS-N is the first hash-based signature that uses a numeral system other than the binary representation. Applying the NAF to hash-based signatures has trade-offs between the key generation time, the signature generation time, and the signature verification time. It would be interesting to determine what other trade-offs occur when applying numeral systems other than the binary representation and the NAF.

Appendix

A. Proof of Theorem 8

In this section, we give the proof of Theorem 8.

Proof. The proof is by induction on i. As a base case, we compute [mathematical expression not reproducible]. Furthermore, it is clear that [mathematical expression not reproducible].

For the inductive step, let 0 [less than or equal to] j < s/w - 2 be an integer and assume that the theorem holds for j. We first have

[mathematical expression not reproducible] (A.1)

for all ([p.sub.w-1], ..., [p.sub.0]) [member of] [P.sub.w], provided [p.sub.w-1] = 0. In the same manner, we have

[mathematical expression not reproducible] (A.2)

for all ([p.sub.w-1], ..., [p.sub.0]) [member of] [P.sub.w], provided [p.sub.w-1] [not equal to] 0.

We next have

[mathematical expression not reproducible] (A.3)

for all ([p.sub.w-1], ..., [p.sub.0]) [member of] [P.sub.w], provided [p.sub.w-1] = 0. In the same manner, we have

[mathematical expression not reproducible] (A.4)

for all ([p.sub.w-1], ..., [p.sub.0]) [member of] [P.sub.w], provided [p.sub.w-1] [not equal to] 0.

Thus, the theorem holds for 0 [less than or equal to] i < s/w - 1, and this completes the proof.

Algorithm 4: WSS-N security reduction algorithm. Input: security parameter n, function key k, one-way challenge [y.sub.c] and second preimage resistance challenge [x.sub.c] Output: a value that is either a preimage of [y.sub.c] or the second preimage for [x.sub.c] under [f.sub.k] or fail. 1. run Kg ([1.sup.n]) to generate a WSS-N([1.sup.n], w, m) key pair (sk, pk). 2. choose an index [alpha] [??] {1, ..., [t.sub.w]}. 3. if 2 [less than or equal to] [alpha] [less than or equal to] [??]m/w[??] then choose an index [beta] [??] {1, ..., N(w) - 1}. 4. else choose an index [beta] [??] {1, ..., [2.sup.w] - 1}. 5. if 2 [less than or equal to] [alpha] [less than or equal to] [??] m/w [??] - 1 then a. if [beta] = N(w) - 1 then set r' = r. b. else (1) choose an index [gamma] [??] {[beta] + 1, ..., N(w) - 1}. (2) obtain r' from r, replacing [mathematical expression not reproducible]. c. obtain pk' by setting [mathematical expression not reproducible] 6. else a. if [beta] = [2.sup.w] - 1 then set r' = r. b. else (1) choose an index [gamma] [??] {[beta] + 1, ..., [2.sup.w] - 1}. (2) obtain r' from r, replacing [mathematical expression not reproducible]. c. obtain pk' by setting [mathematical expression not reproducible] 7. run [A.sup.Sign(sk,*)](pk'). 8. if [A.sup.Sign(sk,*)]pk') queries Sign with a message M then a. compute B as in Algorithm 2. b. if [b.sub.[alpha]] < [beta] then return fail. c. generate a signature of a of M: (1) run [sigma] [less than or equal to] Sign(M, sk, r'). (2) set [mathematical expression not reproducible]. d. reply to the query using [sigma]. 9. if [A.sup.Sign(sk,*)](pk') returns a valid ([sigma]', M') then a. compute B' as in Algorithm 2. b. if [b'.sub.[alpha]] [greater than or equal to] then return fail. c. if 2 [less than or equal to] [alpha] [less than or equal to] [??]m/w[??] and [beta] = N(w) - 1 then return a preimage [mathematical expression not reproducible]. d. else if (([alpha] = 1) [disjunction] ([??]m/w[??] [less than or equal to] a [less than or equal to] [t.sub.w)) and [beta] = [2.sup.w] - 1 then return a preimage [mathematical expression not reproducible]. e. else if [mathematical expression not reproducible] then return a Preimage [mathematical expression not reproducible]. f. else if [mathematical expression not reproducible] then return the second preimage x'. 10. in any other cases, return fail.

B. Security Proof of WSS-N

In this section, we give the proof of Theorem 9. It can be proven in much the same way as [5].

Proof. Suppose that there exists a forger A that (f, 1, [[epsilon].sub.A])-breaks existential unforgeability of WSS-N([1.sup.n], w, m), where [[epsilon].sub.A] > [InSec.sup.EU-CMA](WSS-N([1.sup.n], w, m); t, 1). We construct an algorithm [M.sup.A], by interacting with A with a possibly different input distribution, which breaks either the second preimage resistance or one-wayness of [F.sub.n] (Algorithm 4).

First, [M.sup.A] obtains a key pair (sk, pk) by running the WSS-N([1.sup.n], w, m) Kg (Line 1). Then, [M.sup.A] selects the positions to place its challenges in the public key. It selects a random function chain choosing an index [alpha] [??] {1, ..., [t.sub.w]} (Line 2). It chooses another index [beta] [??] {1, ..., N(w) - 1} when 2 [less than or equal to] [alpha] [less than or equal to] [??]m/w[??] (Line 3); otherwise it chooses [beta] [??] {1, ..., [2.sup.w] - 1} (Line 4) to select a random intermediate value of this chain. [M.sup.A] places the preimage challenge at this position by setting [y.sub.c] as the [beta]th intermediate value of the chain. If p is not the last position of the chain, another intermediate value between p and the end of the chain is selected, sampling y (Lines 5.b.(1) and 6.b.(1)). MA places the second preimage challenge at the input of the [gamma]th evaluation of the chain continued from [y.sub.c], replacing [r.sub.[gamma]] (Lines 5.b.(2) and 6.b.(2)). A manipulated public key pk' is computed (Lines 5.c and Line 6.c).

Then [M.sup.A] runs A on input pk' (Line 7). We assume that A asks for the signature on one message M (Line 8). [M.sup.A] computes B as described in Sign (Line 8.a). [M.sup.A] knows all the secret key values corresponding to pk' except that of the chain a. For the chain [alpha], [M.sup.A] can only answer the query if [b.sub.[alpha]] [greater than or equal to] p (Line 8.c). Otherwise, [M.sup.A] aborts (Line 8.b).

If A outputs a forgery ([sigma], M'), [M.sup.A] computes B1 (Line 9.a). The forgery is only useful if [b'.sub.[alpha]] < [beta]. If not, [M.sup.A] returns fail (Line 9.b). Now, there are two mutually exclusive cases. If [beta] is the last position of the chain a, the forgery contains a preimage of [y.sub.c] (Lines 9.c and Line 9.d). Otherwise, there are again two mutually exclusive cases. When the chain continued from [[sigma]'.sub.[alpha]] has [y.sub.c] as the [beta]th intermediate value, a preimage can be extracted (Line 9.e). And when [y.sub.c] is not the [beta]th intermediate value of the chain continued from [[sigma]'.sub.[alpha]], the chains continued from [y.sub.c] and [[sigma]'.sub.[alpha]] must collide at some position between [beta]+1 and the end ([2.sup.w] - 1 or N(w) -1). If they collide at position [gamma] for the first time, the second preimage for [x.sub.c] can be extracted (Line 9.f). Otherwise, [M.sup.A] aborts (Line 10).

We proceed to compute the success probability of [M.sup.A]. We only compute the probability for a certain success case where [b.sub.[alpha]] obtained from A's query equals [beta]. This happens with probability at least 1/(N(w) - 1). As our modification might have changed the input distribution of A, let [[epsilon]'.sub.A] denote the probability that A returns a valid forgery when run by MA. Due to the check sum, M' leads to at least one [b'.sub.i] < [b.sub.i], 0 < i [less than or equal to] [t.sub.w]. With probability [t.sup.-1.sub.W], this happens for i = [alpha] and the condition in Line 9.b is fulfilled. At this point, there are two mutually exclusive cases.

Case 1. [beta] is the last position of the chain [alpha] or the chain continued from [[sigma]'.sub.[alpha]] has [y.sub.c] as the [beta]th intermediate value. In this case, [M.sup.A] returns a preimage for [y.sub.c] with probability 1.

Case 2. [beta] is not the last position of the chain a and the chain continued from [[sigma]'.sub.[alpha]] does not have [y.sub.c] as the [beta]th intermediate value. In this case, [M.sup.A] returns the second preimage for [x.sub.c] if the two chains collide for the first time at position [gamma]. This happens with probability greater than 1/(N(w) - 1).

Hence the bound of [[epsilon]'.sub.A] can be obtained:

[mathematical expression not reproducible] (B.1)

where the time t' = t + 3[t.sub.w](N(w) - 1) is an upper bound for the runtime of A plus the time needed to run each algorithm of WSS-N([1.sup.n], w, m) once.

At the second step, we bound the difference between [[epsilon].sub.A] and [[epsilon]'.sub.A]. If [[epsilon].sub.A] < [[epsilon]'.sub.A], we already have a contradiction. Hence, we assume that [[epsilon]'.sub.A] [greater than or equal to] [[epsilon]'.sub.A] in what follows. We define two distributions, [D.sub.M] and [D.sub.Kg], over {1, ..., [t.sub.w]} x {1, .... N(w) - 1} x [{0, 1}.sup.n] x [{0, 1}.sup.n(N(w)-1)] x [K.sub.n]. A sample ([alpha], [beta], u, r, k) follows [D.sub.M] if the entries [mathematical expression not reproducible] are chosen uniformly at random and p [??] {1, ..., N(w) - 1} is chosen uniformly at random when 2 [less than or equal to] [alpha] [less than or equal to] [??]m/w[??] and [beta] [??] {1, ..., [2.sup.w] - 1} is chosen uniformly at random otherwise. A sample [mathematical expression not reproducible] are chosen uniformly at random, [beta] [??] {1,..., N(w) - 1} is chosen uniformly at random when 2 [less than or equal to] a [less than or equal to] [??]m/w[??], and [beta] [??] {1, ..., [2.sup.w] - 1} is chosen uniformly at random otherwise and u = [c.sup.[beta].sub.k]([U.sub.n], r). Now we construct an algorithm [M'.sup.A] that distinguishes between [D.sub.Kg] and [D.sub.M]. We bound [[epsilon].sub.A] using the advantage of [M'.sup.A] and [[epsilon]'.sub.A]. Then the bound of the advantage of [M'.sup.A] is obtained using the undetectability of [F.sub.n].

[M'.sup.A] works in the following way. On input ([alpha], [beta], u, r, k) that is chosen from either [D.sub.M] or [D.sub.Kg], [M'.sup.A] generates a WSS N([1.sup.n], w, m) key pair. Instead of using Kg, [mathematical expression not reproducible]. It computes pk as [pk.sub.0] = (r, k) and

[mathematical expression not reproducible]. (B.2)

Then [M'.sup.A] runs A on input pk. When A issues a chosen message query for a message M, [M'.sup.A] behaves the same way as [M'.sup.A]. If A returns a valid forgery, [M'.sup.A] returns 1 and otherwise 0. The runtime of [M'.sup.A] is bounded by the runtime of A plus one evaluation of each algorithm of WSS-N([1.sup.n], w, m). So we get t" = t + 3[t.sub.w](N(w) - 1) as an upper bound.

Now we compute the advantage [mathematical expression not reproducible]. If the sample is taken from [D.sub.M], the distribution of pk generated by [M'.sup.A] is the same as the distribution of pk' generated by [M.sup.A]. Hence [M'.sup.A] outputs 1 with probability

Pr [([alpha], [beta], u, r, k) [less than or equal to] [D.sub.M] : 1 [less than or equal to] [M'.sup.A] ([alpha], [beta], u, r, k)]

= [[epsilon]'.sub.A] (B.3)

If the sample was taken from [DK.sub.g], pk generated by [M'.sup.A] follows the same distribution as that generated by KG and so M' outputs 1 with probability

[mathematical expression not reproducible]. (B.4)

So the advantage of [M'.sup.A] is

[mathematical expression not reproducible]. (B.5)

So we obtain the following bound on [[epsilon].sub.A]:

[mathematical expression not reproducible] (B.6)

We now bound the advantage of [M'.sup.A]. For given [alpha] [member of] {1, ..., [t.sub.w]} and [beta] [member of] {1, ..., N(w) - 1}, we define the hybrids [mathematical expression not reproducible]. Given an adversary B that can distinguish between [H.sub.0] and [H.sub.[beta]] with advantage [[epsilon].sub.B], there must exist two consecutive hybrids, [H.sub.[lambda]] and [H.sub.[lambda]+1], which B distinguishes with advantage [greater than or equal to] [[epsilon].sub.B]/p. Then we can construct an algorithm [M.sup."B] that, by interacting with B, distinguishes between [mathematical expression not reproducible]. Given a challenge (u, k), [M.sup."B] selects r [less than or equal to] [U.sup.2.sub.n], computes x = [c.sup.[beta]-([lambda]+1).sub.k] (u, [r.sub.[lambda]+2],(w)-1]), runs b [left arrow] B([alpha], [beta], x, r, k), and outputs b.

If the sample is taken from [mathematical expression not reproducible] is uniformly random and x = [c.sup.[beta]-([lambda]+1).sub.k] (u, [r.sub.[lambda]+2],N(w)-1]) is distributed exactly like the third element of [H.sub.[lambda]+1]. Otherwise, if the sample is taken from [mathematical expression not reproducible] is an output of [f.sub.k] and we get

[mathematical expression not reproducible]. (B.7)

It is equal to the third element of [H.sub.[lambda]]. Hence, the advantage of [M".sup.B] is equal to that of B. So we get

[mathematical expression not reproducible]. (B.8)

As the advantage of [M".sup.B] is bounded by the undetectability of [F.sub.n], [M'.sup.A] does exactly what we expect B to do and the runtime of [M".sup.B] is that of B plus at most (N(w) - 1) evaluations of elements from [F.sub.n]; we get

[mathematical expression not reproducible], (B.9)

where [t.sup.*] = t" + (N(w) - 1) = t + 3([t.sub.w] + 1)(N(w) - 1) is the runtime of [M".sup.B]. As [beta] [member of] {1, ..., N(w) - 1}, we obtain

[mathematical expression not reproducible]. (B.10)

Putting (B.1), (B.6), and (B.10) together, we obtain a bound on [[epsilon].sub.A] which leads to the required contradiction:

[mathematical expression not reproducible] (B.11)

with t' = t + 3[t.sub.w](N(w) - 1) and [t.sup.*] = t + 3([t.sub.w] + 1)(N(w) 1).

https://doi.org/10.1155/2018/1452457

Conflicts of Interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.

Supplementary Materials

The source code that benchmarks WSS-N and WSS-B is presented. The README file contains the commands and other comments to run the program. (Supplementary Materials)

References

[1] P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," SIAM Journal on Computing, vol. 26, no. 5, pp. 1484-1509, 1997

[2] L. Lamport, "Constructing digital signatures from a one way function," 1979.

[3] D. McGrew and M. Curcio, Hash-Based Signatures, https:// datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/.

[4] D. J. Bernstein, D. Hopwood, A. Hulsinget al., "SPHINCS: practical stateless hash-based signatures," in Advances in cryptology-EUROCRYPT 2015. Part I, vol. 9056 of Lecture Notes in Comput. Sci., pp. 368-397, Springer, Heidelberg, 2015.

[5] A. Hulsing, "W-OTS+--Shorter Signatures for Hash-Based Signature Schemes," in Progress in Cryptology--AFRICACRYPT 2013,vol. 7918 of Lecture Notes in Computer Science, pp. 173-188, Springer Berlin Heidelberg, Berlin, Heidelberg, 2013.

[6] R. C. Merkle, "A certified digital signature," in Advances in cryptology-CRYPTO '89, vol. 435 of Lecture Notes in Comput. Sci., pp. 218-238, Springer, New York, 1990.

[7] S. Even, "On-line/off-line digital signatures," Journal of Cryptology, vol. 9, no. 1, pp. 35-67, 1996.

[8] A. Shamir and Y. Tauman, "Improved online/offline signature schemes," in Advances in cryptology-CRYPTO 2001, vol. 2139 of Lecture Notes in Comput. Sci., pp. 355-367, Springer, Berlin, 2001.

[9] The OpenSSL project, OpenSSL--Cryptography and SSL/TLS Toolkit, http://www.openssl.org.

Dongyoung Roh (iD), Sangim Jung (iD), and Daesung Kwon

National Security Research Institute, Daejeon, Republic of Korea

Correspondence should be addressed to Dongyoung Roh; dyroh@nsr.re.kr

Received 22 December 2017; Revised 13 March 2018; Accepted 18 April 2018; Published 21 June 2018

Academic Editor: Kiseon Kim

Caption: Figure 1: The number of blocks by the number of hash function calls when WSS-B and WSS-N, each having a hashed message length of 256 bits and a block length of 4 bits, generate a signature.

Table 1: Efficiency analyses of the Winternitz signatures. Algorithm pk sk Sig Kg WSS-B 2,656 2,144 2,144 1,005 WSS-N 2,816 2,144 2,144 1,320 Algorithm Sign Vf WSS-B [440.7 [503.5 .sup.[dagger]] .sup.[dagger]] WSS-N [402.8 [810.6 .sup.[dagger]] .sup.[dagger]] Table 2: Implementation parameters and functions. Parameter n w m Kn fk(x) Value 128 4 256 [{0,1}.sup.256] SHA-256 (k [parallel] x) Table 3: Benchmarking on a desktop computer. Algorithm Kg Sign Vf WSS-B 2,039,698 937,302 969,455 WSS-N 2,612,287 863,875 1,550,179

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Roh, Dongyoung; Jung, Sangim; Kwon, Daesung |

Publication: | Security and Communication Networks |

Date: | Jan 1, 2018 |

Words: | 7504 |

Previous Article: | A New Unified Intrusion Anomaly Detection in Identifying Unseen Web Attacks. |

Next Article: | Network Intrusion Detection with Threat Agent Profiling. |

Topics: |