Edoardo Persichetti

Code-based public-key encryption resistant to key leakage

Side-channel attacks are a major issue for implementation of secure cryptographic schemes. Among these, key-leakage attacks describe a scenario in which an adversary is allowed to learn arbitrary information about the private key, the only constraint being the number of bits learned. In this work, we study key-leakage resilience according to the model presented by Akavia, Goldwasser and Vaikuntanathan at TCC '09. As our main contribution, we present a code-based hash proof system; we obtain our construction by relaxing some of the requirements from the original definition of Cramer and Shoup. We then propose a leakageresilient public-key encryption scheme that makes use of this hash proof system. To do so, we adapt a framework featured in a previous work by Alwen et al. regarding identity-based encryption (EUROCRYPT '10). Our construction features error-correcting codes as a technical tool, and, as opposed to previous work, does not require the use of a randomness extractor.

Introduction

Traditionally, the security of cryptographic schemes is analyzed with respect to an idealized, abstract adversarial model [START_REF] Goldwasser | Probabilistic Encryption[END_REF]. Unfortunately, in the real world, implementations of cryptographic schemes are often vulnerable to an additional kind of threat, of a more physical nature. These are the so-called side-channel attacks, which are based on the observation of phenomena directly connected with the implementation, such as power or timing measurements, detection of internal faults and leakage of some private information. It is therefore important to build schemes whose security can be argued even in presence of such attacks.

In this work, we focus on one particular type of attacks, known as "cold boot" or memory attacks, first introduced by Halderman et al. [START_REF] Halderman | Lest We Remember: Cold Boot Attacks on Encryption Keys[END_REF] in 2008. The authors show how it is possible to recover private information stored in the device's memory after the device is turned off; this is because typical DRAM memories only lose their content during a gradual period European Research Council has provided financial support under the European Community's Seventh Framework Programme (FP7/2007-2013) / ERC grant agreement no CNTM-of time. In particular, a significant fraction of the cryptographic key stored in the memory can be easily recovered, leading to potentially devastating attacks. We therefore speak about key-leakage attacks. A general framework that models key-leakage attacks was introduced by Akavia, Goldwasser and Vaikuntanathan [START_REF] Akavia | Simultaneous Hardcore Bits and Cryptography against Memory Attacks[END_REF]. In this model, the adversary is allowed the knowledge of arbitrarily chosen functions of the private key, with the restriction that the total output of these functions doesn't exceed a certain bound λ. Attacks can be performed, as usual, both in an adaptive or nonadaptive fashion. The authors then show that the lattice-based public-key encryption scheme of Regev [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] and the identity-based encryption scheme of Gentry, Peikert and Vaikuntanathan [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF] are resistant to such leakage. The framework was subsequently revisited by Naor and Segev [START_REF] Naor | Public-Key Cryptosystems Resilient to Key Leakage[END_REF] and further generalized by Alwen, Dodis and Wichs [START_REF] Alwen | Leakage-Resilient Public-Key Cryptography in the Bounded-Retrieval Model[END_REF], who provide the first public-key primitives in the Bounded Retrieval Model (BRM). This model had been previously introduced by Dziembowski and Di Crescenzo in independent works [START_REF] Dziembowski | Intrusion-Resilience Via the Bounded-Storage Model[END_REF][START_REF] Di Crescenzo | Perfectly Secure Password Protocols in the Bounded Retrieval Model[END_REF] for symmetric encryption schemes.

To date, many cryptographic primitives have been shown to be resilient to key-leakage attacks, based on a variety of assumptions such as DDH or d-Linear, quadratic residuosity, composite residuosity and LWE; however, there is no known construction based on coding theory assumptions. Code-based cryptography is one of the candidates for "post-quantum" cryptography; compared to LWE-based schemes, codebased schemes have the advantage of a simpler structure (for example, they usually work over the binary field) thus allowing for more practical implementations.

Our contribution

In this paper, we propose a protocol based solely on coding theory assumptions, that achieves semantic security against keyleakage attacks. The first step is to build a Hash Proof System (HPS). This primitive, essentially a special kind of non-interactive zero-knowledge proof system for a language, was first introduced by Cramer and Shoup in [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF] as a theoretical tool to construct efficient public-key encryption schemes. It was later shown by Kiltz et al. [20] that it is possible to view a HPS as a key encapsulation mechanism (KEM) with special properties, and that it is possible to obtain secure hybrid encryption schemes by using randomness extractors. The work of Naor and Segev [START_REF] Naor | Public-Key Cryptosystems Resilient to Key Leakage[END_REF] builds on this method, and the authors present a general framework to design leakage-resilient encryption schemes using any HPS together with a randomness extractor. This is also the basis for a recent paper by Alwen et al. [START_REF] Alwen | Public-Key Encryption in the Bounded-Retrieval Model[END_REF] in which the framework is extended to the identity-based setting. Our construction works as follows. The private key has a high min-entropy that is guaranteed by analyzing the volume of spheres centered on codewords of a randomly generated code. This induces an error in the decapsulation procedure; however, we manage to bound the size of the error term by carefully choosing the scheme's parameters. This allows us to deal with the possible decryption error by using error-correcting codes in our encryption scheme. Finally, we achieve ciphertext indistinguishability thanks to the pseudorandomness of the syndrome construction (Fischer and Stern [START_REF] Fischer | An Efficient Pseudo-Random Generator Provably as Secure as Syndrome Decoding[END_REF]) for low-weight error vectors. To the best of our knowledge, this is the first construction of a hash proof system from coding theory assumptions.

The paper is structured as follows: in Section 2 we give some preliminary definitions necessary for the remainder of the paper. Next, we describe hash proof systems (Section 3) and leakage-resilient public-key encryption (Section 4). Our construction of a code-based hash proof system is presented in Section 5, and the encryption scheme based on it in Section 6. We conclude in Section 7.

Preliminaries

We start by providing some probability notions that are relevant for the paper. The notation x ← χ ρ means sampling an element x from the Bernoulli distribution with parameter ρ: this extends naturally to vectors and matrices with notation, respectively, χ n ρ and χ m×n ρ . The statistical distance between two random variables X and Y with values in Ω is defined as

∆(X, Y ) = 1 2 ω∈Ω Pr[X = ω] -Pr[Y = ω] . The min-entropy of a random variable X is H ∞ (X) = -log(max ω∈Ω Pr[X = ω]
). We also present the notion of average min-entropy, which is useful to describe the unpredictability of a random variable X conditioned on the value of another random variable Y , as H∞ (X|Y ) = -log

E y $ ← -Y 2 -H∞(X|Y =y) .
Next, we present a few basic coding theory notions. Throughout the paper, we will treat all vectors as column vectors, and denote them by a boldface letter. An [n, k] linear code over the finite field F q is a vector subspace C of F n q of dimension k. A generator matrix for C is a matrix whose rows form a basis for the subspace. A parity-check matrix for C is an (n -k) × n matrix H such that Hx = 0 for all codewords x. For every vector x ∈ F n q the Hamming weight wt(x) is the number of its non-zero positions; d(x, y) = wt(xy) is the Hamming distance between the two words x and y. The minimum distance of a code C is simply the minimum between the distance of all codewords of C. The following is a very important bound on the minimum distance of linear codes.

Definition 1 (GV Bound). Let C be an [n, k] linear code over F q . The Gilbert-Varshamov (GV) Distance is the largest integer d 0 such that

|B(0, d 0 -1)| ≤ q n-k (1)
where B(x, r) = {y ∈ F n q |d(x, y) ≤ r} is the n-dimensional ball of radius r centered in x.

For an integer w below the GV bound, the following problem is hard (Berlekamp, McEliece and van Tilborg [START_REF] Berlekamp | On the inherent intractability of certain coding problems[END_REF]).

Definition 2 (Syndrome Decoding Problem). Given an (n -k) × n parity-check matrix H for an [n, k] linear code C over F q , a vector s ∈ F n-k q and an integer w ∈ N + , find e ∈ F n q such that s = He and wt(e) ≤ w.

Hash Proof Systems

Like in the majority of previous work, we use a HPS for our construction. To describe our HPS, we adapt the "simplified" definition of [START_REF] Alwen | Public-Key Encryption in the Bounded-Retrieval Model[END_REF] to publickey encryption schemes. Setup The setup algorithm takes as input a security parameter θ and returns the public parameters of the scheme. The algorithm also defines the set K of encapsulated keys.

KeyGen

The key generation algorithm takes as input the public parameters and outputs a public key pk and a private key sk.

Encap The valid encapsulation algorithm receives as input the public key pk and returns a ciphertext/key pair (ψ0, K).

Encap * The invalid encapsulation algorithm receives as input the public key pk and samples an invalid ciphertext ψ0.

Decap The decapsulation algorithm takes as input a private key sk and a ciphertext ψ0 and outputs a key K .

Note that all of the above algorithms are probabilistic, except Decap, which is deterministic. There are two important requirements on the output of Decap. If ψ 0 is a valid ciphertext (i.e. produced by Encap) we require correctness.

Definition 3 (Correctness of decapsulation). Fix any values of pk and sk, as output by KeyGen, and let (ψ 0 , K) = Encap(pk) and K = Decap(sk, ψ 0 ). Then:

Pr[K = K ] = negl(θ). (2)
For our scheme, a relaxation of the above requirement will suffice, called approximate correctness. This notion was introduced by Katz and Vaikuntanathan in [START_REF] Katz | Smooth Projective Hashing and Password-Based Authenticated Key Exchange from Lattices[END_REF], and asks that the output of Decap is "close" (in Hamming sense) to the actual encapsulated key.

