What a lovely hat

Paper 2025/1509

LEAP: High-Performance Lattice-Based Pseudorandom Number Generator

Abstract

At EUROCRYPT2012, Banerjee, Peikert, and Rosen introduced Ring Learning With Rounding (RLWR) problem and constructed lattice-based pseudorandom functions for the first time. Subsequently, Banerjee, Brenner, Leurent, Peikert, and Rosen named this family of lattice-based pseudorandom functions as SPRING, reanalyzed the security, and gave two practical instances. Building upon the SPRING family, Bouillaguet, Delaplace, Fouque, and Kirchner further extended it to a pseudorandom number generator called SPRING-RS. It is quite fast but still has a certain gap compared with the classical pseudorandom number generator based on symmetric cryptography, and the key size is large. In this work, we present LEAP, a lattice-based pseudorandom number generation scheme characterized by high performance, adaptable parameter selection, and extensive support for parallel processing. Unlike the RLWR problem used in public key cryptography, LEAP treats the public parameter in the RLWR problem as the key as well. Hiding the public parameters leads to larger lattice dimensions and higher standard deviations of error in the concrete security analysis compared to RLWR under identical parameters. These adjustments imply enhanced security, allowing smaller parameters while maintaining the same security level, thereby improving performance. Additionally, we introduce a novel framework that reuses multiple parameters, significantly enhancing overall performance. To mitigate the issue of increased key size caused by treating the public parameter as the key, we design a pseudorandom number generator leveraging the small key size characteristic of a variant of the NTRU assumption, which provides the key required for the high-performance pseudorandom number generator. Compared with the SPRING-RS, the LEAP can reduce the key size by 1.71X while improving performance by 3.30X at the same security level. Under the AVX2 and AVX512 implementations, the performance reaches 1.61 Cycles/byte and 1.14 Cycles/byte, and the throughput reaches 16.12 Gbps and 22.60 Gbps, respectively.