# Circuit depth of linear algebra operations

I was checking the following paper [1] about low-depth PRFs from lattices. In table 1 on page 4, there is comparison with other constructions, and it shows evaluation depths of certain PRFs. I'm not sure I understand the computations of the evaluation depths. For example, in the table for [BP14] it says that the depth is $$\Omega(\log^2 \lambda)$$, where $$\lambda$$ is the security parameter. But if one looks at that construction, the PRF is evaluated as follows.

Let $$g = (1,2,4,\ldots,2^{\ell - 1}) \in \mathbb{Z}_q^\ell$$, for an integer $$q$$. Let $$G^{-1} \colon \mathbb{Z}_q^{n \times n\ell} \to \{0,1\}^{n\ell \times n\ell}$$, such that for all $$A \in \mathbb{Z}_q^{n \times n\ell}$$ we have that $$G \cdot G^{-1} = A$$, where $$G = g^t \otimes I_n = diag(g^t,\ldots,g^t) \in \mathbb{Z}_q^{n \times n\ell}$$. Consider a full binary tree $$T$$, and denote with $$|T|$$ the number of its leaves. If $$|T| \geq 1$$, let $$T.l$$ and $$T.r$$ denote the left and right subtree of $$T$$. Given two matrices $$A_0,A_1 \in \mathbb{Z}_q^{n \times n\ell}$$ and a full binary tree $$T$$, define the function $$A_T \colon \{0,1\}^{|T|} \to \mathbb{Z}_q^{n \times n\ell}$$ recursively as $$A_T(x) = \begin{cases} A_x &\text{if } |T| = 1 \\ A_{T.l}(x_l) \cdot G^{-1}(A_{T.r}(x_r)) &\text{otherwise }\end{cases}$$ where in the second case we parse $$x = x_l || x_r$$ for $$x_l \in \{0,1\}^{|T.l|}$$ and $$x_r \in \{0,1\}^{|T.r|}$$.

Then, the PRF is computed as $$F_{\mathbf{s}}(x) = \lfloor \mathbf{s}^t \cdot \mathbf{A}_T(x) \rceil_p$$, for modulus $$p \leq q$$ and some $$\mathbf{s} \in \mathbb{Z}_q^n$$.

So, if linear operations over $$\mathbb{Z}_q$$ can be performed by depth-one arithmetic circuit, shouldn't the depth here be defined by the number of recursive calls to $$A_T$$? So it should be proportional to the depth of tree $$T$$ and so depth should be $$\Omega(\log \lambda)$$ instead of $$\Omega(\log^2 \lambda)$$? In Section 2.2 of [BP14] there is some explanation on depth, but it did not clarify it for me. A clarification on this depth computation and in general depth of linear algebra operations is highly welcomed.

• I suggest that you edit your question to include a citation towards the papers you are reading (e.g., title, authors, where published), so that others with a similar question about the same paper can fidn this page via web search.
– D.W.
Jun 19 at 17:26