ECRYPT CSA Spring School on Symmetric Crypto

Registration for the ECRYPT CSA Spring School on Symmetric Crypto is now open.

The school is free of charge, but the number of places is limited.

Sixth Bar-Ilan University Winter School on Cryptography (Part 2)

This two-part blog post has been collaboratively written by Eduardo, Marie-Sarah, Matthias and Ralph.

On Wednesday, the second part (special encryption) of the school began.

First, Mor Weiss introduced us to format-preserving encryption (FPE) and explained the importance of tweakable block ciphers. Tweaks are randomized, public values that provide more randomness to block ciphers (kind of like salts in hash functions). Alexandra Boldyreva taught us about some inherent weaknesses of deterministic (i.e., equality-preserving) and order-preserving encryption. Hugo Krawczyk presented the details of ESPADA/OXT. Ben Fisch showed us how a tree of Bloom filters can be used to search on encrypted data (Blind Seer).

The favourite talk of Matthias was given by Benny Pinkas on Thursday. The title was "Searchable Encryption using ORAM" and the argument for choosing that approach over the others presented before, was that, for better security guarantees, it is desirable that the sequence of memory accesses to some encrypted data reveals no more information than the running-time. Oblivious RAM (ORAM) can be informally defined as follows:

A program $P$ is called "memory oblivious" if the memory access pattern $AP(x)$ (a sequence of $\verb!read!(a)$ or $\verb!write!(a,v)$ operations) is independent of the input $x=x(i,a,v)$ (which is a function of an instruction, address and value).
More formally an oblivious memory access pattern of $P$ shall satisfy:
$$
\forall x\neq y: \left\vert x\right\vert =\left\vert y\right\vert \Longrightarrow AP(x)\approx AP(y).
$$
The "ad-hoc solution" requires $\mathcal{O}(nm)$ time and $\mathcal{O}(m)$ memory upon storing $n$ encrypted pairs $(a, v)$ of equal size $m$ in memory using a randomized encryption scheme and going through every memory cell.
If the addresses don't match, re-encrypt and overwrite data cell, else, perform the instruction, encrypt and write results.

In this one-hour talk Pinkas then focused on the simplest tree based ORAM scheme, but gave possible ways to reduce the overhead i.e. by using ORAM schemes recursively.
The basic ORAM scheme consists of the server storing a full binary tree with $\log n$ levels and $n$ leaves, where each intermediate node contains $\log n$ data items.
The client randomly maps items to leaves, which results in $\mathcal{O}(n)$ storage of $\log n$ bits.
Accessing an item requires to traverse the path, from root to leaf, obtained from the position map. In each bucket along the path remove the data item if found and assign a new random leaf to it.  Upon updating the client's position map write the updated item to the root node.
To prevent overflows perform the following oblivious operations in each level:
Choose two nodes at random and pop an item from both (non-empty) buckets, move the item downwards to next node on its path and perform a dummy write operation to the other descendant of the node to hide the operation.

To summarize: The server storage holds $\mathcal{O}(n \log n)$ data items, the client stores $n$ indices requiring $\mathcal{O}(n \log n)$ bits and each access costs $\mathcal{O}(\log^2 n)$ $\verb!read!$ and $\verb!write!$ operations.

Finally he discussed security limitations, efficiency problems and presented encrypted search using ORAM:
A straight-forward solution, given $n$ data items and $k$ keywords assigned to some, is to store $\leq nm$ tuples of the form ($k$, $\langle$data item associated with $k\rangle$ ) which in general requires storing each item multiple times.
Using two ORAMs - the first to store the documents indices given a keyword associated with it (="an inverted index list"), and the second ORAM to store the data items themselves, solves the problem of performing encrypted search more elegantly without the server being able to identify which item is being read nor whether a specific data item is accessed more often.
Sadly, Benny Pinkas also pointed to a result from Naveed's 2015 eprint report --often, sending the entire database to a client is more efficient than doing searchable encryption with ORAM-- so, as with the first part of the Winter School, there is still room for improvements!

We hope we were able to give you a flavour of how amazing this event was with these two posts. If not, or if you want to deepen in the talks, it's your lucky day: They are all uploaded! (We will post a comment when they are online)

Ecrypt-Net fellows in Caesarea

