<p>This question has been open for long now, and after some research I think I have the following answer</p>

<p>There has been two candidate schemes proposed for multilinear pairing by <a href="https://eprint.iacr.org/2012/610" rel="nofollow">Garg, Gentry,  Halevi</a> and <a href="https://eprint.iacr.org/2013/183" rel="nofollow">Coron, Lepoint, Tibouchi</a>.</p>

<p>However either do not have a security proof and their security is given by extensive cryptanalysis. </p>

<p>So, to sum it up, although it is possible to implement a "trilinear" map, these maps are NOT (provably) cryptographically secure. </p>

CC BY-SA 3.0
2014-04-09T06:32:04.110Z
"<snip>..these maps are NOT (provably) cryptographically secure."

For what it's worth, there is no proof that the *bilinear* (computational) Diffie-Hellman problem is hard. It's just convenient to assume it's intractable since (1) it leads to good schemes, and (2) we don't know an attack yet.

Same thing here. (Except multilinear maps are newer.)
Daniel Apon
CC BY-SA 3.0
2014-04-12T16:47:14.627Z
YES, exactly.. bilinear pairing have come a long way.. while Multilinear maps do exists, their system (space) requirements make them far from practical (I think)
Subhayan
CC BY-SA 3.0
2014-04-13T00:22:58.800Z
Yes, space is the main constraint. For security parameter $\lambda\in\mathbb{N}$, the bit-size of the original GGH public params is $\tilde{O}(\lambda^5)$, which makes a home PC have a memory overflow after about multilinearity 10 or so. But..

1) GGHLite, at Eurocrypt 2014 (no public version yet, that I can tell), gives public params with $\tilde{O}(\lambda)$.

2) Many applications of multilinear maps (e.g. obfuscation) do not require the "full" public params; their space complexity is dominated by the actual encodings, not the params used to generate encodings as in MMap schemes themselves.
Daniel Apon
CC BY-SA 3.0
2014-04-07T09:54:33.030Z
2014-04-07T09:54:33.030Z
Subhayan
<p>I could use one that actually is NOT efficient in the target group, more of a trilinear hash.  <span class="math-container">$H(u G, f G, H_g(v_0)/u + H_g(v_1)/u)$</span>.  If <span class="math-container">$(u G)$</span> is a user's pairing key, and the file's pairing key is <span class="math-container">$(f G)$</span>, then this is a trivial way to do collusion-resistant key derivation for cpabe.</p>

CC BY-SA 4.0
2021-12-28T10:27:42.303Z
2021-12-28T10:27:42.303Z
rob
<p>A trilinear pairing is defined a function $e:G_1^3 \rightarrow G_2$, such that it satisfies the property $e(k_1^a, k_2^b, k_3^c) = e(k_1,k_2,k_3)^{abc}$</p>

