Danilo Câmara
email: dfcamara@ic.unicamp.br

Conrado P L Gouvêa
email: conradoplg@ic.unicamp.br

Julio López
email: jlopez@ic.unicamp.br

Ricardo Dahab
email: rdahab@ic.unicamp.br

Fast Software Polynomial Multiplication on ARM Processors using the NEON Engine

Keywords: binary field arithmetic, ARM NEON, elliptic curve cryptography, authenticated encryption, software implementation

Efficient algorithms for binary field operations are required in several cryptographic operations such as digital signatures over binary elliptic curves and encryption. The main performance-critical operation in these fields is the multiplication, since most processors do not support instructions to carry out a polynomial multiplication. In this paper we describe a novel software multiplier for performing a polynomial multiplication of two 64-bit binary polynomials based on the VMULL instruction included in the NEON engine supported in many ARM processors. This multiplier is then used as a building block to obtain a fast software multiplication in the binary field F2m , which is up to 45% faster compared to the best known algorithm. We also illustrate the performance improvement in point multiplication on binary elliptic curves using the new multiplier, improving the performance of standard NIST curves at the 128and 256-bit levels of security. The impact on the GCM authenticated encryption scheme is also studied, with new speed records. We present timing results of our software implementation on the ARM Cortex-A8, A9 and A15 processors.

Introduction

Mobile devices such as smartphones and tablets are becoming ubiquitous. While these devices are relatively powerful, they still are constrained in some aspects such as power consumption. Due to the wireless nature of their communication, it is very important to secure all messages in order to prevent eavesdropping and disclosure of personal information. For this reason, the research of efficient software implementation of cryptography in those devices becomes relevant. Both public key and symmetric cryptography are cornerstones of most cryptographic solutions; in particular, the public-key elliptic curve schemes and the symmetric authenticated encryption schemes are often used due to their high efficiency. Elliptic curve schemes include the well known Elliptic Curve Digital Signature Algorithm (ECDSA) and the Elliptic Curve Diffie Hellman (ECDH) key agreement scheme; while the Galois/Counter Mode (GCM) is an important example of authenticated encryption scheme which is included in many standards such as IPSec and TLS.

A significant portion of mobile devices uses processors based on the 32-bit RISC ARM architecture, suitable for low-power applications due to its relatively simple design, making it an appropriate choice of target platform for efficient implementation. Many ARM processors are equipped with a NEON engine, which is a set of instructions and large registers that supports operations in multiple data using a single instruction. Thus, our objective is to provide an efficient software implementation of cryptography for the ARM architecture, taking advantage of the NEON engine. We have aimed for standard protection against basic side-channel attacks (timing and cache-leakage). Our main contributions are: (i) to describe a new technique to carry out polynomial multiplication by taking advantage of the VMULL NEON instruction, achieving a binary field multiplication that is up to 45% faster than a state-of-the-art LD [START_REF] López | High-speed software multiplication in F2m[END_REF] multiplication also using NEON; (ii) using the new multiplier, to achieve speed records of elliptic curve schemes on standard NIST curves and of authenticated encryption with GCM; (iii) to offer, for the first time in the literarure, comprehensive timings for four binary NIST elliptic curves and one non-standard curve, on three different ARM Cortex processors. With this contributions, we advance the state of the art of elliptic curve cryptography using binary fields, offering an improved comparison with the (already highly optimized) implementations using prime fields present in the literature. Our code will be available1 to allow reproduction of results.

Related work. Morozov et al. [START_REF] Morozov | System integration of elliptic curve cryptography on an OMAP platform[END_REF] have implemented ECC for the OMAP 3530 platform, which features a 500 MHz ARM Cortex-A8 core and a DSP core. Taking advantage of the XORMPY instruction of the DSP core, they achieve 2,106 µs in the B-163 elliptic curve and 7,965 µs in the B-283 curve to compute a shared key, which should scale to 1,053 and 3,982 Kcycles respectively.

Bernstein and Schwabe [START_REF] Bernstein | NEON crypto[END_REF] have described an efficient implementation of nonstandard cryptographic primitives using the NEON engine on a Cortex-A8 at the 128-bit security level, using Montgomery and Edwards elliptic curves over the prime field F (2 255 -19) . The primitives offer basic resistance against side-channel attacks. They obtain 527 Kcycles to compute a shared secret key, 368 Kcycles to sign a message and 650 Kcycles to verify a signature.

Hamburg [START_REF] Hamburg | Fast and compact elliptic-curve cryptography[END_REF] has also efficiently implemented non-standard cryptographic primitives on a Cortex-A9 without NEON support at the 128-bit security level, using Montgomery and Edwards Curves over the prime field F (2 252 -2 232 -1) , with basic resistance against side-channel attacks. He obtains 616 Kcycles to compute a shared key, 262 Kcycles to sign a message and 605 Kcycles to verify a signature.

Faz-Hernández et al. [START_REF] Faz-Hernández | Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV-GLS curves[END_REF] have targeted the 128-bit security level with a GLV-GLS curve over the prime field F (2 127 -5997) 2 , which supports a four dimensional decomposition of the scalar for speeding up point multiplication. The implementation also provides basic resistance against side-channel attacks. They have obtained 417 and 244 Kcycles for random point multiplication on the Cortex-A9 and A15 respectively; 172 and 100 Kcycles for fixed point multiplication and 463 and 266 Kcycles for simultaneous point multiplication.

Krovetz and Rogaway [START_REF] Krovetz | The software performance of authenticated-encryption modes[END_REF] studied the software performance of three authenticated encryption modes (CCM, GCM and OCB3) in many platforms. In particular, they report 50.8 cycles per byte (cpb) for GCM over AES with large messages using the Cortex-A8; an overhead of 25.4 cpb over unauthenticated AES encryption.

Polyakov [START_REF] Polyakov | The OpenSSL project[END_REF] has contributed a NEON implementation of GHASH, the authentication code used by GCM, to the OpenSSL project. He reports a 15 cpb performance on the Cortex-A8.

Paper structure. This paper is organized as follows. In Section 2 we describe the ARM architecture. In Section 3, the binary field arithmetic is explained, along with our new multiplier based on the the VMULL instruction. Section 4 describes the high-level algorithms used and Section 5 presents our results. Finally, concluding remarks are given in Section 6.

ARM Architecture

The ARM is a RISC architecture known for enabling the production of lowpower processors and is widely spread in mobile devices. It features a fairly usual instruction set with some interesting characteristics such as integrated shifts, conditional execution of most instructions, and optional update of condition codes by arithmetic instructions. There are sixteen 32-bit registers (R0-R15), thirteen of which are general-purpose. The version 7 of the ARM architecture has added an advanced Single Instruction, Multiple Data (SIMD) extension referred as "NEON engine", which is composed of a collection of SIMD instructions using 64-or 128-bit operands and a bank of sixteen 128-bit registers. These are named Q0-Q15 when viewed as 128-bit, and D0-D31 when viewed as 64-bit. There are many CPU designs based on the ARM architecture such as the ARM7, ARM9, ARM11 and the ARM Cortex series. In this work, we used three ARM Cortex devices, which we now describe.

Cortex-A8. The ARM Cortex-A8 processor is a full implementation of the ARMv7 architecture including the NEON engine. Compared to previous ARM cores the Cortex-A8 is dual-issue superscalar, achieving up to twice the instructions executed per clock cycle. Some pairs of NEON instructions can also be dual-issued, mainly a load/store or permutation instruction together with a dataprocessing instruction. Its pipeline has 13 stages followed by 10 NEON stages; its L2 cache is internal. The Cortex-A8 is used by devices such as the iPad, iPhone 4, Galaxy Tab, and Nexus S.

Cortex-A9. The ARM Cortex-A9 shares the same instruction set with the Cortex-A8, but it features up to four cores. It no longer supports NEON dual-issue and its L2 cache is external. However, it supports out-of-order execution of regular ARM instructions and register renaming, and has a 9-12 stage pipeline (more for NEON, we were unable to find how many). Devices that feature the Cortex-A9 include the iPad 2, iPhone 4S, Galaxy S II, and Kindle Fire.

Cortex-A15. Implements the ARMv7 architecture, provides dual-issue and outof-order execution for most NEON instructions and can feature up to four cores. Its pipeline is wider, with 15 to 25 stages. The Cortex-A15 is present in devices such as the Chromebook, Nexus 10, and Galaxy S4.

Instructions. We highlight the NEON instructions which are important in this work, also illustrated in Figure 1. The VMULL instruction is able to carry out several multiplications in parallel; the VMULL.P8 version takes as input two 64-bit input vectors A and B of eight 8-bit binary polynomials and returns a 128-bit output vector C of eight 16-bit binary polynomials, where the i-th element of C is the multiplication of the i-th elements from each input.

The VEXT instruction, for two 64-bit registers and an immediate integer i, outputs a 64-bit value which is the concatenation of lower 8i bits of the first register and the higher 64 -8i bits of the second register. Note that if the inputs are the same register then the VEXT instruction computes right bit rotation by multiples of 8 bits. The instruction also supports 128-bit registers, with similar functionality.

Binary Field Arithmetic

Binary field arithmetic is traditionally implemented in software using polynomial basis representation, where elements of F 2 m are represented by polynomials of degree at most m -1 over F 2 . Assuming a platform with a W -bit architecture (W = 32 for ARM), a binary field element a(z) = a m-1 z m-1 +• • •+a 2 z 2 +a 1 z+a 0 may be represented by a binary vector a = (a m-1 , . . . , a 2 , a 1 , a 0 ) of length m using t = m/W words. Remaining s = W t -m bits are left unused.

