Internet DRAFT - draft-khera-lpr-ring-lwe-kex

draft-khera-lpr-ring-lwe-kex



 



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]/<phi_m(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]