AESpoly: Symmetric-Key Cryptographic Designs Using Instruction-Level Parallelism Between AES and Polynomial Hash

This paper studies the impact of instruction-level parallelism between the AES and CLMUL instructions on the design and performance of symmetric-key schemes. Our benchmark on modern processors from different vendors shows that a considerable portion of encryption (e.g., AES-CTR) and hashing (e.g., GHASH) runs in parallel due to the instructionlevel parallelism. This impacts the design space of symmetrickey schemes that has been separately optimized for encryption and hashing. By exploring the design space with a primitive that abstracts parallel execution, we propose a new wide-block encryption (WBE) called AESpolyW that achieves optimal parallel performance with respect to the number of primitive calls. We evaluate software performance of the instantiations with AES-128, Rijndael and Simpira v2, and AESpolyW outperforms the state-of-the-art WBE schemes, HCTR2 and EME, in the majority of twelve target processors from Intel, AMD, Apple, and Amazon AWS. We also propose a new message authentication code (MAC) called AESpolyM optimized for the instruction-level parallelism, and our software implementation of AESpolyM outperforms PMAC and GMAC in the majority of cases.