# What does the linear assumption over bilinear groups mean?

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:

• Can you be a bit more specific or state the assumption given in the paper. Unfortunately, i have no access from home and also did not find the paper online. A typical linear assumption is the decision linear assumption (DLIN) which states that in a group $G$ of prime order $p$ distinguishing between $(aP,bQ,cR)$ and $(aP,bQ,(a+b)R)$ for generators $P,Q,R$ is hard (there is also a computational variant thereof). – DrLecter Oct 26 '13 at 14:31
• @DrLecter - I have added two snapshots of the paper where it discusses linear assumption. I would be particularly interested if you could explain how they break the linear assumption at the bottom paragraph discussing b' not existing in ker(a). Please break it down into simple understandable concepts. – user1068636 Oct 26 '13 at 23:54

## 2 Answers

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.

• How can this matrix d-linear assumption be broken? In the 2nd snapshot I provide above the authors claim if b' \in ker(a) but b' is not in the subspace of B then it breaks this assumption. Could you explain why this is the case? – user1068636 Oct 29 '13 at 0:38
• I'm not familiar with the schemes in the paper you have referenced. But as soon as I find some time I'll have a look at it and then try to formulate an answer ;) – DrLecter Oct 29 '13 at 10:54
• I have created a new question: crypto.stackexchange.com/questions/11376/… – user1068636 Oct 29 '13 at 20:16

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.

• The order of problems is surely wrong: In bilinear groups DDH is easy (by using the pairing) while CDH is still hard. However, DLIN is also considered hard (That's the reason for using DLIN: A decisional problem, that holds in these groups, when DDH does not). From the paper the correct reduction is: DLIN implies CLIN, CLIN implies CDH. Since we know DDH is easy, it wont imply the other problems (but if you can solve DLIN, you also solve DDH). If you want to order the problems, we get DDH < DLIN < CLIN < CDH (if you solve CDH, everything is easy; if you solve DDH, you cant solve the others) – tylo Oct 28 '13 at 10:12