석사학위논문 양자 내성 서명을 이용한 탈중앙화 공개키 기반 구조의 설계 및 분석 2018 안형철 한국과학기술원 전산학부 (정보보호대학원)

석사학위논문 Master s Thesis 양자내성서명을이용한탈중앙화공개키기반구조의설계및분석 Design and Analysis of Decentralized Public Key Infrastructure with Quantum-resistant Signatures 2018 안형철 ( 安亨哲 An, Hyeongcheol) 한국과학기술원 Korea Advanced Institute of Science and Technology

석사학위논문 양자 내성 서명을 이용한 탈중앙화 공개키 기반 구조의 설계 및 분석 2018 안형철 한국과학기술원 전산학부 (정보보호대학원)

Design and Analysis of Decentralized Public Key Infrastructure with Quantum-resistant Signatures Hyeongcheol An Advisor: Kwangjo Kim A dissertation submitted to the faculty of Korea Advanced Institute of Science and Technology in partial fulfillment of the requirements for the degree of Master of Science in Computer Science (Information Security) Daejeon, Korea June 12, 2018 Approved by Kwangjo Kim Professor of Computer Science The study was conducted in accordance with Code of Research Ethics 1. 1 Declaration of Ethical Conduct in Research: I, as a graduate student of Korea Advanced Institute of Science and Technology, hereby declare that I have not committed any act that may damage the credibility of my research. This includes, but is not limited to, falsification, thesis written by someone else, distortion of research findings, and plagiarism. I confirm that my thesis contains honest conclusions based on my own careful research under the guidance of my advisor.

MIS 20164355 안형철. 양자 내성 서명을 이용한 탈중앙화 공개키 기반 구조의 설계 및 분석. 전산학부 (정보보호대학원). 2018년. 50+iv 쪽. 지도교수: 김광조. (영문 논문) Hyeongcheol An. Design and Analysis of Decentralized Public Key Infrastructure with Quantum-resistant Signatures. School of Computing (Graduate School of Information Security). 2018. 50+iv pages. Advisor: Kwangjo Kim. (Text in English) 초록 블록체인은 2008년 비트코인(Bitcoin)에서 처음으로 제안되었으며, 분산형 데이터베이스 기술이다. 현재 키 관리 시스템 중 하나인 공개키 기반 구조(Public Key Infrastructure, PKI) 기술은 중앙집중형 구조로 single point failure의 가능성이 존재한다. 또한 대표적인 암호화폐인 비트코인과 이더리움에서 사용되는 전자서명 알고리즘인 ECDSA는 Shor 알고리즘에 따라 양자 컴퓨터 공격에 취약하다는 문제점이 존재한다. 이에, 본 석사 논문에서는 양자 내성 암호 기술을 적용한 블록체인 기반 키 관리 시스템에 대하여 제안한다. 분산형 구조인 블록체인을 기반으로 설계하여 단일 지점 오류에 안전하다. 또한, 대표적인 양자 내성 암호인 래티 스 기반 전자서명인 GLP 전자서명을 사용하기 때문에 양자컴퓨터의 공격에도 안전하며, 장기간 안전성을 보장한다. 핵 심 낱 말 포스트 양자 암호, 블록체인, 공개키 기반 구조, 키 교환 프로토콜, 격자 문제 Abstract The blockchain technique was first proposed by Satoshi Nakamoto in 2008. It is used for a distributed database technology. Public Key Infrastructure(PKI) system, which is one of the key management systems, is a centralized system. There is a possibility of a single point of failure in the currently used centralized PKI system. Classical digital signature algorithm; ECDSA has used the well-known cryptocurrencies, such as Bitcoin and Ethereum. Using the Shor s algorithm, ECDSA can be broken by the quantum computing attack. In this thesis, we propose a blockchain-based key management system using quantum-resistant cryptography, since we use a GLP digital signature scheme, which is a latticebased mathematical problem. It is secure against the quantum adversary and ensures long-term safety. Besides, we design a decentralized blockchain structure, and it is secure for the single point of failure. Keywords Post-quantum Cryptography, Blockchain, Public Key Infrastructure, Key Exchange Protocol, lattice problem

Contents Contents..................................... i List of Tables.................................. iii List of Figures.................................. iv Chapter 1. Introduction 1 1.1 Overview of Post Quantum Cryptography............. 1 1.2 Motivation................................ 2 1.3 Organization.............................. 3 Chapter 2. Preliminaries 4 2.1 Definitions................................ 4 2.2 Notations................................ 5 2.3 Lattice-based Mathematical Hard Problems............ 5 2.4 Consensus Algorithm......................... 6 2.4.1 Hashcash............................ 7 2.4.2 Proof-of-Work......................... 7 2.4.3 Byzantine Fault Tolerance.................. 7 Chapter 3. Related Works 9 3.1 Lattice-based Cryptography..................... 9 3.1.1 Key Exchange Protocols................... 9 3.1.2 Public-key Encryption Schemes............... 15 3.1.3 Digital Signature Schemes.................. 15 3.2 Overview of Blockchain........................ 17 3.3 Public Key Infrastructure....................... 19 3.3.1 PKI Standards......................... 19 3.3.2 Blockchain-based PKI.................... 20 Chapter 4. QChain: Our Proposed Scheme 22 4.1 Overview of Scheme.......................... 22 4.2 Structure of QChain.......................... 22 4.2.1 QChain Scheme........................ 24 4.2.2 QChain with Key Exchange Protocol........... 30 4.2.3 Performance of Key Exchange Protocols......... 31 4.2.4 Merkle Hash Tree....................... 34 i

4.2.5 Modified GLP Signature................... 35 Chapter 5. Security Analysis 36 5.1 Security Requirements........................ 36 5.2 Generic Attack............................. 37 5.3 Feature Analysis............................ 38 5.3.1 Comparision with Related Work.............. 39 Chapter 6. Concluding Remarks 41 Bibliography 42 Acknowledgments in Korean 47 Curriculum Vitae in Korean 48 ii

List of Tables 2.1 Notations and Variables..................................... 5 2.2 Comparison with PoW and BFT consensus algorithm.................... 8 3.1 Algorithms of liboqs....................................... 10 4.1 Payload on Open Quantum Safe Protocol........................... 32 5.1 Comparison of QChain and X.509 v3.............................. 38 5.2 Comparison of QChain and Related Work........................... 40 iii

