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:

enter image description here

enter image description here

  • $\begingroup$ 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). $\endgroup$
    – DrLecter
    Commented Oct 26, 2013 at 14:31
  • $\begingroup$ @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. $\endgroup$ Commented Oct 26, 2013 at 23:54

2 Answers 2


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


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

  • $\begingroup$ 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? $\endgroup$ Commented Oct 29, 2013 at 0:38
  • $\begingroup$ 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 ;) $\endgroup$
    – DrLecter
    Commented Oct 29, 2013 at 10:54
  • $\begingroup$ I have created a new question: crypto.stackexchange.com/questions/11376/… $\endgroup$ Commented Oct 29, 2013 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.

  • 2
    $\begingroup$ 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) $\endgroup$
    – tylo
    Commented Oct 28, 2013 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.