A sincere "Toda!" to the organizers, Yehuda Lindell, Benny Pinkas, and Yonit Homburger, for such a pleasant school!

Sixth Bar-Ilan University Winter School on Cryptography (Part 1)

This two-part blog post has been collaboratively written by Eduardo, Marie-Sarah, Matthias and Ralph.

Earlier this month, from 4-7 January, a few ECRYPT-NET fellows and about a hundred others attended the Bar-Ilan University winter school on cryptography. It took place in Ramat Gan, a suburb of Tel Aviv, at the Kfar Maccabiah hotel and conference centre (named after the Maccabiah, or Jewish Olympics, that take place there every four years). The school was intense, but well organized. It was split into two parts, verifiable computation and special encryption, and so will be our coverage of it.

Part 1: Verifiable Computation

Michael Walfish, Yael Tauman Kalai, and Eran Tromer guided us through methods for verifying the outsourced computation of functions. We particularly appreciated the crystal-clear overview of all sessions, given by Michael Walfish, that emphasized how the content of the talks fit together.

Let's set the scene for verifiable computation: a client (the verifier) wants to outsource the computation of a function f to a server (the prover) who has more computing resources. But how does the verifier know that the value returned by the prover is actually the result of applying the function f to the purported inputs? A malicious or a lazy server could indeed modify the process to gain some advantages as, for instance, reducing the cost of operating a system.

Verifiable computation of f(x) comprises the following two phases:

1. Program representation (or arithmetization): The verifier (or a party he trusts) expresses the function f as a set of arithmetic constraints over a field, in terms of the input x, output y, and intermediate variables z. Each of these x, y, and z may be vectors, e.g., x=(x₁,x₂,x₃). Typically, the format these constraints needs to have is that of degree-2 polynomials that equal 0 when they (and the function f) are satisfied.
2. Solving and proving: The server must prove to the client that the solution it returns, y, is correct. The landscape of proof protocols shows a trade-off between efficiency, expressiveness and additional properties like zero-knowledge or non-interactivity. The speaker himself recently wrote a survey which is a very nice introduction to the state of the art and these trade-offs.

Yael Kalai's talks took a more theoretical approach, guiding us through the evolution of Probabillistically Checkable Proofs (PCPs). She emphasized the importance of "good" security assumptions, where "good" requires at least, and according to her point of view, that the underlying assumptions can be efficiently falsified. These theoretical worries were well founded, as most of today's verifiable computation protocols rely on SNARKs (standing for Succint Non-interactive ARguments of Knowledge) which cannot be proved secure via black-box reductions from (efficiently) falsifiable assumptions. 

Yael's talks provided also very interesting and intuitive examples. To give one, suppose that Peggy and Victor are playing chess. After a number of moves, Peggy (the prover) wants to prove to Victor (the verifier) that she has a checkmate. If Victor fails to see it, it is for Peggy easier to convince him by continuing the game (an interactive proof) until he does, rather than to explain all the possible combinations of moves without moving any piece (a non-interactive proof). This intuition of the power of interaction extends to the rest of the proof systems. Finally, she even showed us how the subject fits in the quantum framework, introducing us to the notion of non-signalling adversaries.

Eran Tromer recovered the line of Michael Walfish and focused on the details of SNARKs and how they are actually constructed. Among others, he has been writing libsnark, a C++ library that is used a lot for verifiable computation systems relying on SNARKs. He also showed us a potential application for them, called Zerocash. Zerocash is a protocol that provides a privacy-preserving version of Bitcoin. In contrast to Bitcoin, where all the transactions are public in the block chain, Zerocash does not contain information about the payment’s origin, destination or amount. The correctness of the transaction is guaranteed via a zero-knowledge proof. More details can be found here.

Part 1.5: Excursion to Caesarea and Binyamina Winery

Sun starting to go down in Caesarea.

Tuesday afternoon, we made an excursion to the remains of Caesarea, a Roman city on the Mediterranean coast that was built by Herod over 2000 years ago. To say that it had a tumultuous history would be an understatement. Our tour included a walk through a "graveyard" of columns and capitals, the amphitheatre (whose first row is still intact), and the hippodrome.