Multiplication in F 2 m (field multiplication) is performed modulo f (z) = z m + r(z), an irreducible binary polynomial of degree m. This multiplication can be carried out in two steps: first, the polynomial multiplication of the operands; second, the polynomial reduction modulo f (z). The basic method for computing the polynomial multiplication of c(z

) = a(z)b(z) is to read each i-th bit of b(z) and, if it is 1, xor a(z)
i into an accumulator. However, since the left-shifting operations are in general expensive, faster variations of this method have been developed. One of the fastest known methods for software implementation is the López-Dahab (LD) algorithm [START_REF] López | High-speed software multiplication in F2m[END_REF], which processes multiple bits in each iteration. We have implemented it using the NEON engine, taking advantage of the VEXT instruction and larger number of registers.

While the LD algorithm is often the fastest in many platforms, the presence of the VMULL.P8 NEON instruction has the potential to change this landscape. However, it is not obvious how to build a n-bit polynomial multiplier for cryptographic applications (n ≥ 128) using the eight parallel 8-bit multiplications provided by VMULL.P8. Our solution is a combination of the Karatsuba algorithm and a multiplier based on VMULL.P8 which we have named the Karatsuba/NEON/VMULL multiplier (KNV), described below.

New Karatsuba/NEON/VMULL (KNV) Multiplier

Our new approach was to built a 64-bit polynomial multiplier, which computes the 128-bit product of two 64-bit polynomials. This multiplier was then combined with the Karatsuba algorithm [START_REF] Karatsuba | Multiplication of multidigit numbers on automata[END_REF] in order to provide the full multiplication.

The 64-bit multiplier was built using the VMULL.P8 instruction (VMULL for short) as follows. Consider two 64-bit polynomials a(z) and b(z) over F 2 represented as vectors of eight 8-bit polynomials:

A = (a 7 , a 6 , a 5 , a 4 , a 3 , a 2 , a 1 , a 0 ); B = (b 7 , b 6 , b 5 , b 4 , b 3 , b 2 , b 1 , b 0 ).
To compute the polynomial multiplication c(z) = a(z) • b(z) (represented as a vector C), the schoolbook method would require sixty-four 8-bit multiplications with every (a i , b j ) combination, where each product is xored into an accumulator in the appropriate position. In our proposal, these multiplications can be done with eight executions of VMULL by rearranging the inputs. Let ≫ denote a circular right shift; compute

A 1 = A ≫ 8, A 2 = A ≫ 16, A 3 = A ≫ 24, B 1 = B ≫ 8, B 2 = B ≫ 16, B 3 = B ≫ 24 and B 4 = B ≫ 32 using VEXT.
This results in:

A 1 = (a 0 , a 7 , a 6 , a 5 , a 4 , a 3 , a 2 , a 1 ); B 1 = (b 0 , b 7 , b 6 , b 5 , b 4 , b 3 , b 2 , b 1 ); A 2 = (a 1 , a 0 , a 7 , a 6 , a 5 , a 4 , a 3 , a 2 ); B 2 = (b 1 , b 0 , b 7 , b 6 , b 5 , b 4 , b 3 , b 2 ); A 3 = (a 2 , a 1 , a 0 , a 7 , a 6 , a 5 , a 4 , a 3 ); B 3 = (b 2 , b 1 , b 0 , b 7 , b 6 , b 5 , b 4 , b 3 ); B 4 = (b 3 , b 2 , b 1 , b 0 , b 7 , b 6 , b 5 , b 4 ).
Now compute these VMULL products:

D = VMULL(A, B) = (a 7 b 7 , a 6 b 6 , a 5 b 5 , a 4 b 4 , a 3 b 3 , a 2 b 2 , a 1 b 1 , a 0 b 0 ); E = VMULL(A, B 1 ) = (a 7 b 0 , a 6 b 7 , a 5 b 6 , a 4 b 5 , a 3 b 4 , a 2 b 3 , a 1 b 2 , a 0 b 1 ); F = VMULL(A 1 , B) = (a 0 b 7 , a 7 b 6 , a 6 b 5 , a 5 b 4 , a 4 b 3 , a 3 b 2 , a 2 b 1 , a 1 b 0 ); G = VMULL(A, B 2 ) = (a 7 b 1 , a 6 b 0 , a 5 b 7 , a 4 b 6 , a 3 b 5 , a 2 b 4 , a 1 b 3 , a 0 b 2 ); H = VMULL(A 2 , B) = (a 1 b 7 , a 0 b 6 , a 7 b 5 , a 6 b 4 , a 5 b 3 , a 4 b 2 , a 3 b 1 , a 2 b 0 ); I = VMULL(A, B 3 ) = (a 7 b 2 , a 6 b 1 , a 5 b 0 , a 4 b 7 , a 3 b 6 , a 2 b 5 , a 1 b 4 , a 0 b 3 ); J = VMULL(A 3 , B) = (a 2 b 7 , a 1 b 6 , a 0 b 5 , a 7 b 4 , a 6 b 3 , a 5 b 2 , a 4 b 1 , a 3 b 0 ); K = VMULL(A, B 4 ) = (a 7 b 3 , a 6 b 2 , a 5 b 1 , a 4 b 0 , a 3 b 7 , a 2 b 6 , a 1 b 5 , a 0 b 4 ).
These vectors of eight 16-bit polynomials contain the product of every (a i , b j ) combination, as required. We now need to xor everything into place. Let L = E + F , M = G + H and N = I + J. Let k i be the i-th element of vector K and analogously to L, M and N . Now, compute: P 0 = (0, 0, 0, 0, 7 , 0, 0, 0); P 4 = (0, 0, 0, 0, n 7 , n 6 , n 5 , 0);

P 1 = (0, 6 , 5 , 4 , 3 , 2 , 1 , 0 ); P 5 = (0, 0, 0, n 4 , n 3 , n 2 , n 1 , n 0 ); P 2 =
(0, 0, 0, 0, m 7 , m 6 , 0, 0); P 6 = (0, 0, 0, 0, k 7 , k 6 , k 5 , k 4 );

P 3 = (0, 0, m 5 , m 4 , m 3 , m 2 , m 1 , m 0 ); P 7 = (0, 0, 0, 0, k 3 , k 2 , k 1 , k 0 ).
The final result is obtained with:

C = A•B = D+(P 0 +P 1 )
8+(P 2 +P 3 ) 16+(P 4 +P 5 ) 24+(P 6 +P 7 ) 32.

The expansion of the above equation produces the same results of the schoolbook method for multiplication, verifying its correctness. The whole process is illustrated in Figure 2, and Algorithm 6 in the Appendix lists the assembly code for reference. The partial results (P 0 +P 1 ) 8, (P 2 +P 3 ) 16 or (P 4 +P 5 ) 24 can each be computed from L, M or N with four instructions (two xors, one mask operation and one shift). The partial result (P 6 + P 7 ) 32 can be computed from K with three instructions (one xor, one mask operation and one shift). To clarify our approach, we list the assembly code used in the computation of L and (P 0 + P 1 ) 8 from A and B in Algorithm 1 and describe it below. In Algorithm 1, the 128-bit NEON register tq can be viewed as two 64bit registers such that tq = th||tl where tl is the lower part and th is the higher part; the same applies to other registers. In line 1, the VEXT instruction concatenates the lower 8 bits of A with the higher (64 -8) = 56 bits of A, resulting in the value A 1 being stored in tl. Line 2 computes F = VMULL(A 1 , B) in the tq register. Lines 3 and 4 compute B 1 and then E = VMULL(A, B 1 ) in the uq register, while line 5 computes L = E + F in the tq register. Observe that the result we want, (P 0 + P 1 ), can be viewed as (0, 6 , 5 , 4 , 3 + 7 , 2 , 1 , 0 ). The straightforward way to compute (P 0 + P 1 ) from L would be to use a mask operation to isolate 7 , xor it to tq in the appropriate position and do another mask operation to clear the highest 16 bits. However, we use another approach Fig. 2. The 64 × 64-bit polynomial multiplier using VMULL which does not need a temporary register, described as follows. In line 6, we xor the higher part of tq into the lower part, obtaining ( 7 , 6 , 5 , 4 , 3 + 7 , 2 + 6 , 1 + 5 , 0 + 4 ). Line 7 uses a mask operation to clear the higher 16 bits of tq, which now holds (0, 6 , 5 , 4 , 3 + 7 , 2 + 6 , 1 + 5 , 0 + 4 ). In line 8, the higher part of tq is again xored into the lower part, resulting in the expected (0, 6 , 5 , 4 , 3 + 7 , 2 , 1 , 0 ) which is finally shifted 8 bits to the left with the VEXT instruction in line 9.

Additional Binary Field Operations

Squaring a binary polynomial corresponds to inserting a 0 bit between every consecutive bits of the input, which often requires precomputed tables. The VMULL instruction can improve squaring since, when using the same 64-bit value as the two operands, it computes the 128-bit polynomial square of that value.

