Ring learning with errors key exchange

In cryptography, a algorithm is a which allows two parties to create and share a secret key, which they can use to encrypt messages between themselves. The Key Exchange (RLWE-KEX) is one of a new class of public key exchange algorithms that are designed to be secure against an adversary that possesses a . This is important because the vast majority of in use today are easily broken by a quantum computer and scientists are making steady progress toward creating such a computer. -KEX is one of a set of algorithms which are based on the difficulty of solving certain mathematical problems involving . Unlike older lattice based cryptographic algorithms, the -KEX is provably reducible to a known hard problem in lattices.

1 Background
2 Introduction
3 The Key Exchange
4 Key Exchange Security
5 Implementations
6 Source
7 See Also on BitcoinWiki

Background

Since the 1980s the security of cryptographic and digital signatures over the Internet has been primarily based on a small number of algorithms. The security of these algorithms is based on a similarly small number of computationally hard problems in classical computing. These problems are the difficulty of , the difficulty to compute in a carefully chosen finite field, and the difficulty of computing discrete logarithms in a carefully chosen group. These problems are very difficult to solve on a classical computer (the type of computer the world has known since the 1940s through today) but are rather easily solved by a relatively small using only 5 to 10 thousand of bits of memory. There is optimism in the computer industry that larger scale quantum computers will be available around 2030. If a of sufficient size were built, all of the public key algorithms based on these three classically hard problems would be insecure. This public key cryptography is used today to secure Internet websites, protect computer login information, and prevent our computers from accepting malicious software.

Cryptography that is not susceptible to attack by a quantum computer is referred to as , or . One class of quantum resistant cryptographic algorithms is based on a concept called “” introduced by in 2005. A specialized form of Learning with errors operates within the over a . This specialized form is called or .

There are a variety of cryptographic algorithms which work using the RLWE paradigm. There are public key encryption algorithms, algorithms, and algorithms in addition to the public key, key exchange algorithm presented in this article

A is a type of public key algorithm which establishes a shared secret key between two communicants on a communications link. The classic example of a key exchange is the key exchange. The exchange consists of one transmission from one end of the line and one transmission from the other end of the link. and are the two most popular key exchange algorithms.

The RLWE Key Exchange is designed to be a “” replacement for the widely used and key exchanges that are used to secure the establishment of secret keys over untrusted communications channels. Like Diffie-Hellman and Elliptic Curve Diffie-Hellman, the Ring-LWE key exchange provides a cryptographic property called “”; the aim of which is to reduce the effectiveness of programs and ensure that there are no long term secret keys that can be compromised that would enable bulk decryption.

Introduction

Starting with a integer q, the key exchange works in the modulo a polynomial $Phi(x)$ with coefficients in the field of integers mod q (i.e. the ring $R_q := Z_q[x] / Phi(x)$ ). Multiplication and addition of polynomials will work in the usual fashion with results of a multiplication reduced mod $Phi(x)$ .

In 2014, Peikert presented a key transport scheme based on Ring-LWE. For somewhat greater than 128 , Singh presents a set of parameters which have 6956-bit public keys for the Peikert’s scheme. The corresponding private key would be roughly 14000 bits. An RLWE version of the classic MQV variant of a Diffie-Hellman key exchange was later published by Zhang et al. in 2014. The security of both key exchanges is directly related to the problem of finding approximate short vectors in an ideal lattice.This article will closely follow the RLWE work of Ding in “A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem”. For this presentation a typical polynomial is expressed as:

a(x) = a₀ + a₁x + a₂x² + … + a_n-3x^n-3 + a_n-2x^n-2 + a_n-1x^n-1

The coefficients of this polynomial, the a_i‘s, are integers mod q. The polynomial $Phi(x)$ will be the . When n is a power of 2 then $Phi(x)$ = xⁿ +1.

