computer science

Ring learning with errors key exchange

Ring learning with errors key exchange is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Ring learning with errors key exchange rather than just read about it. In short: In cryptography, a public key exchange algorithm is a cryptographic algorithm which allows two parties to create and share a secret key, which they can use to encrypt messages between themselves. The ring learning with errors 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 quantum computer.

Key takeaways

Ring learning with errors key exchange belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Ring learning with errors key exchange to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Ring learning with errors key exchange from memory before moving on to harder problems.

Reference excerpt

In cryptography, a public key exchange algorithm is a cryptographic algorithm which allows two parties to create and share a secret key, which they can use to encrypt messages between themselves. The ring learning with errors 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 quantum computer. This is important because some public key algorithms in use today will be easily broken by a quantum computer if such computers are implemented. RLWE-KEX is one of a set of post-quantum cryptographic algorithms which are based on the difficulty of solving certain mathematical problems involving lattices. Unlike older lattice based cryptographic algorithms, the RLWE-KEX is provably reducible to a known hard problem in lattices.

Background Since the 1980s the security of cryptographic key exchanges and digital signatures over the Internet has been primarily based on a small number of public key 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 factoring the product of two carefully chosen prime numbers, the difficulty to compute discrete logarithms in a carefully chosen finite field, and the difficulty of computing discrete logarithms in a carefully chosen elliptic curve 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 quantum computer 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 quantum computer 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 quantum safe, or post-quantum cryptography. One class of quantum resistant cryptographic algorithms is based on a concept called "learning with errors" introduced by Oded Regev in 2005. A specialized form of Learning with errors operates within the ring of polynomials over a finite field. This specialized form is called ring learning with errors or RLWE. There are a variety of cryptographic algorithms which work using the RLWE paradigm. There are public-key encryption algorithms, homomorphic encryption algorithms, and RLWE digital signature algorithms in addition to the public key, key exchange algorithm presented in this article A key exchange algorithm 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 Diffie–Hellman key exchange. The exchange consists of one transmission from one end of the line and one transmission from the other end of the link. Diffie–Hellman and Elliptic Curve Diffie–Hellman are the two most popular key exchange algorithms. The RLWE Key Exchange is designed to be a "quantum safe" replacement for the widely used Diffie–Hellman and elliptic curve Diffie–Hellman 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 "forward secrecy"; the aim of which is to reduce the effectiveness of mass surveillance programs and ensure that there are no long term secret keys that can be compromised that would enable bulk decryption.

Introduction Starting with a prime integer q, the Ring-LWE key exchange works in the ring of polynomials modulo a polynomial Φ ( x ) {\displaystyle \Phi (x)} with coefficients in the field of integers mod q (i.e. the ring R q := Z q [ x ] / Φ ( x ) {\displaystyle 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 Φ ( x ) {\displaystyle \Phi (x)} . The idea of using LWE and Ring LWE for key exchange was first proposed and filed at the University of Cincinnati in 2011 by Jintai Ding. The idea comes from the associativity of matrix multiplications, and the errors are used to provide the security. The paper appeared in 2012 after a provisional patent application was filed in 2012. The security of the protocol is proven based on the hardness of solving the LWE problem. In 2014, Peikert presented a key-transport scheme following the same basic idea of Ding's, where the new idea of sending an additional 1-bit signal for rounding in Ding's construction is also used. The "New Hope" implementation selected for Google's post-quantum experiment, uses Peikert's scheme with variation in the error distribution. For somewhat greater than 128 bits of security, Singh presents a set of parameters which have 6956-bit public keys for the Peikert's scheme. The corresponding private key would be roughly 14,000 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:

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Ring learning with errors key exchange

Start with the simplest possible case. Write down what Ring learning with errors key exchange claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Ring learning with errors key exchange before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Ring learning with errors key exchange ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Ring learning with errors key exchange

In research: Ring learning with errors key exchange appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Ring learning with errors key exchange in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Ring learning with errors key exchange is common in secondary-school and first-year university syllabi. It links to neighbouring topics Cryptographic algorithms, Lattice-based cryptography, Post-quantum cryptography, so understanding it makes those chapters shorter.
In everyday life: Look for Ring learning with errors key exchange outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Ring learning with errors key exchange in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Ring learning with errors key exchange means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Ring learning with errors key exchange out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Ring learning with errors key exchange in simple terms?

Why does Ring learning with errors key exchange matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Ring learning with errors key exchange?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Ring learning with errors key exchange.