Multiplication and squaring of binary polynomials produce values of degree at most 2m-2, which must be reduced modulo f (z) = z m +r(z). Since z m ≡ r(z) (mod f (z)), the usual approach is to multiply the upper part by r(z) using shift and xors. For small polynomials r(z) it is possible to use the VMULL instruction to carry out multiplication by r(z) with a special 8×64-bit multiplier; this was done for F 2 128 (r(z) = z 7 + z 2 + z + 1) and F 2 251 (r(z) = z 7 + z 4 + z 2 + 1). Reduction in F 2 283 takes advantage of the factorization of r(z) = z 12 + z 7 + z 5 + 1 = (z 7 + 1)(z 5 + 1) as described in [START_REF] Aranha | Faster implementation of scalar multiplication on Koblitz curves[END_REF]. For F 2 571 , r(z) = z 10 + z 5 + z 2 + 1, and its reduction is computed with the usual shifts and xors. Field inversion is commonly carried out with the well-known extended Euclidean algorithm, but it does not take constant time and may be vulnerable to side channel attacks. For this reason, we have used the Itoh-Tsujii algorithm [START_REF] Itoh | A fast algorithm for computing multiplicative inverses in GF(2 m ) using normal bases[END_REF], which is an optimization of inversion through Fermat's little theorem (a(x) -1 = a(x) 2 m -2 ). The algorithm uses a repeated field squaring operation a(x) 2 k for some values of k; we have implemented a special function where field squaring is completely done using NEON instruction and registers using the same techniques described for squaring and reduction, but avoiding reads and writes to memory.

Algorithms

The KNV multiplier was used as the building block for a implementation of Elliptic Curve Cryptography (ECC) and of authenticated encryption (AE), which we now describe together with our implementation of side-channel resistance.

Side-Channel Resistance

Side-channel attacks [START_REF] Kocher | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF] are a serious threat for cryptographic implementations; different attacks require different levels of protection. Here we consider the basic level of resistance which avoids: branching on secret data, algorithms with timings dependent on secret data, and accessing table indexes with secret indices.

The building block of a side-channel resistant (SCR) implementation can be considered the "select" operation t ← Select(a, b, v), which copies a into t if the bit v is 0 or copies b if v is 1. This operation can be implemented without branching as described in [START_REF] Käsper | Fast elliptic curve cryptography in OpenSSL[END_REF] and listed for reference in Algorithm 3 in the Appendix. In ARM assembly, Select can be implemented easily since most instructions can be made conditional to a previous register comparison.

However, a faster approach is to use the NEON instruction VBIT Qd, Qn, Qm (bitwise insert if false) -it inserts each bit in Qn into Qd if the corresponding bit in Qm is 1, otherwise it leaves the corresponding bit in Qd unchanged. If the m value from Algorithm 3 is stored in Qm, then VBIT is precisely the Select operation restricted to the case where t and a refer to the same location (which is often the case).

Some of the algorithms we will describe use precomputed tables to improve performance. However, looking up a table entry may leak its index through sidechannels, since it affects the contents of the processor cache. For this reason, we employ a side-channel resistant table lookup. We follow the strategy found in the source code of [START_REF] Bernstein | NEON crypto[END_REF], listed for reference in Algorithm 4 in the Appendix, where s can be computed without branches by copying the sign bit of r (e.g. in the C language, convert r to unsigned and right shift the result in order to get the highest bit). We have implemented the SCR table lookup for elliptic curve points entirely in assembly with the VBIT instruction. It is possible to hold the entire t value (a point) in NEON registers, without any memory writes except for the final result.

Elliptic Curve Cryptography

Elliptic Curve Cryptography is composed of public key cryptographic schemes using the arithmetic of points on elliptic curves over finite fields, and it uses shorter keys at the same security level in comparison to alternative public-key systems such as RSA and DSA. Two types of fields are mainly used: prime fields (with p elements, where p is prime) and binary fields (with 2 m elements for some m). While prime fields are used more often (and most literature on ECC for ARM uses them), we decided to study the efficiency of ECC using binary fields with our KNV multiplier.

Four standardized curves for Elliptic Curve Cryptography (ECC) [START_REF]Digital signature standard (DSS)[END_REF] were implemented: the random curves B-283 and B-571 which provide 128 and 256 bits of security respectively; and the Koblitz curves K-283 and K-571 which provide the same bits of security respectively. A non-standard curve over F 2 251 [START_REF] Bernstein | Batch binary Edwards[END_REF] ("B-251", roughly 128 bits of security) was also implemented, due to its high efficiency.

The main algorithm in ECC is the point multiplication, which often appears in three different cases: the random point multiplication kP (k terms of the elliptic point P are summed), where the point P is not known in advance; the fixed point multiplication kG, where G is fixed; and the simultaneous point multiplication kP + G where P is random and G is fixed. In the random point case, we chose the Montgomery-LD multiplication [START_REF] López | Fast multiplication on elliptic curves over GF(2 m ) without precomputation[END_REF] which offers high efficiency and basic side-channel resistance (SCR) without precomputed tables. In the fixed point case, the signed multi-table Comb method is employed [START_REF] Hamburg | Fast and compact elliptic-curve cryptography[END_REF], with side-channel resistant table lookups. It uses t tables with 2 w-1 points. For simultaneous point multiplication, we have used the interleaving method [START_REF] Gallant | Faster point multiplication on elliptic curves with efficient endomorphisms[END_REF][START_REF] Möller | Algorithms for multi-exponentiation[END_REF] of w-(T)NAF. It employs two window sizes: d for the fixed point (requiring a precomputed table with 2 d-2 elements) and w for the random point (requiring a on-the-fly table with 2 w-2 elements). SCR is not required in this case since the algorithm is only used for signature verification, whose inputs are public.

The main advantage of Koblitz curves is the existence of specialized algorithms for point multiplication which take advantage of the efficient endomorphism τ present in those curves [START_REF] Solinas | Efficient arithmetic on Koblitz curves[END_REF]. However, we have not used these algorithms since we are not aware of any SCR methods for recoding the scalar k into the representation required by them. Therefore, the only performance gain in those curves were obtained using a special doubling formula with two field multiplications; see Algorithm 2. Montgomery-LD also requires one less multiplication per iteration in Koblitz curves.

Algorithm 2 Our proposed point doubling on the Koblitz curve E a : y 2 + xy = x 3 + ax 2 + 1, a ∈ {0, 1} over F 2 m using LD projective coordinates

Input: Point P = (X1, Y1, Z1) ∈ Ea(F2m ) Output: Point Q = (X3, Y3, Z3) = 2P 1: S ← X1Z1 2: T ← (X1 + Z1) 2 3: X3 ← T 2 4: Z3 ← S 2 5: if a = 0 then 6: Y3 ← ((Y1 + T )(Y1 + S) + Z3) 2 7: else 8:
Y3 ← (Y1(Y1 + S + T )) 2 9: return (X3, Y3, Z3)

We have selected the three following well known ECC protocols. The Elliptic Curve Digital Signature Algorithm (ECDSA) requires a fixed point multiplication for signing and a simultaneous point multiplication for verification. The Elliptic Curve Diffie-Hellman (ECDH) [START_REF] Barker | NIST SP 800-56A: Recommendation for pairwise key establishment schemes using discrete logarithm cryptography[END_REF] is a key agreement scheme which requires a random point multiplication, and the Elliptic Curve Schnorr Signature (ECSS) [START_REF] Schnorr | Efficient signature generation by smart cards[END_REF] is similar to ECDSA but does not require an inversion modulo the elliptic curve order.

Inversion modulo the elliptic curve order

When signing, the ECDSA generates a random secret value k which is multiplied by the generator point; this requires side-channel resistance since if k leaks then it is possible to compute the signer's private key. However, an often overlooked point is that ECDSA also requires the inversion of k modulo the elliptic curve order n. This is usually carried out with the extended Euclidean algorithm, whose number of steps are input-dependent and therefore theoretically susceptible to side-channel attacks. While we are not aware of any concrete attacks exploiting this issue, we are also not aware of any arguments for the impossibility of such an attack. Therefore, we believe it is safer to use a SCR inversion.

The obvious approach for SCR inversion would be to use Fermat's little theorem (a -1 ≡ a n-2 (mod n)), which would require a very fast multiplier modulo n to be efficient. However, we have found a simple variant of the binary extended Euclidean algorithm by Niels Möller [START_REF] Möller | Nettle, low-level cryptographics library[END_REF] which takes a fixed number of steps. For reference, it is described in Algorithm 5 in the Appendix, where branches are used for clarity and can be avoided with Select. The algorithm is built entirely upon four operations over integers with the same size as n: addition, subtraction, negation and right shift by one bit. These can be implemented in assembly for speed; alternatively the whole algorithm can be implemented in assembly in order to avoid reads and writes by keeping operands (a, b, u and v) in NEON registers. We have followed the latter approach for fields at the 128-bit level of security, and the former approach for the 256-bit level, since the operands are then too big to fit in registers.

Interestingly, implementing this algorithm raised a few issues with NEON. The right shift and Select can be implemented efficiently using NEON; however, we had to resort to regular ARM instructions for addition and subtraction, since it is difficult to handle carries with NEON. This requires moving data back and forth from NEON to ARM registers; which can be costly. In the Cortex A8, since the NEON pipeline starts after the ARM pipeline, a move from NEON to ARM causes a 15+ cycles stall. The obvious approach to mitigate this would be to move from NEON to ARM beforehand, but this is difficult due to the limited number of ARM registers. Our approach was then to partially revert to storing operands in memory since it becomes faster to read from cached memory than to move data between NEON and ARM. In the Cortex A9 we followed the same approach, but with smaller gains, since the ARM and NEON pipelines are partly parallel and moving from NEON to ARM is not that costly (around 4 cycles of latency). However, the Cortex A15 is much more optimized in this sense and our original approach of keeping operands in registers was faster.

Authenticated Encryption