Definition 4 (t-Approximate Correctness). Fix any values of pk and sk, as output by KeyGen, and let (ψ 0 , K) = Encap(pk) and K = Decap(sk, ψ 0 ). Then:

Pr[d(K, K ) > t] = negl(θ). (3)
For invalid ciphertexts (i.e. produced by Encap * ), instead, we want Decap to return strings that are almost uniformly distributed. Following [START_REF] Alwen | Public-Key Encryption in the Bounded-Retrieval Model[END_REF], we present three distinct notions in this regard.

Definition 5 (Universality). Let SK and P K be random variables representing, respectively, sk and pk. We say that an HPS is (η, ν)-universal if H∞ (SK|P K) ≥ η and, for any fixed values pk and sk = sk , it holds:

Pr[Decap(sk, ψ 0 ) = Decap(sk , ψ 0 )] ≤ ν ( 4
)
where ψ 0 = Encap * (pk).

Definition 6 (Smoothness). For any fixed pk and sk = sk , let ψ 0 = Encap * (pk), K = Decap(sk, ψ 0 ). Then we say that an HPS is smooth if:

∆((ψ 0 , K), (ψ 0 , K )) = negl(θ) (5)
where ψ 0 = Encap * (pk), K = Decap(sk, ψ 0 ) and K is chosen uniformly at random.

Definition 7 (Leakage Smoothness). We say that an HPS is λ-leakage smooth if, for any (possibly randomized) function f with output size bounded by λ, it holds:

∆((ψ 0 , f (sk), K), (ψ 0 , f (sk), K )) = negl(θ) (6)
for ψ 0 , K and K sampled as in Definition 6.

Finally, an HPS requires an indistinguishability property for ciphertexts, that is, a random valid ciphertext should be computationally indistinguishable from an invalid one. The definition is the following. Definition 8 (Ciphertext Indistinguishability). We define the following attack game between a challenger and an adversary A: 1. Fix system parameters. 2. The adversary A makes a sequence of queries to the challenger, getting back public key/private key pairs (pk, sk).

Adv HPS (A, θ) = Pr[b * = b] - 1 2 . ( 7
)
We say that an HPS satisfies the ciphertext indistinguishability property if the advantage Adv HPS of any polynomial-time adversary A in the above adaptive attack model is negligible.

Remark 1. In the original definition for an identity-based protocol, the adversary would perform queries adaptively submitting a certain identity and getting back the corresponding private key. Adapting this to the public-key setting just means that the adversary is allowed to see public key/private key pairs, including the "target" one. In both cases, this is a very strong requirement, meaning that ciphertexts have to be computationally indistinguishable even if the whole private key is revealed.

Leakage-resilient public-key encryption

We define here the notion of security for public-key encryption schemes under key-leakage attacks. An adversary in this setting is allowed to (adaptively) query a leakage oracle, submitting any function f and receiving f (sk), with the only restriction that the total length of the output is not greater than a certain threshold λ. As pointed out by Akavia et al. [START_REF] Akavia | Simultaneous Hardcore Bits and Cryptography against Memory Attacks[END_REF], this is equivalent to querying the leakage oracle on a single function f whose total output doesn't exceed λ bits. The definition is given below.

Definition 9. An adversary A for key-leakage security is a polynomialtime algorithm that plays the following attack game:

1. Query a key generation oracle to obtain a public key pk.

2. Submit a query f to the leakage oracle. The oracle will reply with f (sk) provided that the output is less or equal to λ bits. 3. Choose φ 0 , φ 1 ∈ P and submit them to an encryption oracle. The oracle will choose a random b ∈ {0, 1} and reply with the "challenge" ciphertext ψ * = Enc(pk, φ b ). 4. Output b * ∈ {0, 1}.

We define the advantage of A against PKE as

Adv(A, θ) = Pr[b * = b] - 1 2 . ( 8
)
We say that a PKE scheme is semantically secure against λ-key-leakage attacks if the advantage of any adversary A in the above attack model is negligible.

As usual, the above notion can be extended to the chosen-ciphertext attack model, allowing for decryption queries before (CCA1) or after (CCA2) the generation of the challenge ciphertext. In this case we speak about resistance to, respectively, a priori and a posteriori chosen-ciphertext key-leakage attacks. The choice of parameters here is important to guarantee that the construction satisfies the requirements presented in the previous section. In particular, we will need the rate R = k/n to be high enough for ρ to be less than 1/ √ n. We now analyze the three properties one at a time:

The Construction

t-Approximate Correctness As in Definition 4, let (ψ 0 , K) = Encap(pk) and K = Decap(sk, ψ 0 ); then K and K differ by a factor of Es, and d(K, K ) = wt(Es), hence we just need to bound the weight of this product. Remember that E and s are distributed, respectively, according to χ ×n ρ and χ n τ , where ρ = O(n -1/2-ε ) and τ = γρ for γ > 0. We now use a result from Döttling, Müller-Quade and Nascimento [START_REF] Döttling | IND-CCA Secure Cryptography Based on a Variant of the LPN Problem[END_REF]. A matrix X ∈ F ×n 2 is said to be (β, )-good if for a fixed constant β and = (n) it holds that for all s ∈ F n 2 if wt(s) ≤ n then wt(Xs) ≤ β . It is proved in [START_REF] Döttling | IND-CCA Secure Cryptography Based on a Variant of the LPN Problem[END_REF] that when ρ = O(n -1/2-ε ) and n is sufficiently large, for any fixed β, γ > 0 a matrix sampled from χ ×n ρ is (β, γρ)-good with overwhelming probability. Thus in our case we will have wt(Es) ≤ t for t = β , and this concludes the proof.

Universality A defines a random linear code C, hence its minimum distance δ is on the GV bound with high probability. Consider the expected number of codewords in B(x, r) for x chosen uniformly at random, µ C (r) = E x∈F n q [|C ∩ B(x, r)|]. Following Dumer, Micciancio and Sudan [START_REF] Dumer | Hardness of approximating the minimum distance of a linear code[END_REF], we know that µ C (r) = 2 k-n • |B(0, r)| (we are interested in the case q = 2), and that for r = δ this number is equal to a certain constant µ > 1. Since each row of M is chosen independently, it holds H ∞ (sk) ≥ µ . This completes the first part. For the second part, recall that Decap(sk, ψ 0 ) = M ψ 0 . Consider two private keys M = M : then Decap(sk, ψ 0 ) = Decap(sk , ψ 0 ) ⇐⇒ M ψ 0 = M ψ 0 ⇐⇒ (M -M )ψ 0 = 0. Now, > k and both M and M are generated uniformly at random, so the matrix N = (M -M ) is of full rank k with high probability [START_REF] Blake | Properties of random matrices and applications[END_REF], say p. It follows that (M -M )ψ 0 = 0 ⇐⇒ ψ 0 = 0. We conclude that the code-based HPS is (η, ν)-universal, for η = µ and ν = 1 -p.

Ciphertext Indistinguishability. We know that ρ = O(n -1/2-ε ), thus choosing s according to χ ρ produces a vector with weight below the GV bound. As proved by Fischer and Stern in [START_REF] Fischer | An Efficient Pseudo-Random Generator Provably as Secure as Syndrome Decoding[END_REF], the vector ψ 0 = As is pseudorandom. Ciphertext indistinguishability follows directly since clearly the private key M doesn't carry information about the ciphertext.

Remark 2. We remark that the t-approximate correctness of the scheme relies heavily on a careful choice of the values ρ and τ , which are selected such that s and the rows of E have very low weight. It is easy to see that, if this condition is not respected, the weight of the corresponding product Es grows very quickly. One could in fact imagine an attack scenario aimed at obtaining an alternative decapsulation key K , in which the attacker produces a vector s = s such that As = As, and subsequently uses s to get K as pk • s . Because of the hardness of SDP, though, such an attacker would only be able to recover a vector s having high weight; for the above argument, the difference factor E(s + s ) would also have high weight, hence this attack would not work in practice.

The Scheme

In this section, we show how to use the HPS that we presented above to achieve leakage-resilient public-key encryption. In addition to the "standard" protocol presented in [START_REF] Alwen | Public-Key Encryption in the Bounded-Retrieval Model[END_REF], we have to include an error-correcting code to deal with the error coming from the approximate correctness. High error-correction capacity can be achieved, for example, by using list-decodable codes; Guruswami and Rudra in [START_REF] Guruswami | Explicit capacity-achieving list-decodable codes[END_REF] show how it is possible to obtain codes that are list-decodable up to a radius 1 -R -ε, for any ε > 0. Setup Set public parameters as in Table 2, and let m be the length of the plaintexts.

Fix an integer t and set t = t + t , then select an [ , m] linear code C which is decodable up to the radius t .

KeyGen Run KeyGen HPS and return the private key sk = M and the public key pk = M A + E.

Enc

On input a plaintext φ ∈ {0, 1} m , run Encap(pk) to obtain the pair (ψ0, K), sample a random vector z $ ← -F 2 having wt(z) ≤ t , then set ψ1 = K + z + EncodeC(φ). Finally, output the final ciphertext ψ = (ψ0, ψ1).

Dec

On input a private key sk = M and a ciphertext ψ = (ψ0, ψ1), calculate K as Decap(sk, ψ0) and return the plaintext φ = DecodeC(K + ψ1).

