0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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, 2014 at 12:17
  • $\begingroup$ Just to clarify: by $G_1$ you mean an arbitrary (finitely presented) group? $\endgroup$
    – Klaus Draeger
    Feb 4, 2014 at 18:00
  • $\begingroup$ $G_1$ is a cyclic group. $g$ is a generator of $G_1$ $\endgroup$
    – Subhayan
    Feb 5, 2014 at 5:08

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 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, 2014 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, 2014 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, 2014 at 0:22
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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