Preface

Security is critical in modern society, particularly in the Internet era, where things as well as people are interconnected. Cryptography plays a critical role to ensure the security of the society by serving as a primitive and building block.

The goal of this book is to introduce the foundations of cryptography to students, researchers, and practitioners so that they design their own secure systems, analyze the existing cryptographic schemes, or apply the provably secure cryptographic schemes to the real world.

Features of the Book Compared to other subjects, cryptography is generally accepted as “difficult to understand,” mainly because the underlying proofs are kind of mental games, which may be hardly understandable. To ease the understanding of cryptography, we introduced detailed-and-intuitive explanations, relevant implementations, and extensible applications in this book. Particularly, sometimes, but not always, we found that detailed-andintuitive explanations are especially helpful for beginners to figure out the structural flow of security proof of cryptographic schemes; it becomes easier to understand a specific complex theoretical concept by implementing itself or constructing relevant applications. Specifically, this book is designed to have the following in mind in detail:

 1. giving a big picture of cryptography, wide and deep

  (a) the basic building blocks

  (b) various cryptographic schemes

  (c) applications to the real world

 2. providing fundamentals on cryptography

  (a) formal definitions of security

  (b) complexity assumptions of computational problems

  (c) proof techniques

 3. giving practice on how to implement cryptographic schemes efficiently

  (a) fundamental mathematical tools for efficient implementation

  (b) efficient techniques to optimize the implementation based on specific hardware

  (c) trade-off to be made during implementation (e.g., memory versus speed)

Structures of the Book In line with the above design purposes and features of the book, the whole book comprises the following four parts:

 1. Part I: Fundamentals of classical and modern cryptography are explained including the structure of security proofs, private-key encryption, message authentication code, hash function, basic number theory, public-key encryption, and digital signature.

 2. Part II: Identity-based encryption can use any arbitrary data for an identity as public keys, which is one of the big differences from traditional public-key encryption, which makes identity-based encryption easier to use, less expensive, and more practical.

 3. Part III: Post-quantum cryptography has emerged recently to prepare for the near future, as existing conventional cryptography is expected to be broken by advanced algorithms executed on quantum computers. Two representative post-quantum approaches, latticebased and code-based, are explored.

 4. Part IV: Various popular cryptographic schemes are implemented using the MIRACL library, which is based on C/C++ programming language. Some post-quantum schemes are implemented with plain C codes and evaluated on the Graphics Processing Units (GPU) with massively parallel architecture. Mathematical tools like Montgomery reduction, Chinese remainder theorem (CRT), and number theoretic transform (NTT) are used to optimize the performance.

Guide to the Book Readers will get much help if they study considering the following guidelines:

1. Proof: One of the key design issues of this book is how to introduce seemingly hard security proofs of cryptographic schemes to readers, particularly beginners and self-learners, in an intuitively easy and detailed method so that they could completely understand them by just following the book. Readers are first recommended to grasp the big picture of security proofs by taking a look at Chapter 2 and revisit this chapter whenever they study a specific security proof techniques. Particularly, they are encouraged to walk through the proofs in each chapter of Part 1 in sequence, which comprises the fundamentals of cryptography. Readers will get many benefits by referring to intuitions or outlines, if any, underlying a specific proof before going deeper into the proof itself. When they go deeper into a specific proof, they can easily understand it by just following the detailed step-by-step explanations of the proof, unique feature quite different from the other cryptography textbooks. If readers fully understand the key proof techniques in Parts 1 and 2, they can easily understand more complex proof techniques.

2. Implementation: Most of the implementations in this book are based on the MIRACL library with detailed guidance on setting up the compilation. The readers can first explore the implementation of ECDSA and Paillier, which are fundamental cryptography. Next, readers may implement more advanced cryptographic schemes including IBE, BE, CP-ABE, and PE. The implementation of RSA involves parallel programming using GPU, which can be explored at the later stage. The readers can explore the implementation of lattice-based and code-based cryptography, wherein various optimization techniques are presented. Finally, the readers can also explore the implementation of AES and SSL. All implementation source code can be accessible at https://ai-security.github.io.

Comments and Errata We would appreciate it if you email any comments or errata to sohwang at gachon dot ac dot kr. A list of errata will be maintained at https://ai-security.github.io.