List of Figures 3.1 Simplified Blockchain of Bitcoin................................. 17 3.2 Simplified Single Block of Bitcoin................................ 18 3.3 Structure of X.509 v3 Certificate................................ 19 4.1 Full Structure of QChain.................................... 23 4.2 Extended Certificate for QChain................................ 24 4.3 Detailed Structure of QChain.................................. 29 4.4 Protocol of QChain and Users.................................. 30 4.5 QChain Protocol with Key Exchange Protocol........................ 31 4.6 Comparing Runtime of OQS Protocols............................. 32 4.7 Runtime of Lattice-based Protocol............................... 33 4.8 Runtime of Code-based and SIDH Protocols.......................... 34 4.9 Example of QChain Merkle Hash Tree............................. 34 iv

Chapter 1. Introduction 1.1 Overview of Post Quantum Cryptography IBM developed a quantum computer with 5-qubit in 2016 and a new quantum computer with 50- qubit in Nov. 2017. The research team of IBM has developed a quantum computer that allows the public to simulate a quantum computer through an IBM Q Experience [1]. Therefore, the emergence of the quantum computer is not theoretical but becomes practical. Researcher and engineers predict that within the next twenty or so years, sufficiently large quantum computers will be built to break public key cryptosystems. If universal quantum computers can be feasible, public key cryptosystems whose difficulties are based on the number theoretic problem will be broken in a polynomial time. Public key cryptosystems, such as Diffie-Hellman (DH) key exchange protocol and RSA, are based on the difficulty of Discrete Logarithm Problem (DLP), Elliptic Curve DLP (ECDLP), and Integer Factorization Problem (IFP). However, DLP and IFP can be solved within the polynomial time by Shor s algorithm [2] using the quantum computer. Symmetric key cryptosystems such as the Advanced Encryption Standards (AES) and Data Encryption Standard (DES) can be solved using Grover s algorithm [3]. Grover s algorithm can be used in the data search problem. In classical computers, the adversary can search in the database as O(2 n ) complexity. Using the quantum computer, the complexity of the data search problem reduces O( 2 n ). Therefore, we need a secure public key cryptosystem against the quantum adversary. Post Quantum Cryptography (PQC) plays an important roles in building a secure cryptosystem against both classical and quantum adversaries. PQC primitives are based on mathematical hard problems which are lattice-based, code-based, hash-based, multivariate-based, and supersingular isogeny elliptic curves. Lattice-based cryptography is used for the encryption scheme, signature, and key exchange protocol. The National Institute of Standards and Technology (NIST) contested a public PQC cryptographic algorithm project until November 30, 2017, to select a secure cryptographic algorithm against the quantum adversary [4]. 1

1.2 Motivation A public-key cryptosystem needs Public Key Infrastructure (PKI), which guarantees the integrity of all user s public keys by binding them with its owner. The currently used PKI system is X.509 v3 [5] as recommended by the international standards. However, the X.509 PKI system has disadvantages such as centralization, single point failure, and fully trusted Certificate Authority (CA). CA is a trusted third party whose signature on the certificate guarantees the authenticity of the public key bound to each entity. If CA is not online called single point failure, the client cannot store or revoke their public keys. Therefore, the currently used centralized PKI system has problems with availability, due to the centralized CA. Due to the centralized CA, we fully trust CA server. Thus, we need decentralized PKI system to solve disadvantages of the centralized PKI system. Currently, Web of Trust (WoT) [6] approach is achieved decentralized public key infrastructure called PGP [7] using the trustworthy users. However, PGP makes that it is difficult for new or remote users to join the network since existing member of WoT must meet with the new user in person to have his identity verified and public key signed for the first time. It is difficult to revoke the public key since member must push the revocation list. Therefore, there is a disadvantage that the public key cannot be canceled immediately. The most famous cryptocurrency, Bitcoin [8] is the first decentralized virtual-currency. Bitcoin uses blockchain, which is a transaction database (or distributed ledger) shared by all peer nodes. With the transaction of the blockchain, anyone can find each block of information in the transaction history. A peer-to-peer (P2P), that is one of a decentralized networks, is a distributed system between peers. Each peer has equally the same privilege in their network. P2P does not have the concept of client or server. Therefore, each peer node operates both client and server on their network at the same time, since the blockchain technique is decentralized. We focus on the lattice-based cryptography that is based on the mathematical hard problem such as Ring Learning with Errors (Ring-LWE) problem. Lattice-based cryptography can be used not only for encryption scheme but also for the key exchange protocol and signature. We use the GLP [9] signature scheme that is based on the ring-lwe problem. GLP signature scheme is a simple and efficient quantumresistant signature algorithm. 2

In this thesis, we propose QChain, which is a quantum-resistant decentralized PKI system. To construct QChain, we combine blockchain and lattice-based cryptography which is one of PQC primitive. QChain is a practical method for managing public key encryption. To construct a quantum secure PKI, we use the lattice-based GLP signature scheme. We also compare the currently used X.509 v3 PKI system and our QChain from the point of connection, non-repudiation, revocation, scalability, trust model, and security level. 1.3 Organization The rest of this thesis is organized as follows: Chapter 2 describes notations and definitions as preliminaries. The related work which consists of lattice-based cryptography, the blockchain, and public key infrastructure is described in Chapter 3. In Chapter 4, we describe our proposed scheme. The security requirement, generic attack, and feature analysis are presented in Chapter 5. Finally, the future work and concluding remarks are discussed in Chapter 6, respectively. 3

