# What does the "Type 1 query" model on Miles, Sahai, and Zhandry's paper?

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\}) + ...$$

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?

• Side note: I just realized that we don't have tags for neither multilinear maps nor obfuscation. Jul 8, 2017 at 11:44

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$).