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.

  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jun 19 at 17:26


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.