Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
In the abstract of "Cryptography with Tamperable and Leaky Memory", at the end of the 3rd paragraph, the authors say:
In both schemes we rely on the linear assumption over bilinear groups.
What is the linear assumption ? How do you break this linear assumption ?
I would appreciate if somebody could give me concrete examples. More specifics about the paper where they talk about linear assumption:
Ok, I took a look at the paper now. Thomas described the DLIN assumption, which is, however, not the assumption used in the paper you are looking at.
Furthermore, what Thomas describes is the 2-DLIN assumption, which can be generalized to the $d$-DLIN assumption in a straightforward manner:
$d$-DLIN Assumption:
Given a group $G$ of prime order $p$, the tuples
$(g_1,\ldots,g_{d+1},g_1^{r_1},\ldots, g_d^{r_d},g_{d+1}^{\sum_{i=1}^d} r_i)$
and
$(g_1,\ldots,g_{d+1},g_1^{r_1},\ldots, g_d^{r_d},g_{d+1}^{r_{d+1}})$
are indistinguishable.
What you are looking at:
The paper actually uses a matrix form of the linear assumption which has been introduced here (see Appendix A) and further used in the reference 7 of the paper cited in the paper you are looking at (which is this one).
Matrix $d$-Linear Assumption:
We have a group $G$ of prime order $p$ and $g$ a generator. Let $R = \{r_i,_j\} \in Z_p^{a\times b}$, $i\in[a],j\in[b]$ be a matrix and denote by $g^R$ the matrix $\{g_{i,j}\} = \{g^{r_{i,j}}\} \in G^{a\times b}$, $i\in[a],j\in[b]$.
Let $Rk_i(Z_p^{a\times b})$ the set of $a\times b$ matrices over $Z_p$ of rank $i$.
Then the matrix $d$-linear assumption states, that for any integers $a$ and $b$, and for any $d \leq i < j \leq \min\{a, b\}$ the tuples $(g, g^R)$ for $R\in Rk_i(Z_p^{a\times b})$ and $(g, g^R)$ for $R\in Rk_j(Z_p^{a\times b})$ are indistinguishable.
The proof that the $d$-Linear assumption implies the matrix $d$-Linear assumption can be found in the paper references above. This should be your starting point and makes more sense in the screenshots you provided.
The problem you are referring to seems to be the Decisional Linear Assumption (DLIN), which states that given $(u,v,u^a,v^b)\in \mathbb{G}^4$, it is hard to distinguish a couple $(h,h^{a+b}) \in \mathbb{G}^2$ from a totally random couple $(h,h') \in \mathbb{G}^2$.
There is also the Computational Linear Assumption (CLIN), which states that it is hard to compute $h^{a+b}$ given $(u,v,u^a,v^b,h)$.
The Decisional Linear Assumption is a weaker assumption (in the sense that it's harder to break) than Decisional Diffie-Hellman Assumption (DDH), so it can come in handy when DDH does not hold, which often happens in pairing-based cryptography. According to this paper (page 9), we even have the following reduction : $$DDH < DLIN < CLIN < CDH$$
I tried to sum up what I found but I'm not an expert in pairing-based crypto so I hope everything was correct.