An authenticated encryption (AE) symmetric scheme provides both encryption and authentication using a single key, and is often more efficient and easy to employ than using two separate encryption and authentication schemes (e.g. AES-CTR with HMAC). The Galois/Counter Mode (GCM) [START_REF] Mcgrew | The security and performance of the Galois/Counter Mode (GCM) of operation[END_REF] is an AE scheme which is built upon a block cipher, usually AES. It was standardized by NIST and is used in IPSec, SSH and TLS. For each message block, GCM encrypts it using the underlying block cipher in CTR mode and xors the ciphertext into an accumulator, which is then multiplied in F 2 128 by a key-dependent constant. After processing the last block, this accumulator is used to generate the authentication tag.

We have implemented the F 2 128 multiplication using the same techniques described above; modular reduction took advantage of the VMULL instruction since r(z) in this field is small. We remark that our implementation does not uses precomputed tables (as it is often required for GCM) and is side-channel resistant (if the underlying block cipher also is). For benchmarking, we have used an assembly implementation of AES from OpenSSL without SCR; however this is not an issue since we are more interested in the overhead added by GCM to the plain AES encryption.

Results

To evaluate our software implementation, we have used a DevKit8000 board with an 600 MHz ARM Cortex-A8 processor, a PandaBoard board with a 1 GHz ARM Cortex-A9 processor and an Arndale board with a 1.7 GHz ARM Cortex-A15 processor. We have used the GCC 4.5.1 compiler. Our optimized code is written in the C and assembly languages using the RELIC library [START_REF] Aranha | RELIC is an Efficient LIbrary for Cryptography[END_REF]. Each function is benchmarked with two nested loops with n iterations each; inside the outer loop, an input is randomly generated; and the given operation is executed n times in the inner loop using this input. The total time taken by this procedure, given by the clock gettime function in nanoseconds, is divided by n 2 in order to give the final result for the given operation. We chose n = 1024 for measuring fast operations such as finite field arithmetic, and n = 64 for the slower operations such as point multiplication.

Table 1 presents the timings of field operations used in ECC. Our new Karatsuba/NEON/VMULL (KNV) multiplication gives a up to 45% improvement compared to the LD/NEON implementation. For field squaring, we have obtained a significant improvement of up to 70% compared to the conventional table lookup approach. The very fast squaring made the Itoh-Tsujii inversion feasible. When limited to standard NIST elliptic curves, our ECDH over K-283 is 70% faster than the results of Morozov et al. [START_REF] Morozov | System integration of elliptic curve cryptography on an OMAP platform[END_REF]. Considering non-standard curves, we now compare our binary B-251 to the prime curves in the state of the art; this is also shown in Table 3. On the A8, compared to Bernstein and Schwabe's [START_REF] Bernstein | NEON crypto[END_REF], our key agreement is 25% slower; our signing is 26% faster; and our verification is 43% slower. On the A9, compared to Faz-Hernández et al. [START_REF] Faz-Hernández | Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV-GLS curves[END_REF], our random point multiplication is 88% slower, our fixed point multiplication is 53% slower; and our simultaneous point multiplication is 132% slower. On the A15, also compared to Faz-Hernández et al. [START_REF] Faz-Hernández | Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV-GLS curves[END_REF], our random point multiplication is 108% slower, our fixed point multiplication is 72% slower; and our simultaneous point multiplication is 162% slower. We remark that this is a comparison of our implementation of binary elliptic curves with the state-of-the-art prime elliptic curve implementations, which are very different. In particular, note that the arithmetic of prime curves can take advantage of native 32 × 32-bit and 64 × 64bit multiply instructions.

For the GCM authenticated encryption scheme, we have obtained 38.6, 41.9 and 31.1 cycles per byte for large messages, for the A8, A9 and A15 respectively; a 13.7, 13.6 and 9.2 cpb overhead to AES-CTR. Our A8 overhead is 46% faster than the timing reported by Krovetz and Rogaway's [START_REF] Krovetz | The software performance of authenticated-encryption modes[END_REF] and 8.6% faster than [START_REF] Polyakov | The OpenSSL project[END_REF].

Conclusions and Future Work

In this paper we have introduced a new multiplier for 64-bit binary polynomial multiplication using the VMULL instruction, part of the NEON engine present in many ARM processors in the Cortex-A series. We then explain how to use the new multiplier to improve the performance of finite field multiplication in F 2 m . We have also shown the performance gains by the new multiplier in elliptic curve cryptography and authenticated encryption with GCM. We were unable to break speed records for non-standard elliptic curves, but we believe this work offers a useful insight in how binary curves compare to prime curves in ARM processors. For standard curves we were able to improve the state of the art, as well for the GCM authenticated encryption scheme.

An interesting venue for future research is on the implementation of standard prime curves for ARM, which seems to be lacking in the literature. In addition, the arrival of ARMv8 processors in the future (including the Cortex A53 and A57) may provide great speed up to binary ECC, since the architecture will provide two instructions for the full 64-bit binary multiplier (PMULL and PMULL2) and will double the number of NEON registers [START_REF]ARM Limited: ARMv8 instruction set overview[END_REF].

A Reference Algorithms

Listed below are algorithms for reference and the full code of our multiplier.

Algorithm 3 Branchless select, described by Emilia Käsper in [START_REF] Käsper | Fast elliptic curve cryptography in OpenSSL[END_REF] Input

Fig. 1 .

 1 Fig. 1. Main NEON instructions in this work: VMULL.P8 (shortened as VMULL) and VEXT. Each square is 8 bits; rectangles are 16 bits.

Fig. 3 .

 3 Fig. 3. Our timings for ECC algorithms at the 128-bit level of security

Table 1 .

 1 Our timings in cycles for binary field arithmetic

	Algorithm/Processor		F 2 251	F 2 283	F 2 571
	Multiplication (LD)	A8	671	1,032	3,071
		A9	774	1,208	3,140
		A15	412	595	1,424
	Multiplication (KNV) A8	385	558	1,506
		A9	491	701	1,889
		A15	317	446	1,103
	Squaring (Table)	A8	155	179	349
		A9	168	197	394
		A15	128	151	282
	Squaring (VMULL)	A8	57	53	126
		A9	63	59	146
		A15	43	42	99
	Inversion (Itoh-Tsujii) A8	18,190 20,777 90,936
		A9	19,565 22,356 97,913
		A15 13,709 16,803 71,220

Table 2 .

 2 Our timings in 10 3 cycles for elliptic curve protocols Timings for ECC protocols are listed in Table2, while Figure3plots the 128-bit level timings to aid visualization. Compared to the LD/NEON multiplier with table-based squaring, the KNV multiplication with VMULL-based squaring improved the point multiplication by up to 50%. ECDSA is 25-70% slower than ECSS due to the SCR modular inversion required.

	Algorithm/Processor		B-251 B-283 K-283 B-571 K-571
	ECDH Agreement A8	657 1,097	934 5,731	4,870
		A9	789 1,350	1,148 7,094	6,018
		A15	511	866	736 4,242	3,603
	ECDSA Sign	A8	458	624	606 2,770	2,673
		A9	442	612	602 2,880	2,816
		A15	233	337	330 1,740	1,688
	ECSS Sign	A8	270	389	371 1,944	1,846
		A9	285	414	404 2,137	2,073
		A15	186	270	263 1,264	1,212
	ECDSA Verify	A8	943 1,397	791 6,673	3,069
		A9	1,100 1,644	887 8,171	3,581
		A15	715 1,064	583 4,882	2,237
	ECSS Verify	A8	933 1,337	735 6,338	3,064
		A9	1,086 1,572	827 7,776	3,602
		A15	715 1,022	546 4,623	2,228

