Area-time-efficient scalable schoolbook polynomial multiplier for lattice-based cryptography

Lattice-based cryptography (LBC) stands out as one of the most viable classes of quantum-resistant schemes. This work explores a time-sharing approach, with different parallelism levels, for a crucial operation in LBC cryptosystems, i.e., polynomial multiplication. We also employ an innovative coefficient ordering method in our time-shared schoolbook polynomial multiplication (SPM) to combine the best of two worlds: design compactness and lower processing latency. Thus, our work offers a choice of design points with performance vs. resource trade-offs. Our fastest proposed design exhibits 80% and 57% reductions in LUTs and throughput, respectively, compared to the existing fully parallel SPM architecture (on Xilinx Ultrascale+), which lead to a 53% improvement in the area-time-product efficiency. Our smallest proposed design is more than 2.2× faster than the existing low-cost parallel SPM architecture (on Xilinx Kintex-7) at the expense of 85% additional area resources.