Is there an efficient construction for a trilinear pairing that has been used in theory or practice

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?

• It just occurred to me if this question might actually reduce to Bilinear Decisional Diffie Hellman? Any thoughts on that? Feb 4, 2014 at 12:17
• Just to clarify: by $G_1$ you mean an arbitrary (finitely presented) group? Feb 4, 2014 at 18:00
• $G_1$ is a cyclic group. $g$ is a generator of $G_1$ Feb 5, 2014 at 5:08

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 and Coron, Lepoint, Tibouchi.

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.

• "<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.) Apr 9, 2014 at 6:32
• 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) Apr 12, 2014 at 16:47
• 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. Apr 13, 2014 at 0:22

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.