Table 3 .

 3 Our best ECC timings (on the non-standard elliptic curve B-251 over binary field) compared to stateof-the-art timings using non-standard elliptic curves over prime fields, at the 128-bit level of security, in 10 3 cycles

	Algorithm/Processor	Ours	[6]	[9]	[7]
	Key Agreement A8	657 527
		A9	789		616 417
		A15	511			244
	Sign	A8	270 368
		A9	285		262 172
		A15	186			100
	Verify	A8	933 650
		A9	1,086		605 463
		A15	715			266

  : W -bit words a, b, v, with v ∈ {0, 1} Output: b if v, else a 1: function Select(a, b, v) Algorithm 4 SCR table lookup, contained in the source code of Bernstein and Schwabe's [6] Algorithm 6 Our proposed ARM NEON 64-bit binary multiplication C = A•B with 128-bit result Input: 64-bit registers ad (holding A), bd (holding B), k16 (holding the constant 0xFFFF), k32 (holding 0xFFFFFFFF), k48 (holding the constant 0xFFFFFFFFFFFF). Output: 128-bit register rq (rh|rl) (holding A).

	2:	m ← TwosComplement(-v, W )	convert -v to W -bit two's complement
	3:	t ← (m & (a ⊕ b)) ⊕ a
	4:	return t Uses temporary 128-bit registers t0q (t0h|t0l), t1q (t1h|t1l), t2q (t2h|t2l),
		t3q (t3h|t3l).
	1: vext.8	t0l, ad, ad, $1	A1
	2: vmull.p8 t0q, t0l, bd	F = A1*B
	3: vext.8	rl, bd, bd, $1	B1
	4: vmull.p8 rq, ad, rl	E = A*B1
	5: vext.8	t1l, ad, ad, $2	A2
	6: vmull.p8 t1q, t1l, bd	H = A2*B
	7: vext.8	t3l, bd, bd, $2	B2
	8: vmull.p8 t3q, ad, t3l	G = A*B2
	9: vext.8	t2l, ad, ad, $3	A3
	10: vmull.p8 t2q, t2l, bd	J = A3*B
	11: veor		t0q, t0q, rq	L = E + F
	12: vext.8	rl, bd, bd, $3	B3
	13: vmull.p8 rq, ad, rl	I = A*B3
	14: veor		t1q, t1q, t3q	M = G + H
	15: vext.8	t3l, bd, bd, $4	B4
	16: vmull.p8 t3q, ad, t3l	K = A*B4
	17: veor		t0l, t0l, t0h	t0 = (L) (P0 + P1) << 8
	18: vand		t0h, t0h, k48
	19: veor		t1l, t1l, t1h	t1 = (M) (P2 + P3) << 16
	20: vand		t1h, t1h, k32
	21: veor		t2q, t2q, rq	N = I + J
	22: veor		t0l, t0l, t0h
	23: veor		t1l, t1l, t1h
	24: veor		t2l, t2l, t2h	t2 = (N) (P4 + P5) << 24
	2: 25: vand (a, b, u, v) ← (x, n, 1, 1) t2h, t2h, k16
	3: 26: veor	← log 2 n + 1 t3l, t3l, t3h	number of bits in n t3 = (K) (P6 + P7) << 32
	4: 27: vmov.i64 t3h, $0 for i ← 0 to 2 -1 do
	5: 28: vext.8 odd ← a & 1 t0q, t0q, t0q, $15
	6: 29: veor	if odd and a ≥ b then t2l, t2l, t2h
	7: 30: vext.8	a ← a -b t1q, t1q, t1q, $14
	8: 31: vmull.p8 rq, ad, bd else if odd and a < b then	D = A*B
	9: 32: vext.8	(a, b, u, v) ← (b -a, a, v, u) t2q, t2q, t2q, $13
	10: 33: vext.8 a ← a t3q, t3q, t3q, $12 1
	11: 34: veor 12: 35: veor	t0q, t0q, t1q if odd then u ← u -v if u < 0 then u ← u + n t2q, t2q, t3q
	13: 36: veor	if u & 1 then u ← u + n rq, rq, t0q
	14: 37: veor	u ← u rq, rq, t2q 1
	15:	return v

Input: array a with n elements of any fixed type, desired index k,

0 ≤ k < n Output: a[k] 1: function Choose(a, n, k) 2: t ← a[0] 3: for i ← 1 to n -1 do 4: r ← (i ⊕ k) -1 5: s ← (r < 0) s holds whether i is equal to k 6: t ← Select(t, a[i], s) 7:

return t Algorithm 5 SCR modular inversion algorithm by Niels Möller in the Nettle library

[START_REF] Möller | Nettle, low-level cryptographics library[END_REF]

Input: integer x, odd integer n, x < n Output: x -1 (mod n) 1: function ModInv(x, n)

http://conradoplg.cryptoland.net/ecc-and-ae-for-arm-neon/

Supported by FAPESP grant 2010/15340-3 Partially supported by a research productivity scholarship from CNPq-Brazil.


Andreas Hülsing

Lea Rausch

Johannes Buchmann

Optimal Parameters for XMSS M T

Keywords: hash-based signatures, parameter selection, linear optimization, forward secure signatures, implementation

We introduce Multi Tree XMSS (XMSS M T ), a hash-based signature scheme that can be used to sign a virtually unlimited number of messages. It is provably forward and hence EU-CMA secure in the standard model and improves key and signature generation times compared to previous schemes. XMSS M T has -like all practical hash-based signature schemes -a lot of parameters that control different trade-offs between security, runtimes and sizes. Using linear optimization, we show how to select provably optimal parameter sets for different use cases.

Introduction

Digital signatures are among the most important cryptographic primitives in practice. They are used to secure communication protocols like SSL/TLS and SSH, software updates, or to replace handwritten signatures. Hash-based signature schemes are an interesting alternative to the signature schemes used today. Not only because they are assumed to resist quantum computer aided attacks, but also because of their fast signature generation and verification times as well as their strong security guarantees. The latest hash-based signature schemes [START_REF] Buchmann | XMSS -a practical forward secure signature scheme based on minimal security assumptions[END_REF][START_REF] Hülsing | Forward secure signatures on smart cards[END_REF] come with a standard model security proof and outperform RSA in many settings regarding runtimes.

Practical hash-based signature schemes have a lot of parameters that control several trade-offs between runtimes and sizes. Hence, an important open problem on the way of making hash-based signatures practical is parameter selection. In previous works [START_REF] Buchmann | XMSS -a practical forward secure signature scheme based on minimal security assumptions[END_REF][START_REF] Buchmann | Merkle signatures with virtually unlimited signature capacity[END_REF][START_REF] Johannes Buchmann | CMSS -an improved Merkle signature scheme[END_REF][START_REF] Dahmen | Digital signatures out of second-preimage resistant hash functions[END_REF][START_REF] Hülsing | Forward secure signatures on smart cards[END_REF] it was shown how to select secure parameters using the exact security reductions, but this still leaves too many possible parameter choices to apply a brute-force search. Even applying reasonable restrictions on the parameters, the search space can easily grow to the order of 2 80 and more. In this work we introduce Multi Tree XMSS (XMSS M T ), a new hash-based signature scheme that contains the latest hash-based signature schemes XMSS and XMSS + as special cases and propose a systematic way to select the optimal parameter set for a given scenario for XMSS M T . XMSS M T improves XMSS in a way, that it allows for a virtually unlimited number of signatures, while it preserves its desirable properties. XMSS M T has minimal security requirements, i.e. it can be proven EU-CMA secure in the standard model, when instantiated with a pseudorandom function family and a second preimage resistant hash function. Moreover, XMSS M T is forward secure [START_REF] Bellare | A forward-secure digital signature scheme[END_REF] and introduces a new trade-off between signature and key generation time on the one hand and signature size on the other hand. XMSS M T can be viewed as applying the tree chaining idea introduced in [START_REF] Johannes Buchmann | CMSS -an improved Merkle signature scheme[END_REF] to XMSS and combine it with the improved distributed signature generation proposed in [START_REF] Hülsing | Forward secure signatures on smart cards[END_REF].

For XMSS M T , we show how to model the parameter selection problem as a linear optimization problem. A straight forward approach would lead many non-linear constraints. To overcome this problem, we use the generalized lambda method [START_REF] Moritz | A Mixed Integer Approach for the Transient Case of Gas Network Optimization[END_REF] for linearization. The resulting model can then be solved using the Simplex algorithm [START_REF] Dantzig | Linear Programming And Extensions[END_REF]. As the general lambda method is exact, the Simplex algorithm outputs a provably optimal solution under the given constraints. We made the model flexible, such that it can be used for different use cases with different requirements using different inputs. We present results for demonstrative use cases and compare them to possible parameter choices from previous work. However, the code is available on the corresponding authors home page and can be used to select optimal parameters for other use cases. Linear optimization was used before in [START_REF] Buchmann | Merkle signatures with virtually unlimited signature capacity[END_REF] to find optimal parameters. Unfortunately, the results given there do not carry over to the new hash-based signature schemes, as less parameters were taken into account and the authors of [START_REF] Buchmann | Merkle signatures with virtually unlimited signature capacity[END_REF] do not provide details about how to model the problem.

Organization. We start with an introduction to XMSS M T in Section 2, where we also discuss theoretical runtimes and parameter sizes as well as security and correctness of the scheme. In Section 3 we show how to model the parameter selection problem for XMSS M T as a linear optimization problem and present optimal parameters for exemplary use cases in Section 4. We discuss our results and draw a conclusion in Section 5.

Multi Tree XMSS -XMSS M T

In this section we introduce XMSS M T . For a better understanding, we first give a brief description of the scheme. A hash-based signature scheme starts with a one-time signature scheme (OTS). To obtain a many time signature scheme, many instances of the OTS are used and their public key are authenticated using a binary hash tree, called Merkle-Tree. The root of the tree is the public key of the scheme and the secret key is the seed of a pseudorandom generator that is used to generate the OTS secret keys. A signature contains an index, the OTS signature, and the so called authentication path which contains the siblings of the nodes on the way from the used OTS key pair to the root. For XMSS M T we extend this using many layers of trees. The trees on the lowest layer are used to sign the messages and the trees on higher layers are used to sign the roots of the trees on the layer below. The public key contains only the root of the tree on the top layer. A signature consists of all the signatures on the way to the highest tree. A graphical representation of the scheme can be found in Appendix E. In the following we describe the construction in detail, starting with the description of some building blocks. Afterwards we describe the algorithms of the scheme and present an theoretical analysis of its performance, security and correctness.

Parameters. For security parameter n ∈ N, the basic building blocks of XMSS M T are a pseudorandom function family F n = {F K : {0, 1} n → {0, 1} n |K ∈ {0, 1} n }, and a second preimage resistant hash function H : {0, 1} 2n → {0, 1} n . Further parameters are the number of layers d ∈ N, the binary message length m and one parameter set per layer. For a layer 0 ≤ i ≤ d-1 a parameter set contains the tree height h i ∈ N, the so called BDS parameter k i ∈ N with the restrictions k i < h i and h i -k i is even and the Winternitz parameter w i ∈ N, w i ≥ 2. To enable improved distributed signature generation we require (h i+1 -

k i+1 + 6)/2 ≤ 2 h i -k i +1 for 0 ≤ i < d-1, as well as (h 0 -k 0 )/2 ≥ d-1. A XMSS M T key pair can be used to sign h = d-1
i=0 h i messages of m bits. The remaining parameters define the various trade-offs explained below. These parameters are publicly known.

