Accès ouvert

Improving BDD Enumeration for LWE Problem Using GPU

Article scientifique 2019 Anglais

Résumé

In this paper, we present a GPU-based parallel algorithm for the Learning With Errors (LWE) problem using a lattice-based Bounded Distance Decoding (BDD) approach. To the best of our knowledge, this is the first GPU-based implementation for the LWE problem. Compared to the sequential BDD implementation of Lindner-Peikert and pruned-enumeration strategies by Kirshanova [1], our GPU-based implementation is almost faster by a factor 6 and 9 respectively. The used GPU is NVIDIA GeForce GTX 1060 6G. We also provided a parallel implementation using two GPUs. The results showed that our algorithm is scalable and faster than the sequential version (Lindner-Peikert and pruned-enumeration) by a factor of almost 13 and 16 respectively. Moreover, the results showed that our parallel implementation using two GPUs is more efficient than Kirshanova et al.'s parallel implementation using 20 CPU-cores.

Citer ce document

Esseissah, M., Bhery, A., Bahig, H. (2019). Improving BDD Enumeration for LWE Problem Using GPU. https://doi.org/10.1109/access.2019.2961091

Accès au document

Voir sur le dépôt source

Ce document est hébergé sur son dépôt institutionnel d'origine.

Auteur(s)

Mohamed S. Esseissah Ashraf Bhery Hatem M. Bahig

Statistiques

Consultations : 1

Téléchargements : 0