As we mentioned above, the correctness of the scheme depends on the t-approximate correctness of the HPS, and the use of error-correcting codes. In fact K + ψ 1 = Encode C (φ) + Es + z and we expect Es to have weight less or equal to t and consequently wt(Es + z) ≤ t + t = t . Hence by applying the decoding algorithm is possible to recover the plaintext φ.

We now proceed to prove the security of the scheme. We start with a result from Alwen et al. [START_REF] Alwen | Public-Key Encryption in the Bounded-Retrieval Model[END_REF]Theorem 3.1].

Theorem 1. Let H be an (η, ν)-universal HPS with key space K = {0, 1} . Then H is also λ-leakage smooth as long as λ ≤ η --ω(log θ) and ν ≤ 2 -(1 + negl(θ)).

It is easy to see that the code-based HPS that we described in the previous section satisfies the conditions of Theorem 1. In addition, we will need the following computational assumption.

Assumption 1 Let E, s and z be distributed as in Table 3. Then given E and y = Es + z it is hard to recover s.

One could think to use a generic decoding algorithm (e.g. Information Set Decoding [START_REF] Peters | Information-Set Decoding for Linear Codes over Fq[END_REF]) or a dedicated decoding algorithm (e.g. bit flipping as for LDPC codes [START_REF] Gallager | Low-density parity-check codes[END_REF]); all these approaches, however, require at some point to check the syndrome equations. Because of the presence of z, these equations can't be trusted. The attacker would then need to guess the positions of z, either beforehand, or during the execution of the algorithm. In both cases, this implies a huge computational effort: there are in fact N = t i=0 n i possibilities for z. Therefore, it is plausible to assume that there is no efficient way to recover s.

We are now ready to prove the following theorem.

Theorem 2. Given that Assumption 1 holds, the scheme in Table 3 is semantically secure against λ-key-leakage attacks.

Proof. For our security analysis we use a sequence of games. This is inspired by the proof of [2, Theorem 4.1], although a few ad hoc modifications are needed, due to the particular nature of our scheme.

Game 0: This is the semantic security game with leakage λ as presented in Definition 9.

Game 1: This game proceeds exactly as Game 0, except that we modify the encryption oracle as follows. We calculate (ψ 0 , K) = Encap(pk) as usual, but instead of using K for encrypting the message, we use K = Decap(sk, ψ 0 ). Because of the approximate correctness, we have to artificially add some noise to preserve the structure of the ciphertext. We thus generate a random vector y of weight less or equal to t , according to the same distribution of Es + z. The challenge ciphertext will then be (ψ * 0 , ψ * 1 ), where ψ * 0 = ψ 0 and ψ * 1 = K + y + Encode C (φ b ). Now, suppose the adversary is in possession of the private key. In order to distinguish between the two games, it could easily recover E from pk and y from ψ * 1 and try to solve for s. However, because of Assumption 1, we claim that there is no efficient way to do this. Hence, the two games are computationally indistinguishable.

Game 2: This is the same as Game 1, but we modify again the encryption oracle, now replacing a valid ciphertext with an invalid one. More precisely, we calculate ψ 0 = Encap * (pk) and K = Decap(sk, ψ 0 ), then return the challenge ciphertext (ψ * 0 , ψ * 1 ) where ψ * 0 = ψ 0 and ψ * 1 = K + y + Encode C (φ b ). By the ciphertext indistinguishability property of the scheme, the two games are computationally indistinguishable. Note that, by definition, this indistinguishability holds even if the whole private key is revealed, hence in particular it holds for any bounded leakage f (sk). Finally, in Game 3 the advantage of any adversary A is equal to 0, since this is independent from the chosen bit b. This completes the proof.

Conclusions

We have shown how to construct an HPS based on coding theory assumptions. The public-key encryption scheme that is based on it is inspired by a framework from Alwen et al. [START_REF] Alwen | Public-Key Encryption in the Bounded-Retrieval Model[END_REF]; however we do not need to use randomness extractors to achieve semantic security against key-leakage attacks. This is because of the universality of our HPS construction. We remark that our scheme is but a first step towards achieving efficient leakage-resilient code-based encryption schemes. We thus hope to stimulate discussion about some open questions that stem from this work. For example, it would be important to improve the scheme in order to resist chosen-ciphertext attacks, without having to use impractical variants such as the one based on the Naor-Yung "double encryption" paradigm presented in [START_REF] Naor | Public-Key Cryptosystems Resilient to Key Leakage[END_REF].

3 .

 3 The challenger fixes a target public key pk * , then chooses a random bit b. If b = 0, it computes (ψ 0 , K) = Encap(pk * ), otherwise computes ψ 0 = Encap * (pk * ). It then gives ψ 0 to A. 4. A keeps performing queries as above. No restrictions apply, hence A can even get sk * . 5. Finally, A outputs b * ∈ {0, 1}. The adversary succeeds if b * = b. More precisely, we define the advantage of A against HPS as

2← -F ×k 2 and

 2 and integers k, n, with k < n, > k. Let δ be the minimum distance of the code having A as generator matrix and set ρ = δ/n and τ = γρ for a certain γ > 0. The set of encapsulated keys is defined as K = F 2 .KeyGen selects matrices M $ E ← χ ×n ρ and outputs the private key sk = M and the public key pk = M A + E.Encap chooses s ← χ n τ and returns the ciphertext/key pair (ψ0, K) where ψ0 = As and K = pk • s.Encap * chooses r $ ← -F k2 and returns the invalid ciphertext ψ0 = r. Decap takes as input the private key sk and a ciphertext ψ0 and obtains K as sk • ψ0.

Game 3 :* 1 $← -F m 2 ,

 312 In Game 3 we proceed as in Game 2, but now we generate ψ * 1 as a uniformly random string. That is, we calculate ψ * 0 = Encap * (pk) and ψ then return the challenge ciphertext (ψ * 0 , ψ * 1 ). Game 2 and Game 3 are statistically indistinguishable because of the leakage smoothness property.

Table 1 :

 1 Hash Proof System.

Table 2 :

 2 Code-based HPS.

	Setup Public parameters are a matrix A

$

← -F k×n

Table 3 :

 3 Leakage-Resilient Public-Key Encryption Scheme.


Improving the Efficiency of Elliptic Curve Scalar

Multiplication using Binary Huff Curves

Gerwin Gsenger and Christian Hanser

Institute for Applied Information Processing and Communications (IAIK), Graz University of Technology (TUG), Inffeldgasse 16a, 8010 Graz, Austria {gerwin.gsenger@student.tugraz.at|christian.hanser@iaik.tugraz.at}

Abstract. In 2010, Joye et. al brought the so-called Huff curve model, which was originally proposed in 1948 for the studies of diophantine equations, into the context of elliptic curve cryptography. Their initial work describes Huff curves over fields of large prime characteristic and details unified addition laws. Devigne and Joye subsequently extended the model to elliptic curves over binary fields and proposed fast differential addition formulas that are well-suited for use with the Montgomery ladder, which is a side-channel attack resistant scalar multiplication algorithm. Moreover, they showed that, in contrast to Huff curves over prime fields, it is possible to convert (almost) all binary Weierstrass curves into Huff form.

We have implemented generalized binary Huff curves in software using a differential Montgomery ladder and detail the implementation as well as the optimizations to it. We provide timings, which show speed-ups of up to 7.4% for binary NIST curves in Huff form compared to the reference implementation on Weierstrass curves. Furthermore, we present fast formulas for mapping between binary Weierstrass and generalized binary Huff curves and vice versa, where in the back conversion step an implicit y-coordinate recovery is performed. With these formulas, the implementation of the differential Montgomery ladder on Huff curves does not require more effort than its counterpart on Weierstrass curves. Thus, given the performance gains discussed in this paper, such an implementation is an interesting alternative to conventional implementations. Finally, we give a list of Huff curve parameters corresponding to the binary NIST curves specified in FIPS 186-3.

Introduction

In 1985, Neal Koblitz [START_REF] Koblitz | Elliptic curve cryptosystems[END_REF] and Victor S. Miller [START_REF] Miller | Use of elliptic curves in cryptography[END_REF] both discovered independently that elliptic curves over finite fields can be used for public key cryptography. By now, elliptic curves have become an important concept within public key cryptography. This is mainly due to small key sizes compared to other public key cryptosystems, such as RSA, which lower the requirements for CPUs as well as the memory footprint. Elliptic curves have a group structure and their cryptographic security relies on the difficulty of solving the elliptic curve discrete logarithm problem (ECDLP). Traditionally, Weierstrass equations have been used to describe elliptic curves. Nevertheless, over time, especially in the last couple of decades, new models to describe elliptic curves have been found, such as the Montgomery form, the Edwards form [START_REF] Bernstein | Faster addition and doubling on elliptic curves[END_REF] and the like. In 1948, Huff was studying a diophantine problem, for which he introduced a new elliptic curve model [START_REF] Huff | Diophantine problems in geometry and elliptic ternary forms[END_REF]. In 2010, Joye et. al [START_REF] Joye | Huff's model for elliptic curves[END_REF], studied Huff's model over fields of odd characteristic and introduced formulas for fast point arithmetics. Each Huff curve defined over F p contains a subgroup isomorphic to Z 4 × Z 2 which, unfortunately, implies that there are no standardized prime curves that can be expressed in Huff form, as all these curves have cofactors equal to one. The Huff model has subsequently been extended by Devigne and Joye [START_REF] Devigne | Binary Huff curves[END_REF] to cover elliptic curves defined over binary fields F 2 m . Furthermore, in [START_REF] Devigne | Binary Huff curves[END_REF], they present a unified addition law and give very fast differential addition formulas for binary Huff curves, which are well-suited for use with the Montgomery ladder, which is a side-channel attack resistant scalar multiplication algorithm.

