الفهرس 
LatticesOnly 14 pages are availabe for public view
 |  | from | 208 |  |  |
| | | from | 208 | | |
Abstract
The widespread use of computers and internets makes information secu- rity an increasingly important domain; some dangerous hacking might affect dramatically the daily life of the attacked persons. One of most confident tool for achieving the security is the Cryptology. Although cryp- tosystems such as RSA [65] and ECC [46] were sufficient to provide a good level of security yet, but the emergence of quantum computing [40, p. 497] and its capability of breaking down those cryptosystems posed a major threat to their quality of security. Until now, there is no physical exis- tence of quantum computation, however some studies expect their physi- cal emergence in the next four years [59]. Cryptosystems based on lattice problems are considered as the most candidate cryptosystems which are robust against the quantum computing attack. NTRU [39] and Regev cryptosystems [49, 62] are one of the famous lattice-based cryptosystems, they are respectively based on the shortest vector problem (SVP) and the learning with error problem (LWE). In fact, LWE is mainly based on the closest vector problem (CVP).
In this thesis, we consider SVP and LWE exposing in detail their mathematical background and then how to make use of graphics pro- cessing unit (GPU) to enhance some attacks approaches on the related cryptosystems. We developed a GPU-based algorithm for solving LWE problem and another algorithm for improving an existing GPU-based al-
xvii
gorithm for solving SVP.
This thesis, will be valuable for any one who needs to make use of GPU, especially in scientific and technical domains, and also much useful for whose are interested in the cryptography; in particular, the recent primitives cryptography systems (schemes) based on Lattice problems.
This thesis consists of six chapters and one appendix:
Chapter one: in this chapter, we present the necessary notations and mathematical background on lattices. In addition, we present lattice problems related to cryptography and some popular algorithms for solving lattice problems.
Chapter two: in this chapter, we present the fundamental concepts of GPU such as GPU processors and memories architectures. In addition, we present compute unified device architecture (CUDA) which is the most common platform dedicated for executing programs on GPU. Further- more, we show concrete examples of how to handle codes in CUDA.
Chapter three: in this chapter, we describe two cryptosystems with security based on lattice problems: SVP and LWE. Also, we present some attacks on these cryptosytems using lattices approaches such as Embedding, BDD and BKW attacks.
Chapter four: in this chapter, we have proposed a new paralleliza- tion strategy of the BDD enumeration algorithm using GPU. We have shown that significant speedups are achieved using GPU. Our experi- mental results showed that a single GPU speeds up a sequential solution of LWE by a factor of almost 6 in the Lindner-Peikert strategy and 9 in the pruned-enumeration strategy. Additionally, the scalability was signif- icantly reached; an additional GPU has improved the scalability further. Our experimental results showed that two GPUs provide speedup around
xviii
2 times than the speedup achieved by a single GPU. Moreover, exper- imental results showed that our implantation using two GPUs is more efficient than Kirshanova’s implementation using 20 CPU cores.
Chapter five: in this chapter, we have proposed three strategies for improving the pruned enumeration for solving SVP: a strategy based on generating GPU-points on GPU, a strategy based on improving the qual- ity of basis by using a randomization approach and a strategy based on expecting the best level on which we generate the GPU-points. We showed that a significant speedup could be gained by using those strategies alto- gether. The experimental results showed that a speedup by a factor of almost 2.5 and 5 was achieved using a single GPU and two GPUs respec- tively. Additionally, we showed that uses of two GPUs is faster twice than 16 physical cores provided by simultaneous multi-threading technology.
Chapter six: in this chapter, we summarize the achieved results and the future work.
Appendix A: this appendix contains the kernel code of GPU for LWE.