Next, we took an informative tour of the Binyamina winery. We learned that grapes are crushed with a flexible rubber material to simulate the skin of feet. For red wine, the grapes are fermented (skin, seeds, and all) before being crushed. For white wine, seeds and skin are removed (by sedimentation) after pressing, then fermented. The tannin (bitter-tasting substances) in wine comes from the seeds, skin, and maybe the material of the barrel in which it is matured. Whether wine is aged or matured in an American oak (sweeter) or French oak (more tannins, adds more complex flavours) barrel affects the final product. Tannins prevent oxidation, so red wine (with more tannins) can be matured longer. Stopping fermentation early makes wine more sweet.

After learning how wine is made, we concluded the day by learning how it tastes (using our five senses!) and enjoying a generous dinner.

Stay tuned for the second and last part of the post!

Threshold implementations

Ever since the discovery of differential power attacks (DPA) in late 1990's, cryptographic community has been trying to find effective methods to twarth attempts to extract secret information, i.e. secret key using such attacks. Initial proposals to protect hardware implementations used simple models. Although easy to understand these schemes can still leak sensitive information through power consumption in case of glitches. In most models we assume that Hamming weight of intermediate result is leaked through power consumption.

 Masking

Masking is one of the first ideas to prevent leaking sensitive information using intermediate values during encryption. In most basic example we split the intermediate value $X$ into two randomized values $X_1$ and $X_2$ such that $X = X_1 \oplus X_2$. We assume that leakage is equal to Hamming weight of the variables $\mathcal{L}(X) =  \text{HW}(X_1, X_2)$.  It turns out that first order analysis doesn't reveal input value since mean of the leakage $\mathcal{L}$ is constant for all values of input $x$.          

Table 1. Leakage behaviour of single bit variable using two shares

$x$	$x_1$	$x_2$	$\mathcal{L}(x)$	Mean$(\mathcal{L}(x))$
$0$	$0$	$0$	$0$	$1$
	$1$	$1$	$2$
$1$	$1$	$0$	$1$	$1$
	$0$	$1$	$1$

In case of second order analysis, however, this scheme will leak. Variance of $\text{HW}(X_1, X_2)$ is different for the case when unmasked value takes value 0 and for the case when it takes value 1. In general, to protect against $n^{\text{th}}$ order attack we would need to decompose original variables into $n + 1$ randomized uniform variables $X_1, ..., X_{n+1}$ such that
\begin{equation}
X = X_1 \oplus X_2 \oplus \cdots \oplus X_{n+1}
\end{equation}

In practice this is done by generating $d$ variables $X_1, .... , X_d$ and deriving $X_{d+1}$ so that it satisfies the upper equation. Each of the variables $X_i$ is referred to as share. Once we have a sharing, we need to perform all the operations using these shares so that in the end we still still have correct output shares. In case of affine transform this is easy - applying linear term to all of the shares and adding constant term to one of the shares. Boolean function that have higher algebraic degree are not so trivial as we need to ensure the order in which the operations in the shares are executed. For example function $f(a, b, c) = a \oplus bc$ can be protected using Boolean masking with 2 shares in following way
\begin{equation}
f_1(a_1, b_1, c_1) = (a_1 \oplus b_1c_1) \oplus b_1c_2\\
f_2(a_2, b_2, c_2) = (a_2 \oplus b_2c_1) \oplus b_2c_2.
\end{equation}

This sharing is not unique and there are multiple possible sharing of the same function.
As noted, order in which operations take place is important. Otherwise, we could expose the unmasked value of $c$ in function $f_1$ because $ b_1c_1 \oplus b_1c_2 = b_1(c_1 \oplus c_2) = b_1c$.

Major problem with conventional masking is that it doesn't provide protection when glitches can occur in the circuit, which is inevitable in CMOS technology. Different propagation times of input signals can cause some gates to change state more than once during a single clock cycle, which causes more input current to be drawn from the power source, resulting in increased power consumption during the clock cycle in which glitch occurred. If the increased power consumption can be correlated to the value we want to protect, there is a leak in the device.

Threshold implementations

Threshold implementation, or TI, is a method of protecting against DPA that is resistant to glitches that can occur. It builds upon the classical masking scheme and threshold cryptography. For $d^{\text{th}}$ order security idea is to create shared functions in a way that any linear combination of $d$ shared function is independent of at least one input share. In other words, if we are able to probe any $d$ wires in the design, we wouldn't be able to create correlation with unshared value because we would always be missing at least one input share for correlation.

