# Implementation of Efficient Operations over GF(232)
## Using Graphics Processing Units

Satoshi Tanaka, Takanori Yasuda, Kouichi Sakurai

► To cite this version:

Satoshi Tanaka, Takanori Yasuda, Kouichi Sakurai. Implementation of Efficient Operations over GF(232) Using Graphics Processing Units. 2nd Information and Communication Technology - EurAsia Conference (ICT-EurAsia), Apr 2014, Bali, Indonesia. pp.602-611, 10.1007/978-3-642-55032-4_62 hal-01397276

HAL Id: hal-01397276

https://inria.hal.science/hal-01397276

Submitted on 15 Nov 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Implementation of Efficient Operations over
$GF(2^{32})$ using Graphics Processing Units

Satoshi Tanaka¹,², Takanori Yasuda², and Kouichi Sakurai¹,²

¹ Kyushu University, Fukuoka Japan
{tanasato@itslab.inf,sakurai@csce}.kyushu-u.ac.jp

² Institute of Systems, Information Technologies and Nanotechnologies, Fukuoka, Japan
yasuda@isit.or.jp

**Abstract.** Evaluating non-linear multivariate polynomial systems over finite fields is an important subroutine, e.g., for encryption and signature verification in multivariate public-key cryptography. The security of multivariate cryptography definitely becomes lower if a larger field is used instead of $GF(2)$ given the same number of bits in the key. However, we still would like to use larger fields because multivariate cryptography tends to run faster at the same level of security if a larger field is used. In this paper, we compare the efficiency of several techniques for evaluating multivariate polynomial systems over $GF(2^{32})$ via their implementations on graphics processing units.

**Key words:** Efficient implementation; multivariate public-key cryptography, GPGPU

# 1 Introduction

## 1.1 Background

The security of the public-key cryptography depends on the complexity of math problems. Of course, the public-key cryptography uses well-known hard problems, however, some of them will be insecure in the future. For example, the security of RSA public-key cryptosystem[5] is based on the complexity of integer factorization. However, quantum computers can solve it in polynomial time[6]. Hence, RSA public-key cryptosystem is going to be insecure in the future.

Therefore, some researchers study post-quatum cryptosystemsas, none of the known quantum algorithms can solve the problem in polynomial time.. The multivariate public-key cryptosystem (MPKC) is expected a candidate of post-quatum cryptosystems. Starting from the seminal work on MPKCy [3], researchers have provided efficient signature scheme [2] and provably secure symmetric-key cipher [1]. The security of MPKC is based on the complexity of solving non-linear multivariate quadratic polynomial equations over a finite field (MP), which is known as NP-complete.

Evaluating non-linear multivariate polynomial systems over a finite field is an important subroutine in MPKC. The core operations in evaluating a multivariate
polynomial system are additions and multiplications over a finite field. Therefore, accelerating these operations will accelerate all multivariate cryptosystems. On the other hand, the security of a MPKC depends on the numbers of unknowns and polynomials, as well as the order of the finite field.

## 1.2 Related works

Typically, $GF(2)$ and its extension fields are used in many multivariate cryptosystems, as additions over them only need cheap XOR operations. In the past, uses of $GF(2)$, $GF(2^4)$ and $GF(2^8)$ have been considered for multivariate cryptosystems [1]. For $GF(2^{16})$, multiplications are implemented by using intermediate fields of $GF(2^{16})$ on CPU and GPU [7]. Figure 1 shows the result of [7].

<figure><img src="image_2.png" /><figcaption>Fig. 1. The result of multiplications over $GF(2^{16})$ [7]</figcaption></figure>

## 1.3 Our contribution

In this paper, we have simply extended to $GF(2^{32})$ case from $GF(2^{16})$ case [7]. We study arithmetic operations over $GF(2^{32})$ and their implementation because we expect that they will be used for MPKC in the future.

