Towards efficient LPN-based symmetric encryption (Q2117050)

A promising approach in cryptography is to construct encryption schemes based on the learning parity with noise (LPN) problem as these schemes can typically be implemented fairly efficiently using mainly ``exclusive or'' (XOR) operations. Most constructed LPN-based schemes are asymmetric, and there is no practical evaluation of any LPN-based symmetric encryption scheme. In this paper, the authors propose a novel LPN-based symmetric encryption scheme that is more efficient than related schemes. They propose a synchronous stream cipher, called Firekite, which uses an LPN-based pseudo-random number generator (PRNG) with a simple structure to generate its keystream. Unlike other proposed encryption schemes based on the LPN problem, this scheme only requires a source of cryptographically strong random bits for a key generation but not for encryption. Moreover, as their scheme can greatly benefit from dedicated hardware, the authors implemented and evaluated it on a low-power field-programmable gate array (FPGA). To the best of our knowledge, this is also the first time any LPN-based encryption scheme is tested and evaluated on an FPGA. For the entire collection see [Zbl 1482.94011].