Decision LWE to Search SIS 


This reduction is often used to attacks on LWE (called the dual attack). Given as input an LWE challenge $(A,b) \in \mathbb{Z}^{m \times n}_q \times \mathbb{Z}^m_q$. Forward A to an SIS-oracle which will respond with a short non-zero vector $z \in \mathbb{Z}^m$ of norm $||z|| \leq \beta$ such that $z^{T}A=0 \mod{q}$. Now, one can compute $z^Tb$. If the resulting element is short, one guesses that $(A,b)$ is a sample of LWE. Else, output that it is a uniform sample. If (A,b) is indeed an instance of LWE it yields $z^{T}b=z^{T}(As+e)=z^{T}e$, where $|z^Te| \leq ||z|| \cdot ||e||$. As both $e$ and $z$ are short, their inner product is small as well. If $b$ is uniformly random, so is $z^Tb$, and hence with reasonable proabbility not short.

Quantumly SIS to LWE


Another connection between SIS and LWE was given in Efficient Public Key Encryption Based on Ideal Lattices (Stehle et al.). More precisely, they use the duality connection between the q-ary lattice $\Lambda_q(A)$ and $\Lambda_q^{\perp}(A)$ to show a quantum reduction from SIS to search LWE. Using the reduction from decision LWE to SIS and search-to-decision for LWE, we can interpret this as both problems being quantumly equivalent. It is still an open problem to show the equivalence for purely classical reductions.

Learning with Errors and Short Integer Solution

Decision NTRU to search R-LWE


The reduction works by a "lossiness" argument. Suppose we have an oracle $\mathcal{O}$ that solves search-R-LWE with high probability, given $\mathcal{l}$ samples. Then an algorithm that solves the NTRU learning problem works as follows: given $\mathcal{l}$ samples $a_i \in R_q$ as input, it chooses a secret $s$ and errors $e_i$ from the LWE error distribution $\chi$ and gives the pairs $(a+i,b_i.= a_i \cdot s + e_i)$ to $\mathcal{O}$, which returns some $\hat{s}$. If $\hat{s}=s$, out algorithm accepts, otherwise it rejects.

NTRU to Ring Learning with Errors

Gap Shortest Vector Problem to Short Integer Solution

Shortest Vector Problem to Closest Vector Problem

Unique Shortest Vector Problem and Gap Shortest Vector Problem

Unique Shortest Vector Problem and Shortest Vector Problem

Given an SVP oracle, find the shortest vector of the lattice. The length of this lattice vector satisfies all $y$ for $y \geq | \lambda_1 |$ and for all vectors such that $y < | \lambda_1 |$, no such lattice vector exists by definition of $\lambda_1$.

Unique Shortest Vector Problem and Shortest Vector Problem

Suppose that the sequence $\{C_k\}$ is such that $(C_k)^{k/(k-1)}$ increases with $k$. Then for any $\gamma \geq \sqrt{\bar{\gamma}}_{n-1}(C_n)^{n/(n-1)}$, $\gamma$-uSVP reduces to $C_n$-HSVP.