Chapter 2. Preliminaries In this chapter, we state the notations, definitions, and lattice-based mathematical hard problems used in this thesis. After that, consensus algorithm such as proof-of-work and Byzantine fault tolerance is described briefly. 2.1 Definitions Bellare and Rogaway defined the public key encryption scheme [10]. We briefly restate the definitions as below: Definition 2.1.1. (Public Key Encryption Scheme). A public key encryption scheme is a tuple of Probabilistic Polynomial-Time (PPT) algorithms (Gen, Enc, Dec) satisfying the following: The key generation algorithm Gen() takes input a security parameter 1 λ and outputs a pair of keys (pk, privk). These are called the public key and the private key, respectively. We assume that pk and privk each have length at least λ, and that λ can be determined from pk and privk. The encryption algorithm Enc() takes as input a public key pk and a message m. It outputs a ciphertext c, and we write this as c Enc pk (m). The decryption algorithm Dec() takes as input a private key privk and a ciphertext c. It outputs a message m. We write this as m = Dec privk (m). We require that for every λ, every (pk, privk) output by Gen(1 λ ), and every message m, it holds that Dec privk (Enc pk (m)) = m Bellare and Rogaway also defined the digital signature scheme [10]. We briefly restate the definitions as below: Definition 2.1.2. (Digital Signature Scheme). A digital signature scheme is a tuple of Probabilistic Polynomial-Time (PPT) algorithms (Gen, Sign, Ver) satisfying the following: The key generation algorithm Gen() takes input a security parameter 1 λ and outputs a pair of keys (pk, privk). These are called the public key and the private key, respectively. We assume that pk and privk each have length at least λ, and that λ can be determined from pk and privk. The signing algorithm Sign() takes as input a private key privk and a message m. It outputs a signature σ, and we write this as σ Sign privk (m). The deterministic verification algorithm Ver() takes as input a public key pk, a message m, and a signature σ. It outputs a bit b, with b = 1 meaning VALID and b = 0 meaning INVALID. We write this as b := Ver pk (m, σ). 4

that We require that for every λ, every (pk, privk) output by Gen(1 λ ), and every message m, it holds Ver pk (m, Sign privk (m)) = 1 2.2 Notations Following notations are used in this thesis. Table 2.1 describes the notations. Table 2.1: Notations and Variables Variables Description privk private key sk secret key pk public key m plaintext c ciphertext e Gaussian error 1 λ security parameter bitwise exclusive-or operator concatenation operator χ σ σ H() Sign() V erif y() NTT() NTT 1 () Gaussian distribution with standard deviation σ standard deviation cryptographic hash function cryptographic digital signature sign function cryptographic digital signature verify function number theoretic transformation inverse number theoretic transformation 2.3 Lattice-based Mathematical Hard Problems LWE problem is introduced by Regev [11] in 2009. LWE is a quantum-resistant mathematical hard problem against the quantum adversary. Definition 2.3.1. (LWE Distribution). LWE distribution A s,χ Z n q Z n q, for a secret vector s Z n q and choose uniformly random a Z n q, and choosing e χ. and outputting; (a, b = s, a + e mod q) Error distribution χ over Z is usually used for Gaussian distribution or binomial distribution. LWE problem has two kinds of version such as search and decision. In cryptography, we use decision version 5

LWE problem. Decision LWE problem is given m independent samples (a i, b i ) Z n q Z n q. A s,χ for a uniformly random s Z n q or uniform distribution, distinguish which chooses the sample. Ring-LWE problem is introduced by Lyubashevsky et al. [12] in 2010. Ring-LWE is also a quantumresistant mathematical hard problem against the quantum adversary. Definition 2.3.2. (Ring-LWE Distribution). For a ring R of degree n over Z, and defining quotient ring R q = R/qR. Ring-LWE distribution A s,χ R q R q, secret vector s R q and choose uniformly random a R q, and choosing e χ. and outputting; (a, b = s a + e mod q) Error distribution χ over Z is usually used for Gaussian distribution or binomial distribution. The ring-lwe problem has two kinds of version such as search and decision. In cryptography, we use decision version ring-lwe problem. Decision ring-lwe problem is given m independent samples (a i, b i ) R q R q. s A s,χ for a uniformly random R q or uniform distribution, distinguish which chooses the sample. Module-LWE problem is introduced by Langlois et al. [13] in 2015. Module-LWE is also a quantumresistant mathematical hard problem against the quantum adversary. Definition 2.3.3. (Module-LWE Distribution). For a ring R of degree n over Z, and defining quotient ring R q = R/qR. Error distribution χ over Z is usually used for Gaussian distribution or binomial distribution. Module-LWE distribution A m,k,η R m k q R m q, secret vector s βη k and choose uniformly random a i R k q, and choosing e i β η. and outputting; (a, b i = a T i s + e i mod q) The module-lwe problem has two kinds of version such as search and decision. In cryptography, we use decision version module-lwe problem. Decision module-lwe problem is given m independent samples (a i, b i ) R k q R q. s βη k for a uniformly random R q or uniform distribution, distinguish which chooses the sample. 2.4 Consensus Algorithm In this section, we describe the consensus algorithm, which uses blockchain, such as Proof-of-Work (PoW) and Byzantine Fault Tolerance (BFT). Consensus algorithm decides whose block to add into blockchain. 6

2.4.1 Hashcash PoW and PoS algorithm is based on hash chain. Lamport suggested a method of user authentication method called hash chain [14] using a hash function. Then, Back suggested the hashcash [15] to prevent denial of service (DoS) attack in 2002. However, consensus algorithms such as PoW and PoS are based on hashcash method. Definition 2.4.1. (Hashcash). To demonstrate work on x, find y such that H(x, y) < z where, H(): hash function, y: nonce, and z: target hash value. If target hash value z is small, the prover needs more computing power to find nonce y. Therefore, we can modify the difficulty level by changing target hash value z. 2.4.2 Proof-of-Work A proof of work is a piece of data which is difficult time or power-consuming to produce but easy for others to verify and which satisfies specific requirements. For well-known cryptocurrency Bitcoin, they use the PoW method based on the hashcash problem. Definition 2.4.2. (Bitcoin Proof-of-Work). Find nonce n such that H( n H prev () Blockdata ) < z where, H(): SHA-256 hash function, n: nonce, and z: target hash value. In PoW of Bitcoin, the difficulty level is adjusted once every two weeks. The meaning of the adjusting difficulty level is to change the value of the target hash value mentioned in Definition 2.4.2. The Bitcoin difficulty adjustment equation is as follows: Diff new = Diff old 20160 t where, Diff new : new difficulty level of Bitcoin, Diff old : previous difficulty level of Bitcoin, and t: total mining time of 2,016 blocks (min). 2.4.3 Byzantine Fault Tolerance Lamport et al. introduced the Byzantine Generals Problem(BGP) [16] in 1982. BGP assumes a situation where the generals of each unit communicate with each other through a messenger and plan 7