Winternitz OTS. XMSS M T uses the Winternitz-OTS (W-OTS) from [START_REF] Buchmann | On the security of the Winternitz one-time signature scheme[END_REF]. W-OTS uses the function family F n and a value X ∈ {0, 1} n that is chosen during XMSS key generation. Besides message length m and Winternitz parameter w it has another parameter = (m, w) that is a function of m and w. The W-OTS secret key, public key and signatures consist of bit strings of length n. An important property of W-OTS is that the public key can be computed from a valid signature. The sizes of signature, public, and secret key are n bits. The runtimes for key generation, signature generation and signature verification are all bounded by (w -1) evaluations of elements from F n . The Winternitz parameter w controls a time -space trade-off, as shrinks logarithmically in w. For more detailed information see Appendix A.

XMSS Tree. XMSS M T uses the XMSS tree construction, originally proposed in [START_REF] Dahmen | Digital signatures out of second-preimage resistant hash functions[END_REF]. An XMSS tree of height h is a binary tree with h + 1 levels. The leaves are on level 0, the root on level h. The nodes on level j, are denoted by N i,j , for 0 ≤ i < 2 h-j , 0 ≤ j ≤ h. To construct the tree, h bit masks B j ∈ {0, 1} 2n , 0 < j ≤ h and the hash function H, are used. N i,j , for 0 < j ≤ h, is computed as

N i,j = H((N 2i,j-1 ||N 2i+1,j-1 ) ⊕ B j ).
Leaf Construction. The leaves of a XMSS tree are the hash values of W-OTS public keys. To avoid the need of a collision resistant hash function, another XMSS tree is used, called L-tree. The leaves of an L-tree are the bit strings (pk 0 , . . . , pk ) from the corresponding public key. If is not a power of 2, a left node that has no right sibling is lifted to a higher level of the L-tree until it becomes the right sibling of another node. For the L-tree, the same hash function as above but log new bitmasks are used. These bitmasks are the same for all L-trees.

Pseudorandom Generator. The W-OTS key pairs belonging to one XMSS tree are generated using two pseudorandom generators (PRG) build using F. The stateful forward secure PRG FsGen : {0, 1} n → {0, 1} n × {0, 1} n is used to generate one seed value per W-OTS keypair. Then the seed is expanded to the W-OTS secret key bit strings using F n .

FsGen starts from a uniformly random state S 0 $ ←-{0, 1} n . On input of a state S i , FsGen generates a new state S i+1 and a pseudorandom output

R i : FsGen(S i ) = (S i+1 ||R i ) = (F S i (0)||F S i (1)).
The output R i is used to generate the ith W-OTS secret key (sk 1 , . . . , sk ) as sk j = F R i (j -1), 1 ≤ j ≤ .

Tree Traversal -The BDS Algorithm. To compute the authentication paths for the W-OTS key pairs of one XMSS tree, XMSS M T uses the BDS algorithm [START_REF] Buchmann | Merkle tree traversal revisited[END_REF]. The choice of this algorithm is already a time -memory trade-off. Instead of computing every node of the authentication path when needed, BDS uses some storage to decrease the worst case runtime. The BDS algorithm uses the TreeHash algorithm (see Algorithm 1) as a subroutine. The BDS algorithm reduces the worst case signing time from 2 h -1 to (h -k)/2 leaf computations and evaluations of TreeHash. More specifically, the BDS algorithm does three things. First, it uses the fact that a node that is a left child can be computed from values that occurred in an authentication path before, spending only one 2 -3k -2 + 2 k tree nodes that is initialized during key generation. To compute the authentication paths, the BDS algorithm spends (h -k)/2 leaf computations and evaluations of TreeHash as well as (h -k) calls to F to update its state per signature. For more details see [START_REF] Buchmann | Merkle tree traversal revisited[END_REF].

Key Generation. The XMSS M T key generation algorithm takes as input all of the above parameters. First, the max 0≤i≤d-1 {h i + log i } bitmasks and X are chosen uniformly at random. The same bitmasks and X are used for all layers. Then, the root of the first XMSS tree on each layer is computed. This is done in an ordered way, starting from layer 0. For the tree Tree i on layer i the initial state of FsGen, S 0,i is chosen uniformly at random and a copy of it is stored as part of the secret key SK. The tree is constructed using the TreeHash algorithm above. Starting with an empty stack Stack i and S 0,i , all 2 h i leaves are successively generated and used as input to the TreeHash algorithm to update Stack i . This is done updating S i and generating the W-OTS key pairs using its output. The W-OTS public key is then used to compute the corresponding leaf using an L-tree which in turn is used to update the current Stack i using TreeHash. Then the W-OTS key pair is deleted. After all 2 h i leaves were processed by TreeHash, the only value on Stack i is the root Root i of Tree i . When Root i 0 ≤ i < d-1, is computed, it is signed using the first W-OTS key pair of Tree i+1 , which is computed next. This signature σ i+1 can be extracted while Tree i is generated and hence does not need any additional computation. Then σ i+1 is stored as part of SK. If the highest layer d -1 is reached, Root d-1 is stored in the public key PK. During the computation of Root i , the state of the BDS algorithm State BDS,i is initialized. For details see [START_REF] Buchmann | Merkle tree traversal revisited[END_REF].

Finally, the data structures for the next trees are initialized: For the next tree Next i on each layer 0 ≤ i < d -1 a FsGen state S n,i is chosen uniformly at random and a new TreeHash stack Stack next,i is initialized. Summing up, SK consists of the states (S 0,i ,

State BDS,i ), 0 ≤ i ≤ d -1 and the d -1 signatures σ i , 0 < i ≤ d -1. Additionally, it contains d -1 FsGen states S n,i , d -1 TreeHash stacks Stack next,i and d -1 BDS states State BDS,n,i for the next trees Next i on layer 0 ≤ i < d -1.
The public key PK consists of the max 0≤i≤d-1 {h i + log i } bitmasks, the value X and Root d-1 .

Signature generation. The signature generation algorithm takes as input a m bit message M , the secret key SK, and the index i, indicating that this is the ith message signed with this keypair. The signature generation algorithm consists of two phases. First, M is signed. A XMSS M T signature Σ = (i, σ 0 , Auth 0 , σ 1 , Auth 1 , . . . , σ d , Auth d ) contains the index i, the W-OTS signature σ 0 on the message M , the corresponding authentication path for Tree 0 and the W-OTS signatures on the roots of the currently used trees together with the corresponding authentication paths. The only thing that has to be computed is σ 0 -the W-OTS signature on message M using the ith W-OTS key pair on the lowest layer. All authentications paths and the W-OTS signatures on higher layers are already part of the current secret key.

The second phase is used to update the secret key. Therefor BDS is initialized with State BDS,0 and receives (h 0 -k 0 )/2 updates. If not all of these updates are needed to update State BDS,0 , i.e. all scheduled TreeHash instances are finished and there are still updates left, the remaining updates are used for the upper trees. On the upper layers, not only the BDS state has to be updated, but while one leaf is used, one leaf in the next tree must be computed and h i -k i FsGen states must be updated. This means that remaining updates from layer zero are first used to update State BDS,1 . If all scheduled TreeHash instances in State BDS,1 are finished, one update is used to compute a new leaf for Next 1 and to update Stack next,1 afterwards. The next update is used to for the FsGen states. If layer 1 does not need anymore updates, the remaining updates are forwarded to layer 2 and so on, until either all updates are used or all tasks are done. Finally, one leaf of the next tree is computed and used as input for TreeHash to update Stack next,0 . A special case occurs if i mod 2 h 0 = 2 h 0 -1. In this case, the last W-OTS key pair of the current Tree 0 was used. This means that for the next signature a new tree is needed on every layer j with i mod 2 h j = 2 h j -1. For all these layers, Stack next,j already contains the root of Next j . So, Tree j+1 is used to sign Root j . Each signature is counted as one update. In case not all updates are needed, remaining updates are forwarded to the first layer that did not get a new tree. In SK, State BDS,j , S j , and Σ j are replaced by the newly computed data. Afterwards, new data structures for the next tree on layer j are initialized and used to replace the ones in SK. Finally, the signature SIG, the updated secret key SK and i + 1 are returned.

Signature verification. The signature verification algorithm takes as input a signature Σ = (i, σ 0 , Auth 0 , σ 1 , Auth 1 , . . . , σ d , Auth d ), the message M and the public key PK. To verify the signature, σ 0 and M are used to compute the corresponding W-OTS public key. The corresponding leaf N 0,j of Tree 0 is constructed and used together with Auth 0 to compute the path (P 0 , . . . , P h 0 ) to the root of Tree 0 , where P 0 = N 0,j , j = i mod 2 h 0 and

P c = H((P c-1 ||Auth c-1,0 ) ⊕ B c ), if j/2 c ≡ 0 mod 2 H((Auth c-1,0 ||P c-1 ) ⊕ B c ), if j/2 c ≡ 1 mod 2
for 0 ≤ c ≤ h 0 . This process is then iterated for 1 ≤ a ≤ d -1, using the output of the last iteration P h a-1 = Root a-1 as message, σ a , Auth a and j = i/2

a-1 b=0 h b mod 2 ha . If the output of the last iteration P h d-1 equals the root value contained in PK, Root d-1 , the signature is assumed to be valid and the algorithm returns 1. In any other case it returns 0.

Analysis