In order to create a TI of a given function $f(x) : \mathcal{F}_2^n \Rightarrow \mathcal{F}_2^m$ with $s_{in}$ input shares and $s_{out}$ output shares we apply a Boolean masking to input variable $x$, so that we create shares $x_1, ... , x_{s_{in}}$ for which holds $\sum x_i = x$. Now we have a sharing of variable $x$, $\mbox{Sh}(x), \mathbf{x} \in \mathcal{F}_2^{ns_{in}}$. Similarly, we create a sharing of function $f$ by creating $s_{out}$ function components $\mathbf{f} = f_1, ... , f_{s_{out}}, \mathbf{f} \in \mathcal{F}_2^{m s_{out}}$.
Threshold implementation satisfies four key properties:

1. Uniform masking
2. Correctness
3. Non-Completness
4. Uniformity of a sharing

First property simply states that for each possible value of input variable $x$ probability of each valid input sharing is always the same. If we denote the input sharing with $\mathbf{X}$ we could rewrite the previous statement as

\begin{equation}
(\forall x), (\mathbf{x} \in \mbox{Sh}(x) \Rightarrow \mbox{Pr}(\mathbf{X} = \mathbf{x} | X = x) = p)\,  \land  \, (\mathbf{x} \notin \mbox{Sh}(x) \Rightarrow \mbox{Pr}(\mathbf{X} = \mathbf{x} | X = x) = 0) \\ \land \\ (\sum_{\mathbf{x} \in Sh(x)} \mbox{Pr}(\mathbf{X} = \mathbf{x}) = \mbox{Pr}(X = x))
\end{equation}

where $p$ is a constant.

Second property of correctness states that for sharing of a function $f(x)$, $\mathbf{f}(\mathbf{x}) = f_1(\mathbf{x}), .... , f_{s_x}(\mathbf{x})$ XORing all output component gives back the unshared output:
\begin{equation}
(\forall x) ((\mathbf{x} \in \mbox{Sh}(x), a = f(x), a_i = f_i(\mathbf{x})) \Rightarrow a = \sum_i a_i = \sum_i f_i(\mathbf{x}))
\end{equation}

It is simply there to ensure that once we apply the sharing we still get the same result in the output when we perform unmasking.

The previous two properties applies to all masking schemes, not only TI. Property of non-completeness is what ensures $d^{\text{th}}$ order of security:

Any combination of up to $d$ component functions $f_i$ of $\mathbf{f}$ is independent of at least one input share $x_j$.

Being independent of one input share means that even the attacker that knows values of $d$ component functions cannot recreate the original input value $x$. Without all the input shares, the information from all other input shares is independent of the input.

It can be shown that to achieve $d^{\text{th}}$ order TI we need at least $d + 1$ input shares. It can also be shown that there always exists a $d^{\text{th}}$ order TI of a function of algebraic degree $t$ with number of input shares $s_{in} \geq td + 1$ and number of output shares $s_{out} \geq \binom {s_{in}}t$. Also, in order to achieve non-completeness we need at least $t+1$ input shares if degree of the function is $t$.

The final property Threshold implementation requires that the output sharing also need to preserve output distribution, e.g. if the $f$ is a permutation then $\mathbf{f}$ is also a permutation:

$d^{\text{th}}$ order sharing of $\mathbf{f}$ if uniform if and only if
\begin{equation}
\forall x \in \mathcal{F}^n, \forall a \in \mathcal{F}^m \textit{ where } f(x) = a, \forall \mathbf{a} \in \mbox{Sh}(a) \text{ : }|\mathbf{x} \in \mbox{Sh}(x)  | \mathbf{f}(\mathbf{x}) = \mathbf{a}| = \frac{|\mathcal{F}|^{n(s_{in} - 1)}}{|\mathcal{F}|^{m(s_{out} - 1)}}
\end{equation}
It is important when we are cascading TIs of two or more functions, because we need the input sharing of the second function to be uniform. This is almost always the the case, e.g. when we are applying TI to block cipher, output of the previous round is used as input for the next round etc.

Uniformity in practice is non-trivial to achieve and finding a methodical way to get a uniform output sharing is still extensively researched. There is a couple of heuristics, but none of them guarantee a sharing that has uniform output distribution. We will tackle some of them in a future blog.  
  