Assume we have access to a $C_n$-HSVP oracle. Let $\mathcal{L}$ be an $n$-dimensional lattice such that $\lambda_2(\mathcal{L}) > \sqrt{\bar{\gamma}}_{n-1}(C_n)^{n/(n-1)} \lambda_1(\mathcal{L})$. Assume we are given a basis $B$ of $\mathcal{L}$. We use the HSVP oracle in the following way:
<li/> Use the oracle on the dual lattice $\mathcal{L}^* = \mathcal{L}(B^*)$, to find a short vector $c^*_1 \in \mathcal{L}^*$ in the dual lattice; Compute the largest integer $k$ such that $c^*_1$ belongs to $k \mathcal{L}^*$ and divide $c^*_1$ by $k$; Extend $c^*_1$ into a complete basis $C^*$ of $\mathcal{L}^*$. This can be done in polynomial time by considering the unimodular $n \times n$ matrix $V$ such that $(c^*_1)^tV$ is in Hermite Normal Form; the first $n-1$ rows of $V^{-1}$ complete the basis.
<li/> For $i = 2,...,n$: Project the vectors $c_i^*,...,c_n^*$ to the orthogonal complement of the space generated by $c_1^*,...,c^*_{i-1}$. Let $\bar{c}_i^*, ..., \bar{c}_n^*$ be the projected vectors. Note that the determinant of the projected lattice $\mathcal{L}([\bar{c}^{*}_{i}, ..., \bar{c}^*_n])$ is equal to
$$\frac{\det(L^*)}{\det([c^{*}_{i}, ..., c^*_{i-1}])} = \frac{\det(\mathcal{L^*})}{\prod^{i-1}_{j=1}r^*_{j,j}} = \prod^n_{j=1}r^*_{j,j},$$
where $C^* = Q^*R^*$ is the QR decomposition of $C^*$. Apply the the HSVP oracle again to find a short vector
$$\bar{v}^*_i = \sum^n_{k=i}x_k\bar{c}^*_k$$
in the projected lattice $\mathcal{L}([ \bar{c}^*_i, ..., \bar{c}^*_n ] )$; Lift it to a vector $v_i^*$ in $\mathcal{L}([c^*_i, ..., c^*_n])$ given by
$$v^*_i = \sum_{k=i}^n x_kc^*_k$$
Then replace $c^*_i$ by $v_^*_i$ and complete the dual basis. Since lifting doesn't affect the orthogonal projections nor the $r^*_{i,i} = \langle q_i^*, v^*_i \rangle$, the new basis satisfies
$$r^*_{i,i} \leq \| v^*_i \| \leq C_{n-i+1}(\prod^n_{j=i} r^*_{j,j})^{\frac{1}{n-i}}$$
and consequently
$$r^*_{i,i} \leq (C_{n-i+1})^{\frac{n-i+1}{n-i}}(\prod^n_{j=i+1} r^*_{j,j})^{\frac{1}{n-i}}$$

This property still holds at subsequent steps of the algorithm since the operation of extracting a short vector and lifting decreases $r^*_{i,i}$, and so increases $\prod^n_{j=i+1} r^*_{j,j}$.

We claim that $c_1$ in the primal basis $C = (C^*)^*$ is the shortest vector $v$ of $\mathcal{L}(B)$. We prove this fact by contradiction. Suppose that $c_1 \neq \pm v$, where $\pm v$ are the unique shortest vectors of $\mathcal{L}$. Note that $c_1$ cannot be $\pm 2 v$ or other multiples, since in that case $C$ would not be a basis of $\mathcal{L}$. We may write 

$$v = \sum^k_{i=1} x_ic_i$$
where $x_i$ is an integer and $k$ is the largest $i$ such that $x_i$ nonzero.

Observer that if $C = QR$ is the QR decomposition of $C$,
$$
\begin{align*} 
v &= \sum^k_{i=1}x_i(r_{i,i} q_i + \sum^{i-1}_{j=1} r_{j,i} q_j)\\
&= \sum^{k-1}_{i=1}(x_i r_{i,i} + \sum^k_{j=i+1} x_j r_{i,j}) q_i + x_k r_{k,k}q_k
\end{align*}$$

Since the $q_i$'s are orthogonal, we have:
$$\lambda_1 \geq \| v \| \geq \|r_{k,k} q_k \| = r_{k,k}$$
Using the assumption that $c \neq \pm v$, we have that $k > 1$. This ensures that:
$$ \lambda_2 \leq \lambda_1(\mathcal{L}[b_1, ..., b_{k-1}])$$

