|
Título:
|
MPI-based implementation of an enhanced algorithm to solve the LPN problem in a memory-constrained environment
|
|
Autor/a:
|
Teixidó Torrelles, Ivan; Sebé Feixas, Francesc; Conde Colom, Josep; Solsona Tehàs, Francesc
|
|
Notas:
|
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.
This work was supported by the Ministerio de Ciencia e Innovación (Spain) under Contracts TIN2011-28689-C02-02, CSD- 2007-00050, CSD-2007-0004 and the European Social Fund. The authors are members of the research groups 2009SGR145 and 2009SGR442, which are funded by the Generalitat de Catalunya (Spain). |
|
Materia(s):
|
-Brute-force algorithm
-LPN problem
-Parallelization
-MPI |
|
Derechos:
|
(c) Elsevier, 2014
info:eu-repo/semantics/restrictedAccess |
|
Tipo de documento:
|
article
publishedVersion |
|
Editor:
|
Elsevier
|
|
Compartir:
|
|
