## Thursday, January 21, 2016

### ECRYPT CSA Spring School on Symmetric Crypto

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

## Monday, January 18, 2016

### 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!

## Sunday, January 17, 2016

### 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.*

###

Part 1: Verifiable Computation

*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.

*f(x)*comprises the following two phases:

The verifier (or a party he trusts) expresses the function**Program representation (or a**rithmetization):*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*Typically, the format these constraints needs to have is that of degree-2 polynomials that equal 0 when they (and the function_{1},x_{2},x_{3}).*f*) are satisfied.**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.

### Part 1.5: Excursion to Caesarea and Binyamina Winery

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

## Sunday, January 10, 2016

### Threshold implementations

**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$.**

$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:

- Uniform masking
- Correctness
- Non-Completness
- Uniformity of a sharing

\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.

## Thursday, January 7, 2016

### Max Levchin Prize @ RealWorldCrypto 2016

- 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.

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.

## Monday, January 4, 2016

### 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:

- $\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*}
- 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