In the following we provide an analysis of XMSS M T . A discussion of correctness and security can be found in appendices B, C and D. In the following we discuss key and signature sizes and the runtimes of the algorithms.

First we look at the sizes. A signature contains the index and d pairs of W-OTS signature and authentication path. Hence a signature takes 24 + n • d-1 i=0 ( i + h i ) bits, assuming we reserve three bytes for the index. The public key contains the bitmasks, X and Root d-1 . Thus, the public key size is n • (max 0≤i≤d-1 {h i + log i } + 2) bits. The secret key contains one FsGen state and one BDS state consisting of 2(h i -k i ) FsGen states and no more than (3h i + h i 2 -3k i -2 + 2 k i ) tree nodes [START_REF] Buchmann | Merkle tree traversal revisited[END_REF] per currently used tree Tree i . In addition it contains the d -1 W-OTS signatures σ 1 , . . . , σ d-1 which have a total size of n • d-1 i=1 i bits and the structures for upcoming trees. As observed by the authors of [START_REF] Hülsing | Forward secure signatures on smart cards[END_REF], these structures do not require a full BDS state, as some of the structures are not filled during initialization and the space to store the k top levels of nodes can be shared with the current tree. Thus, these structures require only (h i -k i + 1) FsGen states (one for building the tree and the remaining as storage for the BDS state) and no more than 3h i -k i + 1 tree nodes per Tree i , 0 ≤ i < d -1. The secret key size is

n• d-1 i=0 5h i + h i 2 -5k i -2 + 2 k i + 1 + d-2 i=0 ( i+1 + 4h i -2k i + 2)
bits. For the runtimes we only look at the worst case times and get the following. During key generation, the first tree on each layer has to be computed. This means, that each of the 2 h W-OTS key pairs has to be generated, including the execution of the PRGs. Further, the leaves of the trees have to be computed and all internal nodes of the tree, to obtain the root. If key generation generates the trees in order, starting from the first one, the W-OTS signatures on the roots of lower trees need no additional computation, as the signature can be extracted while the corresponding W-OTS key pair is generated. The key generation time is

t Kg ≤ t H d-1 i=0 2 h i ( i + 1) + t F d-1 i=1 2 h i (2 + i (w i + 1)) ,
where t H and t F denote the runtimes of one evaluation of H and F, respectively. During one call to Sign, a W-OTS signature on the message must be generated, including generation of the key (t F (2 + 0 (w 0 + 1))), the BDS algorithm receives (h 0 -k 0 )/2 updates, one leaf of the next tree on layer 0 must be computed and the BDS algorithm updates h 0 -k 0 upcoming seeds (t F (h 0 -k 0 )). The worst case signing time is bounded by

t Sign ≤ max i∈[0,d-1]    t H h 0 -k 0 +2 2 • (h i -k i + i ) + h 0 +t F h 0 -k 0 +4 2 • ( i (w i + 1)) + h 0 -k 0   
Signature verification consists of computing d W-OTS public keys and the corresponding leafs plus hashing to the root. Summing up verification takes t Vf ≤ d-1 i=0 (t H ( i + h i ) + t F ( i w i )) in the worst case.

Given the theoretical formulas for runtimes and sizes from the last section, we now show how to use them to model the parameter selection problem as linear optimization problem. There are parameters which control different trade-offs. The BDS parameters k i ∈ N control a trade-off between signature time and secret key size, the Winternitz parameters w i ∈ N control a trade-off between runtimes and signature size and the number of layers d determines a trade-off between key generation and signature time on the one hand and signature size on the other hand. Moreover there are the different tree heights h i that do not define any obvious trade-off, but influence the security as well as the performance of the scheme. The goal of the optimization is to choose these parameters. The function families F n and H can be instantiated, either using a cryptographic hash function or a block cipher. Hence the security parameter n is restricted to the output size of such functions. We choose 128 and 256 bit corresponding to AES and SHA-2 for our optimization, respectively.

Optimization Model. To find good parameter choices, we use linear optimization. In the following we discuss how we model the problem of optimal parameter choices as a linear optimization problem. As objective function of our problem we chose a weighted sum of all runtimes and sizes that should be minimized. Using the weights it is possible to control the importance of minimizing a certain parameter and thereby using the model for different scenarios. We further allow to apply absolute bounds on the runtimes and sizes. The formulas for runtimes and sizes are modeled as constraints as well as the parameter restrictions and the formula for bit security (see Appendix D). The input to the model are the runtimes of F and H for n = 128 and n = 256, the overall height h, the message length m and a value b as lower bound on the bit security. As many of our initial constraints are not linear, we have to linearize all functions and restrictions. This is done using the generalized lambda method [START_REF] Moritz | A Mixed Integer Approach for the Transient Case of Gas Network Optimization[END_REF]. In addition, we split the problem into sub problems each having some decision variables fixed. The optimization problem contains the parameters of the scheme (d, n, the h i , k i , w i for all layer) as decisions variables which are determined by solving the optimization. Further the message length m i on each layer has to be modelled as a decision variable. Since solving the optimization problem takes much time and memory, we split the problem into sub problems by fixing the decision variables n and d. Therefore, we receive one sub problem for each combination of possible values of n and d. The resulting sub problems are solved independently and the best of their solutions is chosen as global solution of the original optimization problem.

The next step is to linearize the remaining sub problems by using the generalized lambda method. Therefore, we introduce a grid point for each possible combination of the remaining variables h, k, w and m on each layer i. For each grid point we have a binary variable λ h,k,w,m,i which takes value 1 if the combination of h, k, w, m is chosen on layer i. Otherwise, it takes value 0. Since we need one choice of h, k, w, m for each i ∈ [0, d -1], d λ's must be chosen.

We use those lambdas to calculate the functions describing the problem. Thus, before optimizing we determine the values of the functions for each possible values of their variables. To make this feasible, we have to introduce bounds on the decision variables. We bound the tree height per layer layer by 24. As k ≤ h this bound also applies to k. For w we chose 255. These bounds are reasonable for the scenarios of the next section. For different scenarios they might have to be changed. Then, to model the needed space of signatures d-1 i=0

( i + h i ) • n, we formulate the constraint SpaceSig == d-1 i=0 24 h=1 24 k=1 512 w=2 m∈{128,256} λ h,k,w,m,i • f SpaceSig (w, h, m) pre-calculated
in the optimizing model, where f SpaceSig (w, h, m) = ( + h)n. Thus, SpaceSig gives the exact value of the needed space of signatures for the choice of lambda's and can be used in constraints and objective function.

To linearize a condition containing the maximum of some terms, such as the public key size n • (max 0≤i≤d-1 {h i + log i } + 2), we write the following constraint:

∀i ∈ {1, ..., T } SpaceP K ≥ 24 h=1 24 k=1 512 w=2 m∈{128,256} λ h,k,w,m,i • (f log (w, m) pre-calculated +h + 2)n
Hence, SpaceP K gives the public key size for the choice of lambda's. This constraint pushes the value of SpaceP K up high and due to the objective function the value will be pushed down as low as possible, so that in the end it takes the exact value.

Optimization Results

In this section we present optimal parameters for two exemplary use cases. More results will be included in the full version of this paper. To solve the optimization problem, we used the IBM Cplex solver [START_REF]IBM ILOG CPLEX Optimizer[END_REF], that implements the Simplex algorithm [START_REF] Dantzig | Linear Programming And Extensions[END_REF] with some improvements. The linearization described in the last section is exact. Thus, there is no loss of information or error. Therefore, it can be proven that the solution found by linear optimization based on the Simplex algorithm is the best possible solution. In the following we present the results and compare them with the results for parameter sets proposed in [START_REF] Buchmann | XMSS -a practical forward secure signature scheme based on minimal security assumptions[END_REF] and [START_REF] Hülsing | Forward secure signatures on smart cards[END_REF]. We choose a message length of 256 bits for all use cases assuming that the message is the output of a collision resistant hash function. Moreover we use 80 bits as lower bound for the provable bit security. This seems reasonable, as the used bit security represents a provable lower bound on the security of the scheme and is not related to any known attacks. We used the instantiations for F and H proposed in [START_REF] Buchmann | XMSS -a practical forward secure signature scheme based on minimal security assumptions[END_REF] with AES and SHA2 for n = 128 and n = 256, respectively and measured the resulting runtimes on a Laptop with Intel(R) Core(TM) i5-2520M CPU @2.5 GHz and 8 GB RAM. We got t F = 0.000225ms and t H = 0.00045ms for n = 128 as well as t F = 0.00169ms and t H = 0.000845ms for n = 256.

The first use case we look at meets the requirements of a document or code signature. We assume that the most important parameters are signature size and verification time and try to minimize them, while keeping reasonable bounds on the remaining parameters. We used the bounds t Sign < 1000ms, t Vf < 1000ms, t Kg < 60s, sk < 25kB, pk < 1.25kB, σ < 100kB and the weights t Sign = 0.00000001, t Vf = 0.00090000, t Kg = 0.00000001, sk = 0.00000001, σ = 0.99909996, pk = 0.00000001 for h = 20. We chose different weights for t Vf and σ, because the optimization internally counts in bits and milliseconds. We set the weights such that 1ms costs the same as 1000 bit. The remaining weights are not set to zero but to 1.0e -8, the smallest possible value that we allow. This is necessary to ensure that our implementation of inequalities in the model works. This also ensures that within the optimal solutions regarding t Vf and σ, the best one regarding the remaining parameters is chosen. It turns out, that the optimization can be solved for d ≥ 2. For d = 1 the bound on the key generation time cannot be achieved for the required height. If we relax this bound to be t Kg < 600s, i.e. 10 minutes, the problem can be solved for n = 128 using AES. For d ≥ 2 this relaxation does not change the results. The optimal parameters for this setting are n = 128, d = 2, h 0 = 17, k 0 = 5, w 0 = 5 and h 1 = 3, k 1 = 3, w 1 = 22. For comparison we use a parameter set from [START_REF] Hülsing | Forward secure signatures on smart cards[END_REF] that matches the bound on the bit security (n = 128, d = 2, h 0 = h 1 = 10, k 0 = k 1 = 4, w 0 = w 1 = 4). The resulting runtimes and sizes are shown in Table 1. The results show that it is possible to reduce the signature size by almost one kilo byte, changing the other parameters within their bounds and increasing the second important parameter, the verification time, by 0.08 milliseconds.

