| Hardness Estimation of the Generalized Learning with Errors Problem（一般化されたLearning with Errors問題の困難性評価） |
 王 偉尭
（指導教員：高木 剛／数理情報第1研究室）
Estimating the hardness of the learning with errors (LWE) problem is an essential topic for analyze the security of the lattice-based cryptography. For the purpose of analyze the hardness of the LWE problem, we study embedding techniques which reduce the LWE problem to a unique shortest vector problem (uSVP). Kannan’s and Bai-Galbraith’s embedding techniques are usually applied for solving the standard LWE problem and the binary LWE problem, respectively. In this thesis, we define the generalized LWE problem which extend the definition of the LWE problem and propose our half-twisted embedding that combines Kannan’s and Bai-Galbraith’s embedding techniques. The proposed embedding enables us to analyze the LWE problem in a generic manner and improves the reduction under some parameters.
During these two years, I learned a lot about mathematics, cryptography and academic writing and finally finished the above work as my thesis. I want to express my sincere gratitude to my supervisor Professor Tsuyoshi Takagi, Assistant Professor Atsushi Takayasu, Yuntao Wang, Yacheng Wang, and Yasuhiko Ikematsu. I cannot carry on my research without your instructions.
|
