MPI-based implementation of an enhanced algorithm to solve the LPN problem in a memory-constrained environment

Teixidó Torrelles, Ivan; Sebé Feixas, Francesc; Conde Colom, Josep; Solsona Tehàs, Francesc

doi:https://doi.org/10.1016/j.parco.2014.04.002

View/Open

021168.pdf (631.0Kb)
Sol·licita una còpia

Issue date

2014

Author

Teixidó Torrelles, Ivan

Sebé Feixas, Francesc

Conde Colom, Josep

Solsona Tehàs, Francesc

Suggested citation

Teixidó Torrelles, Ivan; Sebé Feixas, Francesc; Conde Colom, Josep; Solsona Tehàs, Francesc; . (2014) . MPI-based implementation of an enhanced algorithm to solve the LPN problem in a memory-constrained environment. Parallel Computing, 2014, vol. 40, núm 5-6, p. 100-112. https://doi.org/10.1016/j.parco.2014.04.002.

Abstract

In recent years, several lightweight cryptographic protocols whose security lies in the assumed intractability of the learning parity with noise (LPN) problem have been proposed. The LPN problem has been shown to be solvable in subexponential time by algorithms that have very large (subexponential)

memory requirements, which limits their practical applicability. When the memory resources are constrained, a brute-force search is the only known way of solving the LPN problem. In this paper, we propose a new parallel implementation, called Parallel-LPN, of an enhanced algorithm to solve the LPN problem. We implemented the Parallel-LPN in C and MPI (Message Passing Interface), and it was tested on a cluster system, where we obtained a quasi-linear speedup of approximately 90%. We also proposed a new algorithm by using combinatorial objects that enhances the ParallelLPN performance and its serial version.

URI

http://hdl.handle.net/10459.1/57203

DOI

https://doi.org/10.1016/j.parco.2014.04.002

Is part of

Parallel Computing, 2014, vol. 40, núm 5-6, p. 100-112