Crypto Forum Research Group Rohit Khera Internet-Draft Pivotal Intended Category: Informational Expires April 24 2018 October 24, 2017 Post-Quantum Key Exchange From Learning With Errors Over Rings draft-khera-lpr-ring-lwe-kex-00 Abstract This note describes a key exchange method based on the ring-LWE (RLWE) assumption. It builds upon several results, including Regev's landmark quantum reduction from certain worst case lattice problems (approx. GapSVP and SIVP) to random instances of the search variant of a particular learning problem (LWE). It also builds on the follow on work of Lyubashevsky, Peikert and Regev on the average case hardness of the RLWE search variant for polynomially bounded numbers of RLWE samples, along with novel applications of automorphism groups in number fields for a RLWE search to decision reduction (thereby demonstrating pseudorandomness of RLWE in these number fields). Subsequently, these results were adopted for the construction of Diffie-Hellman like key exchange methods by Peikert, and then by Lindner and Peikert followed by Ding and then by Ding, Xie and Lin who proposed efficient variants of such protocols. Subsequent work by Peikert proposed another efficient variant, phrased as a key encapsulation method, incorporating a low bandwidth "reconciliation" technique allowing two parties to exactly agree on a uniformly distributed secret value from noisy RLWE instances. This was followed by a concrete instantiation with parameter sets by Bos, Costello, Naehrig, Stebila, followed by another instantiation by Alkim, Ducas, Poppelmann and Schwabe with the same ring polynomial but a smaller modulus and a different reconciliation method. Unlike most other public key cryptography based key exchange methods, it is believed that RLWE based key exchange would remain secure in the event that an adversary is able to build a quantum computer. This document is a product of the Crypto Forum Research Group (CFRG). Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, Khera, Rohit Expires April 24 2018 [Page 1] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts can be accessed at https://www.ietf.org/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at https://www.ietf.org/shadow.html Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on April 24th, 2018. Copyright Notice Copyright (c) 2017 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Also refer to the subsequent section entitled "Code Implementations and Licensing". Table of Contents 1. Introduction........................................3 2. Notation, Definitions and Operators.................4 2.1 Algebra and Number Theory 2.2 Set Notation 2.3 Random Variables and Distributions 2.4 Arithmetic 2.5 Miscellaneous 3. Error Distribution and Embeddings...................11 3.1 Sampling 4. Functions...........................................13 Khera, Rohit Expires April 24 2018 [Page 2] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 4.1 Modular Rounding Function 4.2 Cross Rounding Function 4.3 Randomized Doubling Function 4.4 Reconciliation Function. 4.5 Extending to the rings OK_q and OK_2q 4.5.1 Extended Modular Rounding Function 4.5.2 Extended Cross Rounding Function 4.5.3 Extended Reconciliation Function 4.5.4 Extended Randomized Doubling Function 5. Flow Diagram........................................16 6. Efficient Polynomial Operations.....................16 7. Protocol............................................17 7.1 Server 7.1.1 Ring Element 'a' 7.1.2 Server Secret Key and Error 7.1.3 Server Public Key 7.1.4 Server Key and Parameter Exchange 7.1.5 Client Key and Cross Rounding Vector Receipt 7.1.6 Server Reconciliation and Key Derivation 7.2 Client 7.2.1 Client Secret Key and Error 7.2.2 Server Key and Parameter Receipt 7.2.3 Client Public Key 7.2.4 Client Doubling and Cross Rounding 7.2.5 Client Key and Cross Rounding Vector Exchange 7.2.6 Client Modular Rounding and Key Derivation 8. TLS Extensions....................................20 8.1 Fundamental RLWE Suites 8.2 Fundamental RLWE Key Exchange Algorithms 8.2.1 RLWE_RSA 8.2.2 RLWE_ECDSA 8.3 Fundamental TLS Extensions for RLWE 8.3.1 Fundamental RLWE Parameters Extension 8.3.2 Client Hello Extension 8.3.3 Server Hello Extension 8.3.4 Server Certificate 8.3.5 Server Key Exchange 8.3.6 Certificate Request 8.3.7 Client Certificate 8.3.8 Client Key Exchange 8.3.9 Certificate Verify 8.4 Hybrid TLS Extensions for RLWE 9. Authenticity.....................................28 10. Code Implementations and Licensing...............28 11. IANA Considerations..............................29 12. Security Considerations..........................29 12.1 Security Parameters 12.2 Ring Element 'a' Khera, Rohit Expires April 24 2018 [Page 3] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 12.3 Side Channels 13. References.......................................31 13.1 Normative References 13.2 Informative References 14. Acknowledgements................................35 15. Author's Address................................35 1. Introduction Recent years have seen the development of key exchange protocols from problems on lattices (discrete additive subgroups in vector spaces). This note describes one such method based on the ring-LWE problem. We start by describing some of the main results connecting lattice problems with lattice based cryptosystems. Regev [Reg2005] demonstrated a quantum reduction from certain worst case lattice problems (approx. GapSVP and SIVP) to random instances of the search variant of a particular learning problem (LWE). This means that an oracle that returns the LWE secret vector from randomly selected LWE instances implies an efficient quantum algorithm for approximating lattice problems. Peikert demonstrated a classical reduction from approx. GapSVP to decision LWE, partially de- quantizing Regev's result [Pei2009a]. This reduction, however, does not extend to approx. SIVP and requires a modulus exponential in the lattice dimension. Lyubashevsky, Peikert and Regev [LPR2013a] used Regev's quantum reduction along with aspects and tools from algebraic number theory to provide a quantum reduction from approx. SVP on ideal lattices (in the worst case) to random instances of the search variant of RLWE. This was followed by a novel application of automorphisms groups of cyclotomic fields for a classical search to decision reduction, thereby proving the pseudo- randomness of RLWE for sets of samples polynomially bounded in the lattice dimension. In a companion publication [LPR2013b] Lyubashevsky, Peikert and Regev provided a toolkit of algorithms and techniques for applications. The following is a description of work around the construction of key exchange methods from the ring-LWE problem. Peikert in 2009 [Pei2009b] and Lidner and Peikert [LP2011] in 2011 proposed cryptosystems and key exchange methods from both standard and RLWE assumptions. Ding [DI2012] and Ding, Xie and Lin [DXL2012] proposed optimized variants of such methods based on so called "robust extractors" that allow two parties to recover the same value from two closely separated ring elements. This was followed work by Peikert [Pei2014] who presented a key encapsulation method incorporating a low bandwidth "reconciliation" technique, which once again, allowed two parties to exactly agree on a uniformly distributed secret value from noisy RLWE instances. Subsequently Khera, Rohit Expires April 24 2018 [Page 4] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 Bos, Costello, Naehrig, Stebila [BCNS2014] published a concrete instantiation with parameter sets, followed by another instantiation by Alkim, Ducas, Poppelmann and Schwabe [ADPS2015] with the same ring polynomial but a smaller modulus and a different error distribution. 2. Notation, Definitions and Operators 2.1 Algebra and Number Theory Q : The rational numbers. Z : The integers. Z/nZ : Integers modulo n. Also written as Z_n. R : The real numbers. C : The complex numbers. [K:F] : For a field K containing F, the degree of K/F as an extension of fields. Equivalently the dimension of K as a vector space over F. phi_m(x) : The m'th cyclotomic polynomial This note uses the value m = 2048 \zeta : An abstract root of phi_m(x). \zeta_m : An m'th root of unity. Q[X] : Polynomials with rational Khera, Rohit Expires April 24 2018 [Page 5] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 coefficients Z[X] : Polynomials with integer coefficients K = Q(\zeta) : A simple extension generated over the rationals by the algebraic number \zeta, the root of an irreducible polynomial over the rationals. If zeta is an abstract root of phi_m(x) as defined above, then Q(\zeta) is the cyclotomic field of m'th roots of unity and is \iso to the quotient Q[X]/. Power Basis : A basis for the field Q(\zeta) when taken as a vector space over Q, consisting of the elements {1, \zeta , \zeta^2 ,..., \zeta^(n-1)} where n = [Q(\zeta):Q] and \zeta is the root of an irreducible polynomial over Q. In the case of the cyclotomic Khera, Rohit Expires April 24 2018 [Page 6] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 field K, the power basis is also an integral basis for the ring of algebraic integers in K. OK : The ring of algebraic integers of the number field K. As mentioned, the power basis of K spans OK as a Z-module of rank n and is an integral basis for the full ring of algebraic integers in K. q : A large prime modulus such that q = 1 mod 2n where n = [Q(\zeta):Q]. This note uses the value q = (2^31) - 1. mod : The modular reduction operator OK_q = OK/qOK : The quotient of OK mod the ideal qOK. OK^V : A fractional ideal, the "trace product" dual of OK. F^n : An n-dimensional vector space over the field F. Alternatively, if F is a ring, the F-module of Khera, Rohit Expires April 24 2018 [Page 7] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 rank n. /x/^n in F^n : Denotes a vector in F^n. Written in component form as /x/^n = {x_1, x_2, ..., x_n}. X_ : Cartesian product, A X_ B denotes the Cartesian product of A and B. M_:OK -> C^n : Minkowski embedding, also called the canonical embedding, comprising injective homomorphisms from the ring OK to C^n where n = [Q(\zeta):Q]. In this context, for two positive integers d_1 and d_2 such that n = d_1 + 2*d_2, M_ is a map from OK to the space R^d1 X_ C^(2*d_2) iso to C^n. Coef-Embedding : Coefficient embedding. For an element a_ in the ring OK, a representation of a_ in a polynomial basis of Q(\zeta). 2.2 Set Notation {,} : Set brackets. {a,b,c}, for example, denotes the set consisting of the elements Khera, Rohit Expires April 24 2018 [Page 8] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 a,b and c. [,) : right-open interval. As an example, [a,b) for an integer x denotes the set of integers satisfying the inequalities a <= x < b. {0,1}^n : The set of n bit strings. \union : The union of sets. A \union B \union C, for example, denotes the union of sets A,B and C. \intersect : The intersection of sets. \in : Denotes set membership. 2.3 Random Variables and Distributions x <- P_X() : Denotes the sampling of x in the set X from the probability distribution P_X() over X. Normal_R(,s_) : The (centered) 1-D Gaussian distribution over the reals with parameter s_. d-Normal_Z_q(,s_) : A discretization of Normal_R(,s_) over the ring Z_q. Spherical_R^n(,s_) : The (centered) spherically Khera, Rohit Expires April 24 2018 [Page 9] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 symmetric n-dimensional Gaussian distribution with parameter s_ over the vector space R^n. d-Spherical_Z_q^n(,s_) : A discretization of Spherical(,s_)_R^n over the d-Spherical_OK_q(,s_) module (Z_q)^n. This leads to the related definition d-Spherical_OK_q(,s_) over the ring OK_q. An element w in OK_q can be written as a polynomial in powers of X such that w = w_0 + w_1*X + ... + w_(n-1)*X^(n-1) where n = [Q(\zeta):Q]. To sample an element from d-Spherical_OK_q(,s_), it suffices to independently sample the coefficients w_0, ..., w_(n-1) from d-Normal_Z_q(,s_). Sampling an element w \in OK_q Khera, Rohit Expires April 24 2018 [Page 10] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 according to this method is denoted as w <- d-Spherical_OK_q(,s_). d-Uniform_Z_q() : For x_ \in Z_q, the uniform distribution over Z_q. d-Uniform_Z_q^n() : The uniform distribution over the module d-Uniform_OK_q() (Z_q)^n. This leads to the related definition d-Uniform_OK_q() over the ring OK_q. An element w in OK_q can be written as a polynomial in powers of X such that w = w_0 + w_1*X + ... + w_(n-1)*X^(n-1) where n = [Q(\zeta):Q]. To sample an element from d-Uniform_OK_q(), it suffices to independently sample the coefficients w_0, ..., w_(n-1) from d-Uniform_Z_q(). Sampling an element Khera, Rohit Expires April 24 2018 [Page 11] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 w \in OK_q according to this method is denoted as w <- Uniform_OK_q(). 2.4 Arithmetic * : a * b denotes the product of a multiplied by b where a and b are field or ring elements. / : a / b denotes the quotient of a by b. + : a + b denotes the sum of a and b. - : a - b denotes the difference of a and b. 2.5 Miscellaneous floor(x) : Given a real number x, outputs the nearest integer less than or equal to x. nint(x) : Given a real number x, outputs floor(x + 1/2) with ties broken upward. 3. Error Distribution and Embeddings This section provides the rationale behind choice of the error distribution, starting with Regev's reduction from approx. GapSVP and SIVP to LWE [Reg2005], where the error is sampled from a Khera, Rohit Expires April 24 2018 [Page 12] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 discrete Gaussian. This is an approach that can be traced back to Micciancio and Regev's [MR2004] utilization of Gaussian measures to obtain tighter bounds on the approx. SVP to SIS reduction through Gaussian sampling of offsets to random lattice points. While the LWE error is a one dimensional Gaussian, RLWE requires that error polynomials are sampled from n-dimensional Gaussians over the Minkowski embedding of the ring OK. More precisely, the literature ([LPR2013a]) defines an error distribution over the space R^d1 X_ C^(2*d_2) (refer to the definition of the Minkowski embedding in section 2) as a distribution over the tensor product over Q of Q(\zeta) and the Reals (denoted K_R) . Further, in the full description of the RLWE distribution, the work exploits the fact that fractional ideals of Q(\zeta) canonically embed as lattices. The RLWE secret is then drawn from a distribution over the fractional ideal OK_V, defined as the dual of OK under a trace product. Finally, the full RLWE instance is defined as a tuple over (OK_q X_ K_R/qOK_V). Certain RLWE applications, on the other hand, sample errors and secret polynomials from distributions over the ring OK_q [BGV2011], [GHS2011]. In the context of power of 2 cyclotomics, this leads to a RLWE variant commonly known as polynomial LWE (PLWE Assumption - Hermite Normal Form (HNF), [BV2011]). In a similar vein, key exchange methods [Pei2014] employ the PLWE variant by describing the ring-LWE instance as a tuple over (OK_q X_ OK_q) where both the secret and the error are drawn from a distribution over the ring OK_q and this is the variant considered in this note. When considering general RLWE hardness for search, the reductions require a solution for any Gaussian error distribution. The decision problem requires that Gaussian parameters are chosen at random. Despite this fact, this note employs a discretized fixed spherical Gaussian. Hardness can be established with such a distribution if the adversary is constrained to have a bounded number of samples [LPR2013a]. In practice, constructions including the key exchange method specified here, comply with this constraint. 3.1 Sampling [BCNS2014] describe an adaptation of inverse transform sampling [Dev1986] of errors from a Gaussian. [ADPS2015] on the other hand sample errors from a centered binomial distribution partly owing to its implementation simplicity. The binomial distribution is a Khera, Rohit Expires April 24 2018 [Page 13] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 suitable alternative for practical applications, however, this note follows the [BCNS2014] implementation and specifies Gaussian error. Though the [BCNS2014] implementation uses the inversion method to transform uniform variates in [0,1] to Gaussian errors, this note does not specify a sampling method and leaves it as implementation choice. 4. Functions 4.1 Modular Rounding Function [Pei2014] For the modulus q, an integer p that divides q, and for for x in Z_q, define the modular rounding function modR_q_2(x) : Z_q -> Z_2 as modR_q_2(x) = nint((2/q) * x) mod 2 4.2 Cross Rounding Function [Pei2014] For a modulus q, and for x in Z_q, define the cross rounding function crossR_q_2(x) : Z_q -> Z_2 as crossR_q_2(x) = floor((4/q) * x) mod 2 4.3 Randomized Doubling Function [Pei2014] Sample e_ from the set {-1, 0, 1} such that Pr(0) = 1/2 Pr(-1) = 1/4 Pr(1) = 1/4 Where Pr(x) is the probability of event x. Define the function dbl(x) : Z_q -> Z_2q as dbl(x) = 2x - e_ 4.4 Reconciliation Function [Pei2014] Define the following sets: I_0 = {0,1,...,nint(q/2) -1 } I_1 = {-floor(q/2),...,-1} mod q Khera, Rohit Expires April 24 2018 [Page 14] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 E = [-q/4,q/4) \intersect Z For an element w_ in Z_2q and b \in {0,1}, define the function rec_2q(w_,b) : Z_2q X_ Z_2 -> Z_2 as { 0 if w_ \in I_b + E mod 2q rec_2q(w_,b) = { 1 otherwise 4.5 Extending to the rings OK_q and OK_2q 4.5.1 Extended Modular Rounding Function The modular rounding function, previously defined as modR_q_2(x) : Z_q -> Z_2 is extended to elements in OK_2q co-efficient wise in a polynomial basis of OK_2q. That is for an element w in OK_2q written as w = w_0 + w_1*X + ... + w_(n-1)*X^(n-1) where w_i \in Z_2q and n = [Q(\zeta):Q], the extended modular rounding function is defined as modR_OK_2q_2(w) = ( modR_2q_2(w_0), modR_2q_2(w_1), ... , modR_2q_2(w_(n-1)) ) : OK_2q -> {0,1}^n 4.5.2 Extended Cross Rounding Function The cross rounding function, previously defined as crossR_q_2 : Z_q -> Z_2 is extended to elements in OK_2q coefficient wise as crossR_OK_2q_2(w) = ( crossR_2q_2(w_0), crossR_2q_2(w_1), ... , crossR_2q_2(w_(n-1)) ) : OK_2q -> {0,1}^n For their arguments, both of these functions take an element in OK_2q and output an n-bit vector. 4.5.3 Extended Reconciliation Function The reconciliation function, previously defined as rec_2q(w_,b) : Z_2q X_ Z_2 -> Z_2 is also extended to elements in OK_2q co- Khera, Rohit Expires April 24 2018 [Page 15] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 efficient wise in a polynomial basis of OK_2q. For an n-bit vector b_vec containing coefficient wise cross rounding information for an element in OK_2q: b_vec = (b_0, b_1, ..., b_(n-1)), the extended reconciliation function is defined as rec_OK_2q(w,bvec) = ( rec_2q(w_0, b_0), rec_2q(w_1, b_1),..., \ rec_2q(w_(n-1), b_(n-1)) ) : (OK_2q X_ {0,1}^n) -> {0,1}^n For its arguments, this function takes an element w in OK_2q and the n-bit vector containing co-efficient wise cross rounding information for w and returns an n-bit vector. 4.5.4 Extended Randomized Doubling Function Finally, the randomized doubling function, previously defined as dbl(x) : Z_q -> Z_2q is also extended to elements in OK_q co- efficient wise in a polynomial basis of OK_q. For an element in OK_q defined as w = w_0 + w_1*X + ... + w_(n-1)*X^(n-1) where w_i \in Z_2q and n = [Q(\zeta):Q], the doubling function dbl_OK_q(w) is defined as dbl_OK_q(w) = dbl(w_0) + dbl(w_1)*X ... + \ dbl(w_(n-1))*X^(n-1) : OK_q -> OK_2q For its arguments, the extended doubling function takes an element in OK_q and returns an element in OK_2q. Khera, Rohit Expires April 24 2018 [Page 16] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 5. Flow Diagram Server Client ------ ------ a < d-Uniform_OK_q() s_1, e_1 <- d-Spherical_OK_q(,s_) s_2, e_2, e_3 <- d-Spherical_OK_q(,s_) b = a*s_1 + e_1 -------> a,b u = a*s_2 + e_2 v = b*s_2 + e_3 v_ = dbl(v) v* = crossR_OK_2q_2(v_) u,v* <-------- pms = rec_OK_2q(2*u*s_1,v*) ms = KDF(pms) pms = modR_OK_2q_2(v_) ms = KDF(pms) a,b, s_1, s_2, e_2, e_3, u and v are elements in OK_q, v_ is an element in OK_2q, v* and pms (the pre-master secret) are both 1024 bit vectors, ms is the master secret. KDF() is a key derivation function. In practice, it is expected that the key derivation method specified in TLS 1.2 section 8.1 [RFC5426] will be used (refer to subsequent section on TLS extensions). For an alternate approach to generation of the parameter 'a' [ADPS2015] refer the security section of this note. Figure 1: Flow Diagram 6. Efficient Polynomial Operations This note does not specify methods for efficient polynomial Khera, Rohit Expires April 24 2018 [Page 17] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 operations, this is a choice that is left to for implementations to consider.The Number Theoretic Transform (NTT) has been used as a technique for fast polynomial multiplication in rings of algebraic integers ([PG2012], [PG2013], [ADPS2015]), and is therefore particularly well suited for lattice based cryptography. 7. Protocol 7.1 Server 7.1.1 Ring Element 'a' Server generates the ring element a by sampling from the the uniform distribution over OK_q a <- d-Uniform_OK_q() This can be done by sampling each coefficient of a independently from the uniform distribution over Z_q 7.1.2 Server Secret Key and Error Server generates its ephemeral secret key s_1 and the error e_1 sampling the ring elements from the discrete spherical Gaussian distribution over OK_q with parameter s_. s_1 <- d-Spherical_OK_q(,s_) e_1 <- d-Spherical_OK_q(,s_) This can be done by sampling each coefficient of s_1 and e_1 independently from the discrete Gaussian distribution over Z_q centered at 0 with parameter s_. 7.1.3 Server Public Key Server computes its ephemeral public key b by multiplying the element a and its ephemeral secret key s_1 and then adding the error e_1 Khera, Rohit Expires April 24 2018 [Page 18] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 b = a*b + e_1 7.1.4 Server Key and Parameter Exchange Server returns the ring element a and the its ephemeral public key b to the client 7.1.5 Client Key and Cross Rounding Vector Receipt Server receives the client public key u along with cross rounding information v* from the client 7.1.5 Server Reconciliation and Key Derivation The server then computes h = 2*u*s_1 by multiplying the ephemeral client public key with its ephemeral secret key and doubling the result. The server then computes the premaster secret (pms) as: pms = rec_OK_2q(h,v*) An approved key derivation function can then be used for deriving the master secret key. In practice, its expected that the key derivation method specified in TLS 1.2 section 8.1 [RFC5426] will be used. 7.2 Client 7.2.1 Client Secret Key and Error The client generates its ephemeral secret key s_2 and the error terms e_2 and e_3 by sampling the ring elements from the discrete spherical Gaussian distribution over OK_q with parameter s_. s_2 <- d-Spherical_OK_q(,s_) e_2 <- d-Spherical_OK_q(,s_) e_2 <- d-Spherical_OK_q(,s_) This can be done by sampling each coefficient of s_2 and e_2 and e_3 independently from the discrete Gaussian distribution over Khera, Rohit Expires April 24 2018 [Page 19] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 Z_q centered at 0 with parameter s_. 7.2.2 Server Key and Parameter Receipt The client receives the parameter a from the server and the ephemeral server public key b. 7.2.3 Client Public Key The client computes its ephemeral public key u by multiplying elements a and its ephemeral secret key s_2 and then adding the error e_2. u = a*s_2 + e_2 7.2.4 Client Doubling and Cross Rounding Client computes the element v by multiplying the ephemeral server public key b with its secret key s_2 and adding the error term e_3. v = b*s_2 + e_3 The client then applies the extended randomized doubling function to v and obtains the element v_ in OK_2q: v_ = dbl_OK_q(v) The client then computes the cross rounding of v_ by applying the extended cross rounding function to v_ and obtains the n-bit vector v* v* = CrossRound_OK_2q(v_) 7.2.5 Client Key and Cross Rounding Vector Exchange The client returns its ephemeral public key u and the cross rounding vector v* to the server. 7.2.6 Client Modular Rounding and Key Derivation The client then applies the extended modular rounding function to v_ and computes the premaster secret (pms) as: Khera, Rohit Expires April 24 2018 [Page 20] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 pms = modR_OK_2q_2(v_) An approved key derivation function can then be used for deriving the master secret key. In practice, its expected that the key derivation method specified in TLS 1.2 section 8.1 [RFC5426] will be used. 8. TLS Extensions This section addresses authentication as it relates to key exchange along with guidance for integration of this key exchange method with the TLS protocol. Authenticated key exchange (AKE) protocols allow two parties to mutually establish ephemeral authenticated session keys for two way communications. There is a body of literature in the area of formalizing models for AKE, including the significant work of Canetti and Krawczyk [CN2002) on demonstrating security of so called "post-specified peer" SIGMA ("SIGn-and-MAc") protocols in the simulation paradigm. Whereas protocols such as IKE achieve some of these goals, the passive lattice based key exchange protocol described here does not. The approach to address this deficiency is to integrate it within the TLS handshake protocol. There are two ways to do this, the first as a "fundamental" replacement for FFC / ECC discrete log based classical key exchange methods [NIST-SP-800- 56A] which will be described below, and the second being a "hybrid" approach that incorporates this lattice based method with discrete log based key exchange (which is clearly the more conservative approach that should be considered by implementations). Khera, Rohit Expires April 24 2018 [Page 21] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 Client Server ------ ------ ClientHello --------> ServerHello Certificate* ServerKeyExchange* CertificateRequest*+ <-------- ServerHelloDone Certificate*+ ClientKeyExchange CertificateVerify*+ [ChangeCipherSpec] Finished --------> [ChangeCipherSpec] <-------- Finished Application Data <-------> Application Data * message is not sent under some conditions + message is not sent unless client authentication is desired Figure 2: TLS handshake 8.1 Fundamental RLWE Suites This note therefore follows after the guidance in [BCNS14] and its associated implementation for TLS versions supporting AEAD modes by specifying the following cipher suites. Also, this note follows the blueprint for specifying TLS extensions set forth in [RFC4492] ( which defines the TLS extensions for Elliptic Curve cipher suites): +-----------------------------------------+ | | | TLS_RLWE_RSA_AES128_GCM_SHA256 | | | | TLS_RLWE_ECDSA_AES128_GCM_SHA256 | | | +-----------------------------------------+ Figure 3: Fundamental RLWE Cipher Suites 8.2 Fundamental RLWE Key Exchange Algorithms Khera, Rohit Expires April 24 2018 [Page 22] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 The following server key exchange algorithms are specified 8.2.1 RLWE_RSA For this method the server's certificate must contain a RSA capable signing key and be signed with RSA. The server sends its ephemeral RLWE public key, the ring element 'a' and a specification of the lattice parameters in the ServerKeyExchange message. These parameters MUST be signed with RSA using the private key corresponding to the public key in the server's Certificate. The client generates an ephemeral RLWE public and secret keys based on the server's lattice parameters and ring element 'a' its ephemeral public key and the cross rounding vector in the ClientKeyExchange message. The client then performs the modular rounding operation whereas the server performs the reconciliation operation (as described in the protocol section above). Client and server then use the resultant shared secret as the premaster secret. 8.2.2 RLWE_ECDSA This key exchange algorithm is the same as ECDH_RSA except that the server's certificate MUST be signed with ECDSA rather than RSA. 8.3 Fundamental TLS extensions for RLWE A single new TLS extension is specified in this section, called the Fundamental RLWE Parameter Set extension (which specifies the ring polynomial, the modulus q, the distribution type, standard deviation and expected value, see section immediately below for more details). Though a single set of parameters is described here, in the future these extensions should allow for negotiating other lattice parameters. The client should enumerate the lattice parameters it supports in its ClientHello message. The server should in a similar way enumerate the lattice parameters it supports in its ServerHello message. A TLS client that proposes RLWE cipher suites in its ClientHello message SHOULD include this extension. Servers implementing RLWE cipher suites MUST support this extension, and when a client uses this extension, servers MUST NOT negotiate the use of a RLWE cipher suite unless they can complete the handshake under the choice of RLWE parameters supported by the client. The client MUST NOT include this Khera, Rohit Expires April 24 2018 [Page 23] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 extension in the ClientHello message if it does not propose any RLWE cipher suites. 8.3.1 Fundamental RLWE Parameters Extension enum { sec_cyclotomic_2048 (1), reserved (..) } RingPolynomial; enum { sec_mod_2_32_1 (1), reserved (..) } Modulus; enum { sec_gaussian (1), reserved (..) } Distribution; enum { sec_std_8_Sqrt_2_by_Pi (1), reserved (..) } StandardDeviation enum { sec_ev_0 (1), reserved (..) } ExpectedValue; struct { RingPolynomial poly; Modulus mod; Distribution dist; StandardDeviation std; ExpectedValue ev; } FundamentalRLWEParamSet; struct { FundamentalRLWEParamSet paramSetList<1..2^8-1>; } FundamentalRLWEParamSetList; In this version of the note, the only valid instantiation of the struct FundamentalRLWEParamSet is the following: struct FundamentalRLWEParamSet params = { sec_cyclotomic_2048, sec_mod_2_32_1, sec_gaussian, \ sec__std_8_Sqrt_2_by_Pi, sec_ev_0 }; Khera, Rohit Expires April 24 2018 [Page 24] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 Implementations MUST ensure that passed parameters agree with the above. The above namespace will need to be maintained by IANA. 8.3.2 Client Hello Extension This section specifies the TLS extension that can be included with the ClientHello message for RLWE based key exchange. This extension is the Fundamental RLWE Parameter Set extension. When this extension is sent: The extension SHOULD be sent along with any ClientHello message that proposes RLWE cipher suites. The extension allows a client to enumerate the RLWE parameter sets that it supports. The general structure of TLS extensions is described in [RFC4366], and this note specification adds the following to ExtensionType. enum { FundamentalRLWE(..) } ExtensionType; FundamentalRLWE (Fundamental RLWE Parameter Set extension): Indicates the Fundamental RLWE parameters supported by the client. For this extension, the opaque extension_data field contains the FundamentalRLWEParamSetList. See the preceding section for details. Actions of the sender: A client that proposes RLWE cipher suites in its ClientHello message appends this extension, In the current version of this note, clients clients SHOULD only send the single parameter set outlined in the preceding section. Actions of the receiver: A server that receives a ClientHello containing this extension MUST use the client's enumerated capabilities to guide its selection of an appropriate cipher suite. One of the proposed RLWE cipher suites must be negotiated only if the server can successfully complete the handshake while using the Fundamental RLWE parameter set supported by the client. 8.3.3 Server Hello Extension This section specifies a TLS extension that can be included with the ServerHello message for RLWE based key exchange (the Khera, Rohit Expires April 24 2018 [Page 25] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 Fundamental RLWE Parameter Set Extension). When this extension is sent: The Fundamental RLWE Parameter Set Extension is included in a ServerHello message in response to a ClientHello message containing the Fundamental RLWE Parameter Set Extension when negotiating an RLWE cipher suite. Meaning of this extension: This extension allows a server to enumerate RLWE parameters that it supports for the parameter and key material exchanges in its ServerKeyExchange message. Structure of this extension: The server's Fundamental RLWE Parameter Set Extension has the same structure as the client's Fundamental RLWE Parameter Set Extension (see preceding section). Actions of the sender: A server that selects a RLWE cipher suite in response to a ClientHello message (that includes a Fundamental RLWE Parameter Set) and appends this extension to its ServerHello message. Actions of the receiver: A client that receives a ServerHello message containing a Fundamental RLWE Parameter Set Extension MUST respect the server's choice of RLWE parameters. 8.3.4 Server Certificate This message is sent for all non-anonymous Fundamental RLWE key exchange algorithms. No additional or modified processing is required for this message for the fundamental RLWE key exchange methods described here. 8.3.5 Server Key Exchange When this message is sent: This message is sent when using the RLWE_ECDSA and RLWE_RSA key Khera, Rohit Expires April 24 2018 [Page 26] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 exchange algorithms. This message is used to convey the (i) the fundamental RLWE parameter set (ii) The public ring element 'a' (refer to preceding sections on protocol flow and description), along with the server's ephemeral public key b. struct { FundamentalRLWEParamSet params; opaque a <2^12>; opaque b <2^12> } ServerFundamentalRLWEParams; The ServerKeyExchange message is extended as follows: enum { fundamental_RLWE_kex } KeyExchangeAlgorithm; This indicates the ServerKeyExchange message contains the ring element 'a' and the ephemeral server RLWE public key. select (KeyExchangeAlgorithm) { case fundamental_RLWE_kex: ServerFundamentalRLWEParams params; Signature signed_params; } ServerKeyExchange; params: Specifies the server ephemeral RLWE public key, the ring element 'a' and associated fundamental RLWE parameters signed_params: Consists of a hash of the params, along with the appropriate signature corresponding to the key exchange method (i.e. RLWE_RSA or RLWE_ECDSA). The private key corresponding to the certified public key in the server's Certificate message is used for signing. Actions of the sender: The server selects the Fundamental RLWE parameters (see prior section for a description of valid parameters), ephemeral public key and the ring element 'a' and conveys this information to the client in the ServerKeyExchange message using the format defined above. Actions of the receiver: The client verifies the signature and retrieves the server's RLWE parameters, ephemeral public key and the ring element 'a' from the ServerKeyExchange message. Khera, Rohit Expires April 24 2018 [Page 27] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 8.3.6 Certificate Request This message sent when requesting client authentication. No additional or modified processing is required for this message for the Fundamental RLWE key exchange methods described here. 8.3.7 Client Certificate This message is sent in response to a CertificateRequest. No additional or modified processing is required for this message for the fundamental RLWE key exchange methods described here. 8.3.8 Client Key Exchange This message contains the client's ephemeral RLWE public key and cross rounding information. Meaning of the message: This message is used to convey ephemeral data relating to the key exchange belonging to the client. Structure of this message: The TLS ClientKeyExchange message is extended as follows. struct { FundamentalRLWEParamSet params; opaque u <2^12>; opaque cr <2^7>; } ClientFundamentalRLWEParams; This message contains the client's ephemeral RLWE public key and cross rounding information. struct { select (KeyExchangeAlgorithm) { case fundamental_RLWE_kex: ClientFundamentalRLWEParams; } exchange_keys; } ClientKeyExchange; Actions of the sender: The client generates its ephemeral public key upon receipt of the parameter 'a' from the server and sends this along with the cross rounding vector to the server. Actions of the receiver: Khera, Rohit Expires April 24 2018 [Page 28] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 The server retrieves the client's ephemeral RLWE public key from the ClientKeyExchange message and ensures that it is consistent with the agreed upon Fundamental RLWE parameters. 8.3.9 Certificate Verify Pending 8.4 Hybrid RLWE Suites This section, which is pending, will specify TLS extensions for the use of RLWE key exchange in conjunction with FFC/ECC discrete log based key exchange. The hybrid method will be the preferred key exchange method specified in this note. +----------------------------------------------------+ | | | TLS_RLWE_DHE_RSA_AES128_GCM_SHA256 | | | | TLS_RLWE_ECDHE_RSA_AES128_GCM_SHA256 | | | | TLS_RLWE_DHE_ECDSA_AES128_GCM_SHA256 | | | | TLS_RLWE_ECDHE_ECDSA_AES128_GCM_SHA256 | | | +----------------------------------------------------+ Figure 4: Hybrid RLWE Cipher Suites 9. Authenticity As discussed in the previous section on TLS integration, the proposed approach relies on classical signature schemes RSA and ECDSA [FIPS186-4] for authenticity. For compatibility with 128 bit security, implementations should use 3072 RSA and ECDSA on the nist curve p256. 10. Code Implementations and Licensing The following code is the closest code implementation of the method described in this note and is attributed to [BCNS14]: Khera, Rohit Expires April 24 2018 [Page 29] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 https://github.com/dstebila/rlwekex The licensing terms are from: http://unlicense.org An OpenSSL fork incorporating RLWE key exchange is available here under the terms of the OpenSSL license: https://github.com/dstebila/openssl-rlwekex/tree/OpenSSL_1_0_1- stable The availability of [ADPS2015] implementation is also noted. This implementation utilizes a smaller modulus and a different reconciliation method, and is available under a public license from: https://github.com/tpoeppelmann/newhope and from: https://cryptojedi.org/crypto/#newhope 11. IANA Considerations IANA is required to maintain the namespaces for the following TLS extensions: 1) FundamentalRLWEParamSet 2) ServerFundamentalRLWEParams 3) ClientFundamentalRLWEParams 4) Pending - namespaces for hybrid key exchange 12. Security Considerations The security of the key exchange method described here stems from a quantum reduction from approx. SVP on ideal lattices in the worst case to random instances of the search RLWE problem. The pseudorandomness of RLWE has been proven through a classical search to decision reduction for Galois number fields. The reader is referred to the introduction of this document as well as the section on error distributions for more details and for citations to the relevant literature. The security of the RLWE instantiations depend on the choice of error distribution. In particular, security with a fixed spherical error has been established for bounded numbers of RLWE samples, a constraint that is achieved in the key exchange method described here. The reader is referred to the introduction and the section on error distributions for more details. Incorrect choice of parameters and errors can lead to vulnerable Khera, Rohit Expires April 24 2018 [Page 30] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 RLWE instantiations. Rather than state the nature and cryptanalysis of such instantiations, the reader is referred to the literature on this subject such as [Pei2016a]. This key exchange method relies on the public ring element a_ (refer to description of the high level flow). Rather than specify this to be a global, fixed parameter, this note takes the approach of sampling this element uniformly from the ring OK/qOK for every key exchange. 12.1 Security Parameters In order to fully describe the RLWE distribution used in this key exchange method, the ring polynomial, modulus "q" and the 1-D Gaussian standard deviation and expected value need to be defined. In order to do so, this note adopts the following parameter sets from [BCNS2014]: +---------------------------------------------+ | | | Ring polynomial : 2048th cyclotomic | | | | Modulus q : (2^31) -1 | | | | Error distribution : Gaussian | | | | Guassian parameter (s_): 8 / Sqrt(2*Pi) | | | | Expected value : 0 | | | +---------------------------------------------+ Figure 5: Parameter Sets These parameters provide a security of 128 bits against classical attacks as described in the literature ([LP2011],[BCNS2014]). 12.2 Ring Element 'a' This key exchange method relies on the public ring element a_ (refer to description of the high level flow). Rather than specify this to be a global, fixed parameter, in this note, the server samples this element uniformly from the ring OK/qOK for every key exchange and passes this element to the client (in the TLS setting this is done in the Server Key Exchange message). It is noted that [ADPS2015] on the other hand use the approach where Khera, Rohit Expires April 24 2018 [Page 31] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 one of the parties samples a seed and generates a by application of the SHAKE-128 function. This is an approach that may be considered in a future version of this draft. 12.3 Side Channels This note treats certain computational aspects such as efficient polynomial multiplication as an implementation choice. In a similar vein, it is expected that implementations make their own determination around countermeasures against side channel attacks. 13. References 13.1 Normative References [FIPS186-4] FIPS pub. 186-4, "Federal Information Processing Standards Publication, Digital Signature Standard (DSS)" [NIST-SP-800-56A] NIST Special Publication 800-56A Revision 2, "Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography" [RFC4492] Blake-Wilson, S., Bolyard, N., Gupta, V., Hawk, C., and B. Moeller, "Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS)", RFC 4492, May 2006. [RFC4366] Blake-Wilson, S., Nystrom, M., Hopwood, D., Mikkelsen, J., and T. Wright, "Transport Layer Security (TLS) Extensions", RFC4366, April 2006. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 2434, October 1998. [RFC4506] Eisler, M., "XDR: External Data Representation Khera, Rohit Expires April 24 2018 [Page 32] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 Standard", RFC 4506, May 2006. [RFC5246] T. Dierks and E. Rescorla. The Transport Layer Security (TLS) Protocol Version 1.2. RFC 5246 (Proposed Standard) 13.2 Informative References [ADPS2015] Erdem Alkim and Leo Ducas and Thomas Poppelmann and Peter Schwabe, " Post-quantum key exchange - a new hope", IACR Cryptology ePrint Archive report 2015/1092, 2015 [BCNS2014] Joppe W. Bos and Craig Costello and Michael Naehrig and Douglas Stebila, "Post-quantum key exchange for the TLS protocol from the ring learning with errors problem", Cryptology ePrint Archive, Report 2014/599, 2014. [BGV2011] Zvika Brakerski and Craig Gentry and Vinod Vaikuntanathan, "Fully Homomorphic Encryption without Bootstrapping", Cryptology ePrint Archive, Report 2011/277 [BV2011] Brakerski, Zvika and Vaikuntanathan, Vinod, "Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages", Advances in Cryptology -- CRYPTO 2011 Ed. Rogaway, Phillip, Springer Berlin Heidelberg pages 505 - 524 [Can2000] Ran Canetti, "Universally Composable Security: A New Paradigm for Cryptographic Protocols", Cryptology ePrint Archive, Report 2000/067, 2000, http://eprint.iacr.org/2000/067 [CN2002] Ran Canetti and Hugo Krawczyk, "Security Analysis of IKE's Signature-based Key-Exchange Protocol", Cryptology ePrint Archive, Report 2002/120, 2002, http://eprint.iacr.org/2002/120 [Dev1986] L. Devroye, "Non-Uniform Random Variate Generation", Springer-Verlag, New York (1986) Available from: http://www.nrbook.com/devroye/ [DI2012] Jintai Ding, "A simple provably secure key exchange scheme Khera, Rohit Expires April 24 2018 [Page 33] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 based on the learning with errors problem". IACR Cryptology ePrint Archive report 2012/688. [DXL2012] Jintai Ding, Xiang Xie, Xiaodong Lin, "A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem", Cryptology ePrint Archive Report 2012/688, 2012. [GHS2011] Craig Gentry and Shai Halevi and Nigel P. Smart, "Fully Homomorphic Encryption with Polylog Overhead", Cryptology ePrint Archive, Report 2011/566 [LP2011] "Lindner, Richard and Peikert, Chris", "Better Key Sizes (and Attacks) for LWE-Based Encryption", In proceedings "Topics in Cryptology -- CT-RSA 2011: The Cryptographers' Track" at the RSA Conference 2011, San Francisco, CA, USA, February 14-18, 2011. Proceedings", 2011, Ed. Kiayias, Aggelos, Springer Berlin Heidelberg, pgs 319--339 [LPR2013a] Lyubashevsky, Vadim and Peikert, Chris and Regev, Oded, "On Ideal Lattices and Learning with Errors over Rings". J. ACM, November 2013 Vol.60/6, 2013. [LPR2013b] Vadim Lyubashevsky and Chris Peikert and Oded Regev, "A Toolkit for Ring-LWE Cryptography". Cryptology ePrint Archive, Report 2013/293}, 2013. [MR2004] Daniele Micciancio, Oded Regev, "Worst-Case to Average- Case Reductions Based on Gaussian Measures", vol. 00, pp. 372-381, 2004, FOCS.2004.72 [Pei2009a] Chris Peikert, "Public-key cryptosystems from the worst- case shortest vector problem". In STOC, pages 333-342. 2009 [Pei2009b] Chris Peikert, "Public-key cryptosystems from the worst- case shortest vector problem, 2009". https://web.eecs.umich.edu/~cpeikert/pubs/svpcrypto.pdf [Pei2014] Chris Peikert} "Lattice Cryptography for the Internet", Cryptology ePrint Archive Report 2014/070, 2014 Khera, Rohit Expires April 24 2018 [Page 34] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 [Pei2016a] Chris Peikert, Chris,,"How (Not) to Instantiate Ring- LWE", from "Security and Cryptography for Networks: 10th International Conference, SCN 2016, Proceedings", Ed. Zikas, Vassilis and De Prisco, Roberto, Springer International Publishing pages 411 - 430 [Pei2016b] Chris Peikert, "A Decade of Lattice Cryptography", Cryptology ePrint Archive, Report 2015/939, 2015 [PG2012] Poppelmann, Thomas and Guneysu, Tim, "Towards Efficient Arithmetic for Lattice-Based Cryptography on Reconfigurable Hardware", Ed. Hevia, Alejandro and Neven, Gregory", 2012, Springer Berlin Heidelberg [PG2013] Poppelmann, Thomas and Guneysu, Tim, "Towards Practical Lattice-Based Public-Key Encryption on Reconfigurable Hardware", in Selected Areas in Cryptography -- SAC 2013: 20th International Conference, Burnaby, BC, Canada, August 14-16, 2013, Revised Selected Papers, Ed. Lange, Tanja, and Lauter, Kristin and Lisonvek, Petr, 2014, Springer Berlin Heidelberg [Reg2005] Regev, O., "On lattices, learning with errors, random linear codes , and cryptography". In Proc. 37th ACM Symp. on Theory of Computing (STOC), pages 84-93 (2005). 14. Acknowledgements The author would like to thank Pivotal for support in putting together this draft. The author would also like to thank Eric Malm for insightful discussions and perspectives into the relevant aspects of algebra and algebraic number theory. 15. Author's Address Rohit Khera Pivotal 875 Howard St. San Francisco Khera, Rohit Expires April 24 2018 [Page 35] Internet Draft ring-LWE Key Exchange (LPR-kex) October 24, 2018 CA 94103 EMail: rkhera@pivotal.io Khera, Rohit Expires April 24 2018 [Page 36]