Max Levchin Prize @ RealWorldCrypto 2016

This week saw Real World Crypto 2016 in Stanford California. The highlight was the first awarding of the Levchin prize for work in the field of practical cryptography. The prize award is donated by Max Levchin, a founder of PayPal, and two such prizes of $10,000 will be awarded annually. 

The first recipients of the award are 

• Phil Rogaway for his long standing work on developing practical cryptographic algorithms, the development of practice oriented provable security, format preserving encryption and numerous other algorithms which are used every day to secure our online world.
• The miTLS team for their work on producing a formal analysis of the TLS protocol specification, and in the process finding a number of  real world attacks on this protocol such as the triple-handshake attack.

The real purpose of the award though is to highlight work to the wider community that one can have deep and lasting impact on society by working in an area as mathematically opaque as cryptography. Awards such as this, and events such as Real World Crypto, are designed to raise the profile of applied work in this space and encourage people to apply their skills to solving the pressing security problems affecting our online world.

In the rest of the conference there was an amazing program of interesting talks (although I would say so, since I was on the panel for selecting the talks). The highlight of day one for me was the talk by Adrienne Porter Felt on usability issues related to TLS failures in Google Chrome. By collecting numerous bug reports from Chrome users the team at Google found that most errors are not due to poor server configurations (indeed most errors occur when users connect to sites such as Google or Facebook), but are due to poor client configurations. For example a significant proportion of errors are caused by device times being incorrect. So lesson: Make sure you set your clocks correctly. 

One highlight of the second day was Hovav Shacham's talk on the recent discovery of a backdoor Juniper's ScreenOS. The initial backdoor was rather uninteresting in that if a certain key combination was presented a user would be given enhanced privileges. However, on discovery of this backdoor Hovav and his colleagues discovered a more interesting potential backdoor based on the Dual-EC PRNG that could compromise the VPN traffic that Juniper is used to protect. The interesting part was that previous cryptographic focus on Dual-EC has been on products which had explicitly listed Dual-EC usage as part of their FIPS certification. The Juniper product had not explicitly listed that it used Dual-EC, so the discovery of a Dual-EC based potential backdoor could imply that many more products, by many more vendors, could be using the Dual-EC PRNG.

The talks generating the most interest on the third day were the ones explaining the new Intel SGX technology. This is a technology which allows applications to run in an "encrypted enclave" on an Intel chip; where data is held encrypted in memory and is only decrypted as it enters the chip and is processed. When it returns to memory it is automatically encrypted. At its heart this idea goes back to the original paper on homomorphic encryption by Rivest et al from the mid 1970s. However, the new Intel technology has a number of additional features which make it suitable for a modern environment. The first talk by Rebekeh Leslie Hurd introduced the overall technology and some of the attestation and communication issues needed to authenticate the enclaves, and allow enclaves to talk to each other. The second talk by Shay Gueron discussed the details of how the memory is encrypted in a way which respects the cache architecture on modern microprocessors.

Learning problems and cryptography: LPN, LWE and LWR

The beginning of a new year is always a perfect moment to make plans for the future: one can sit down, look at the past year and figure out what to do and where to go during the upcoming one. It is legitimate, then, to take a while and think of new directions in the field of cryptography too. One of such is certainly post-quantum cryptography, that is to say what we should do when quantum computers running Shor's algorithm will break all the cryptosystems based on integer factorisation problem and (elliptic curve) discrete logarithm problem. In the literature, different approaches can be found: Code-based cryptographic systems depend on the hardness of correcting a codeword following a random error-correcting code while the security of lattice-based cryptosystems is based on the hardness of finding the shortest vector of a given lattice and of several other problems, just to mention two widely known and studied branches of post-quantum cryptography. In fact, at the present moment no quantum algorithm is known to solve them significantly better than any classic one. But there is more: hidden behind, there is a vast class of problems known as learning problems.

Essentially, they are computational problems related to learning theory, whose main issue is what kind of functions can be learned efficiently from noisy, imperfect data. Although only in recent years the link between learning theory and cryptography has been deeply studied, it existed since the early '90s. These two subjects are in a sense complimentary since the ease of learning an information, which is desirable in learning theory, excludes the possibility of hiding it, a must in cryptography. Hard learning problems are then good candidates to base cryptographic schemes on and the fact that they are thought to be quantum-resistant makes them even more appealing.

