In this paper, we consider the ABC cryptosystem based on multivariate polynomial systems which is one of the post-quantum cryptosystems. We review the theoretical structure of the ABC cryptosystem and implement it on the GPU by using the NVIDIA CUDA technology. We carry out the GPU and CPU implementation details of the ABC cryptosystem on three computers with different graphics cards. We also give a comprehensive comparison between the implementations. We compute the required number of arithmetic operations for each process: key generation, encryption and decryption. According to the experimental results, the GPU implementations have better memory performance than the CPU implementations. Moreover, the encryption process is faster in the GPU implementation. Due to the structure of ABC cryptosystem, the decryption process is slower in the GPU implementation.
Public-key encryption systems developed in the late 1970s are becoming a crucial component of communication networks. Especially with the spread of the internet, public key systems have become common with the key exchange in SSL (Secure Sockets Layer). Systems developed for the secure transmission and storage of information have enabled further study and development on public key encryption. However, it is thought that the classical public key encryption systems will lose their reliability when quantum computers working with very small cubits are developed and spread out. For this reason, it is essential to develop public key encryption systems that are resistant to quantum attacks. Besides, the reliability of the developed systems against quantum attacks should be tested.
At present, the internet and the other communication systems are mainly based on the Digital
Signature Algorithm (DSA), the Elliptic Curve DSA or the Diffie-Hellman key exchange using
related algorithms, RSA encryption and digital signatures [
When quantum computers of the required size are available, RSA [
Although there are many practical multivariate signature schemes [
Multivariate polynomial systems based cryptosystems are very attractive in the post-quantum
world. GeMSS, LUOV, Rainbow, MQDSS and their derivations have been proposed [
The security of the information obtained as a result of certain labor and the applications we use in our social and professional lives is vitally important. There are several encryption algorithms for the computers and for quantum computers that are currently prototypes. The ABC encryption algorithm based on multivariate polynomials is one of these algorithms. In this study, an implementation of the ABC encryption system which works on CPU and GPU has been developed to provide necessary security after quantum computers are available. We also give a comprehensive comparison between the implementations.
The organization of the paper as follows: In Section 2, we recall basic parts of the ABC cryptosystem. In Section 3, we give implementation details as well as a comprehensive comparison.
(1) − ( ) and variables as follows:
In this section, the details of ABC cryptosystem is given. ABC is one of the quantum attack
resistant cryptosystems. In [
The security of ABC cryptosystem depends on the hardness of the solution of multivariate polynomial systems. In a multivariate quadratic (MQ) polynomial system, there are equations
. multivariate quadratic polynomial system is needed such as : structure of public key, linear transformations are used such as 1: → . Then, to hide the linear → and 2: → . cryptosystem has three phases: key generation, encryption and decryption.
Then, the public key is formed as ´ = 2
1. The private key set includes 1, and 2. ABC Key Generation : Let F be a finite field with q elements. Let ∈ , = 2 and = 2 . Then = 1 ⋮ ( −1)( +1) ⋯ ⋱ ⋯ ⋮ , = 1 ⋮ ⋯ ⋱
⋮ , = ( −1)( +1) ⋯ 1 ⋮ ( −1)( +1) ⋯ ⋱
⋮ ⋯ linear transformations.
[ 1, … , ] is obtained by using ( 1, … , ) monomials. Then, by the linear combinations of Two invertible linear maps 2: →
and 1: ( 1, … , ), ( 1, … , ) and ( 1, … , ) are computed. 1 = and 2 =
are calculated. → are randomly chosen. Then, the public key is the composition ´ = 2 1: → . The private key includes B, C matrices and 1, 2 Encryption: Let ∈ be a message (plaintext). Then, the ciphertext is computed as follows: = ´ ( ) and ∈ .
Then, the message ∈ is obtained. The detailed decryption process is as follows: Decryption: After receiving the ciphertext, = −21( ), = −1( ) and = −11( ) are performed. 1) 1 = = −21( ) is computed. Then, ∈ is used to form ´1 and ´2 matrices.
1 ⋮ ⋯ ⋱ ⋮ , 2 = +1
⋮ ( −1)( +1) ⋯ +( −1)( +1) ⋯ ⋯ + ⋱ ⋮ 2) 3) = ( 1, … , ) is found such that ( ) = .
= −11( 1, … , ) is computed.
The decryption failure probability in Step 2 is 1/q. This means that there might be more than one solution of (1), … , ( ). Therefore, each possible solution should be checked. In order to implement ABC cryptosystem, finite field arithmetic (polynomial addition, multiplication inversion), matrix multiplication, matrix inversion, matrix transpoze, and Gaussian elimination algorithms are needed.
This section details the implementations of the ABC cryptosystem running on CPU and GPU separately. The ABC system operates in three main stages that are “key generation”, “encryption” and “decryption”. The parameters in the implementations on the CPU and GPU are given in Table 1. The implementations were carried out on three different platforms with the different operating systems; Windows 8 x64 and Windows 10 x64. The experiments were conducted on NVIDIA GeForce GT 740M, NVIDIA GeForce GT 840M and NVIDIA GeForce GTX 1050Ti graphics cards. One of the processes in which performance improvement is required is the addition in GF(28).
In the implementation on the CPU, after the predefined variables and the variables in the Main() function are defined, the implementation is executed by calling the functions written for key generation, encryption and decryption in the given order. The number of calls of the operations mentioned in Section 2 by three functions (key generation, encryption, decryption) is given in Table 2 for the CPU and GPU implementation.
Addition, subtraction and multiplication in the finite field GF(28) can be implemented on the Graphics Processing Unit (GPU) to provide performance improvement for the ABC cryptosystem.
The main task of a GPU is to display the images on the screen that are created on the computer. The first GPUs only performed this task. Over time, the Central Processing Unit (CPU) was inadequate for major computational problems, and the idea of parallel computing using the GPU is revealed. A GPGPU model has been created to provide that GPUs have a programmable interface and can be programmed in high- level languages.
Compute Unified Device Architecture (CUDA) is a parallel computing architecture introduced by NVIDIA in 2006 to take advantage of computing power of the GPU. CUDA is an application programming interface (API) model that supports programming languages such as FORTRAN, C/C++ and Python. It runs on Linux, Windows and Mac Osx platforms. Its advantages over its competitors include shared memory usage, faster data reading from the GPU, and bit-level operation.
The GPU differs from the CPU in that it has a SIMD (Single Instruction Multiple Data) architecture. Figure 2 shows the schematic comparison of CPU and GPU structures. While CPU calculations are performed in series, GPU performs calculations in parallel.
One of the most commonly used operations in the ABC algorithm is the addition in GF(28). When the overall algorithm is considered, the summation function is called once in the “key generation” function and three times in the “decryption” function.
} global void addcuda(WORD *a, WORD *b, WORD *c) { *c = *a ^ *b;
Similar to the function definition in C++ programming language, but a function other than the main function is defined in CUDA. “a”, “b” and “c” are pointer variables of type “WORD”. “c” is the variable that will store the result of the summation of “a” and “b” and carries it over the GPU to the CPU.
Calling the “addcuda” function in the key generation function is as follows. First, “*tempA”, “*tempB”, “*tempC” and “tempFB” are defined as WORD data type. Then the cudaMalloc which is a pre-defined CUDA function is used to define the size of the GPU. With the cudaMemcpy function, the values on the CPU are copied to the GPU. We call the function on the GPU with “addcuda <<< 1, 1 >>> ()”. After completing this process, we use the cudaMemcpy function to copy the values on the GPU back to the CPU.
WORD *tempA, *tempB, *tempC, tempFB; cudaMalloc((void**)&tempA, sizeof(WORD)); cudaMalloc((void **)&tempB, sizeof(WORD)); cudaMalloc((void **)&tempC, sizeof(WORD)); for (s = 0; s < VARIABLE; s++) { for (t = s; t < VARIABLE; t++) { if (t == s)
FB[flag++] = V[s * VARIABLE + t]; else { cudaMemcpy(tempA, &V[s*VARIABLE+t], sizeof(WORD), cudaMemcpy HostToDevice); cudaMemcpy(tempB, &V[t*VARIABLE+s], sizeof(WORD), cudaMemcpy HostToDevice); addcuda<<<1,1>>>(tempA,tempB,tempC); cudaMemcpy(&tempFB,tempC,sizeof(WORD), cudaMemcpyDeviceToHost);
FB[flag++] = tempFB; }
} } cudaFree(tempA); cudaFree(tempB); cudaFree(tempC); 3.3.
The implementation prepared in .Net environment using Microsoft Visual Studio for the ABC cryptosystem has been tested on three different computers, each with different graphics processors. Table 3 summarizes the computer, graphics processor, and operating system information used. In Table 4, the total running time of both CPU and GPU implementations prepared for the ABC cryptosystem in three different environments are given in microseconds (µs).
RAM In Table 6, the running times of the encryption and decryption functions on both CPU and GPU implementations prepared for the ABC cryptosystem in three different environments are given in microseconds (µs).
The running times of the implementations and the functions required for the ABC cryptosystem shown in Table 2 in detail are evaluated by counting the number of times the key generation, encryption and decryption are called and used. As can be noticed in the call of functions the entire addition operations in GF(28) are performed on the GPU. Furthermore, although an increase in total time has been observed, an improvement has been achieved in the process of encryption. In addition to running time improvements, there is an improvement in memory usage. The running time in Table 4 is measured for both implementations as follows: time starts before the key generation and ends with the completion of the decryption.
The running time of the CPU implementation is 4336000 microseconds in Computer1. The running time of GPU implementation is 6089299 microseconds on the same computer. There is a 40% increase in time compared to the CPU implementation. However, the memory consumption of the CPU implementation is 90MB while the memory consumption of the GPU implementation is 76MB. That is, a 15% memory saving is achieved compared to the CPU implementation. In the encryption function, the time is reduced from 16000 microseconds to 8000 microseconds and a 50% time-saving is achieved.
The running time of the CPU implementation is 5123000 microseconds in Computer2. The running time of GPU implementation is 6589299 microseconds on the same computer. There is a 28% increase in time compared to the CPU implementation. However, the memory consumption of the CPU implementation is 100MB while the memory consumption of the GPU implementation is 87MB. That is, a 13% memory saving is achieved compared to the CPU implementation. In the encryption function, the time is reduced from 19000 microseconds to 11000 microseconds and a 42% timesaving is achieved.
The running time of the CPU implementation is 2214000 microseconds in Computer3. The running time of GPU implementation is 4856900 microseconds on the same computer. There is a 19% increase in time compared to the CPU implementation. However, the memory consumption of the CPU implementation is 127MB while the memory consumption of the GPU implementation is 118MB. That is, a 7% memory saving is achieved compared to the CPU implementation. In the encryption function, the time is reduced from 10000 microseconds to 3000 microseconds and a 70% time-saving is achieved.
Regardless of the working environment, the GPU implementation is slower than the CPU implementation, but it is better in memory consumption. The reason for this difference is that the addition operations in GF(28) are performed on the GPU.
It is believed that the ABC, one of the multivariate public key cryptosystems, will be robust to computational attacks using quantum computers. As a result of this study, an application or implementation that works with a graphics processor regardless of the working environment of the computers is better in memory usage. The running times are evaluated by counting the number of calls of the key generation, encryption and decryption. The number of the arithmetic operations is computed. The memory consumption of the CPU implementation is larger than the GPU implementation in all platforms. In addition to the efficiency in terms of memory consumption, running the entire implementation on the GPU will allow better results to increase performance in terms of time.
The first and second authors were partially supported by TÜBİTAK under grant no. EEEAG116E279.