As a second use case we take a total tree height of 80 and aim for a balanced performance over all parameters. This use cases corresponds to the use in a communication protocol. Again, we choose the weights such that 1ms costs the same as 1000 bit, but this time we use the same weights for all runtimes and for all sizes. For comparison we use parameters from [START_REF] Buchmann | Merkle signatures with virtually unlimited signature capacity[END_REF]

(d = 4, h 0 = h 1 = h 2 = h 3 = 20, w 0 = 5, w 1 = w 2 = w 3 = 8, k 0 = k 1 = k 2 = k 3 = 4
). As they do not use a BDS parameter, we choose k = 4 on all layers. To make a fair comparison, we limited our optimization also to four layers. The optimal parameters returned by the optimization are h 0 = h 1 = h 2 = h 3 = 20, w 0 = 14, w 1 = w 2 = w 3 = 24 and k 0 = k 1 = k 2 = 4, k 3 = 2. The results are shown in Table 1. It turns out, that again, by trading some runtime, the signature size can be significantly reduced.

Conclusion

With XMSS M T we presented a new hash-based signature scheme, that allows to use a key pair for 2 80 signatures, which is a virtually unlimited number of signatures in practice. The new scheme is highly flexible and can be parameterized to meet the requirements of any use case for digital signatures. In order to get the maximum benefit from this parameterization, we showed how to use linear optimization to obtain provably optimal parameter sets. We have shown the strength and functionality of our approach by presenting the parameter sets for two different use cases. Comparing our results to parameter sets from other works, it turns out that there is a lot of space for optimization.

A Winternitz OTS.

XMSS M T uses the Winternitz-OTS (W-OTS) from [START_REF] Buchmann | On the security of the Winternitz one-time signature scheme[END_REF]. W-OTS uses the function family F n and a value X ∈ {0, 1} n that is chosen during XMSS key generation. For K, X ∈ {0, 1} n , e ∈ N, and F K ∈ F n we define F e K (X) as follows. We set F 0 K (X) = K and for e > 0 we define K = F e-1 K (X) and F e K (X) = F K (X). Also, define

1 = m log(w) , 2 = log( 1 (w -1)) log(w) + 1, = 1 + 2 .
The secret signature key of W-OTS consists of n-bit strings sk i , 1 ≤ i ≤ . The generation of the sk i will be explained later. The public verification key is computed as

pk = (pk 1 , . . . , pk ) = (F w-1 sk 1 (X), . . . , F w-1 sk (X)),
with F w-1 as defined above. W-OTS signs messages of binary length m. They are processed in base w representation. They are of the form M

= (M 1 . . . M 1 ), M i ∈ {0, . . . , w -1}. The checksum C = 1 i=1 (w -1 -M i ) in base w representation is appended to M . It is of length 2 .
The result is a sequence of base w numbers, denoted by (T 1 , . . . , T ). The signature of M is σ = (σ 1 , . . . , σ ) = (F T 1 sk 1 (X), . . . , F T sk (X)). It is verified by constructing (T 1 . . . , T ) and checking

(F w-1-T 1 σ 1 (X), . . . , F w-1-T σ (X)) ? = (pk 1 , . . . , pk ).
The sizes of signature, public, and secret key are n bits. The runtimes for key generation, signature generation and signature verification are all bounded by (w -1) evaluations of elements from F n . The Winternitz parameter w controls a time -space trade-off, as shrinks logarithmically in w. For more detailed information see [START_REF] Buchmann | On the security of the Winternitz one-time signature scheme[END_REF].

B Correctness

In the following we argue that the BDS state on every layer receives its (h -k)/2 updates between two signatures. The authors of [START_REF] Hülsing | Forward secure signatures on smart cards[END_REF] showed that there is a gap between the updates a XMSS key pair receives over its lifetime and the updates it really uses. Namely, for 2 ≤ k ≤ h there are 2 h-k+1 unused updates. For every tree on a layer other than 0, h -k + 3 updates are needed. The first h -k updates are needed to update the TreeHash instances in the BDS state. Further one update is needed to compute a node in the next tree, to update the FsGen states in the BDS state and to sign the root of the next tree on the lower layer, respectively. Between two signatures of a tree on layer i + 1, a whole tree on layer i is used, so if we ensure that (h i+1 -k i+1 + 6)/2 ≤ 2 h i -k i +1 , as we do, the (h i -k i )/2 updates Tree i receives over its lifetime leave enough unused updates such that Tree i+1 receives the required updates. There would still occur a problem, if the number of updates per signature would be smaller than d -1. The reason is, that this would mean that the roots of the new trees on different layers could not always be signed using the updates of the last signature before the change. In this case the private storage would grow, as we would need some intermediate storage for the new signatures. This is the reason why the second condition ((h 0 -k 0 )/2 ≥ d -1) is needed.

C Security

For the security, the argument is similar to that of [START_REF] Hülsing | Forward secure signatures on smart cards[END_REF]. In [START_REF] Buchmann | XMSS -a practical forward secure signature scheme based on minimal security assumptions[END_REF], an exact proof is given which shows that XMSS is forward secure, if F is a pseudorandom function family and H a second preimage resistant hash function family. The tree chaining technique corresponds to the product composition from [START_REF] Malkin | Efficient generic forward-secure signatures with an unbounded number of time periods[END_REF]. In [START_REF] Malkin | Efficient generic forward-secure signatures with an unbounded number of time periods[END_REF] the authors give an exact proof for the forward security of the product composition if the underlying signature schemes are forward secure. It is straight forward to combine both security proofs to obtain an exact proof for the forward security of XMSS M T . In contrast to the case of XMSS + , for XMSS M T the product composition is applied not only once, but d-1 times. As forward security implies EU-CMA security, this also shows that XMSS M T is EU-CMA secure.

D Security Level

We compute the security level in the sense of [START_REF] Arjen | Key lengths. Contribution to The Handbook of Information Security[END_REF]. This allows a comparison of the security of XMSS M T with the security of a symmetric primitive like a block cipher for given security parameters. Following [START_REF] Arjen | Key lengths. Contribution to The Handbook of Information Security[END_REF], we say that XMSS M T has security level b if a successful attack on the scheme can be expected to require approximately 2 b-1 evaluations of functions from F n and H n . Following the reasoning in [START_REF] Arjen | Key lengths. Contribution to The Handbook of Information Security[END_REF], we only take into account generic attacks on H n and F n . A lower bound for the security level of XMSS was computed in [START_REF] Buchmann | XMSS -a practical forward secure signature scheme based on minimal security assumptions[END_REF]. For XMSS M T , we combined the exact security proofs from [START_REF] Buchmann | XMSS -a practical forward secure signature scheme based on minimal security assumptions[END_REF] and [START_REF] Malkin | Efficient generic forward-secure signatures with an unbounded number of time periods[END_REF]. Following the computation in [START_REF] Buchmann | XMSS -a practical forward secure signature scheme based on minimal security assumptions[END_REF]

E XMSS M T in Graphics

Here we included some graphics for a better understanding of XMSS M T . Figure 1 shows the construction of the XMSS tree. An authentication path is shown in Figure 2. And finally Figure 3 shows a schematic representation of a XMSS M T instance with four layers.

Algorithm 1 1 .

 11 TreeHash Input: Stack Stack, node N1 Output: Updated stack Stack While top node on Stack has same height as N1 do (a) t ←-N1.height() + 1 (b) N1 ←-H ((Stack.pop()||N1) ⊕ Bt) 2. Stack.push(N1) 3. Return Stack evaluation of H. Second, it stores the right nodes from the top k levels of the tree during key generation. Third, it distributes the computations for right child nodes among previous authentication path computations. It schedules one instance of TreeHash per tree level. The computation of the next right node on a level starts, when the last computed right node becomes part of the authentication path. BDS uses a state State BDS of 2(h-k) states of FsGen and at most 3h + h

4 -

 4 , we can lower bound the security level b by w i -2log( i w i ) -

Fig. 1 .

 1 Fig. 1. The XMSS tree construction

Fig. 2 .Fig. 3 .

 23 Fig. 2. The authentication path for a leaf i.

Table 1 .

 1 Runtimes and sizes for optimized parameters and parameters proposed in previous works.

		Runtimes (ms)		Sizes (bit)
	Use case	t Kg	t Sign t Vf	σ	PK	SK
	U C1 optimal 27251 1.65 0.36 21376 6144 25472
	U C1 from [9] 326	1.00 0.28 28288 4608 25856
	U C2 optimal 166min 25.55 9.13 83968 13824 209152
	U C2 from [4] 98min 14.53 5.01 119040 13824 233472

Supported by grant no. BU 630/19-1 of the German Research Foundation (www.dfg.de).