Let us begin the 2016 with a brief description of three well known learning problems: LPN, LWE and LWR.

Learning Parity with Noise (LPN)

The decisional LPN problem asks to find a secret vector $\mathbf{s} \in \mathbb{Z}_2^n$ where $n\in\mathbb{N}$, given samples of the form $$ ( \mathbf{a},\langle \mathbf{a} , \mathbf{s} \rangle \oplus e) \in \mathbb{Z}_2^n\times\mathbb{Z}_2 $$ where $\mathbf{a}\xleftarrow{U}\mathbb{Z}_2^n$ is drawn uniformly at random and $e\leftarrow Ber_\tau$ is drawn from the Bernoulli distribution of parameter $\tau \in (0,1/2)$, i.e. $\mathbb{P}(e=1)=\tau$. Equivalently, LPN can be stated as the problem of solving a system of noisy linear equations with coefficients in $\mathbb{Z}_2$, or to decode the codeword $\mathbf{s}$ affected by error $e$ using the random code generated by $\mathbf{A}$, which is the matrix whose rows are different $\mathbf{a}$ from several samples. More formally, for $\tau\in(0,1/2)$ and $n\in\mathbb{N}$ the LPN$_{\tau,n}$ is $(q,t,\epsilon)$-hard if for every distinguisher $\mathcal{D}$ running in time $t$: $$ \Big\lvert \underset{\mathbf{s},\mathbf{A},e}{\mathbb{P}}(\mathcal{D}(\mathbf{A},\mathbf{s}\mathbf{A}\oplus \mathbf{e})=1) - \underset{\mathbf{r},\mathbf{A}}{\mathbb{P}}(\mathcal{D}(\mathbf{A},\mathbf{r})=1) \Big\rvert \leq \epsilon $$ where $\mathbf{s}\xleftarrow{U}\mathbb{Z}_2^n$ is the vector to be discovered, $q\in\mathbb{N}$ is the number of samples, $\mathbf{A}\xleftarrow{U}\mathbb{Z}_2^{n\times q}$, $\mathbf{r}\xleftarrow{U}\mathbb{Z}_2^q$ and $\mathbf{e}\leftarrow Ber_\tau^q$.

Another particularly elegant way of describing the problem is the following. Given a secret $\mathbf{s} \in \mathbb{Z}_2^n$ and $\tau \in (0,1/2)$, I denote by $\Pi_{\tau,n}(\mathbf{s})$ the distribution over $\mathbb{Z}_2^n\times\mathbb{Z}_2$ sampled choosing a vector $\mathbf{a}\xleftarrow{U} \mathbb{Z}_2^n$ and outputting $( \mathbf{a},\langle \mathbf{a} , \mathbf{s} \rangle \oplus e)$ with $e\leftarrow Ber_\tau$. Hence, the hardness of LPN$_{\tau,n}$ is equivalent to $\Pi_{\tau,n}(\mathbf{s})$ and the uniform distribution over $\mathbb{Z}_2^n\times\mathbb{Z}_2$ being indistinguishable.

As an example of usage of LPN to build cryptosystems, I describe the symmetric scheme LPN-C. Let $C : \mathbb{Z}_2^r \rightarrow \mathbb{Z}_2^n$ be an $[n, r, d]$ error-correcting code (i.e. of length $n$, dimension $r$ and minimal distance $d$) with correction capacity $t = \big\lfloor \frac{d-1}{2} \big\rfloor$. The code $C$ is assumed to be publicly known. Let $\mathbf{M}$ be a secret $k\times n$ matrix constituting the secret key of the cryptosystem. To encrypt a $r$-bit vector $\mathbf{x}\in\mathbb{Z}_2^r$, the sender draws $\mathbf{a}\xleftarrow{U}\mathbb{Z}_2^k$ and computes $$ \mathbf{y} = C(\mathbf{x}) \oplus \mathbf{a}\mathbf{M} \oplus \boldsymbol\nu $$ where $\boldsymbol\nu\leftarrow Ber_\tau^n$. The ciphertext is $(\mathbf{a},\mathbf{y})$. Thanks to the fact that the receiver knows $\mathbf{M}$ and that $\mathbf{a}$ is public, the decryption algorithm is just the XOR $\mathbf{y} \oplus \mathbf{a}\mathbf{M} = C(\mathbf{x}) \oplus \boldsymbol\nu$ followed by the decoding of $C(\mathbf{x}) \oplus \boldsymbol\nu$, which is always possible in the case $HW(\boldsymbol\nu)\leq t$, otherwise $\bot$ is returned. Since the noise vector $\boldsymbol\nu$ is drawn by the sender, a simple test on its Hamming weight can be done to avoid incorrect decoding.