For m ≥ 4, every Weierstrass curve over F 2 m is birationally equivalent to a generalized Huff curve. Therefore, we are free to convert all standardized binary curves into corresponding (generalized) binary Huff curves. The authors of [START_REF] Devigne | Binary Huff curves[END_REF], give formulas for mapping points between binary Weierstrass curves and binary Huff curves, using an intermediate Weierstrass curve isomorphic to the original curve in short Weierstrass form.

Contribution

We have implemented generalized binary Huff curves in software, where for scalar multiplication we use a differential Montgomery ladder, which is a good choice for software implementations running in server environments, as it is resistant to remote timing attacks [START_REF] Brumley | Remote timing attacks are practical[END_REF][START_REF] Brumley | Remote timing attacks are still practical[END_REF][START_REF] Zhang | Cross-vm side channels and their use to extract private keys[END_REF]. The differential Montgomery ladder is based on the differential addition formulas given by Devigne and Joye in [START_REF] Devigne | Binary Huff curves[END_REF]. The timings show that for the binary NIST curves, this implementation is up to 7.4% faster than the reference implementation of the differential Montgomery ladder on the original Weierstrass curves, to which we have applied the same optimizations.

The conversion between binary Weierstrass and generalized binary Huff curves requires two steps. As generalized binary Huff curves are birationally equivalent to a class of Weierstrass curves, which are themselves isomorphic to curves in short Weierstrass form, it is necessary to apply a birational equivalence as well as an isomorphism for the conversion. Additionally, after applying the differential Montgomery ladder on binary Huff curves and mapping the result back to the corresponding Weierstrass curve, a y-coordinate recovery is necessary. We address this issue by providing fast all-in-one, back-and-forth conversion formulas. These back-and-forth conversions turn out to be almost as efficient as the ycoordinate recovery on Weierstrass curves, which is required anyway after using the differential Montgomery ladder on Weierstrass curves, which preserves most of the savings obtained through the faster differential addition formulas. When using the formulas presented in this paper, the implementation of the differential Montgomery ladder on Huff curves does not require more effort than its counterpart on Weierstrass curves. Thus, given the performance gains discussed in this paper such an implementation is an interesting alternative to conventional implementations.

Finally, we present curve parameters for Huff curves, which are birationally equivalent to the NIST-recommended binary Weierstrass curves specified in FIPS 186-3 [START_REF] Gallagher | Fips pub 186-3 federal information processing standards publication digital signature standard[END_REF].

Outline

In Section 2 and 3 we are going to talk about elliptic curves in general and the Huff curve model in particular. Section 4 gives the Huff curve parameters we have derived for the NIST-recommended curves. It details the implementation, the improvements we have achieved, shows the benchmark results and draws a comparison to the reference implementation. At last, Section 5 concludes the paper.

Preliminaries

An elliptic curve over the field K is a plane, smooth curve described by the Weierstrass equation:

E : Y 2 + a 1 XY + a 3 Y = X 3 + a 2 X 2 + a 4 X + a 6 , (1)
where a 1 , a 2 , a 3 , a 4 , a 6 ∈ K. The set E(K) of points (x, y) ∈ K 2 satisfying Equation (1) plus the point at infinity O = (0 : 1 : 0), which is the neutral element, forms an additive Abelian group. The addition of points on an elliptic curve is achieved using the chord-and-tangent method [START_REF] Silverman | The Arithmetic of Elliptic Curves[END_REF].

For cryptographic purposes, we are interested in elliptic curves over finite fields F q , especially in curves over fields F 2 m and F p with p being a large prime number. The security of elliptic curve cryptography is based on the assumption that in general there is no subexponential-time algorithm to solve the discrete logarithm problem in elliptic curve groups (ECDLP). Given Q, P ∈ E(F q ) the ECDLP constitutes the problem of finding a scalar k ∈ Z such that Q = k • P .

In cryptography, usually non-supersingular curves are being used, as supersingular curves turned out to be susceptible to the MOV attack [START_REF] Menezes | Reducing elliptic curve logarithms to logarithms in a finite field[END_REF], which reduces the ECDLP to the DLP on finite fields, for which an efficient subexponentialtime algorithm is known. Non-supersingular curves defined over F 2 m , are described using the following short form of Equation ( 1):

Y 2 + XY = X 3 + a 2 X 2 + a 6 , (2)
where a 2 , a 6 ∈ F 2 m and a 6 = 0.

For binary field multiplications we are using the windowed left-to-right comb multiplier as detailed in [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]. This algorithm uses lookup-tables, which can be cached and reused to speed up multiplications with frequently used values, such as curve parameters. In the following, let M and S denote the costs of one field multiplication and one field squaring, respectively. Moreover, let m w stand for the cost of the multiplication with some value, for which the lookup table of window size w has already been calculated.

Differential Addition and the Montgomery Ladder

Scalar multiplication is the most crucial and at the same time the most costly operation on elliptic curves and there are many ways to perform elliptic curve scalar multiplications. One way to do so is the so-called Montgomery ladder, which is both side-channel resistant and reasonably fast. Its side-channel resistance is due to the fact that at each ladder step, regardless of the currently processed bit of the scalar k, one point doubling operation as well as one point addition operation are performed and only the order of execution is changed. Thus, in order to mitigate side-channel attacks, the Montgomery ladder is widely used, especially in hardware implementations. In the context of software implementations, side-channel resistance is less important. Still, there are scenarios, such as cryptographic implementations running on servers, where remote timing attacks can be performed (cf. [START_REF] Brumley | Remote timing attacks are practical[END_REF][START_REF] Brumley | Remote timing attacks are still practical[END_REF][START_REF] Zhang | Cross-vm side channels and their use to extract private keys[END_REF]) and, therefore, timing-attack proof implementations are required. This issue can again be addressed with the use of the Montgomery ladder, as its execution time is constant for fixed scalar lengths.

For the fast application of the Montgomery ladder, differential addition and doubling formulas are necessary. Luckily, these two operations can be performed very efficiently on Huff curves. By differential point addition, we mean the computation of w(P + Q) from w(P ), w(Q), and w(P -Q), where w(•) is a coordinate function for which typically w(P ) = w(-P ) is demanded. Note that the difference w(P -Q) required for the differential addition steps within the Montgomery ladder is fixed, i.e., the difference of the resulting points stays invariant throughout the whole process. For differential addition on Weierstrass curves, the knowledge of y-coordinates is irrelevant, as the computation of x-coordinates does not involve them, which is reflected in the definition of w(•). Clearly, this saves computational effort, as the y-coordinate of intermediate results is not computed. Analogously, we mean by differential doubling the computation of w(2P ) from w(P ).

On Weierstrass curves, the fastest differential addition formulas are due to Bernstein and Lange (see [START_REF] Bernstein | Explicit-formulas database[END_REF]). From the results of Stam [START_REF] Stam | On Montgomery-like representations for elliptic curves over GF(2 k )[END_REF], they derive a representation, called XZ-coordinates, featuring fast differential addition and doubling formulas. Per bit of scalar k, these formulas require 5M + 1m 8 + 4S for P known a priori and 6M + 2m 8 + 5S otherwise.

The Montgomery ladder for projective differential addition formulas is shown in Algorithm 1. Here, the addition and the doubling steps are carried out using differential addition and differential doubling formulas, where in the former case the input is W (2P ), W (P ) and the invariant, consequently, is W (P ). Note that W (•) stands for the projective version of the coordinate function w(•).

After application of the Montgomery ladder, the y-coordinate of the product k•P = (x 1 , y 1 ) can be restored efficiently and, hence, there is no need to compute it in the intermediate steps. Restoring the y-coordinate for affine coordinates, also means simultaneously scaling the x-coordinate, in order to avoid multiple inversions. It works in the following way, as detailed in [START_REF] López | Fast multiplication on elliptic curves over GF(2 m ) without precomputation[END_REF] and in [START_REF] Stam | On Montgomery-like representations for elliptic curves over GF(2 k )[END_REF]:

Algorithm 1 Differential Montgomery Ladder

x 1 = Z XZ 2 X 1 Z XZ 2 Z 1 and y 1 = Ȳ + γ((X 1 Z + XZ 1 )γ + Z 1 Z 2 X2 + Z 1 Z 2 Z Ȳ ) Z XZ 2 Z 1 ,
where γ = X 2 Z + XZ 2 and P = ( X : Ȳ : Z) = O. There are two special cases to check, see [START_REF] López | Fast multiplication on elliptic curves over GF(2 m ) without precomputation[END_REF] for more details on that. Using these formulas requires 1I + 10M, when assuming Z = 1, i.e., P to be scaled.

The Binary Huff Curve Model

This section is mainly a recapitulation of the research done by Joye et. al in [START_REF] Devigne | Binary Huff curves[END_REF] and [START_REF] Joye | Huff's model for elliptic curves[END_REF], since we need these facts in Section 4 in order to derive compact formulas for mapping between binary Weierstrass and binary Huff curves. As defined in [START_REF] Devigne | Binary Huff curves[END_REF], binary Huff curves are a new class of elliptic curves. For every Weierstrass curve defined over F 2 m with m ≥ 4, there is a birationally equivalent generalized binary Huff curve. A generalized binary Huff curve is given by the set of projective points (X : Y : Z) over F 2 m satisfying the subsequent equation:

