Efficient Hardware Implementations of Legendre Symbol Suitable for MPC Applications.

Multi-party computation (MPC) allows each peer to take part in the execution of a common function with their private share of data without the need to expose it to other participants. The Legendre symbol is a pseudo-random function (PRF) that is suitable for MPC protocols due to their efficient evaluation process compared to other symmetric primitives. Recently, Legendre-based PRFs have also been employed in the construction of a post-quantum signature scheme, namely LegRoast. In this paper, we propose, to the best of our knowledge, the first hardware implementations for the Legendre symbol by three approaches: 1) low-area, 2) high-speed, and 3) high-frequency. The high-speed architecture outperforms state-of-the-art software implementations, which run on Intel’s Core-i5. Our evaluation results on FPGA show that this architecture reduces the Legendre calculation time by $2.56\times $ compared to software implementations on Core-i5. On the other hand, the low-area architecture consumes only 5489 slices on the Artix-7 FPGA and is suitable for resource-constrained devices. Moreover, our ASIC implementation results indicate that the low-area architecture consumes 97.56K gates to implement and requires $4.01~mW$ to operate on 50 MHz. The high-frequency architecture increases the frequency by $1.72\times $ over the high-speed architecture and achieves 200 MHz frequency on FPGA. [ABSTRACT FROM AUTHOR]