Learning With Errors (LWE)

The Learning With Errors (LWE) problem is a machine learning problem and its hardness reduces from worst-case lattice problems. Essentially, LWE is a generalisation of LPN to larger moduli and different error distributions, i.e. the secret vector $\mathbf{s}$ and the random vector $\mathbf{a}$ live in $\mathbb{Z}_p^n$ for a certain prime $p$ and natural $n$, while the error is drawn from a generic distribution $\chi$, which is the Bernoulli one in standard LPN. In its simplest (search) formulation, LWE asks to recover a secret vector $\mathbf{s}\xleftarrow{U}\mathbb{Z}_q^n$ from a number of samples of the form (note the extreme similarity with the correspondent equation in LPN): $$ ( \mathbf{a},\langle \mathbf{a} , \mathbf{s} \rangle + e) \in \mathbb{Z}_q^n\times\mathbb{Z}_q $$ where $\mathbf{a}\xleftarrow{U}\mathbb{Z}_q^n$ is picked uniformly at random, $e\xleftarrow{\chi}\mathbb{Z}_q$ is chosen according a certain distribution $\chi$ and addition is performed modulo $q$.

Such description, however, does not allow the construction of schemes being efficient enough for practical purposes. For this reason, an interesting variant of LWE called Ring-LWE has been developed which significantly decreases the amount of storage needed and speeds up the computations. Informally speaking, vectors of bits in $\mathbb{Z}_q^n$ are seen as coefficients of polynomials in $R_q=\mathbb{Z}_q[x]/(f)$ where $f$ is a polynomial of degree $n$ in $\mathbb{Z}_q[x]$. Hence, one element of the ring $R_q$ can stand for $n$ elements of $\mathbb{Z}_q$, thus reducing public and private keys by a factor of $n$.

A basic public-key scheme based on Ring-LWE works as follows. Let $R=\mathbb{Z}[x]/(x^n+1)$ where $n$ is a power of two and $R_q=R/qR$. Both the secret key $s$ and the error $e$ are chosen according to an error distribution $\chi$, hence $s,e\xleftarrow{\chi}R$. The public key is $(a,b=a\cdot s + e)\in R_q^2$ where $a\xleftarrow{U}R_q$. An $n$-bit message $z\in\{0,1\}^n$ is then seen as an element of $R$ via the following transformation. \[ (z_1,\dots ,z_n) \mapsto \sum_{i=1}^n z_ix^{i-1} \] Then, three "small" random elements $r,e_1,e_2 \in R$ are chosen according to $\chi$ and are used to compute the ciphertext $(u,v)\in R_q^2$ as follows. \begin{align*} u &= a \cdot r + e_1 \pmod{q} \\ v &= b \cdot r + e_2 + \Big\lfloor \frac{q}{2} \Big\rceil \cdot z \pmod{q} \end{align*} The decryption works as follows (the $\pmod{q}$ is implicit). \begin{align*} v - u\cdot s &= b \cdot r + e_2 + \Big\lfloor \frac{q}{2} \Big\rceil \cdot z - a \cdot s \cdot r - e_1 \cdot s \\ &= a\cdot s \cdot r + e\cdot r + e_2 + \Big\lfloor \frac{q}{2} \Big\rceil \cdot z - a \cdot r \cdot s - e_1 \cdot s \\ & = (e\cdot r + e_2 - e_1 \cdot s)+ \Big\lfloor \frac{q}{2} \Big\rceil \cdot z \\ & = E + \Big\lfloor \frac{q}{2} \Big\rceil \cdot z \end{align*} For a suitable choice of the parameters, $E\in R$ is a polynomial whose coefficients have magnitude less than $q/4$ (this is the reason why $r,e_1,e_2 \in R$ were "small"), so that the bits of $z$ can be recovered by rounding each coefficient of $v - u \cdot s$ back to either $0$ or $\lfloor q/2 \rceil$.