E H : aX(Y 2 + f Y Z + Z 2 ) = bY (X 2 + f XZ + Z 2 ) (3)
with a, b, f ∈ F * 2 m and a = b. Three points at infinity, i.e., (1 : 0 : 0), (0 : 1 : 0), and (a : b : 0), satisfy Equation [START_REF] Brumley | Remote timing attacks are still practical[END_REF]. The affine version of Equation ( 3) is birationally equivalent to the subsequent binary Weierstrass curve:

E W : v(v + (a + b)f u) = u(u + a 2 )(u + b 2 ), ( 4
)
which itself is isomorphic to the short Weierstrass form through the following isomorphism:

Θ : E W (F 2 m ) -→ E W (F 2 m ) (u, v) -→ µ 2 u, µ 3 (v + su + √ a 6 ) ,
and its inverse:

Ω : E W (F 2 m ) -→ E W (F 2 m ) (u , v ) -→ ν 2 u , ν 3 v + sν 2 u + √ a 6 with µ = (a + b) f , ν = µ -1 , and s ∈ F 2 m satisfying s 2 + s = a 2 + f -2 . The birational equivalence Φ : E W (F 2 m ) -→ E H (F 2 m ) , (u, v) -→ b u + a 2 v , a u + b 2 v + (a + b) f u ,
maps from the Weierstrass curve E W onto the Huff curve E H . Its inverse looks as follows:

Ψ : E H (F 2 m ) -→ E W (F 2 m ) , (x, y) -→ ab xy , ab (axy + b) x 2 y
The neutral element is (0, 0) and the group law is based on the chord-and-tangent rule. Note, however, that the birational equivalences are not line-preserving. The inverse some affine point P = (x 1 , y 1 ) ∈ E H is

-P = y 1 (αx 1 + 1) (βy 1 + 1) , x 1 (βx 1 + 1) (αx 1 + 1) , (5)
with α = a+b b•f and β = a+b a•f . The projective homogenization of Equation ( 5) can be evaluated using 4M + 4m 8 . Furthermore, there are four exceptional cases, which have to be dealt with separately. We refer the reader to [START_REF] Devigne | Binary Huff curves[END_REF] for more details on that. Compared to binary Weierstrass curves, where point inversion costs at most one field addition and, hence, is negligible, this operation is very expensive on binary Huff curves.

Projective point doubling, and point addition take 6M + 2m 8 + 6S and 15M + 3S, respectively. The affine doubling formula looks as follows:

2P =            (1 : 0 : 0) if x 1 = 1, (0 : 1 : 0) if y 1 = 1, (a : b : 0) if x 1 y 1 = 1, and
f (a+b)x 2 1 (1+y1) 2 b(1+x1) 2 (1+x1y1) 2 , f (a+b)y 2 1 (1+x1) 2 a(1+y1) 2 (1+x1y1) 2 otherwise. ( 6
)
where P = (x 1 , y 1 ) ∈ E H . Also note that for subgroups not including the points at infinity a complete addition law exists, i.e., it can also be used for point doublings.

Differential Addition

For Huff curves, the authors of [START_REF] Devigne | Binary Huff curves[END_REF] give differential addition formulas for use with the Montgomery ladder. To do so, they introduce the coordinate function w(x, y) = xy, which fulfills the condition w(P ) = w(-P ). From Formula (6), they derive the following differential doubling formula:

w(2P ) = γ • w 2 1 (1+w1) 4
if w 1 = 1, and

(1 : 0) otherwise. [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF] where γ = (a+b) 2 ab and w 1 = w(P ). Using the birational equivalence Φ and the multiplicative differential addition formula from [START_REF] Stam | On Montgomery-like representations for elliptic curves over GF(2 k )[END_REF], the authors of [START_REF] Devigne | Binary Huff curves[END_REF] obtain the subsequent addition formula:

w(P + Q) = (w1+w2) 2 w(1+w1w2) 2 if w 1 w 2 = 1, and
(1 : 0) otherwise.

(

) 8
where P = Q, w 1 = w(P ), w 2 = w(Q), and w = w(P -Q).

Working with affine coordinates is less satisfying due to the costly inversion required in each step. Hence, Devigne and Joye introduce projective W Z- for some θ ∈ F * 2 m . Now, when given P = (W 1 : Z 1 ) and Q = (W 2 : Z 2 ), the projective differential addition formulas look as follows: 4 and

coordinates. A point P = ( X1 Z1 , Y1 Z1 ) ∈ E H in W Z-
W (2P ) = γ • (W 1 Z 1 ) 2 Z(2P ) = (W 1 + Z 1 )
W (P + Q) = Z (W 1 Z 2 + W 2 Z 1 ) 2 Z(P + Q) = W (W 1 W 2 + Z 1 Z 2 ) 2 ,
where W (P -Q) = ( W , Z) are the W Z-coordinates of P -Q. Obviously, the first requires 1M + 1m 8 + 3S, whereas the latter requires 6M + 2S, which can be improved to 4M + 2S by computing

W 1 Z 2 + W 2 Z 1 as (W 1 + Z 1 )(W 2 + Z 2 ) + (W 1 W 2 + Z 1 Z 2 )
and scaling the coordinate ( W : Z), since it remains constant throughout the whole Montgomery ladder process.

Contribution

In this section we are going to describe a Huff curve implementation and the optimizations we have applied to it. Furthermore, we contrast its performance with a reference implementation that is based on Weierstrass curves, to which we have applied the same set of optimizations. Then, we present timings of both implementations, which show that for the binary NIST curves, the Huff curve implementation is up to 7.4% faster than the reference implementation. We also present the curve parameters for the binary Huff curves corresponding to the binary NIST curves and give formulas for back-and-forth conversion between binary Huff curves and binary curves in short Weierstrass form.

Deriving Curve Parameters

Deriving curve parameters a, b, f ∈ F 2 m from a given binary Weierstrass curve with parameters a 2 , a 6 ∈ F 2 m , works as follows [5, Proof of Proposition 2]:

1. Select an arbitrary f ∈ F 2 m so that T r(f -1 ) = T r(a 2 ) and T r(f 8 a 6 ) = 0, 2. find a solution t ∈ F 2 m to the equation t 2 + f 4 √ a 6 -1 t + 1 = 0, and

3. determine a, b ∈ F 2 m such that √ t = ab -1 ,
where T r(•) is the trace function T r :

F 2 m → F 2 , x → m-1 i=0 x 2 i
. The parameters we have obtained for the NIST-recommended curves [START_REF] Gallagher | Fips pub 186-3 federal information processing standards publication digital signature standard[END_REF] plus the value s needed for Ω and Θ are listed in Table 1 and in Table 2, respectively.

Mapping between Huff and Weierstrass Curves

Let P W = (u, v) be a point on E W (F 2 m ), P W = (u , v ) = Θ (P W ) ∈ E W (F 2 m
) and P = Ω (P W ) be the corresponding point on E H (F 2 m ).

Weierstrass to Huff Curve: From the birational equivalence Φ • Θ, we derive the following formula for directly mapping P W to W Z-coordinates:

(W : Z) = ab µ 2 u + a 2 µ 2 u + b 2 : µ 6 (v + su + √ a 6 ) ((v + su + √ a 6 ) + u)
Through decomposition we get:

-A = µ 2 u, -B = (A + a 2 ), C = (A + b 2 ), -D = v 1 + su + √ a 6 , E = D + u, -W = ab • B • C, and -Z = µ 6 • D • E.
The values a 2 , b 2 , and √ a 6 as well as the multiplication lookup tables for the values µ 2 , µ 6 , s, and ab can be determined a priori. For this setting, we get a total of 2M + 4m 8 for obtaining the W Z-coordinates of P W . Of course, if P W is fixed, one can precompute its scaled W Z-coordinates.

Huff to Weierstrass Curves: In order to convert the result W (k • P ) = (W 1 : Z 1 ), obtained from applying the differential Montgomery ladder on E H , back to E W , we need to evaluate the birational equivalence Ω • Ψ . The naive approach would be to, firstly, compute the x-coordinate of the corresponding point on

E W Curve a b f B-163 0x1 0x253f3c45a6d779b47e63758c35336f0679b42f4c0 0x6 K-163 0x1 0x20000000000000000000000000000000000000033 0x6 B-233 0x1 0x115b7c737bec7a5cc19212911c2bd03cadb9a29ddf9b1dc64b\ 0x3 8b3550fb3 K-233 0x1 0x1e5ff5c884156aaebbd38370425882dff04f04ba05a7f40740\ 0x2 82385c149 B-283 0x1 0x6a263cdd28c309d3d3068046747abe51375b0d763dccc64868\ 0x3 251918d59c21842dd4fe1 K-283 0x1 0x7a0fa1ffdaf44208a4efb593c405714e0fbc4423dd0db57384\ 0x2 89cb583073c2cae153d0d B-409 0x1 0x3f2918c0e689aca093d4cf5a389aeda96eb5cdcb930617991d\ 0x9 09111a3f91dc7283123ef8ab912744e193c34c9bd3cd532e17b7 K-409 0x1 0x846538361ed11b7c42b9e302169a3ea16009df82f80a155d56\ 0x2 39d78d4ba8dd02284110d6b3fbc05dda9c0ed1c0d6316c72d676 B-571 0x1 0x3c0904534c17c94a947b971ee5e6a3f3fb917dd3b57d7ad1f6\ 0xf ea35ec2593bae024934b8efe08d2a5bb97c4286665408d50f80c\ afc8dfbee0011c03e785fe39c94c977d5e3a7f065 K-571 0x1 0x6a28a2cf6fb77a9485f438a79f8832d86c465b689fd80b3d9c\ 0x2 4b1ef40380b5d92f85044e450336618a69b209eb37ecdd23da7b\ f7ee9e0fc1e98248edb0dc92f3510027be50cd2bb
Table 1: Generalized Huff curve parameters for NIST-recommended binary curves (cf. [START_REF] Gallagher | Fips pub 186-3 federal information processing standards publication digital signature standard[END_REF]).

