SABER-GPU: A Response-Based Cryptography Algorithm for SABER on the GPU

The Internet of Things (IoTs) contain many low-powered devices that require secure communication. Post-quantum cryptography (PQC) is needed to address quantum computers that eventually will be able to break current encryption schemes. However, IoT devices are low-powered and often do not have the computational power to carry out computationally expensive error correction schemes. To address this limitation, we propose leveraging response-based cryptography (RBC) to secure IoT devices. Physical unclonable functions (PUFs) can replace random number generators that are used in the public key creation procedures. In this scheme, a server authenticates a client by generating the same seed from the image of the client's PUF stored in the server in a secure environment, thus replacing static public keys with dynamically generated key pairs. In this paper, we focus on generating the public key from the SABER PQC algorithm. Due to the inherent bit error rates existing in PUF technology, the protocol requires that the server recognizes the erratic keys. This error correction requires a massive parallel search over a key space bounded by the expected PUF error rate. This paper examines the use of parallel computing technologies to rapidly find a client's public key within reasonable time constraints. In particular, we examine using multi-core CPUs and many-core Graphics Processing Units (GPUs) in shared-memory environments. The design space for the SABER PQC algorithm is large. Therefore, we focus on performance engineering several CUDA kernels used in the RBC search that systematically explore this space. Our RBC search algorithms are highly scalable: the multi-core CPU algorithm achieves a speedup of 61.82 x on 64 CPU cores, and our multi-GPU algorithm achieves a near-perfect speedup of 2.93 x on 3 GPUs. Using a typical PUF error rate that requires searching 1.75 × 108 keys, we find that our GPU algorithm can authenticate a user within 6 seconds, which is well below our authentication time threshold.