Paper 2015/938

Lattice Based Cryptography for Beginners

Dong Pyo Chi, Jeong Woon Choi, Jeong San Kim, and Taewan Kim

Abstract

The purpose of this lecture note is to introduce lattice based cryptography, which is thought to be a cryptosystem of post-quantum age. We have tried to give as many details possible specially for novice on the subject. Something may be trivial to an expert but not to a novice. Many fundamental problems about lattice are thought to be hard even against quantum computer, compared to factorization problem which can be solved easily with quantum computer, via the celebrated Shor factorization quantum algorithm. The first part of our presentation is based on slides of Christ Peikert 2013 Bonn lecture (crypt@b-it2013). We, more or less, give somewhat detailed explanation of Professor Peikert's lecture slides. We unfortunately could not attend his Bonn class. We are afraid that there are many mistakes in this note; if any, they are due to our misunderstanding of the material. Part II of our lecture note is on ring LWE, based on the paper ``A tool-kit for Ring-LWE Cryptography" by Lyubashevsky, Peikert and Regev. Part III is about multilinear maps together with cryptanalysis of GGH map due to Hu and Jia. Our presentation follows professor Steinfeld's lecture slides on GGHLite, and the paper by Yupu Hu and Huiwen Jia. When you read this lecture note, the corresponding original paper should be accompanied. We thank professor Jung Hee Cheon for introducing the subject and asking Dong Pyo Chi to give a lecture on the subject at the department of mathematics in Seoul National University. We also thank Hyeongkwan Kim for many helps, especially many corrections and improvements of the manuscript during the 2015 Summer session at UNIST. We also thank the students who took the classes at SNU and UNIST. The lecture was given by a novice for novice, so many mistakes are unavoidable. If the reader lets us know any errors, we will very much appreciate it.

Metadata
Available format(s)
PDF
Publication info
Preprint. Minor revision.
Keywords
Lattice-based cryptographyRing-LWE cryptographyMultilinear map
Contact author(s)
april02 @ snu ac kr
History
2015-12-21: revised
2015-09-28: received
See all versions
Short URL
https://ia.cr/2015/938
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/938,
      author = {Dong Pyo Chi and Jeong Woon Choi and Jeong San Kim and Taewan Kim},
      title = {Lattice Based Cryptography for Beginners},
      howpublished = {Cryptology ePrint Archive, Paper 2015/938},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/938}},
      url = {https://eprint.iacr.org/2015/938}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.