The RLWE-KEX uses polynomials which are considered “small” with respect to a measure called the “.” The infinity norm for a polynomial is simply the value of the largest coefficient of the polynomial when the coefficients are considered as integers in Z rather than $Zq$ (i.e.from the set {-(q-1)/2,…, 0, … (q-1)/2} ). The algorithm’s security depends on an ability to generate random polynomials which are small with respect to the infinity norm. This is done simply by randomly generating the coefficients for a polynomial (s_n-1, …, s₀) which are guaranteed or very likely to be small. There are two common ways to do this:

Using – The coefficients of the small polynomial are uniformly sampled from a set of small coefficients. Let b be an integer that is much less than q. If we randomly choose coefficients from the set: { -b, -b+1, -b+2. … -2, -1, 0, 1, 2, … , b-2, b-1, b} the polynomial will be small with respect to the bound (b). Singh suggest using b = 5.

For the rest of this article, the random small polynomials will be sampled according to a distribution which is simply specified as D. Further q will be an odd prime such that q is congruent to 1 mod 4 and 1 mod 2n. Other cases for q and n are thoroughly discussed in “A Toolkit for Ring-LWE Cryptography” and in Singh’s “Even More Practical Key Exchange for the Internet using Lattice Cryptography.” and another paper by Singh. A fixed public polynomial, a(x), shared by all users of the network. It is deterministically generated from a cryptographically secure source.

Given a(x) as stated, we can randomly choose small polynomials s(x) and e(x) to be the “private key” in a public key exchange. The corresponding public key will be the polynomial p(x) = a(x)s(x) + 2e(x).

The Key Exchange

The key exchange will take place between two devices. There will be an initiator for the key exchange designated as (I) and a respondent designated as (R). Both I and R know q, n, a(x), and have the ability to generate small polynomials according to the distribution $chi_alpha$ with parameter $alpha$ . The distribution $chi_alpha$ is usually the discrete gaussian distribution on the ring R_q = $Zq$ [x]/ $Phi(x)$ . The description which follows does not contain any explanation of why the key exchange results in the same key at both ends of a link. Rather, it succinctly specifies the steps to be taken. For a thorough understanding of why the key exchange results in the initiator and responder having the same key, the reader should look at the referenced work by Ding et al.

Also in their November 2015 paper, Alkim, Ducas, Popplemann and Schwabe recommend that the choice of the base polynomial for the key exchange ( a(x) above ) be either generated randomly from a secure random number generator for each exchange or created in a verifiable fashion using a “nothing up my sleeve” or NUMS technique. Their first method prevents amortization of attack costs across many key exchanges at the risk of leaving open the possibility of a hidden attack like that described by Dan Bernstein against the NIST elliptic curves. The NUMS approach is open to amortization but generally avoids the Bernstein attack if only common mathematical constants such as pi and e are used.

Key Exchange Security

The security of this key exchange is based on the underlying hardness of problem that has been proven to be as hard as the worst case solution to the (SVP) in an . According to the BKZ 2.0 algorithm the key exchange parameters listed above will provide greater than 128 or 256 bits of security, respectively.

Implementations

In 2014 Douglas Stebila made a patch for OpenSSL 1.0.1f. based on his work and others published in “Post-quantum key exchange for the TLS protocol from the ring learning with errors problem.” Software implementing the work of Singh is found on GitHub at https://github.com/vscrypto/ringlwe. The concept of creating what has been called a Diffie-Hellman-like Key Exchange using lattices with a reconciliation function appears to have first been presented by French researchers Aguilar, Gaborit, Lacharme, Schrek, and Zemor at PQCrypto 2010 in their talk, “Noisy Diffie-Hellman Protocols.”

In November 2015, Alkim, Ducas, Popplemann, and Schwabe built on the prior work of Peikert and used what they believe is a more conservative costing of lattice attacks to recommend parameters. Software based on the work of Alkim, Ducas, Popplemann, and Schwabe is found on GitHub at https://github.com/tpoeppelmann/newhope

Source

http://wikipedia.org/