<p>In general I am trying to solve the following problem,
given a tuple $$(g, g^s, g^{r_1}, g^{r_2}, k_1, k_2, k_1^{r_1s},k_2^{r_2s'} )$$
where $g, k_1,k_2 ∈ G_1$ and $r_1, r_2, s,s' ∈ {Z_q}$ </p>

<p>Is it possible to predict if $s = s'$?</p>

<p>One of the easy ways is to use trilinear mapping function $e$ to evaluate
$$e(g^{r_2}, k_1^{r_1s}, k_2 ) = e(g^{r_1}, k_1, k_2^{r_2s'})$$</p>

<ol>
<li><p>However this can only be true if there exists an efficient construction of a trilinear pairing... 
Is there a feasible construction available for a trilinear mapping or at least is it/has it been used in theory and in proofs?</p></li>
<li><p>Is there any other way to examine the same?</p></li>
</ol>

CC BY-SA 3.0
2014-02-04T12:17:01.980Z
It just occurred to me if this question might actually reduce to Bilinear Decisional Diffie Hellman? Any thoughts on that?
Subhayan
CC BY-SA 3.0
2014-02-04T18:00:55.603Z
Just to clarify: by $G_1$ you mean an arbitrary (finitely presented) group?
Klaus Draeger
CC BY-SA 3.0
2014-02-05T05:08:48.487Z
$G_1$ is a cyclic group. $g$ is a generator of $G_1$
Subhayan
<reference-request><cr.crypto-security>
Is there an efficient construction for a trilinear pairing that has been used in theory or practice
Subhayan
# Is there an efficient construction for a trilinear pairing that has been used in theory or practice

(Asked by: username_0 on 2014-02-02)

A trilinear pairing is defined a function $e:G\_1^3 \rightarrow G\_2$, such that it satisfies the property $e(k\_1^a, k\_2^b, k\_3^c) = e(k\_1,k\_2,k\_3)^{abc}$

In general I am trying to solve the following problem,
given a tuple $$(g, g^s, g^{r\_1}, g^{r\_2}, k\_1, k\_2, k\_1^{r\_1s},k\_2^{r\_2s'} )$$
where $g, k\_1,k\_2 ∈ G\_1$ and $r\_1, r\_2, s,s' ∈ {Z\_q}$

Is it possible to predict if $s = s'$?

One of the easy ways is to use trilinear mapping function $e$ to evaluate
$$e(g^{r\_2}, k\_1^{r\_1s}, k\_2 ) = e(g^{r\_1}, k\_1, k\_2^{r\_2s'})$$

1. However this can only be true if there exists an efficient construction of a trilinear pairing...
   Is there a feasible construction available for a trilinear mapping or at least is it/has it been used in theory and in proofs?
2. Is there any other way to examine the same?

**Tags:** reference-request, cr.crypto-security
> **Comments:**
> **username_0**: It just occurred to me if this question might actually reduce to Bilinear Decisional Diffie Hellman? Any thoughts on that?  
> **username_1**: Just to clarify: by $G_1$ you mean an arbitrary (finitely presented) group?  
> **username_0**: $G_1$ is a cyclic group. $g$ is a generator of $G_1$  

---

## 2 answers

### Answer by username_0 on 2014-04-07. Score: 1 | Accepted answer

This question has been open for long now, and after some research I think I have the following answer

There has been two candidate schemes proposed for multilinear pairing by [Garg, Gentry, Halevi](https://eprint.iacr.org/2012/610) and [Coron, Lepoint, Tibouchi](https://eprint.iacr.org/2013/183).

However either do not have a security proof and their security is given by extensive cryptanalysis.

So, to sum it up, although it is possible to implement a "trilinear" map, these maps are NOT (provably) cryptographically secure.

> **Comments:**
> **username_2**: "<snip>..these maps are NOT (provably) cryptographically secure."  For what it's worth, there is no proof that the *bilinear* (computational) Diffie-Hellman problem is hard. It's just convenient to assume it's intractable since (1) it leads to good schemes, and (2) we don't know an attack yet.  Same thing here. (Except multilinear maps are newer.)  
> **username_0**: YES, exactly.. bilinear pairing have come a long way.. while Multilinear maps do exists, their system (space) requirements make them far from practical (I think)  
> **username_2**: Yes, space is the main constraint. For security parameter $\lambda\in\mathbb{N}$, the bit-size of the original GGH public params is $\tilde{O}(\lambda^5)$, which makes a home PC have a memory overflow after about multilinearity 10 or so. But..  1) GGHLite, at Eurocrypt 2014 (no public version yet, that I can tell), gives public params with $\tilde{O}(\lambda)$.  2) Many applications of multilinear maps (e.g. obfuscation) do not require the "full" public params; their space complexity is dominated by the actual encodings, not the params used to generate encodings as in MMap schemes themselves.  

---

### Answer by username_3 on 2021-12-28. Score: 1

I could use one that actually is NOT efficient in the target group, more of a trilinear hash. $H(u G, f G, H\_g(v\_0)/u + H\_g(v\_1)/u)$. If $(u G)$ is a user's pairing key, and the file's pairing key is $(f G)$, then this is a trivial way to do collusion-resistant key derivation for cpabe.


---