an attack together while the various units of the Byzantine army are trying to attack the enemy city. In this situation, some of the generals may have mixed traitors. At that time, despite the existence of the traitor, how many generals must be for the commanders to plan the same attack. Byzantine Fault Tolerance (BFT) algorithm is based on the BGP and used for the fault-tolerant computing system. The general BFT algorithm has five-phase, which consists of the request, pre-prepare, prepare, commit, and reply. The BFT consensus algorithm is a method by which a leader is elected, that leader creates a block, propagates it to the verifier, and the verifiers vote. The most important feature of BFT is that it requires 2/3 or more consent among all voters to generate the block. Table 2.2 compare PoW and BFT consensus algorithm. PoW can be applied in the public blockchain, and BFT can be applied in the private or consortium blockchain. BFT consensus algorithm has the advantage that there is no waste of energy and it is possible to agree immediately by voting through the stake. Therefore, power consumption is low, and a leader must exist. However, as compared with PoW, it is limited in scalability and has a high latency because it has to propagate block status immediately to all blocks. Table 2.2: Comparison with PoW and BFT consensus algorithm Consensus Algorithm PoW BFT Operating member Anyone Specific operator Scalability Unlimited limited Performance(transaction) low high Performance(latency) high low Power Consumption high low 8

Chapter 3. Related Works In this chapter, we introduce the related works of lattice-based cryptography which is one of the most popular PQC primitives. Then, we briefly describe the overview of the blockchain. Finally, public key infrastructure standards and previous approach of blockchain-based PKI are presented. 3.1 Lattice-based Cryptography In this section, the well-known lattice-based mathematical hard problem such as Learning with Errors (LWE), Ring Learning with Errors (Ring-LWE), and Module Learning with Errors (Module- LWE) problems will be described in brief. Lattice-based cryptography is one of the most popular PQC primitives. Therefore, lattice-based cryptography is secure against the quantum adversary. There are many kinds of lattice-based cryptographic primitives such as LWE, ring-lwe, module-lwe, Learning with Rounding (LWR), and so on. Lattice-based cryptography can be used not only for encryption scheme but also for key exchange protocol and digital signature scheme. We will describe LWE, ring-lwe, and module-lwe problems in brief. 3.1.1 Key Exchange Protocols We focus on lattice-based key exchange protocols. OQS project [17] is an open source and a consist of 9 PQC cryptography. The OQS project is based on three kinds of PQC primitives such as lattice-based, code-based, and supersingular isogeny elliptic curve. Key exchange protocols such as Frodo, BCNS, NewHope, MSrln, Kyber, and NTRU are based on lattice-based scheme. IQC and MSR SIDH are based on supersingular isogeny elliptic curve scheme. Besides, McBits is based on code-based scheme. Table 3.1 describes algorithms of liboqs. To merge with OpenSSL, they implement same header file form in OpenSSL. We will describe lattice-based key exchange protocol in detail. 9

Table 3.1: Algorithms of liboqs Primitive Protocol LWE Frodo BCNS Lattice-based Ring-LWE NewHope MSrln Module-LWE Kyber NTRU Supersingular Elliptic Curve SIDH IQC Reference MSR SIDH Code-based Error-correcting codes McBits NewHope Alkim et al. [18] proposed ring-lwe key exchange protocol called NewHope in 2016. Protocol 1 describes key exchange protocol of NewHope. To compute NewHope, we define HelpRec() and Rec() functions. Protocol 1: NewHope Alice Bob seed $ {0, 1} 256 a Parse(SHAKE-128(seed)) s, e, $ Ψ n 16 s, e, e $ Ψ n 16 v us (b,seed) (u,r) a Parse(SHAKE-128(seed)) u as + e v bs + e r $ HelpRec(v) ν Rec(v, r) ν Rec(v, r) µ SHA3-256(ν) µ SHA3-256(ν) Let CVP ˆD4 (x R 4 ) is that an integer vector z such that is a closest vector to x : x Bz V. The HelpRec(x; b) is defined as follows: ( 2 r ) HelpRec(x; b) = CVP ˆD4 q (x + bg) mod 2 r where b {0, 1} is uniformly chosen random bit. The Decode(x R 4 /Z 4 ) is that a bit k such that kg is a closest vector to x + Z 4 : x kg V + Z 4. 10

The Rec(x, r) is defined as follows: ( 1 Rec(x, r) := Decode q x q ) 2 r Br Parameters of NewHope are n = 1024 and q = 12289. They use binomial distribution in error sampling Ψ n 16. Frodo Bos et al. [19] proposed LWE key exchange protocol called Frodo in 2016. Protocol 2 describes key exchange protocol of Frodo. To compute Frodo, we define rec(), rounding, and cross-rounding functions. Let the number B of bits that from one coefficient in Z q be such that B < (log 2 q) 1. Let B = (log 2q) B. The rounding function 2 B is defined as follows: 2 B : v 2 B v mod 2 B The cross-rounding function 2 B is defined as follows: 2 B : v 2 B+1 v mod 2 Then, we can define rec() function as follows: rec(w, v 2 B) := v 2 B if v w < 2 B 2 Protocol 2: Frodo Alice Bob seed A $ U({0, 1} s ) A Gen(seed A ) S, E $ χ(z n n q ) B AS + E K rec(b S, C) seed A,B {0,1} s Z n n q B C Z m n q Z m n 2 A Gen(seed A ) S, E $ χ(z n n q ) B S B + E C V 2 B K V 2 B 11

There are four kinds of parameter sets in Frodo such as Challenge, Classical, Recommended, and Paranoid. In OQS library (liboqs) and this paper, we test recommended parameter set. Parameters of Frodo are n = 752, q = 2 15, B = 4. They use rounded Gaussian distribution in error sampling χ. BCNS Bos et al. [20] proposed ring-lwe key exchange protocol called BCNS in 2015. Protocol 3 describes key exchange protocol of BCNS. Protocol 3: BCNS Alice Bob s, e $ χ s, e $ χ b as + e R q b b as + e R q e $ χ v bs + e R q k A rec(2b s, c) {0, 1} n b,c v $ dbl(v) R 2q c v 2q,2 {0, 1} n k B v 2q,2 {0, 1} n To compute BCNS, we define dbl(), rec(), modular rounding, and cross-rounding functions. Let : R Z be the x = z for z Z and x [z 1/2, z + 1/2). The modular rounding function q,2 is defined as follows: 2 q,2 : Z Z, x x q,2 = q x mod 2 The cross-rounding function q,2 is defined as follows: 4 q,2 : Z Z, x q,2 = q x mod 2 Let dbl(): Z q Z 2q, x dbl(x) = 2x e, where e is sampled from { 1, 0, 1} with probabilities p 1 = p 1 = 1 4 and p 0 = 1 2. Define the sets I 0 = {, 1,, 2 q 1} and I 0 = { q 2,, 1}. Let E = [ q 4, q 4 ) the reconciliation function rec() function as follows: 12

