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

Simple item page
dc.contributor.authorTeixidó Torrelles, Ivan
dc.contributor.authorSebé Feixas, Francesc
dc.contributor.authorConde Colom, Josep
dc.contributor.authorSolsona Tehàs, Francesc
dc.date.accessioned2016-06-14T11:50:04Z
dc.date.embargoEndDate2025-01-01
dc.date.issued2014
dc.description.abstractIn 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.ca_ES
dc.description.sponsorshipThis 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).ca_ES
dc.identifier.doihttps://doi.org/10.1016/j.parco.2014.04.002
dc.identifier.idgrec021168
dc.identifier.issn0167-8191
dc.identifier.urihttp://hdl.handle.net/10459.1/57203
dc.language.isoengca_ES
dc.publisherElsevierca_ES
dc.relationinfo:eu-repo/grantAgreement/MICINN//TIN2011-28689-C02-02/ES/EJECUCION EFICIENTE DE APLICACIONES MULTIDISCIPLINARES: NUEVOS DESAFIOS EN LA ERA MULTI%2FMANY CORE/ca_ES
dc.relation.isformatofReproducció del document publicat a https://doi.org/10.1016/j.parco.2014.04.002ca_ES
dc.relation.ispartofParallel Computing, 2014, vol. 40, núm 5-6, p. 100-112ca_ES
dc.rights(c) Elsevier, 2014ca_ES
dc.rights.accessRightsinfo:eu-repo/semantics/restrictedAccessca_ES
dc.subjectBrute-force algorithmca_ES
dc.subjectLPN problemca_ES
dc.subjectParallelizationca_ES
dc.subjectMPIca_ES
dc.titleMPI-based implementation of an enhanced algorithm to solve the LPN problem in a memory-constrained environmentca_ES
dc.typearticleca_ES
dc.type.versionpublishedVersionca_ES
Files
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Articles publicats (Enginyeria Informàtica i Disseny Digital)
Grup de Recerca en Computació Distribuïda (INSPIRES)
Grup de Recerca en Criptografia i Grafs (INSPIRES)
Publicacions de projectes de recerca del Plan Nacional