Curve s

B-163 0x4058c6f9ae170f30f3ec9def6b2ddf2a28f0c0872 K-163 0x4058c6f9ae170f30f3ec9def6b2ddf2a28f0c0872 B-233 0xe7b4bcdb4af3163783507af91971d49927298e32e548d55b3a0b602a42 K-233 0xb1ce7164613a37fed984a32b18d265ada947ed207757d373d4e139835a B-283 0x21b24c4336e195a894fc9021fabac4e6988ff780c29522af3261508be\ fb321108eda3fa K-283 0x387fd1da986a7fa48458bf27d26d9162d60c2f7f6e3da61f30d215c6b\ 193e73f223326e B-409 0x106176448c66d8e7d0ddc074d76277a7ac8093ee53499d108099266d9\ 82c68dae5cb61d5054b30ecfce3c3beebc8cbecb904fd0 K-409 0x15dedff38eafec7e43a277eea795fbb1d52e6075a8bfe6a275be0dcba\ f6b781f8c9d37e4f414e8de3634d946434d9b6a6d62e20 B-571 0x12007d9377488ff6122ccce941d1cef856279188c8e82a6696a918b2f\ ccd78353385beb5e972f83d491d22db627117ab1580dabd23c6e8adeb99\ d3bdbc95d6fb645833ba6b4f182 K-571 0x2780c6d786569591600518d211a5d6fbd900d9b44a1e4e65016d2331d\ d243a6b31db129832a46326c7e3fd9b43f900ee58ed165e550a3cc3a41f\ b88b001fa79f398351bb7c35dea
Table 2: Auxiliary parameter s for mapping between NIST-recommended binary Weierstrass curves (cf. [START_REF] Gallagher | Fips pub 186-3 federal information processing standards publication digital signature standard[END_REF]) and the corresponding binary Huff curves.

as u 1 = ab w(k•P ) then, secondly, to map the result from E W to E W , and, finally, to recover its y-coordinate v 1 using the formula from [START_REF] López | Fast multiplication on elliptic curves over GF(2 m ) without precomputation[END_REF]:

v 1 = (u 1 + u) (u 1 + u) (u 2 + u) + u 2 + v u + v, (9)
which requires the additional value u 2 = ab w((k+1)•P ) , which can be computed using the point W ((k + 1)P ) = (W 2 : Z 2 ) from the last step of the Montgomery ladder. All in all, this would require several inversions, which can be saved by combining the formulas. To do so, one can replace u 1 = ab w(k•P ) with u 1 = δ•Z1 W1 , where w(k • P ) = W1 Z1 as W (k • P ) = (W 1 : Z 1 ), δ = ab µ 2 and µ = (a + b)f , and so implicitly apply Ω. By inserting it into Equation ( 9), one derives the following formula:

v 1 = (δZ 1 + uW 1 ) (δZ 1 + uW 1 ) (δZ 2 + uW 2 ) + u 2 + v W 1 W 2 uW 2 1 W 2 + v,
Now, one can compute

U 1 = δZ 1 uW 1 W 2 and V 1 = β β (δZ 2 + uW 2 ) + u 2 + v W 1 W 2 + uvW 2 1 W 2 with β = 1 + uW 1 and obtain (u 1 , v 1 ) = U1 uW 2 1 W2 , V1 uW 2 1 W2
. Common subexpression elimination yields the following relations:

-A = δZ 1 , B = δZ 2 , -C = uW 1 , D = uW 2 , -E = A + C, F = B + D, -G = W 1 W 2 , H = (u 2 + v), -I = (C • G) -1 , J = A • G, -K = J • I, L = E • I, -u 1 = uK, and -v 1 = L • (E • F + H • G) + v.
During the computation one can save the lookup tables of the intermediate values I and G, replacing 4M by 2M + 2m 4 . Moreover, δ is constant and multiplications with it require 1m 8 . Finally, we recycle the lookup table of u 1 , exchanging 3M for 1M + 2m 4 . In case the point P W = (u, v) is fixed, one can precompute the lookup tables of u and H using w = 8. Thus, one can trade 1M + 3m 4 + 1S for 4m 8 . To sum this up, the back-conversion including the y-coordinate recovery costs 1I + 6M + 5m 4 + 2m 8 + 1S in general, and 1I + 5M + 2m 4 + 6m 8 for P W fixed.

Implications: If the point P W is not fixed, in which case one needs both back and forth conversions including a y-coordinate recovery, one obtains total costs of at most 1I + 8M + 5m 4 + 6m 8 + 1S. Using XZ-coordinates on short Weierstrass curves, the formulas for restoring the y-coordinate turn out to be faster by only 2m 8 and, hence, this difference is negligible. Taking the conversion to W Z-coordinates into account, one gets a small difference of 2M + 6m 8 , which only becomes significant if P W is not known a priori. This minimal overhead for the conversion pays off, as for the scalar multiplication using W Z-coordinates one has 4M + 2m 8 + 5S contrary to 5M + 1m 8 + 4S per bit of the scalar k when using XZ-coordinates.

Implementation Details and Optimizations

The implementation is written in Java and is based on the NIST recommended elliptic curves B-163, B-233, B-283, B-409 and B-571 [START_REF] Gallagher | Fips pub 186-3 federal information processing standards publication digital signature standard[END_REF]. We are using fast reductions for the underlying binary fields and long-arrays for values thereof, which are in polynomial representation. Furthermore, we perform squarings in linear time using table lookups [START_REF] Schroeppel | Fast key exchange with elliptic curve systems[END_REF] and multiplications using the windowed left-to-right comb multiplier. The latter works with precomputed multiplication lookup tables and is due to Lim and Lee (cf. [START_REF] López | High-speed software multiplication in F2m[END_REF][START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]). For ordinary binary field multiplications we use windows of size w = 4 and for multiplications with values known beforehand, such as curve parameters and combinations thereof, we use windows of size w = 8. Additionally, we cache these lookup tables for curve parameters and recurring intermediate values in the addition/doubling formulas resulting in a quite reasonable speedup. We point out that both implementations only restore the y-coordinates without scaling the result and, thus, return projective coordinates. The coordinate W (2P -P ) = W (P ) = W : Z gets scaled and, thus, one can ignore Z. Furthermore, W is either fixed because of P being the base point, or fixed throughout the whole ladder steps as the point difference stays the same. In both cases one can store the multiplication lookup tables for w = 8. Hence, the costs of the differential addition drop from 4M + 2S to 3M + 1m 8 + 2S. With differential doubling requiring 1M + 1m 8 + 3S, one gets an overall of 4M + 2m 8 + 5S per bit of scalar k. In case P is not fixed, one has additional one-time costs for scaling W : Z , that is 1I + 1M, and one-time costs for assembling its lookup tables with window size w = 8.

Finally, we emphasize that the implementation of the differential Montgomery ladder on Huff curves is straight-forward and does not require more effort than its counterpart on Weierstrass curves, especially when the all-in-one formulas presented in this paper are being used. Timings: All benchmarks were carried out on an Intel Core i5-2540M running Ubuntu Linux 12.10/amd64 and OpenJDK 7u15/amd64 in server mode. Table 3 shows the timings of one application of the Montgomery ladder on the test platform using both W Z and XZ-coordinates on the binary NIST curves, where in the former case we present the timings for both cases, i.e., for fixed P fixed and random P . The performance gains achieved through precomputations, which are possible in case of fixed P , are reflected in the timings. Furthermore, all timings include the recovery of the y-coordinate as well as in case of W Z-coordinates the back-and-forth conversion between Weierstrass and Huff curves.

In Table 4, one can see the relative costs of one squaring and one multiplication with a curve parameter compared to an ordinary field multiplication. This

Conclusions

We have implemented binary Huff curves in software. For scalar multiplication, we were using a differential Montgomery ladder, based on the differential addition formulas given by Devigne and Joye in [START_REF] Devigne | Binary Huff curves[END_REF]. The timings show that for the binary NIST curves, this implementation is up to 7.4% faster than the reference implementation of the differential Montgomery ladder on the corresponding Weierstrass curves, to which we have applied the same set of optimizations.

We have presented fast all-in-one back-and-forth conversion formulas, which implicitly include the recovery of the y-coordinate. These conversions turn out to be almost as efficient as the y-coordinate recovery on Weierstrass curves, which is required anyway after using the Montgomery ladder on Weierstrass curves. This preserves most of the savings obtained through the faster differential addition formulas. Furthermore, we have presented curve parameters for Huff curves, which are birationally equivalent to the NIST-recommended binary Weierstrass curves.