Indeed, the second minimum $\lambda_2$ must be no greater than the norm of the shortest nonzero vector in the sublattice spanned by $\{b_1, ..., b_{k-1} \}$, since these vectors are linearly independent with $v$. The fact that $k > 1$ ensures that there are non-zero vectors in that lattice. Using Minkowski's first theorem, we obtain
$$
\begin{align*}
\lambda_2 &\leq \sqrt{\gamma_{k-1}} \det( \mathcal{L}[b_1, ..., b_{k-1} ])^{\frac{1}{k-1}}\\
&= \sqrt{\gamma_{k-1}}(\prod^{k-1}_{i=1} r_{i,i})^{\frac{1}{k-1}}\\
&= \sqrt{\gamma_{k-1}}(\prod^{n}_{i=n-k+2} r^*_{i,i})^{-\frac{1}{k-1}}
\end{align*}
$$
where we used the relation $r_{i,i} = 1 / r^*_{n-i+1, n-i+1}$. In the meantime the HSVP oracle ensures that
$$r^*_{n-k+1, n-k+1} \leq (C_k)^{\frac{k}{k-1}} (\prod^n_{i=n-k+2} r^*_{i,i})^{\frac{1}{k-1}}$$

for any $k > 1$. Substituting, we have 
$$
\begin{align*}
\lambda_2 &\leq \sqrt{\gamma_{k-1}}(C_k)^{\frac{k}{k-1}} r_{k,k}\\
&\leq \sqrt{\bar{\gamma}_{n-1}}(C_n)^{\frac{n}{n-1}} \lambda_1\\
\end{align*}
$$

where we used the (mild) assumption that $(C_k)^{k / (k-1)}$ increases with $k$. The last statement is a contradiction because we assumed $\lambda_2 > \sqrt{\bar{\gamma}_{n-1}}(C_n)^{n / (n-1)} \lambda_1$.

Unique Shortest Vector Problem to Hermite Shortest Vector Problem

Hermite Shortest Vector Problem to Shortest Vector Problem

Hermite Shortest Vector Problem to Shortest Vector Problem

Densest Sublattice Problem to Hermite Shortest Vector Problem

Unique Shortest Vector Problem and Bounded Distance Decoding

Unique Shortest Vector Problem and Bounded Distance Decoding

Knapsack Problem and Learning with Errors


