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?

  • $\begingroup$ It just occurred to me if this question might actually reduce to Bilinear Decisional Diffie Hellman? Any thoughts on that? $\endgroup$ – Subhayan Feb 4 '14 at 12:17
  • $\begingroup$ Just to clarify: by $G_1$ you mean an arbitrary (finitely presented) group? $\endgroup$ – Klaus Draeger Feb 4 '14 at 18:00
  • $\begingroup$ $G_1$ is a cyclic group. $g$ is a generator of $G_1$ $\endgroup$ – Subhayan Feb 5 '14 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.

  • 1
    $\begingroup$ "<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.) $\endgroup$ – Daniel Apon Apr 9 '14 at 6:32
  • 1
    $\begingroup$ 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) $\endgroup$ – Subhayan Apr 12 '14 at 16:47
  • 2
    $\begingroup$ 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. $\endgroup$ – Daniel Apon Apr 13 '14 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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