0 if w I b + E mod 2q rec(w, b) = 1 otherwise Parameters of BCNS are n = 1024, q = 2 32 1, σ = 8/ 2π 3.192. They use discrete Gaussian distribution in error sampling χ. MSrln Longa et al. [21] proposed ring-lwe key exchange protocol called MSrln in 2016. They suggest modular reduction technique using Montgomery reduction. Number Theoretic Transform (NTT) is used in polynomial multiplication and addition operations. Key exchange protocol scheme is same as NewHope protocol. Also, they use same parameters from NewHope key exchange protocol. Kyber Bos et al. [22] proposed module-lwe key exchange protocol called Kyber in 2017. Protocol 4 describes key exchange protocol of Kyber. To compute Kyber, we define Compress() q and Decompress() q functions. Let x Z q and d < log 2(q). The Compress() q function is defined as follows: Protocol 4: Kyber Alice Bob ρ, σ {0, 1} 256 A Sam(ρ) Rq k k m {0, 1} 256 (s, e) Sam(σ) βη k βη k ( ˆK, r, d) G((t, ρ), m) t Compress q (As + e, d t ) m Dec(s, (u, v)) ( ˆK, r, d ) G(pk, m ) (t,ρ) c (u, v) Enc((ρ, t), m; r)) c (u, v, d) (u, v ) Enc((ρ, t), m ; r ) K H(c, K) (u, v, d ) = (u, v, d); K H( ˆK, c) (u, v, d ) (u, v, d); K H(z, c) Compress() q (x, d) = (2 d /q) x mod + 2 d 13

The Decompress() q is defined as follows: Decompress() q (x, d) = (q/2 d ) x The Enc(pk, m) function is defined as follows: Enc(pk, m) = (u, v) u = Compress q (A T r + e 1, d u ) q v = Compress q (t T r + e 2 + m, d v ) 2 where, t = Decompress q (t, d t ), (r, e 1, e 2 ) β k η β k η β η The Dec(privK, (u, v)) function is defined as follows: Dec(privK, (u, v)) = Compress q (v s T u, 1) where, u = Decompress q (v, d v ), v = Decompress q (u, d u ) Parameters of Kyber are n = 256, q = 7681, k = 3, η = 4, d u = 11, d v = 3, d t = 11. They use binomial distribution in error sampling βη k. H() and G() are cryptographic hash functions. There is three version of key exchange protocol such as unauthenticated, one-sided authenticated, and authenticated. Protocol 4 describes unauthenticated key exchange protocol using Kyber. 14

3.1.2 Public-key Encryption Schemes Lybashevsky et al. first proposed the ring-lwe public key encryption scheme in 2010. Ring-LWE encryption scheme describes in this subsection briefly. A public key is sampled by Gaussian distribution, and the cyclotomic ring R is defined as R = Z[X]/(X n + 1). A public key encryption scheme is a tuple of Probabilistic Polynomial-Time (PPT) algorithms (Gen, Enc, Dec) satisfying the following: The key generation algorithm Gen() takes input a security parameter 1 λ and outputs a pair of keys (pk, privk). These are called the public key and the private key, respectively. We assume that pk = (a, b s a) R q R q and privk R each have length at least λ, and that λ can be determined from pk and privk. The encryption algorithm Enc() takes as input a public key pk and a message m R 2. It outputs a encryption message c = (u a r, v b r +m q 2 ) R q R q, and we write this as c Enc pk (m). The decryption algorithm Dec() takes as input a private key privk and a ciphertext c. It outputs a message m = v s u. where, m q 2 m q 2 + b r s a r We write this as m = Dec privk (m). that We require that for every λ, every (pk, privk) output by Gen(1 λ ), and every message m, it holds Dec privk (Enc pk (m)) = m 3.1.3 Digital Signature Schemes Akleylek et al. proposed the ring-lwe based signature scheme called Ring-TESLA [23]. Private key consist of a tuple of three polynomials (s, e 1, e 2 ) $ R q, e 1 and e 2 with small coefficients. Centered discrete Gaussian distribution D σ is used for sampling errors. Public key is a tuple of (b 1, b 2 ). Polynomial $ a 1, a 2 Rq, and computes b 1 = a 1 s+e 1 mod q and b 2 = a 2 s+e 2 mod q. To sign the message m, signing algorithm samples y $ R q with coefficient in [ B, B]. Then, computes c = H( v 1 d,q, v 2 d,q, m) and polynomial z = y + sc. Signature value is a tuple of (z, c ). To verify signature (z, c ) with message m, verification algorithm computes H( a 1 z b 1 c d,q, a 2 z b 2 c d,q, m). 15

Güneysu et al. [9, 24] published the GLP signature scheme based on ring-lwe problem and implements embedded hardware systems. Polynomial ring defines R pn = Z q [X]/(X n + 1) and R pn k defines subset of the ring R pn. R pn k consists of all polynomials with coefficients in the range [ k, k]. To sign message µ, it needs cryptographic hash function H with range D n 32. For n 512 consists of all polynomials of degree n 1 that have all zero coefficients except for at most 32 coefficient that is ±1. First, we need to read 5-bit (r 1 r 2 r 3 r 4 r 5 ) at a time. If r 1 is 0, put 1 in position r 2 r 3 r 4 r 5. Otherwise, put 1 in position r 2 r 3 r 4 r 5. Then, we convert the 512-bit string into a polynomial of degree at least 512 as follows: i th coefficient of the polynomial the i th -bit of the bit-string. If the polynomial is of degree 512, then all of its higher-order terms will be 0. Algorithm 1 describe GLP signature scheme. Ducas et al. [25] proposed BLISS signature scheme, which is the lattice-based signature with bimodal Gaussian distribution in 2013. Algorithm 1: GLP Signature Signing Key : s 1, s 2 $ R p n 1 Verification Key: a $ R pn, t as 1 + s 2 Hash Function : H : {0, 1} D n 32 1 Sign(µ, a, s 1, s 2 ) 2 begin 3 y 1, y 2 $ R p n k ; 4 c H(ay 1 + y 2, µ); 5 z 1 s 1 c + y 1 ; 6 z 2 s 2 c + y 2 ; 7 if z 1 / R pn k 32 or z 2 / R pn k 32 then 8 go to line 3; 9 else 10 return (z 1, z 2, c); 11 end 12 end 13 Verify(µ, z 1, z 2, c, a, t) 14 begin 15 if z 1, z 2 R pn k 32 then 16 c H(az 1 + z 2 tc, µ); 17 return reject; 18 else 19 return success; 20 end 21 end 16

