On the paper Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13, authors present, in section 2, an abstract model to analyze security of $i\mathcal{O}$ and current multilinear maps candidates.

In this model, there are two queries that an attacker may do, but I'm now interested on the first one: the Type 1 query, which works as follows:

The attacker has a polynomial $p_k = p_k^{(0)}(\{X_j\}, \{Z_i\}) + gp_k^{(1)}(\{X_j\}, \{Z_i\}) + g^2p_k^{(2)}(\{X_j\}, \{Z_i\}) + ...$ on variables $X_j$, $Z_i$, and $g$, and it may submit this polynomial to the challenger. Then, the challenger answers in the following way:

If $p_k$ is identically 0, then the adversary receives $\perp$ in return. If $p_k^{(0)}$ is not identically 0, then the adversary receive $\perp$ in return. If $p_k$ is not 0 but $p_k^{(0)}$ is identically 0, then the adversary receives a handle to a new variable $W_k$, which is set to be $p_k / g = p_k^{(1)}(\{X_j\}, \{Z_i\}) + gp_k^{(2)}(\{X_j\}, \{Z_i\}) + ...$.

So, this is my doubt... At first glance, it seemed to me that this query was trying to model the fact that the attacker can multiply the zero-testing parameter $p_{zt} := [hz^kg^{-1}]_q$ by the high-level encoding $u$ it has (as if he/she would test $u$ encodes a zero) but without ending the test to get a bit (encodes or not a zero), taking, instead, another ring element.

In this case, the polynomial $p_k$ would model a level-$k$ encoding. Thus, the two cases where the symbol $\perp$ is returned make sense, but the third case is weird, because I don't see how the returned expression $p_k / g$ may be obtained from $p_{zt}$. It seems that the value $hz^k$ is missing, I mean, I was expecting that

$$p_k \cdot p_{zt} = hz^k p_k / g = hz^k p_k^{(1)}(\{X_j\}, \{Z_i\}) + hz^kgp_k^{(2)}(\{X_j\}, \{Z_i\}) + ...$$

would be returned instead.

Then, am I right about supposing that this query really models the ability of performing a product by the public parameter $p_{zt}$?

If so, how could the value $ p_k / g $ be returned?

  • $\begingroup$ Side note: I just realized that we don't have tags for neither multilinear maps nor obfuscation. $\endgroup$ – Hilder Vitor Lima Pereira Jul 8 '17 at 11:44

Based on the author's presentation at CRYPTO 2016 (available on youtube), we see that the Type 1 query is really modeling the attacker's ability of multiplying the zero-testing parameter by the values it has.

The point is that this abstract query is conservative in the sense that it gives to the attacker more power than it would have (a priori) in practical in multilinear maps setting. Also, this query is modeled like that because it is likely that if an attacker can get the expressions I described as the expected ones, than she/he can also get the ones returned by the queries (for instance, by recovering $g$ and dividing the value $ p_k $ she/he has to get $ p_k / g $).

  • $\begingroup$ I have answered it by myself just to reduce the statistics of "unanswered questions" here. But if you have something to add, feel free to writing another answer and if it is better than mine, I can even mark yours the correct one (: $\endgroup$ – Hilder Vitor Lima Pereira Oct 11 '17 at 8:07

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.