In the following, we compare four methods for multiplications over $GF(2^{32})$ with CPU and graphics processing units (GPU) implementations.

# 2 Operations over Extension Fields

## 2.1 Extension of Finite Field

Let $p$ be a prime, and $F = GF(p^m)$, $K = GF(p^n)(m, n \ge 1)$. Then $K$ is an extension field of $F$, where $m | n$. We assume that $k = n/m$, $q = p^m$. Then the
Frobenius map $\sigma_0$ of $K/F$ is defined as:

$$ \sigma_0(a) = a^q. $$

$\sigma_0$ is a map from $K$ to $K$. It satisfies:

1. $\sigma_0(a+b) = \sigma_0(a) + \sigma_0(b) \quad \forall a, b \in K$;

2. $\sigma_0(ab) = \sigma_0(a)\sigma_0(b)$; and

3. $\sigma_0(\alpha) = \alpha \quad \forall \alpha \in F$.

The Galois group $\text{Gal}(K/F)$ is given by:

$$ \text{Gal}(K/F) = \{\sigma : K \to K : \text{automorphism} \mid \sigma(\alpha) = \alpha (\forall \alpha \in F)\}. $$

The elements of a Frobenius map $\sigma_0$ are the elements of the Galois group $\text{Gal}(K/F)$, in which the group operation is simply function composition. Moreover, $\text{Gal}(K/F)$ is a cyclic group generated by the Frobenius map $\sigma_0$, i.e.,

$$ \text{Gal}(K/F) = \{\sigma_0^0, \sigma_0^1, \sigma_0^2, \dots, \sigma_0^{k-1}\}. $$

## 2.2 Additions over Extension Fields

$K$ can be represented as a set of polynomials of degrees less than $k$ over $F$. Now, we choose a degree-$k$ irreducible polynomial over $F$:

$$ f_0(x) = x^k + a_{k-1}x^{k-1} + \dots + a_1x + a_0, a_0, \dots, a_{k-1} \in F. \quad (1) $$

Then, $K$ can be described by following the formula:

$$ K = \{c_{k-1}x^{k-1} + \dots + c_1x + c_0 | c_0, \dots, c_{k-1} \in F\}. $$

Addition $e_1 + e_2$ can be represented as:

$$ e_1 + e_2 := e_1(x) + e_2(x) \mod f_0(x), $$

where $e_1, e_2 \in K$. Therefore, we can compute additions over extension fields by summations of coefficients of polynomials over the base field.

## 2.3 Multiplications over Extension Fields

**Polynomial Basis** Let $K$ be a set of polynomials over $F$. Then, we can compute multiplication $e_1 * e_2$, where $e_1, e_2 \in K$, by:

$$ e_1 * e_2 := e_1(x) * e_2(x) \mod f_0(x), \quad (2) $$

**Zech's Method** $K^* := K \setminus \{0\}$ is a cyclic group. Therefore, $K^*$ has a generator $\gamma \in K^*$, and $K = \langle\gamma\rangle$. Then we can represent any element in $K^*$ as $\gamma^l$, where $l$ is an integer. In particular, $\gamma^l \neq \gamma^{l'}$, $0 \le l \ne l' \le p^n - 2$. In this way, $K^*$ can be represented by $[0, p^n - 2]$. Then, multiplications over $K^*$ can be computed by integer additions modulo $p^n - 1$.
**Normal Basis** There exists an $\alpha \in K$ for a finite Galois extension $K/F$ such that $\{\sigma(\alpha)|\sigma \in \text{Gal}(K/F)\}$ is an $F$-basis of $K$, which is called a normal basis of $K/F$. A normal basis of $K/F$ can thus be denoted by:

$$ \{\alpha, \alpha^q, \alpha^{q^2}, \dots, \alpha^{q^{k-1}}\}. \qquad (3) $$

Then, an element $a \in K$ can uniquely be written as:

$$ a = c_0\alpha + c_1\alpha^{p^m} + \dots + c_{k-1}\alpha^{p^{(k-1)m}}, \quad c_0, \dots, c_{k-1} \in F. \qquad (4) $$

Let $a = [c_0, c_1, \dots, c_{k-1}]_n \in K$ be defined in Eq. (4). Then Frobenius map $\sigma_0(a)$ as:

$$ \sigma_0(a) = a^q = [c_{k-1}, c_0, c_1, \dots, c_{k-2}]_n. \qquad (5) $$

In other words, $\sigma_0(a)$ is simply a right circular shift [4].

Furthermore, let $a = [c_0, c_1, \dots, c_{k-1}]_n, b = [c'_0, c'_1, \dots, c'_{k-1}]_n \in K$, and the result of the multiplication $a * b$ be $[d_0, d_1, \dots, d_{k-1}]_n$. Then, every $d_i$, where $0 \le i < k$, can be computed by evaluating the quadratic polynomials of $c_0, c_1, \dots, c_{k-1}, c'_0, c'_1, \dots, c'_{k-1}$ over $F$. Let $d_i = p_i(c_0, \dots, c_{k-1}, c'_0, \dots, c'_{k-1})$, $\forall 0 \le i < k$. According to Eq. (5), we can compute $\sigma_0(a * b)$ by:

$$ \begin{aligned} \sigma_0(a * b) &= [d_{k-1}, d_0, d_1, \dots, d_{k-2}]_n \\ &= \sigma_0(a) * \sigma_0(b) \\ &= [c_{k-1}, c_0, \dots, c_{k-2}]_n * [c'_{k-1}, c'_0, \dots, c'_{k-2}]_n \\ &= [p_0(c_{k-1}, c_0, \dots, c_{k-2}, c'_{k-1}, c'_0, \dots, c'_{k-2}), \dots, \\ & \qquad p_{k-1}(c_{k-1}, c_0, \dots, c_{k-2}, c'_{k-1}, c'_0, \dots, c'_{k-2})]_n. \end{aligned} \qquad (6) $$

By comparing coefficients, $d_{k-2}$ can be computed by:

$$ d_{k-2} = p_{k-1}(c_{k-1}, c_0, c_1, \dots, c_{k-2}, c'_{k-1}, c'_0, c'_1, \dots, c'_{k-2}), $$

with Eq. (6). In the same way, we can compute $\sigma_0^2(a * b), \dots$, for all $i$ by doing right circular shifts and computing all the $d_r$'s by evaluating $p_{k-1}$.

**Multiplication Tables** We create a multiplication table by offline precomputing all combinations of multiplications over $K$. Then, we can compute multiplications by looking up the multiplication table.

## 2.4 Analysis of Multiplication Algorithms

**Polynomial Basis** Let $e_1, e_2 \in K$ be $c_{k-1}x^{k-1} + \dots + c_1x + c_0$ and $c'_{k-1}x^{k-1} + \dots + c'_1x + c'_0$, respectively, and an irreducible polynomial $f_0$ be defined as Eq. (1). Then, the addition $e_1 + e_2$ needs $k$ additions over $F$. On the other hand, the multiplication $e_1 * e_2$ can be computed by:

$$ e_1 * e_2 = c_{k-1}c'_{k-1}x^{2k-2} + \dots + c_0c'_0 \quad \text{mod } f_0(x). $$
In this method, we need compute multiplications $c_i c'_j$ for $0 \le i, j < k$ and summations $\sum_{i+j=t, i, j \ge 0} c_i c'_j$ for $0 \le t \le 2(k-1)$ over $F$. The summation $\sum_{i+j=t, i, j \ge 0} c_i c'_j$ needs $t$ and $2k-t-2$ additions for $0 \le t < k$ and $k \le t \le 2(k-1)$ respectively. Therefore, it needs $(k-1)^2$ additions and $k^2$ multiplications over $F$ if schoolbook multiplication is used. Moreover, $e_1 * e_2$ takes $k[\log_2 p^m] \approx n[\log_2 p]$ bits of memory.

**Zech's Method** In this method, a multiplication over $K$ needs one integer addition modulo $k-1$. On the other hand, addition is not simple. Therefore, we convert it to the polynomial basis for additions and convert it back to the cyclic group representation for multiplications. Therefore, a multiplication needs three such conversions. One is for converting from polynomial to cyclic group representation, while the other is the opposite. Therefore, an addition takes $k$ additions over $F$, similar to the polynomial basis representation, and a multiplication needs one integer addition modulo $k-1$ plus three conversions between polynomial and cyclic group representations. Moreover, since the tables represent maps from $K$ to itself, Zech's method needs $2p^n[\log_2 p^m]$ bits of memory.

**Normal Basis** Let $a, b \in K$ be $[c_0, \dots, c_{k-1}]_n$ and $[c'_0, \dots, c'_{k-1}]_n$, respectively. An addition over $K$ takes $k$ additions over $F$, similar to the polynomial basis method. On the other hand, a multiplication $a * b$ takes $2(k-1)$ right circular shift operations and $k$ evaluations of a fixed (quadratic) polynomial $p_{k-1}(c_0, \dots, c_{k-1}, c'_0, \dots, c'_{k-1})$. An evaluation of a quadratic polynomial takes $k^2-1$ additions and $2k^2$ multiplications over $F$. We can further speed up such an evaluation by precomputing common multiplications $c_i c_j$ over $F$, where $0 \le i, j \le k-1$. Moreover, we can modify formula for $c_i, c_j, c'_i, c'_j$ to:

$$p_{k-1}(c_0, \dots, c_{k-1}, c'_0, \dots, c'_{k-1}) \\ = c_0 c'_0 + \sum_{0 \le i < j < k} s_{i,j} (c_i + c_j)(c'_i + c'_j) \quad \forall (i, j), s_{i,j} \in F,$$

where $i \neq j$. Therefore, a multiplication over $K$ needs $k(k-1)(k+2)/2$ additions and $k(k^2+1)/2$ multiplications over $F$ plus $2(k-1)$ right circular shift operations. Moreover, the normal basis method needs $(k^2-k+2)[\log_2 p^m]/2$ bits of memory.

**Multiplication Tables** An addition over $K$ can be computed using $k$ additions over $F$. On the other hand, a multiplication over $K$ needs only one table look-up. Since the entire multiplication table needs to store every possible combination of multiplications over $K$, this method requires $p^{2n}[\log_2 p^m]$ bits of memory.

## 3 GPGPU via CUDA

A graphics processing unit (GPU) is a special-purpose processor for accelerating computer graphics computations. Due to the nature of its computational tasks, GPUs can handle many operations in parallel in a high speed.
General-purpose GPU (GPGPU) computing is a technique that uses GPUs for general-purpose computation. Since GPUs are designed for single instruction multiple data (SIMD) operations, they are quite efficient for parallel processing. On the other hand, they are not so efficient when there is limited amount of parallelism. Therefore, the most important task in GPGPU is to identify or manufacture parallelism in the algorithms to be implemented.

## 3.1 CUDA API

CUDA is a development environment for NVIDIA's GPUs [8]. Before CUDA, GPGPU must have been done via hacking OpenGL or DirectX. These tools are not easy to use for non-experts of graphics programming, which was changed by the introduction of CUDA.

In CUDA, hosts correspond to computers, whereas devices correspond to GPUs. In CUDA, a host controls one or more devices attached to it. A kernel is a function that the host uses to control the device(s). In earlier CUDA, only one kernel can run at a time, and a program launches a kernel whenever parallel processes is needed. A kernel handles several number of blocks in parallel. A block also handles multiple threads in parallel. Therefore, a kernel can handle many threads simultaneously.

## 3.2 Parallelization for CUDA implementations

In CUDA API, we should consider how parallelize algorithms on GPUs. Especially, the number of threads in each block is important. This number is defined by GPUs. For example, NVIDIA GeForce 580 GTX can use 1,024 threads in each block registers. On the other hand, this number is also confined by the number of registers in blocks. Every thread use different registers for variables in kernels. When the total number of registers in every thread is greater than the number of registers in blocks, GPUs shows unexpected behavior (e.g. GPUs are halted). Therefore, we should parallelize algorithms for threads lest numbers of threads is greater than these GPU limitations.

# 4 Multiplications over GF(2<sup>32</sup>)

We can use XOR operations for computing additions over GF(2). Moreover, multiplications over GF(2) can be computed by the logical conjunctions AND.

## 4.1 Costs of multiplications over GF(2<sup>32</sup>)

Table 1 shows the costs of multiplications over GF(2<sup>32</sup>).

The polynomial basis method and the normal basis method need a lot more computational cost. On the other hand, Zech's method and using multiplication table are impractical, as it needs 32 GBytes and 64 EBytes of memory space, respectively.
<table><caption>**Table 1.** Costs of multiplications over GF(2³²).</caption><thead><tr><th>Methods</th><th>Computational cost</th><th>Memory space</th></tr></thead><tbody><tr><td>Polynomial basis method</td><td>961 XOR + 1,024 AND + 1 MOD</td><td>4 Byte</td></tr><tr><td>Zech's method</td><td>1 ADD + 1 MOD + 3 LOOKUP</td><td>32 GByte</td></tr><tr><td>Normal basis method</td><td>16,864 XOR + 16,400 AND + 2 SHIFT</td><td>125 Byte</td></tr><tr><td>Multiplication table</td><td>1 LOOKUP</td><td>64 EByte</td></tr></tbody></table>

## 4.2 Using Intermediate Fields

Although the multiplication table method is impractical for GF(2³²), it is possible for GF(2⁸), as the table there requires only 256 KByte. Also, Zech's method over GF(2³²) needs just 256 KByte. Here, we consider a method using an intermediate field GF(2¹) for GF(2³²)/GF(2), where $l = 2, 4, 8, 16$. In this method, we can compute multiplications over GF(2³²) by considering it as an extension field over GF(2¹) and by using the polynomial basis method or the normal basis method. For example, since the extension degree $k = 4$ for GF(2³²)/GF(2⁸), we can compute multiplication over GF(2³²) by 9 additions over GF(2⁸)(72 XORs), 16 table look-ups, and one modulo over GF(2⁸) with the polynomial basis method, or 288 XORs and 34 table look-ups with the normal basis method.

Similarly, we estimate the computational costs of multiplications over GF(2³²) using GF(2²), GF(2⁴) or GF(2¹⁶). We show the computational costs of multiplications over GF(2³²) using these intermediate fields in Table 2.

<table><caption>**Table 2.** Costs of multiplications over GF(2³²) using intermediate fields.</caption><thead><tr><th rowspan="2">Intermediate field GF(2<sup>l</sup>)</th><th colspan="2">Computation method</th><th colspan="4">Computational cost</th><th rowspan="2">Memory space</th></tr><tr><th>GF(2<sup>l</sup>)/GF(2)</th><th>GF(2<sup>32</sup>)/GF(2<sup>l</sup>)</th><th>XOR</th><th>LOOKUP</th><th>MOD</th><th>ADD</th></tr></thead><tbody><tr><td>GF(2<sup>2</sup>)</td><td rowspan="6">Multiplication table</td><td>Polynomial basis</td><td>450</td><td>512</td><td>1</td><td>-</td><td>6B</td></tr><tr><td rowspan="2">GF(2<sup>4</sup>)</td><td>Normal basis</td><td>4,320</td><td>4,112</td><td>-</td><td>-</td><td>35B</td></tr><tr><td>Polynomial basis</td><td>196</td><td>256</td><td>1</td><td>-</td><td>132B</td></tr><tr><td rowspan="2">GF(2<sup>8</sup>)</td><td>Normal basis</td><td>1,120</td><td>1,040</td><td>-</td><td>-</td><td>143B</td></tr><tr><td>Polynomial basis</td><td>72</td><td>128</td><td>1</td><td>-</td><td>64kB+4B</td></tr><tr><td rowspan="2">GF(2<sup>16</sup>)</td><td>Normal basis</td><td>288</td><td>272</td><td>-</td><td>-</td><td>64kB+4B</td></tr><tr><td>Zech's method</td><td>Polynomial basis</td><td>16</td><td>12</td><td>4</td><td>4 + 1</td><td>256kB+4B</td></tr><tr><td></td><td></td><td>Normal Basis</td><td>64</td><td>15</td><td>5</td><td>5</td><td>256kB+4B</td></tr></tbody></table>
# 5 Experimentation

We implement the three basic multiplication methods, namely, polynomial basis, Zech's method, and normal basis, over GF(2³²) on CPU and GPU. We evaluate and compare the running time of 67,108,864 multiplications with random elements over GF(2³²) for each methods. Similarly, we also implement and perform the same experiment using intermediate fields as follows:

1. Multiplication table + polynomial basis method:
   $GF(2^{32})/GF(2^k)/GF(2) (k = 1, 2, 4, 8)$

2. Multiplication table + normal basis method:
   $GF(2^{32})/GF(2^k)/GF(2) (k = 1, 2, 4, 8)$

3. Zech's method + polynomial basis method:
   $GF(2^{32})/GF(2^{16})/GF(2)$

4. Zech's method + normal basis method:
   $GF(2^{32})/GF(2^{16})/GF(2)$

Moreover, we describe primitive polynomials for each field extensions.

1. $GF(2^{32})/GF(2)$:
   $Y^{32} + Y^{22} + Y^2 + Y + 1 = 0$

2. $GF(2^{32})/GF(2^2)/GF(2)$:
   $Y^{16} + Y^3 + Y + X = 0$

3. $GF(2^{32})/GF(2^4)/GF(2)$:
   $Y^8 + Y^3 + Y + X = 0$

4. $GF(2^{32})/GF(2^8)/GF(2)$:
   $X^4 + Y^2 + (X + 1)Y + (X^3 + 1) = 0$

5. $GF(2^{32})/GF(2^{16})/GF(2)$:
   $Y^2 + Y + X^{13} = 0$

## 5.1 Environment of Implementation

All the experiments are performed on Ubuntu 10.04 LTS 64bit, Intel Core i7 875K and NVIDIA GeForce 580 GTX with 8 GBytes of DDR3 memory.

Table 3 shows constructions of parallelizations of 67,108,864 multiplications on NVIDIA GeForce 580 GTX for each multiplication method.

<table><caption>**Table 3.** Constructions of parallelizations on NVIDIA GeForce 580 GTX.</caption><thead><tr><th rowspan="2">Intermediate field GF(2<sup>l</sup>)</th><th colspan="3">Polynomial basis</th><th colspan="3">Normal basis</th></tr><tr><th>Block</th><th>Thread</th><th>Iteration</th><th>Block</th><th>Thread</th><th>Iteration</th></tr></thead><tbody><tr><td>GF(2)</td><td>32,768</td><td>32</td><td>64</td><td>32,768</td><td>32</td><td>64</td></tr><tr><td>GF(2<sup>2</sup>)</td><td>32,768</td><td>128</td><td>16</td><td>32,768</td><td>128</td><td>64</td></tr><tr><td>GF(2<sup>4</sup>)</td><td>32,768</td><td>512</td><td>4</td><td>32,768</td><td>512</td><td>4</td></tr><tr><td>GF(2<sup>8</sup>)</td><td>32,768</td><td>512</td><td>4</td><td>32,768</td><td>512</td><td>4</td></tr><tr><td>GF(2<sup>16</sup>)</td><td>32,768</td><td>512</td><td>4</td><td>32,768</td><td>512</td><td>4</td></tr></tbody></table>
## 5.2 Experiment Results

We show the result of implementations in Figure 2.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Experimental result of multiplications over GF(2<sup>32</sup>)</figcaption></figure>

In CPU implementations, the normal basis method using GF(2<sup>16</sup>) is the fastest, possibly because it needs the fewest computations among every method.

On the other hand, in GPU implementations, the polynomial basis method using GF(2<sup>8</sup>) for the intermediate field is the fastest. We believe that the GPU cannot efficiently access the tables in Zech's method over GF(2<sup>8</sup>), as these tables are too large to fit into the fast memory on GPU.

# 6 Conclusions

In this work, we have implemented and compare of several multiplication methods over GF(2<sup>32</sup>). In CPU implementations, the normal basis method using GF(2<sup>16</sup>) is the fastest. The second fastest is the polynomial method over GF(2<sup>16</sup>). On the other hand, for GPU implementations, it seems that GF(2<sup>8</sup>) is a very efficient intermediate field for building extension fields over it. Comparing CPU and GPU implementations, the fastest GPU implementation is about 49 times faster than the fastest one on the CPU. However, our GPU implementations are just parallelized CPU ones. We expect our research makes enables to enhance the security of MPKC by converting small finite fields (like GF(2<sup>8</sup>)) to GF(2<sup>32</sup>).

In future work, we would like to discuss optimizing multiplication methods for both CPU and GPU. Moreover, we would like to evaluate MPKCs using our implementations.
Acknowledgement

This work is partly supported by “Study on Secure Cryptosystem using Mul-
tivariate Polynomial System,” no. 0159-0172, Strategic Information and Com-
munications R&D Promotion Programme, the Ministry of Internal Affairs and
Communications, Japan, Grants for Excellent Graduate Schools, the Ministry
of Education Culture, Sports, Science and Technology, Japan and “The Con-
stitutive Theory of Non-Interactive Zero-Knowledge Proof based on Probability
Certification and Practical Enhancement to the Cryptography,” no. 25540004,
Grant-in-Aid for Challenging Exploratory Research, Japan Society for the Pro-
motion of Science. The authors are grateful to Xavier Dahan for his valuable
comments on our proposal.

References

1. Berbain, B., Gilbert, H., Pataring, J.: QUAD: a Practical Stream Cipher with Prov-
able Security. In EUROCRYPT'06, LNCS, vol.4004, pp.109-128, Springer, 2006.

2. Jintai, D., Dieter, S.: Rainbow, a new multivariable polynomial signature scheme.
In Applied Cryptography and Network Security - ACNS 2005, LNCS, vol. 3531,
pp.164-175, Springer, 2005.

3. Matsumoto, T., Imai, H.: Public quadratic polynomial-tuples for efficient signature-
varification and message-encryption. LNCS, vol.330, Proceedings of EURO-
CRYPT'88, pp. 419-453, Springer, 1988.

4. Menezes, A.J., van Oorschot, Vanstone, S.A.: Handbook of Applied Cryptography,
CRC Press 1997.

5. Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures
and public-key cryptosystems. In Communications of the ACM, Vol. 21, No. 2, pp.
120?126, 1978.

6. Shor, P. W.: Algorithms for quantum computation. In discrete logarithms and factoring, 1994.

7. Tanaka, S., Yasuda, T., Yang, B.-Y., Cheng. C.-H., Sakurai, K.: Efficient Com-
puting over GF(2<sup>16</sup>) using Graphics Processing Unit. In the Seventh International
Workshop on Advances in Information Security, 2013.

8. NVidia Developer Zone
https://developer.nvidia.com/category/zone/cuda-zone