Learning With Rounding (LWR)

Among these three, the Learning With Rounding (LWR) problem is the newest. With respect to LWE, instead of adding random noise to $\langle \mathbf{a} , \mathbf{s} \rangle\in\mathbb{Z}_q$, LWR consists in rounding such value to the nearest element in a subgroup $\mathbb{Z}_p$ of $\mathbb{Z}_q$, hence computing $\lfloor\langle \mathbf{a} , \mathbf{s} \rangle\rceil_p\in\mathbb{Z}_p$. The hardness guarantee follows from the fact that, with a careful choice of the parameters, the following holds with high probability. $$ \lfloor\langle \mathbf{a} , \mathbf{s}\rangle +e\rceil_p=\lfloor\langle \mathbf{a} , \mathbf{s}\rangle\rceil_p $$ LWR has the immediate huge advantage that sampling the error $e$ is no longer needed. Moreover, since the operation of rounding is deterministic, a layer of uncertainty is cut down.

LWR can be directly used to build a deterministic encryption scheme, which is a cryptosystem always producing the same ciphertext for a given plaintext and key, even over separate executions of the encryption algorithm. Although this raises security flaws, in some situation is a desired feature (e.g. searchable databases). The parameters are $n$, $m$, $q$ and $p$. First of all, a matrix $\mathbf{A}\in\mathbb{Z}_q^{m\times n}$ statistically closed to uniform is chosen as public key while the secret key is a trapdoor function $T$. The existence of an algorithm $Invert$ that returns a secret $\mathbf{s}\in\mathbb{Z}_q^n$ given $\mathbf{A}$, $T$ and the LWE sample $\mathbf{c}=\mathbf{A}\mathbf{s} + \mathbf{e}\in\mathbb{Z}_q^m$ is assumed. Then, the encryption of an $n$-bits message $s\in\{0,1\}^n$ is just $\mathbf{c}=\lfloor\mathbf{A}\mathbf{s}\rceil_p$. The decryption algorithm takes as input the ciphertext $\mathbf{c}$ and the secret key $T$ and works in two steps:

1. $\mathbf{c}$ is transformed from a LWR sample to a LWE one by applying $\lfloor(q/p)\cdot \mathbf{c}\rceil\in\mathbb{Z}_q^m$. Indeed: \begin{align*} \lfloor(q/p)\cdot \mathbf{c}\rceil &= \lfloor (q/p)\lfloor \mathbf{A}\mathbf{s} \rceil_p\rceil \\ &= \lfloor (q/p)\lfloor (p/q)\mathbf{A}\mathbf{s} \rceil\rceil \\ &= \lfloor (q/p)((p/q)\mathbf{A}\mathbf{s} + \mathbf{e}')\rceil \\ &= \mathbf{A}\mathbf{s} + \mathbf{e} \end{align*}
2. the algorithm $Invert$ is applied to $\mathbf{A}$, $T$ and $\lfloor(q/p)\cdot \mathbf{c}\rceil$.

References

[Pie12] is a very broad survey on LPN problem and gives several cryptographic applications as well as security proofs. LWE was first introduced in [Reg05] and its ring variant can be found in [LPR10]. Finally, LWR was introduced in [BPR12] but an improved version, allowing the choice of a bigger class of parameters, is given in [AKPW13].

[AKPW13]

Joel Alwen, Stephan Krenn, Krzysztof Pietrzak, and DanielWichs. Learning with rounding, revisited. In Advances in Cryptology CRYPTO 2013, pages 57-74. Springer, 2013.

[BPR12]

Abhishek Banerjee, Chris Peikert, and Alon Rosen. Pseudorandom functions and lattices. In Advances in Cryptology EUROCRYPT 2012, pages 719- 737. Springer, 2012.

[LPR10]

Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Advances in Cryptology EUROCRYPT 2010, pages 1- 23. Springer, 2010.

[Pie12]

Krzysztof Pietrzak. Cryptography from learning parity with noise. In SOFSEM 2012: Theory and Practice of Computer Science, pages 99- 114. Springer, 2012.

[Reg05]

Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 84 -93. ACM, 2005.

Marco