3.2 Overview of Blockchain Blockchain was introduced to the Bitcoin cryptocurrency system. Bitcoin is first decentralized crypto and virtual currency and designed as a P2P network by Nakamoto in 2008. It operates in a P2P environment and adopts Proof of Work (PoW) agreement algorithm. All users in the blockchain network can create a transfer transaction with public key cryptography. A user called miner can take advantage of Proof-of-Work (PoW) operations by generating blocks with multiple valid transactions. The generated blocks are broadcast to the entire network and registered in the chain. After proposed the Bitcoin, many other cryptocurrencies such as Ethereum [26], Ripple [27], and IOTA [28] has proposed by cryptocurrency research groups. IBM is also proposed for the Hyperledger Fabric [29, 30], which is based on permissioned blockchain platform. Figure 3.1 shows the simplified version of Bitcoin blockchain. Figure 3.1: Simplified Blockchain of Bitcoin Every block s header has hash value of previous block header. Using the transaction of each block, we can make Merkle hash tree. The first block called genesis block is defined as hardcoded into the application to utilize blockchain. Genesis block consists of a timestamp, nonce, version information, and Merkle tree hash value. After generate genesis block, block 1 generates using previous genesis block hash value. Therefore, blockchain is designed as a decentralized managing technique of Bitcoin for issuing and transferring cryptocurrency. This technique can support the public ledger of all Bitcoin or other cryptocurrency transactions that have ever been executed, without any control of a Trusted Third Party (TTP). The advantage of Blockchain is that the public ledger cannot be modified or deleted after all user nodes have approved the data. Thus, blockchain is fully distributed and decentralized technique 17

system. The blockchain is well-known for data integrity and security. Blockchain technology can also be applied to other types of usage. It can, for example, create an environment for digital contracts and P2P data sharing in a cloud service. Blockchain technique can be used for other services and applications such as smart contract, medical industry, and also PKI system. Figure 3.2 shows the simplified single block of Bitcoin. Bitcoin header contains the following: Figure 3.2: Simplified Single Block of Bitcoin - Version: The block version number indicates which set of block validation rules to follow. - Previos Block Hash: A SHA256() hash in internal byte order of the previous block s header. This ensures no previous block can be changed without also changing this block s header. - Merkle Root: The Merkle root is derived from the hashes of all transactions included in this block, ensuring that none of those transactions can be modified without modifying the header. - Bits: An encoded version of the target threshold this block s header hash must be less than or equal to the previous target value. - Nonce: An arbitrary number of miners change to modify the header hash in order to produce a hash less than or equal to the target threshold. 18

3.3 Public Key Infrastructure In this section, we present the X.509 PKI standards, briefly. Then, previous work of blockchain-based PKI system is described. 3.3.1 PKI Standards A certificate is a digital document that contains public key and metadata. Legal CA can issue the valid certificates. X.509 is defined by the International Telecommunications Union s Standardization sector [5]. Figure 3.3 shows the structure of X.509 v3 certificate. Certificates contain the following fields: Figure 3.3: Structure of X.509 v3 Certificate - Public Key: This field consists of the public key algorithm and subject public key. It contains the specific public key algorithm and public key value for each user. - Version Number: X.509 standards has three kinds of version. Version 1 is default format, and if the Initiator Unique Identifier or Subject Unique Identifier is present, that must be used version 2. If more extension of certificates, the version must be used 3. - Subject Name: The name of the user to whom certificate refers. - Issuer: The name of CA that issued and signed the certificate. 19

- Validity Period: Valid date of certificate consist of begin and end date. - Signature: This field includes signature algorithm and certificate signature. It covers all other field value and signs the certificate. 3.3.2 Blockchain-based PKI Current PKI system is based on the centralized database. However, there is the vulnerability of single point failure. Since blockchain aims to provide a decentralized and unmodifiable ledger of information, it has qualities considered highly suitable for the storage and management of public keys. Emercoin(EMC) [31] is cryptocurrency, which is used for blockchain-based PKI system. EMCSSH integrates between the OpenSSH and EMC blockchain, providing decentralized PKI. EMC blockchain is based on both Proof-of-Work and Proof-of-Stake consensus protocol and forked from Peercoin. EMC uses the SHA-256 hash function, and it is not secure against the quantum adversaries by Grover s algorithm [3]. Lewison et al. propose the blockchain-based PKI system [33] in 2016. This research describes the concept of a blockchain-based PKI and shows the advantage of their system. However, they did not consider the quantum adversary and consensus protocol. Matsumoto et al. suggest the Ethereum-based PKI system called IKP [34]. IKP s decentralized nature and smart contract system allow open participation offer incentives for vigilance over CAs, and enable financial resourse against misbehavior. However, there are some security issues for Ethereum platform. Compared to the Lewison work, IKP uses the quantum-resistant hash function called Ethash [26] based on Keccak [35]. In addition, IKP uses the quantum-resistant hash function called Ethash [26]. Ethereum is based on ECDSA signature algorithm, which is not secure against the quantum adversaries. Therefore, IKP does not guarantee the long-term security. Yakubov et al. propose the blockchain-based PKI management framework [36] in 2018. They design a blockchain-based PKI, which modifies the X.509 certificates. X.509 v3 certificate standard consists of extension fields, which are reserved for extra information. They modify X.509 v3 certificate and design hybrid X.509 certificate, which consists of blockchain name, CA key and subject key identifier, and hashing algorithm in the extension field. This work is based on smart contract in Ethereum. Certcoin [37] is the public and decentralized PKI system using blockchain technique and based on 20

Namecoin [38]. In revocation phase, they did not use Certificate Revocation List (CRL). The weak point of this approach is that Certcoin uses only timestamp (lifetime) in each public key. They consider that Certcoin uses RSA accumulators, which is insecure against the quantum adversaries. However, Certcoin benefits a fault tolerance and redundancy. 21