Finally, we emphasize that when using the formulas presented in this paper, the implementation of the differential Montgomery ladder on Huff curves does not require more effort than its counterpart on Weierstrass curves. Thus, given the performance gains discussed in this paper such an implementation is an interesting alternative to conventional implementations.

  Require: A point P on E and a scalar k = (k l-1 , . . . , k0)2 ∈ Z Ensure: W (k • P ) = (X1 : Z1) (X1 : Z1) = W (P ) and (X2 : Z2) = W (2P ) for i = l -2 downto 0 do if ki = 0 then (X1 : Z1) = 2(X1 : Z1), and (X2 : Z2) = (X1 : Z1) + (X2 : Z2) else (X1 : Z1) = (X1 : Z1) + (X2 : Z2), and (X2 : Z2) = 2(X2 : Z2) end if end for

  coordinates, is represented by the tuple (W : Z) = (θw(P ) : θ) = (θX 1 Y 1 : θZ 2 1 ) if P = (a : b : 0), and (θ : 0) otherwise.

  Coordinates B-163 [ms] B-233 [ms] B-283 [ms] B-409 [ms] B-571 [ms]

	XZ	0.709	1.315	1.896	4.203	8.403
	W Z	0.692	1.251	1.826	4.040	8.143
	Speedup	2.46%	5.12%	3.83%	4.03%	3.19%
	W Z (P fixed)	0.662	1.224	1.778	3.928	8.039
	Speedup	7.10%	7.43%	6.64%	7.00%	4.53%

Table 3 :

 3 Timings of the Montgomery ladder for W Z and XZ coordinates using binary NIST curves.analysis shows that trading 1M for 1m 8 + 1S per ladder iteration, as done by using W Z instead of XZ-coordinates, saves up to 0.54M per ladder step on the test platform.

	F 2 163	F 2 233	F 2 283	F 2 409	F 2 571
	1S = 0.094M 0.080M 0.077M 0.061M 0.055M
	1m8 = 0.369M 0.411M 0.387M 0.418M 0.430M

Table 4 :

 4 Costs of squarings and multiplications with curve parameters in relation to ordinary multiplications.


Tomasz Hachaj
email: tomekhachaj@o2.pl

Marek R Ogiela
email: mogiela@agh.edu.pl

Computer karate trainer in tasks of personal and homeland security defense

Keywords: GDL, gesture description language, semantic classifier, gestures recognition, karate, self-defense

In this paper will be presented a new possibility of using GDL (Gesture Description Language) approach for recognition of basic combat techniques from martial arts. The GDL approach allows not only to analyze the several Shorin-Ryu Karate techniques but also to support the training and teaching activities of such arts. Moreover the GDL allow performing the human behavioral analysis, which may be important for recognition of dangerous situations while ensuring the homeland security.

Introduction

In case of attack of foe who has more physical strength, proper self-defense training might save the life and health of potential victim. The knowledge of defense martial arts is important aspect of personal and social security. In our opinion easy and common access to cheap self-defense courses would highly increase dexterity, confidence and composure in crisis situations of large society group. This is how popularization of personal training program can affect the homeland security. Some aspects of selfdefense training require physical contact with human trainer however some exercises can be practiced alone. Those are arduous repetitions of movement sequences that have to be "remembered by body" to be quickly and subconsciously performed if there is only time for rapid reaction. We believe that those exercises can be overseen by computer application which will give advices and motivation to the adept. What is more that kind of application can be run whenever user wants to train. The overseeing computer programs of that type have to recognize specialized movement sequencesgestures of the user. The problem of computer gestures recognition has long history and there are many approaches how to deal with this task. The most popular are:

• Statistical methods [START_REF] Vinayak | Shape-It-Up: Hand gesture based creative expression of 3D shapes using intelligent generalized cylinders[END_REF],

• Neural networks and fuzzy sets [START_REF] Elakkiya | Fuzzy Hand Gesture Recognition Based Human Computer Interface Intelligent System[END_REF],

• Optimal path finding [START_REF]Full Body Interaction Framework[END_REF],

• Semantic methods and finite state machines [START_REF] Arulkarthick | Sign Language Recognition using K-Means Clustered Haar-Like Features and a Stochastic Context Free Grammar[END_REF], [START_REF] Yeasin | Visual understanding of dynamic hand gestures[END_REF].

Lately appearance of new relatively cheap multimedia hardware enabled to introduce full body tracking and gestures recognition technology to personal computers and gaming consoles. For example a Kinect controller captures depth data stream which is then processed [START_REF] Shotton | Real-time human pose recognition in parts from single depth images[END_REF] in order to detect three-dimensional coordinates of 20 body joints (so called skeleton data). This approach has many important advantages:

• It does not require special markers to be placed over tracked body,

• It track skeleton relatively fast (with approximate frequency of 30 Hz),

• It has been proven that it can provide input data applicable for vast range of pattern recognition methods [START_REF] Bianco | Karate moves recognition from skeletal motion[END_REF], [START_REF] Miranda | Real-time gesture recognition from depth data through key poses learning and decision forests[END_REF].

• The multimedia controller is much cheaper than motion-capture hardware.

It was only matter of time while this technology has been applied to more sophisticated gestures that those that appears in computer games. Work [START_REF] Miranda | Real-time gesture recognition from depth data through key poses learning and decision forests[END_REF] introduces a method for real-time gesture recognition from a noisy skeleton stream, such as the ones extracted from Kinect depth sensors. Each pose is described using a tailored angular representation of the skeleton joints. Those descriptors serve to identify key poses through a multi-class classifier derived from Support Vector learning machines. The gesture is labeled on-the-fly from the key pose sequence through a decision forest that naturally performs the gesture time warping and avoids the requirement for an initial or neutral pose.

The computer -aided training and rehabilitation was a concept of many previously published papers and implemented systems. For many years the application of gestures recognition methods were limited because of specialized motion -capture hardware requirements [START_REF] Mirabella | A motion capture system for sport training and rehabilitation[END_REF]. Lately the Kinect technology was used in number of sports video game like "My Self Defence Coach", "UFC Personal Trainer" or "Nike+ Kinect Training" [10] however those applications are mainly done for entertainment and should not be treated as reliable computer coaching programs. One of the first well described approach of applying Kinect in personal training systems in presented in [START_REF] Bianco | Karate moves recognition from skeletal motion[END_REF]. This work aims at automatically recognizing sequences of complex Karate movements and giving a measure of the quality of the movements performed. The proposed system is constituted by four different modules: skeleton representation, pose classification, temporal alignment, and scoring. The proposed system is tested on a set of different punch, kick and defense karate moves executed starting from the simplest case, i.e. fixed static stances up to sequences in which the starting stances is different from the ending one. The skeleton is represented by chosen 14 angles designated by vectors defined by selected skeleton joints. Each gesture is split into key-poses. The classification of key poses is done with a multi-class Support Vector Machine (SVM), which recognizes key poses with a one-versus-all approach. The temporal alignment of sequences is done with classic Dynamic Time Warping approach. The system proposed in that paper has however two very important limitations caused by hardware and applied methodology. It has to be remembered that depth data captured by the Kinect sensor can be visualized as relief -like plate. If particular part of the body is covered by one another it exact position cannot be accurately measured. If this situation happens the tracking software computes the position of "invisible joint" estimating its position basing on known position of neighboring joints. This approach however might be highly insufficient in some real-life situations. The second limitation is pattern recognition method itself. Training of SVM (and other popular classifiers) requires huge data set to obtain high effectiveness. This might be a serious obstacle which limits this methodology only for research centers that manage to gather sufficiently big training dataset. However, it should be remembered that each selfdefense trainer exactly knows how the particular movements should be performed and what are the key-poses that have to be present in gestures sequence. In this paper we presents our novel method GDL (Gesture Description Language) for overcoming those hardware and methodology limitations and results of the initial tests of our approach. The GDL allows not only to analyze the several Shorin-Ryu Karate techniques but also to support the training and teaching activities of such arts. Moreover the GDL allow performing the human behavioral analysis, which may be important for recognition of dangerous treats while ensuring the homeland security.

Methodology

In this paragraph we will discuss our approach for calibration of multi -Kinect environment that can use standard tracking libraries for skeleton segmentation. In the second part of this paragraph the karate techniques recognition approach will be presented.

Overcoming hardware limitation

In order to acquire real three dimensional skeleton of observed user (not only as relief -like plate projection) more than one capture device has to be used. The most intuitive hardware configuration is presented in Figure 1 Each Kinect measures distance to observed point in its own right-handed Cartesian frame situated relatively to sensor orientation. Because of that same point V has dif-

ferent coordinates [ ] 1 , ' , ' , ' ' z y x v = and [ ] 1 , , , z y x v =
relatively to each pair of devices. Our task now is to map all of those points to the same coordinate system. In order to do this we have to find linear transform that is represented by following matrix: (1)

v t t t a a a a a a a a a v z y x =               ⋅ 1
Where ij a coordinates represents the rotation and k t translation. To compute unknown values we have to know coordinates of points in both Cartesian frames. Let us assume that a Cartesian frame that represents orientation of each Kinect was trans-lated and rotated around y (vertical) axis relatively to each other frame. That means there are four degrees of freedom (three for translation, one for rotation). Knowing that the linear transformation that maps coordinates of a point represented by vector ' v in one coordinate system to coordinates v in another one has form of following matrix:

v t t t v z y x =               - ⋅ 1 0 ) cos( 0 ) sin( 0 0 1 0 0 ) sin( 0 ) cos( ' β β β β (2)
In order to find unknown matrix coefficients following linear system has to be solved:

( ) ( )             =             ⋅               - - 2 2 1 1 ' 2 ' 2 ' 2 ' 2 ' 1 ' 1 ' 1 ' 1 sin cos 1 0 0 1 1 0 0 1 z x z x t t x z z x x z z x z x β β (3) 1 ' y t y y = + Where [ ] 1 , , , 1 1 1 1 z y x v = , [ ] 1 , , , 2 2 2 2 z y x v =
are points which coordinates are known in both frames. That matrix has to be solved both for center-left Kinects set and center-right Kinects set.

GDL classifier in task of Shorin-Ryu Karate recognition

GDL is a semantic classifier that uses syntactic description of gestures to be detected. The preliminary description of GDL architecture has been presented in [START_REF] Hachaj | Semantic Description and Recognition of Human Body Poses and Movement Sequences with Gesture Description Language, Computer Applications for Bio-technology[END_REF]. In those papers we discussed application of this methodology to recognition basic common life gestures (like waving or clapping). However it is also possible to apply GDL to sophisticated and complex movement sequences like those from Shorin-Ryu Karate.

The schema of gestures recognition pipeline with GDL classifier is presented in Figure 2. Movement is separated into key frames. Each key frame is represented by a rule in GDL script that has a conclusion. If a rule is satisfied for actual set of body joints positions (GDL uses forward chaining reasoning schema) its conclusion is memorized. It is possible to check with GDL script if some conclusion was satisfied in given time period. With this mechanism it is possible to generate chains of key frames, which create gestures. Because of space limitation we cannot present detailed description of all possible GDL script productions. Instead of that in Appendix we will show GDL script listings of all tested Karate techniques. The GDL syntax is very intuitive so we believe that short comments in source code will be sufficient for understanding.

Fig. 2.

The schema of gestures recognition pipeline with GDL classifier. The input data is recorded with depth sensor (for example Kinect). Then data is processed with appropriate libraries to extract features -skeleton. The skeleton is an input to GDL classifier. In GDL movement is described by set of rules consisted in GDL script file (GDL script is context -free grammar). Inference engine performs forward chaining reasoning on those rules. The conclusions of satisfied rules are stored in memory heap together with actual and previously captured skeletons and previously satisfied conclusions.

Results

In order to check possibilities of using GDL approach for recognition of basic combat techniques from martial arts, together with black belt instructor (3 dan) of Shorin-Ryu Karate we have created GDL script descriptions of one stationary position (Motodachi), one block (Age-uke) and one kick (Mae-geri). Than we recorded the instructor performing those techniques with system presented in Figure 2. Tables 1

Discussion and conclusion

As has been shown in our experiment it is possible to overcome limitation of single capturing device by adding more devices of the same type that gather user data at different angles. What is more our approach can be used with standard tracking libraries. Our experiment has also shown that integration of tracking data acquired by several Kinect devices with standard software increases the effectiveness of GDL classi-fier. This is due the fact that additional sensors that are situated at different angles than central one are capable of tracking body joints that in some situations might be covered by different body parts. This condition is especially visible in case of nonstatic Karate techniques: Age-uke and Mae-geri. After integrating skeleton data from three sensors as it was presented in paragraph 2 the recognition rate of Age-uke was increased by 42% and Mae-geri by 62%. All recognition errors were caused by inaccurate tracking of users' body joints. We anticipate that we can minimize "not classified" error rate even more by applying device setup that was presented in Figure 1 left. This sensor positioning will supply the system with "real" three dimensional measurements however the new tacking algorithm has to be generated. The creation of this new algorithm will be our goal for the future research. We have created the prototype of our training system which was used to gather data presented in result section and to our novel methodology validation. The photographs taken during this test session are presented in Figure 4. The implementation of system is capable of real time recognition of defined rules. The GDL approach allows not only to analyze the several Shorin-Ryu Karate techniques but also to support the training and teaching activities of such arts. In present form our approach enables karate techniques recognition that indicate to user if he or she made the gesture "enough similar to the pattern" to be classified. The proposed approach has to be expanded by additional module that would give the user the supporting information how well (how similarly to pattern) he made his gesture. In paper [START_REF] Bianco | Karate moves recognition from skeletal motion[END_REF] authors proposed the scoring methodology to give as output a score representative of the effectiveness and quality of the move performed independently of the move length. The final score is obtained by regression among human judgments and the normalized dynamic time warping distances obtained by each technique. The model fitted is a 5-parameters logistic. This approach can easily be adapted to our solution. In the future we will generate another scoring methodology to make scoring dependent only to similarity of performed movement to GDL script description.

Our future goal will be development of GDL script for recognition of complete set of most popular karate techniques. The completed classifier will be than utilized in selftraining multimedia application. We also plan to expand the GDL script syntactic [START_REF] Ogiela | Random graph languages for distorted and ambiguous patterns: single layer model[END_REF] to enable creation rules that describes behavior of more than one tracked user at the same time. With this simple extension GDL will allow to perform the human behavioral and human interaction analysis, which may be important for recognition of dangerous situations while ensuring the homeland security.

π and 4 π-

 4 -left. Three devices are positioned around object of observation on the vertices of equilateral triangle. This configuration however requires new depth stream processing algorithm. Because of that we propose another hardware configuration (Figure1-right). It also uses three sensors, the center one and two additional rotated around y (vertical) axis at the angle of 4 to center one relatively. With this Kinects positioning it is still possible to use standard tracking software. As we have proved in paragraph 3 of this paper filming the same scene from different angles enables to acquire more tracking information. Right parts of the body are better (more efficiently) tracked by right Kinect while left parts are more efficiently tracked by left one. That is because if for example user is performing Mae-geri kick with his right leg, in the end phase of movement the right knee is in the same vertical position as right foot and hip. It cannot be reliably tracked by center (the one that is in front of user) sensor because foot cover the position of two other body joints. In the same time those three joints are not overlapping from perspective of right sensor. The tracking software supplies us with three dimensional coordinates of body joints with information if particular joint position is obtained from direct tracking or it was estimated because that one is not visible. Knowing if joint tracked from central Kinect has exact coordinates or not we can use the coordinates from left or right additional device to make the overall skeleton position more reliable.

Fig. 1 .

 1 Fig. 1. Example multi Kinect setup, left -three devices are situated around the user, rightthree devices are situated in front of user. Detailed description is in text.

Fig. 4 .

 4 Fig. 4. The set of photographs taken during test session of our training system. In top left and top right photo we see hardware set up. It is consisted of three PC computers connected together in local network. Each of them runs single instance of application that implements gesture recognition pipeline from Figure 2. The recordings are synchronized by synchronization server that sends timestamps to each instance by UDP protocol. In bottom left and right photo we can see system performing real-time recognition of defined Karate techniques.

Table 1 .

 1 -2 summarize the classification results of our experiment. The description in first column is the actual technique (or group of techniques) that is present in particular recording. Each technique (or group of techniques) was repeated 50 times. Symbol + means that particular recording consisted of more than one technique. Description in first row is classification results. Last row sums up percentage of correct classifications of particular technique. Summing up, we had 150 recordings of karate techniques. In this experiment we check if it is possible to recognize the considered techniques and if multi sensor system setup increases overall recognition rate. The classification results of our experiment. Data was captured with single Kinect device (central one). Number in each cell is how many recordings belong to the certain class.

		Moto-dachi	Age-uke	Mae-geri	Not classified
	Moto-dachi	50	0	0	0
	Age-uke +	49	21	0	1+29=30

Table 2 .

 2 The classification results of our experiment. Data was captured with three Kinect devices situated as shown in Figure1on the right. Number in each cell is how many recordings belong to the certain class.

		Moto-dachi	Age-uke	Mae-geri	Not classified
	Moto-dachi	50	0	0	0
	Age-uke +	49	42	0	1+8=9
	Moto-dachi
	Mae-geri	0	0	32	18
	%	99.0%	84.0%	64.0%	13.5%
	Figure 3 graphically compares results presented in Table 1 and

Table 2 .

 2 Fig. 3. Plot that graphically compares results presented in Table1 and Table 2.

Acknowledgments. We kindly acknowledge the support of this study by a Pedagogical University of Krakow Statutory Research Grant.

Appendix -GDL script bases and examples

Skeleton is consisted of body joints. There are following possible names of body joints:

HipCenter, Spine, ShoulderCenter, Head, ShoulderLeft, El-bowLeft, WristLeft, HandLeft, ShoulderRight, ElbowRight, WristRight, HandRight, HipLeft, KneeLeft, AnkleLeft, FootLeft, HipRight, KneeRight, AnkleRight, FootRight.

Each rule starts with RULE keyword, and ends with conclusion name which is preceded by THEN keyword. Syntax:

means that you take three dimensional coordinate of joint HipLeft from the top of memory heap (actual joint position). Synatx:

HipLeft.y[0]

means that you take only y-coordinate (vertical). The coordinate frame is righthanded as shown in Figure 1.

KneeRight.a[0]

is an angle between vectors defined by joint KneeRight and two neighboring joints (HipRight and AnkleRight), the vertex of the angle is in joint KneeRight.

is angle between two vectors defined by joints coordinates. ABS is absolute value of real number. DISTANCE is an Euclidean distance between vectors. | is logical "or" operator, & is logical "and" operator.

is true if conclusion MaeMiddleRight has appeared in memory heap not longer than 1 second ago (this is "1" digit after comma) and MaeStart has appeared in memory heap not longer 1 second ago while MaeMiddleRight has appeared in memory heap.

The following listing is GDL script we defined together with black belt instructor (3 dan) of Shorin-Ryu Karate. Because of space limitation and intuitiveness of description we leave the detailed analysis to the reader.