In pairing-based cryptography, we have 3 types, namely Type-I, where $\mathbb{G}_1 = \mathbb{G}_2$, and in Type-II and Type-III we have that $\mathbb{G}_1 \neq \mathbb{G}_2$, however in Type-II we have an efficiently computable homomorphism between $\mathbb{G}_1$ and $\mathbb{G}_2$, however in Type-III, we do not have this homomorphism.

Now, going over the definition of multilinear maps here [BWZ14] (pages 4 and 5), the authors define two multilinear maps, where one is called asymmetric. Where the asymmetricity come in this situation? As in the first definition (which I just called symmetric for a lack of a better name), do we have to consider that all the $n$ groups $\mathbb{G}_1,\ldots,\mathbb{G}_n$ are the same group? Because, there the definition does not say this. And why the use of integer vectors for indexing in the asymmetric case?

  • 1
    $\begingroup$ "Because, there the definition does not say this" unfortunately, it is not rare that the authors do not pay much attention in writing well the definitions because they implicitly suppose that the readers work on the field and, therefore, already know the correct definitions. So, if you find something strange like this again in the future, try to check the cited papers to find the original definitions. $\endgroup$ Jun 25 '19 at 17:11

Symmetric means that the source group and all the intermediate groups are the same, i.e. $\mathbb{G}_1 = \mathbb{G}_2 = ... = \mathbb{G}_{n-1}$ using the notation of the paper you linked, while asymmetric means that they can be different.

Check, for instance, remark 1 on the original paper about multilinear maps.

And about the vectors as indices, the aim is just to identify the levels more clearly. Since you have $2^n$ levels, you could use numbers from $0$ to $2^n-1$ to identify them, but then, increasing the levels with the multiplication would not have this nice interpretation of adding the entries of the vectors (or, equivalently, doing a union of the sets that represent the levels).

In several papers, for the symmetric scenario, we have a ring $R$ and an invertible element $z \in R$. Then, the map goes from $(z^{-1}R)^n$ to $z^{-n}R$. But, since the schemes are actually graded, you can apply the map partially and get elements in $z^{-k}R$ for $k < n$. Then, this $k$ is the level.

So, basically, we have elements of the form $r_i / z$ and you can multiply $n$ of them to get $(\prod_{i=1}^nr_i) / z^n \in z^{-n}R$.

In the asymmetric scenario, instead of a single $z$, we have $z_1$, .., $z_n$. Then, the map goes from $z_1^{-1}R \times ... \times z_n^{-1}R$ to $(z_1^{-1}\cdots z_n^{-1})R$.

So, you have elements $r_j / z_i$ and you can multiply them. But now, you can get any product of $z_i$'s in the denominator, so, it is easier to represent the levels by the exponents of each $z_i$, or, equivalently, with an $n$-dimensional integer vector.

For example, considering $n = 4$, an element $r / (z_1 z_3)$ is in level $(1, 0, 1, 0)$, and an element $r' / z_4$ is in level $(0, 0, 0, 1)$. Therefore, combining them (applying the map partially), gives us $r r' / (z_1 z_3 z_4)$ that is in level $(1, 0, 1, 1)$.

Thus, the vectors used to represent the levels tell us which groups were already used in evaluation of the map.

  • $\begingroup$ Thanks for the answer. $\endgroup$
    – tinker
    Jun 25 '19 at 19:47

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.