Security threats are rising due to widely available computational power and near-future quantum computers. New cryptographic protocols have been developed to address these challenges, but very few protocols take advantage of parallel computing. In this paper, we propose optimizations to the cryptography protocol Response-Based Cryptography (RBC). Since the protocol is general-purpose, it can be incorporated into post-quantum cryptography systems to authenticate users in resource-constrained environments, like Internet of Thing (IoT) devices. The optimizations proposed in this paper allow for clients to be authenticated faster. Additionally, this paper makes a cross-platform comparison of the performance of the optimized RBC protocol on the Graphics Processing Unit (GPU), the Central Processing Unit (CPU), and the Associative Processing Unit (APU). We find that the GPU and APU yield similar performance but the APU can be much more energy efficient. Furthermore, we evaluate the multi-GPU scalability of the algorithm and achieve a minimum speedup of 2.66 × on 3 × A100 GPUs.