There is a reduction from (search/decision) Knapsack to (search/decision) LWE and vice versa. This equivalence is sometimes also referred to as syndrome decoding. The high level idea is the following: Sampling a uniformly random matrix $A \in \mathbb{Z}^{m,n}$ for sufficiently large $m$ (i.e. $m \geq n + \omega$(log n)), provides with overwhelming probability a non-singular matrix, that is, the rows of $A$ generate $\mathbb{Z}^n_q$. By linear algebra, we can find a mtraix $G \in \mathbb{Z}_q^{(m-n) \times m}$ such that $GA = 0 \in \mathbb{Z}_q^{(m - n) \times n}$ and such that all columns of $G$ generate $\mathbb{Z}^{m-n}_q$. We can further randomize $G$ by left-multiplying it by a random unimodular matrix (recall: this doesn't change the underlying lattice). For simplicity, let's call the randomized matrix $G$ as well . Let $(A,b)$ be an input to the LWE problem. We can transform this sample to an input sample $(G,t)$ of the knapsack by computing $t= Gb$. If $b$ was uniform, so is $t$. If $b = As + e$, it yields $t = Ge$. In other words, the noise distribution of LWE becomes the secret distribution of the Knapsack problem. The reduction in the other direct is similar.

Knapsack Problem and Learning with Errors

Learning with Errors to Sparse Learning with Errors

Learning with Errors to Sparse Learning with Errors

LWE Distribution Definition 

For a vector $s \in \mathbb{Z}^n_{q}$ called the secret, the LWE distribution $A_{s,\chi}$ over $\mathbb{Z}^n_q \times \mathbb{Z}_q$ is sampled by choosing $a \in \mathbb{Z}^n_q$ uniformly at random, choosing $e \leftarrow \chi$, and outputting $(a, b= \langle s, a \rangle + e \mod{q}$.


Search-LWE

Given $m$ independent samples $(a_i,b_i) \in \mathbb{Z_q^n} \times \mathbb{Z}_q$ drawn from $A_{s,\chi}$ for a uniformly random $s \in \mathbb{Z}^n_q$ (fixed for all samples), find $s$.


Decision-LWE

Given $m$ independent samples $(a_i,b_i) \in \mathbb{Z}^n_q \times \mathbb{Z}_q$ where every sample is distributed according to either: (1) $A_{s,\chi}$ for a uniformly random $s \in \mathbb{Z}^n_q$ (fixed for all samples), or (2) the uniform distribution, distinguish which is the case (with non-negligible advantage).

Learning with Errors

Short Integer Solution

Given $m$ uniformly random vectors $a_i \in \mathbb{Z}^n_q$ forming the columns of a matrix $A \in \mathbb{Z}^{n \times m}_q$, find a nonzero integer vector $z \in \mathbb{Z}^m$ of norm $||z|| \leq \beta$ such that 

$$f_A(z) := Az = \sum_i a_i \cdot z_i = 0 \in \mathbb{Z}^n_q$$

Short Integer Solution

Search Shortest Vector Problem 
For $\gamma=\gamma (n) \geq 1$, the search version of the approximate Shortest Vector Problem ($\gamma$-SVP) is defined as follows. On input a basis $B \in \mathbb{Q}^{n \times n}$ of a lattice $\mathcal{L}$, output a non-zero vector $v \in \mathcal{L}$ satisfying $||v|| \leq \gamma \cdot \lambda_1(\mathcal{L})$.

Shortest Vector Problem

Decisional Shortest Vector Problem


For $\gamma=\gamma(n) \geq 1$, the decision version of the $\gamma$-approximate Shortest Vector Problem ($\gamma$-GapSVP) is defined as follows. On input a basis $B \in \mathbb{Q}^{n \times n}$ of a lattice $\mathcal{L}$ and a distance threshold $r > 0$, decide whether the input satisfies


- (YES instance) $\lambda_1(\mathcal{L}) \leq r$, or 
- (NO instance) $\lambda_1(\mathcal{L}) > \gamma r$ 
when one of these cases is promised to hold.

Gap Shortest Vector Problem

Given $m$ uniformly random elements $a_i \in R_q$, defining a vector $\vec{a} \in R^m_q$, find a nonzero vector $\vec{z} \in R^m$ of norm $||\vec{z}|| \leq \beta$ such that

$$f_{\vec{a}}(\vec{z}) := \langle \vec{a},\vec{z} \rangle = \vec{a}^t \cdot \vec{z} = \sum_i a_i \cdot z_i = 0 \in R_q$$

Ring Short Integer Solution

Ring-LWE Distribution


For an $s \in R_q$ called the secret, the ring-LWE distribution $A_{s,\chi}$ over $R_q \times R_q$ is sampled by choosing $a \in R_q$ uniformly at random, choosing $e \leftarrow \chi$, and outputting $(a, b= s \cdot a + e \mod{q}$).


Decision R-LWE 


Given $m$ independent samples $(a_i,b_i) \in R_q \times R_q$ where every sample is distributed according to either: (1) $A_{s,\chi}$ for a uniformly random $s \in R_q$ (fixed for all samples), or (2) the uniform distribution, distinguish which is the case (with non-negligible advantage).

Ring Learning with Errors

NTRU Learning Problem


For an invertible $s \in R^*_q$ and a distribution $\chi$ on $R$, define $N_{s,\chi}$ to be the distribution that outputs $e/s \in R_q$ where $e \leftarrow \chi$. The NTRU learning problem is: given indepdendent samples $a_i \in R_q$ where every sample is distributed according to either: (1) $N_{s,\chi}$ for some randomly chosen $s \in R^*_q$ (fixed for all samples), or (2) the uniform distribution, distinguish which is the case (with non-negligible advantage).

NTRU

Bounded Distance Decoding


Given a basis $B$ of an n-dimensional lattice $\mathcal{L}=\mathcal{L}(B)$ and a target point $t \in \mathbb{R}^n$ with the guarantee that $dist(t,\mathcal{L}) < d = \lambda_1(\mathcal{L})/(2\gamma(n))$, find the unique lattice vector $v \in \mathcal{L}$ such that $|| t - v|| < d$.

Bounded Distance Decoding Problem

Factoring Assumption

Let GenModulus be a polynomial-time algorithm that, on input $1^n$, outputs $(N,p,q)$, where $N=pq$, and $p$ and $q$ are $n$-bit primes except with probability negligible in $n$. Factoring is hard relative to GenModulus if for all probalistic polynomial-time algorithms $\mathcal{A}$ there exists a negligible function negl such that 

$$Pr[\text{Factor}_{\mathcal{A}, \text{GenModulus}}(n)=1] \leq \text{negl}(n)$$

Factoring Assumption

Approximate Shortest Independent Vectors Problem 


Given a basis $B$ of a full-rank n-dimensional lattice $\mathcal{L}=\mathcal{L}(B)$, output a set $S = \{s_i\} \subset \mathcal{L}$ of $n$ linearly independent lattice vectors where $||s_i|| \leq \gamma(n) \cdot \lambda_n(\mathcal{L})$ for all i.

Shortest Independent Vector Problem

RSA Assumption


Let GenRSA be a probabilistic polynomial-time algorithm that, on input $1^n$, outputs a modulus $N$ that is the product of two $n$-bit primes, as well as integers $e,d > 0$ with $\text{gcd}(e,\phi(N))=1$ and $ed=1 \mod{\phi(N)}$. The algorithm may fail with probability negligible in $n$. The RSA problem is hard relative to GenRSA if for all probabilistic polynomial-time algorithms $\mathcal{A}$ there exists a negigible function negl such that $\text{PR[RSA-inv}_{\mathcal{A,\text{GenRSA}}}(n) = 1] \leq \text{negl}(n)$.

RSA Assumption

Module Short Integer Solution

Let $m,d$ and $q$ be positive integers and $\beta$ be a positive real. Given $m$ independent vectors $a_j$ sampled uniformly at random over $R^d_q$, forming the columns of a matrix $A \in R^{d \times m}_q$, the problem $M-SIS_{d,q,\beta,m}$ asks to find a nonzero vector $z \in R^m$ of norm $0 < ||z|| \leq \beta$ such that 

$$Az \sum_{i=1}^m z_i a_i = 0 \mod{q}$$

Module Short Integer Solution

Module Learning with Errors Distribution


Let $d$ and $q$ be positive integers and let $\chi$ be a distribution over $R$. For a fixed secret $s \in R^d_q$, the M-LWE distribution $A_{s,\chi}$ over $R^d_q \times R_q$ is obtained by choosing $a \leftarrow U(R^d_q), e \leftarrow \chi$ and outputting $(a,b) = \langle s, a \rangle + e \mod{q}$


Module Learning with Errors (Search) 


Let $m$ be a positive integer. Given $m$ independent samples $(a_i,b_i) \in R^d_q \times R_q$ from $\mathcal{A}_{s,\chi}$ for a uniformly random $s \in R^d_q$. The problem $\text{search-M-LWE}_{d,q,\chi,m}$ asks to find $s$.

 
Module Learning with Errors (Decision) 

Let $m$ be a positive integer. Given $m$ independent samples $(a_i,b_i) \in R^d_q \times R_q$ that are either drawn from $\mathcal{A}_{s,\chi}$ for a uniformly random $s \in R^d_q$ or drawn from the uniform distribution $U(R^d_q \times R_q)$. The problem $\text{dec-M-LWE}_{d,q,\chi,m}$ asks to distinguish both cases with non-negligible advantage.

Module Learning with Errors

Successive Minima Problem 


Given a basis of $L$, find a linearly independent set $\{y_1,...,y_d\}$ in $L$ such that $||y_i|| = \lambda_i(L)$ for $i=1,...,d$.

Successive Minima Problem

Given a basis of $L$ and an approximation factor $\gamma \geq 1$, find a basis $\{b_1,...,b_d \}$ of $L$ with $\text{max}_i||b_i|| \geq \gamma \text{min} \{ \text{max}_i \|a_i\| | \{a_i,...,a_d \}$ is a basis of $L \}$.

Shortest Basis Problem

Approximate Closest Vector Problem


Given a basis of $L$, a target $t \in \mathbb{R}^d$ and an approximation factor $\gamma \geq 1$, find $y \in L$ such that $\|t - y \| \leq \gamma d(t,L)$.


The Decision Closest Vector Problem

Given a basis of $L$, a target vector $t \in \mathbb{R}^d$ and a radius $r > 0$, decide whether there exists a $y \in L$ such that $\| y - t \| \leq r$.

Closest Vector Problem

Approximate Shortest Length Problem


Given a basis of $L$ and an approximation factor $\gamma > 1$, find a $\lambda$ such that $\lambda_1(L) \leq \lambda \leq \gamma \lambda_1(L)$.

Shortest Length Problem

Unique Shortest Vector Problem


Given a basis of $L$ and a gap factor $\gamma \geq 1$, find (if it exists) the unique nonzero $y \in L$ such that any $v \in L$ with $\| v \| \leq \gamma \| y \|$ is an integral multiple of y.

Unique Shortest Vector Problem

Hermite Shortest Vector Problem


Given a basis of $L$ and an approximation factor $\gamma > 0$, find $y \in L$ such that $0 < \|y \| \leq \gamma \cdot vol(L)^{1/d}$.

Hermite Shortest Vector Problem

Densest Sublattice Problem 


For $n \geq \mathcal{l} \geq 1$ and $\gamma \geq 1$, the $(n, \mathcal{l}, \gamma$)-approximate densest sublattice problem ($(n,\mathcal{l},\gamma)$-DSP is defined as follows. The input is (a basis for) a rank-n lattice $\mathcal{L} \subset \mathbb{Q}^d$, for some $d \geq n$. The output is (a basis for) a sublattice $\mathcal{L}' \subset \mathcal{L}$ of rank $\mathcal{l}$ satisfying $\gamma(\mathcal{L}',\mathcal{L}) \leq \gamma$.

Densest Sublattice Problem

Discrete Logarithm Assumption


The Discrete Logarithm Assumption (DL) is a cryptographic assumption over certain cyclic groups. Given a PPT algorithm 
$$(\mathbb{G},G, q) \leftarrow \text{GroupGen}(1^\lambda)$$

which takes a security parameter $\lambda$ and produces the description of a cyclic group $\mathbb{G}$ of order $q$ generated by a single group element $G$, the discrete logarithm assumption asserts that for all PPT algorithms $\mathcal{A}$,

$$\Pr [\mathcal{A}(\mathbb{G},G,q, x \cdot G] = x : (\mathbb{G}, G, q) \leftarrow \text{GroupGen}(1^\lambda)$$
In other words, given an element $x \cdot G$, $x$ cannot efficiently be found.

Discrete Logarithm Assumption

Diffie-Hellman Assumption


The Diffie-Hellman Assumption is a cryptographic assumption over certain cyclic groups. Given a PPT algorithm

$$(\mathbb{G}, G, q) \leftarrow \text{GroupGen}(1^\lambda)$$

which takes a security parameter $\lambda$ and produces the description of a cyclic group $\mathbb{G}$ of order $q$ generated by a single group element $G$, the Diffie-Hellman assumption comes in several flavors:

 Decisional Diffie-Hellman Assumption

The Decisional Diffie-Hellman Assumption asserts that if
$$(\mathbb{G}, G, q) \leftarrow \text{GroupGen}(1^\lambda), (x,y,z) \leftarrow \mathbb{Z}^3_q$$

then

$$(G,q, x \cdot G, y \cdot G, y \cdot z \cdot G) \approx_c (G, q, x \cdot G, y \cdot G, z \cdot G)$$

In other words, given $x \cdot G$ and $y \cdot G$ (and knowledge of the group in which these elements lie) , $y \cdot x \cdot G$ cannot be edfficiently distinguished from $z \cdot G$ for some random $z$.


Computational Diffie-Hellman Assumption (CDH)

The computational Diffie-Hellman Assumption asserts that for all PPT algorithms $\mathcal{A}$,
$$\Pr[\mathcal{A}(G,q, x \cdot G, y \cdot G) = y \cdot x \cdot G) = y \cdot x \cdot G : \\ (\mathbb{G},G,q) \leftarrow \text{GroupGen}(1^\lambda), (x,y) \leftarrow \mathbb{Z}^2_q] \in \text{negl}(\lambda)$$

In other words, given $x \cdot G$ and $y \cdot G$ (and knowledge of the group in which these elements lie), $y \cdot x \cdot G$ cannpt be efficiently calculated. Note that this is implied by DDH.

The Gap Diffie-Hellman Assumption 


The Gap Diffie-Hellman Assumption (GDH) asserts that CDH holds but DDH does not.

Diffie-Hellman Assumption

Decisional Linear Assumption


The Decisional Linear Assumption (DLin) is a cryptographic assumption over certain cyclic groups. Given a PPT algorithm

$$(\mathbb{G},G,q) \leftarrow \text{GroupGen}(1^\lambda)$$
which takes a security parameter $\lambda$ and produces the description of a cyclic group $\mathbb{G}$ of order $q$ generated by a single group element $G$, the decision linear assumption asserts that if

$$(\mathbb{G},G,q) \leftarrow \text{GroupGen}(1^\lambda), (U,V,W) \leftarrow \mathbb{G}^3, (x,y,z) \leftarrow \mathbb{Z}^3_q$$

then

$$(U,V,W,q,x \cdot U, y \cdot V, (x+y) \cdot W) \approx_c (U, V, W, q, x \dot U, y \cdot V, z \cdot W)$$

In other words, given $x \cdot U$ abd $y \cdot V$ and knowledge of the three basepoints $U,V$ and $W$ and teh group in which all five points lie, $(x + y) \cdot W$ cannot be efficiently distinguished from $z \cdot W$ for some random $z$.

Decisional Linear Assumption

Elliptic Curve Discrete Logarithm Problem


Given a point $P$ of order $n$ in an elliptic curve $E$ over a finite field $\mathbb{F}_q$ and a point $Q$ in the subgroup of $E$ generated by $P$, denoted by $\langle P \rangle$, the ECDLP is to find an inteer $m$, where $0, \leq m \leq n - 1$, such that $Q \ m \cdot P$.

Elliptic Curve Discrete Logarithm Problem

Elliptic Curve Diffie-Hellman Problem


Given a point $P$ of order $n$ in an elliptic curve $E$ over a finite field $\mathbb{F}_q$ and two points $(k \cdot P)$ and $(l \cdot P)$, the ECDHP is to find the point $(kl \cdot P)$.

Elliptic Curve Diffie-Hellman Problem

Hidden Subgroup Problem 


Let $G$ be a group, $X$ a finite set, and $f : G \rightarrow X$ a function such that there exists a subgroup $H < G$ for which $f$ separates cosets of $H$. Using information gained from evaluations of $f$, determine a generating set for $H$.

Hidden Subgroup Problem

Knapsack Problem


We have a set of objects, each with a specific value $(v_i)$ and its respective weight $(w_i)$. We also have a knapsack, with a limited space of $W$ and the goal is to fit as many objects in the knapsack as we can in order to achieve the maximum profit. Each object can either be selected or not selected, so the problem is usually referred to as the 0-1 Knapsack Problem.

Knapsack Problem

Sparse Learning with Errors Assumption

Let $k = k(n) \ in [0,n], p = p(n) : \mathbb{N} \rightarrow \mathbb{N}, \sigma = \sigma(n) : \mathbb{N} \rightarrow \mathbb{N}, m = m(n) : \mathbb{N} \rightarrow \mathbb{N}$ be efficiently computable functions (computable in time polynomial in n). We say that the sparse LWE assumption with respect to sparsity $k(n)$, prime modulus $p(n)$, noise parameter $\sigma = \sigma(n)$ and sample complexity $m(n)$ holds, denoted as the $\text{sLWE}_{n,k,m,p,\sigma}$ assumption, if for every non-uniform p.p.t. adversary $\mathcal{A}$, the distinguishing advantage in winning the $\text{sLWE}_{n,k,m,p,\sigma}$ distinguishing problem is bounded by some negligible function $\text{negl}(n)$.
We say that the sparse LWE assumption with respect to sparsity $k(n)$, prime modulus $p(n)$, noise parameter $\sigma = \sigma(n)$ and unbounded polynomial number of samples holds, denoted as the $\text{sLWE}_{n,k,p,\sigma}$ assumption, if the above condition holds for every non-uniform p.p.t. adversary $\mathcal{A}$, and every polynomial $m(n)$.

We say that the subexponential $\text{sLWE}_{n,k,m, p,\sigma}$ (respectively $\text{sLWE}_{n,k,p,\sigma}$) assumption holds if there exists a constant $\epsilon \in (0,1)$, such that, every non-uniform probabilistic $poly(2^{n^\epsilon})$-time adversary $\mathcal{A}$ (and respectively every polynomial $m(n)$), the distinguishing advantage in winning the $\text{sLWE}_{n,k,m,o,\sigma}$ distinguishing problem is bounded by $1 / \text{poly}(2^{n^\epsilon})$.

Sparse Learning with Errors

Graph Isomorphism Problem


A graph is a set (the set of vertices) endowed with an irreflexive, symmetric binary relation called adjacency. Isomorphisms are adjacency-preseving bijections between the sets of vertices. The Graph Isomorphism (GI) problem asks to determine whether two given graphs are isomorphic.

Graph Isomorphism Problem

Code Equivalence Problem


Let $\mathbb{F}$ be a finite field and let $G_1$ and $G_2$ be generator matrices of two linear codes $C_1$ and $C_2$ over $\mathbb{F}$. We say that $G_1$ and $G_2$ are code-equivalent, denote $G_1 \sim G_2$, if the sets $C_1$ and $C_2$ are the same, up to a fixed permutation on the coordinates of the codewords of $C_1$. In other words, $G_1 \sim G_2$ if and only if both matrices have the same order $k \times n$, and there exist an $n \times n$ permutation matrix $P$ and a nonsingular $k \times k$ matrix $S$ over $F$ such that $G_1 = S G_2 P$. The problem of deciding whether two generator matrices are code-equivalent will be referred to as the Code Equivalence problem.

Code Equivalence Problem

Dense-Sparse Learning Parity with Noise (Informal)


Let $k \geq 3$ be a constant, and consider parameters $n \in \mathbb{N}, m = m(n) < n^{k/2}$, and $\epsilon = \epsilon (n) < 1$. Let $\mathcal{M}_{sp}$ be an efficiently sampleable "good" distribution over all k-sparse matrices in $\mathbb{F}_2^{n \times m}$. We say that the $(n, m,k, \mathcal{M}_{sp}, \epsilon)$-Dense-Sparse LPN assumption holds if the following two distributions are computationally indistinguishable:

$$\{(\text{TM,sTM + e})\}_{n \in \mathbb{N}} \approx_c \{(\text{TM,u)}\}_{n \in \mathbb{N}}$$

where $T \leftarrow \mathbb{F}_2^{n/2 \times n}$, $M \leftarrow \mathcal{M}_{sp}, s \leftarrow \mathbb{F}_2^{1 \times n/2}, e \leftarrow \text{Ber}(\epsilon)^{1 \times m}$, and $u \leftarrow \mathbb{F}_2^m$


Decisional $(\mathcal{M}, \epsilon)$-LPN

Dense-Sparse Learning Parity with Noise

Quadratic Residuosity Problem

Covering Radius Problem

An input to $\text{GapCRP}_\gamma$ is a pair $(\text{B},d)$ where $\text{B}$ is an n-dimensional lattice basis and d is a rational number. In YES inputs $v(B) \leq d$ and in NO inputs $v(B) > \gamma(n) \cdot d$

Covering Radius Problem

Lattice Isomorphism Problem

Given two lattices $\mathcal{L}_1$ and $\mathcal{L}_2$ the
goal is to decide whether there exists an orthogonal linear transformation mapping $\mathcal{L}_1$ to $\mathcal{L}_2$.

CryptoMap

Welcome to cryptographymap.com