Chapter 4. QChain: Our Proposed Scheme We have described the lattice-based cryptography, blockchain, and public key infrastructure. In this chapter, we design the quantum-resistant PKI scheme called QChain. Specifically, we propose our construction and structure of the QChain, which consist of key exchange protocol, Merkle hash tree, and modified GLP signature scheme. 4.1 Overview of Scheme Our proposed quantum-resistant PKI scheme is based on the ring-lwe problem. In this section, we describe the full structure of QChain in detail. We construct QChain, which is quantum-resistant PKI using blockchain. In following sections, we describe the structure of scheme, which contains Merkle hash tree, modified GLP signature scheme, and key exchange protocol. We also propose a QChain with key exchange protocol that can increase the efficiency in a communication process. QChain uses the extension field of X.509 v3 certificate. Therefore, there is an advantage that it can be compatible with existing X.509 certificate standards. QChain assumes a permissioned blockchain. Therefore, consensus protocol uses BFT instead of PoW or PoS. 4.2 Structure of QChain Our scheme is designed to prevent quantum computing attacks. Figure 4.1 shows the full structure of QChain. We use ring-lwe encryption scheme, which is quantum-resistant primitive in QChain. More precisely, the public key encryption scheme is based on ring-lwe by Lyubashevsky et al. [12] which is secure against the quantum computing attacks. Figure 4.2 shows the extended certificate for QChain. QChain certificate contains the following fields: - Public Key: This field consists of the public key algorithm and subject public key. It contains the specific public key algorithm and public key value for each user. 22

Figure 4.1: Full Structure of QChain - Version Number: X.509 standards has three kinds of version. Version 1 is default format, and if the Initiator Unique Identifier or Subject Unique Identifier is present, that must use version 2. For more extension of certificates, the version must be used 3. - Subject Name: The name of the user to whom certificate refers. - Issuer: The name of CA that issued and signed the certificate. - Validity Period: Valid date of certificate consist of begin and end date. - Signature: This field includes signature algorithm and certificate signature. It covers all other field values and signs the certificate. - CRL Distribution Point: This field includes a list of which establishes a CRL distribution points. Each distribution point contains a name and optionally reasons for revocation and the CRL issuer name, specifically, block leader. - Asserted Data: This field consists of the previous hash value and Merkle root. Previous hash value is based on the previous block. If the leader is a malicious node, the certificate is abolished and a new leader is elected. Thus, it prevents malicious node of the leader. The leader has a CRL, and the user confirms revocation of the 23

public key in the leader s CRL. The previous leader transfers the CRL and its hash value to the next leader when the leader changes. Figure 4.2: Extended Certificate for QChain 4.2.1 QChain Scheme The polynomial ring defines R q = Z q [X]/(X n + 1). The error distribution χ σ uses a discrete Gaussian distribution with standard deviation σ. For efficient encryption time, we use Number Theoretic Transformation (NTT) [39] operations. The NTT is commonly used in the implementation of latticebased cryptography. NTT operation denotes ẑ = NTT(z). Cryptographic nonce and random number are randomly selected nonce $ {0, 1} n and rand $ {0, 1} n. We denote the hash function and signature algorithm H() and Sign(), respectively. The public and private key denote pk and privk, respectively. Equation 4.2.1 defines the error-reconciliation function. In Section 4.2.5, we will introduce the modified GLP digital signature scheme. For a polynomial g = Σ 1023 i=0 g ix i R q, we define 24

1023 NTT(g) = ĝ = ĝ i X i, with i=0 1023 ĝ i = γ j g j ω ij where, ω = 49, γ = ω = 7. The function NTT 1 defines the inverse of NTT function. j=0 1023 NTT 1 (ĝ) = g = ĝ i X i, with i=0 1023 g i = n 1 γ i ĝ j ω ij where, n 1 mod q = 12277, γ 1 mod q = 8778, ω 1 mod q = 1254. The QChain scheme is described as follows: j=0 QChain.Setup(1 λ ): Choose security parameter λ and output a parameter n, q, and σ = 16/2 2.828 [40]. QChain.KeyGen(n, σ): Polynomial r 1 and r 2 sampled from the Gaussian distribution use NTT operation in polynomial multiplication and addition. r 1,i, r 2,i χ σ ; y 1,i, y 2,i $ R k q ; a i $ Rq ; â i NTT(a i ); ˆr 1,i NTT(r 1,i ); ˆr 2,i NTT(r 2,i ); ŷ 1,i NTT(y 1,i ); ŷ 2,i NTT(y 2,i ); ˆp i ˆr 1,i â i ˆr 2,i ; ˆt i â i ˆr 1,i + ˆr 2,i ; The public key is (â i, ˆp i, ˆt i ) pk i and the private key is (ˆr 1,i, ˆr 2,i, ŷ 1,i, ŷ 2,i ) privk i for user i. QChain.GenesisBlock.Setup(): The genesis block is the first block of QChain. We also call it block 0, which is hardcoded into the software of our system. The genesis block does not have previous 25

hash value. Therefore, we use {0} n for previous hash value in genesis block. We fix i = 2 10 in genesis block. nonce $ {0, 1} n ; rand i $ {0, 1} n ; where, 0 i 2 10 timestamp current time; QChain.GenesisBlock.Merkle(): We construct Merkle hash tree after QChain.GenesisBlock.Setup() using random number rand i, timestamp, hash function H(), and the signature algorithm Sign(). In genesis block, we fix pk i = rand i, ID i = i, and Username i = i. Each pk i defines as follows: pk i Info. = rand i H(i) timestamp i Sign(rand i ) Using pk i Info., we construct Merkle hash tree as follows: H i 1 2,,j = H i 1 H i 1 2,,0 = H(pk iinfo.) if i = odd 2,,1 = H(pk iinfo.) if i = even Then, we compute the top hash value H root using each hash value of leaf nodes. QChain.GenesisBlock.Final(): We finally construct the genesis block in this final algorithm. To make a previous hash of block 1, QChain needs a hash value. Previous hash value computes as follows: H Block0 = H(({0}) n nonce timestamp H root ) QChain.User.Setup(pk i, H root ): In the user setup algorithm, it is similar to QChain.GenesisBlock.Setup() algorithm. The user setup algorithm runs as follows: 26

Previous hash H Block0 ; nonce $ {0, 1} n ; pk i User public key {0, 1} n ; where, 0 i l 2 10 timestamp i current time; QChain.User.Add(ID i, Username i, privk i, pk i ): After the genesis block has been made by the QChain.User.Setup() algorithm, we add information about the user s public keys as follows: H(ID i ), ID i User ID; H(Username i ), Username i Username; (ˆr 1,i, ˆr 2,i, ŷ 1,i, ŷ 2,i ) privk i ; y 1,i NTT 1 (ŷ 1,i ); y 2,i NTT 1 (ŷ 2,i ); (â i, ˆp i ) pk i ; a i NTT 1 (â i ); c i H(a i y 1,i + y 2,i, ID i ); ĉ i NTT(c) r 1,i NTT 1 (ˆr 1,i ); r 2,i NTT 1 (ˆr 2i ); Sign(ID i, a i, r 1,i, r 2,i ); Using ID i and Username i, we compute each hash and signature value. The output signature value is (z 1,i, z 2,i, ĉ i ). Then, we construct Merkle hash tree same as genesis block process. The maximum users of each block are 2 10. Because we restrict the maximum depth of Merkle hash tree due to complexity. We will explain the Merkle hash tree in Section 4.2.4. The Sign() algorithm is a modified GLP signature scheme. QChain.User.Verify(ID i, pk i, Sign(ID i )): To verify the public key pk i and Sign(ID i ) of the user, 27

using the verify algorithm V erif y(). The user verify algorithm runs as follows: â i, ˆt i pk i ; a i NTT 1 (â i ); t i NTT 1 (ˆt i ); z 1,i, z 2,i, ĉ i Sign(ID i ); c i NTT 1 (ĉ i ); V erify(id i, z 1,i, z 2,i, c i, a i, t i ); Using public parameters pk i and Sign(ID i ), we can easily verify the user. QChain.User.Enc(pk i, m): To encrypt a message m R 2, the encryption algorithm runs as follows: (â i, ˆp i, ˆt i ) pk i ; (a i, p i, t i ) (NTT 1 (â i ), NTT 1 (ˆp i ), NTT 1 (ˆt i )); e 1, e 2, e 3 χ σ ; ê 1 NTT(e 1 ); ê 2 NTT(e 2 ); q ˆm m ; 2 (ĉ 1, ĉ 2 ) (â i ê 1 + ê 2, ˆp i ê 1 + NTT(e 3 + ˆm)); Then, we can generate (ĉ 1, ĉ 2 ) and the ciphertext is c = (ĉ 1, ĉ 2 ) using a user public key pk i and message m. QChain.User.Dec(privK i, c): To decrypt message c = (ĉ 1, ĉ 2 ), decryption algorithm as follows: ˆr 2,i privk i ; (ĉ 1, ĉ 2 ) c; m NTT 1 (ĉ 1 ˆr 2 + ĉ 2 ); m Decode(m ); Decode() is an error reconciliation function. In QChain.Enc() function, we encode the message m. To decode the message m, we use Decode() function. The Decode() function defines as follows: Decode(m) := 2 q q m q/2 2 (4.1) 28

We design QChain scheme to contain ten algorithms. Figure 4.3 shows detail structure of each block of QChain. In the structure of QChain, each block consists of the previous hash, nonce, timestamp, a public key of the user, hash value of the block, and Merkle hash tree. The public key and private key of users are based on the ring-lwe key generation scheme. Users can communicate with the application data using the public key cryptosystem of the based on ring-lwe scheme. Figure 4.3: Detailed Structure of QChain Figure 4.4 shows the simplified protocol of QChain between two users. The first QChain operator initiates genesis block (block 0). The operator has five-steps algorithms. QChain.Setup() sets the parameter of QChain. QChain.KeyGen() makes a public and a private key of users. Then, QChain.Genesis Block.Setup(), QChain. GenesisBlock.Merkle(), and QChain. GenesisBlock.Final() algorithms to operate the genesis block. After generating genesis block, QChain makes next block called Block 1. To register the public key, users set QChain.User.Setup() algorithm and they can register the public key with algorithm QChain.User.Add(). They can also verify the public key with algorithm QChain.User.Verify(). Using this algorithm, users can challenge to QChain for verifying the anonymous user. QChain will answer if it 29

is an authenticated user or not. Finally, through algorithms QChain.Enc() and QChain.Dec(), users can communicate application data securely with each other. Figure 4.4: Protocol of QChain and Users 4.2.2 QChain with Key Exchange Protocol Figure 4.5 shows the simplified protocol of QChain between two users with key exchange protocol. Compared to Figure 4.4, server and client communicate in QChain.Enc() and QChain.Dec() algorithm can be replaced by a blockcipher. Therefore, it is possible to increase the efficiency over the previous protocol in the communication process of the application data. QChain.KE(ID i, KE()): To share the common secret key sk i,j, using the key exchange protocol KE(), which are the public parameter and key exchange protocol. Therefore, we can easily compute the common secret key sk i,j. In Section 3.1.1 describe the detailed lattice-based key exchange protocols. QChain.Enc(sk i,j, m): To encrypt a plaintext m, using the blockcipher, which is symmetric key encryption. Then, we can generate the ciphertext that is c = Enc ski,j (m) using common secret key sk i,j and plaintext m. QChain.Dec(sk i,j, c): To decrypt a ciphertext c, using the blockcipher, which is symmetric key encryption. Then, we can generate the plaintext that is c = Dec ski,j (c) using common secret key 30

Figure 4.5: QChain Protocol with Key Exchange Protocol sk i,j and ciphertext c. 4.2.3 Performance of Key Exchange Protocols In the previous section, we proposed a design that can increase the efficiency by adding the key exchange protocol to QChain. In this section, we show detail results of the quantum-resistant library called liboqs, in case of payload and runtime. We compare the experimental setup and performance of liboqs with tables and graphs. Experimental Setup The experimental environment is as follows: Intel(R) CPU i7-5500, RAM 16GB, and test on Ubuntu v16.04. The compiler also uses gcc v5.4.0. We download the reference liboqs source code in GitHub 1. Performance of liboqs Table 4.6 describes payload of OQS project. NTRU has smallest total payload as 2049-byte. Ring- LWE and SIDH key exchange protocols have a smaller payload than code-based protocol. The largest payload in the table is McBits, which is 311,877-byte. We also check payload of LWE scheme is larger than ring-lwe scheme. Because ring-lwe computes ring structure. Therefore, ring-lwe is efficient 1 https://github.com/open-quantum-safe/liboqs 31