... were forced to hurry with that proof due to a deadline so that particular proof sketch is a bit rough. Nevertheless, we hope that this approach opens up a new avenue of techniques for the multiparty DPF problems. Feel free to ask questions about this paper. (12/12)

...could reduce the problem to some version of MinRank, as the matrices at every level form a MinRank problem. However, those MinRank problems are tangled with each other in a highly nontrivial way, thus we were forced to come up with a new assumption about eigenvectors. To be frank, we ...(11/12)

... this scalar product. We thus get the correctness of the scheme. As for the security, we show that if we work over Z_pq, and double all the values, then learning any of the secret vectors is as hard as factoring. This of course does not give the security of the scheme. We hoped that we ...(10/12)

..generalized eigenvectors. At the end, we have a situation that the active node has the value z_n and all the inactive nodes have a vector collinear to w_n. As a last step, we have a vector d (in the exponent), that is chosen such that <d,w_n>=0 and <d,z_n>=beta. The last operation is ... (9/12)

...publicly known matrices. At i-th level, there are two important secret vectors z_i and w_i. z_i is the secret value for the active node. w_i, up to collinearity,is the secret value for all the inactive nodes. The matrices are chosen in such a way that they map w_i to w_{i+1}, a kind of... (8/12)

...the other does not. All the operators keep the zero values to be zero. We build upon this construction but use different kinds of operators and a different kind(s) of invariant(s) for inactive nodes. Namely, we use a secret-shared vector over a ring as the secret state,the operators are...(7/12)

... in the path to the active leaf, the shared state is nonzero, and zero elsewhere. There are two possible operators at every level, we use one of them based on what the i-th bit of the value at which we evaluate our DPF at. On the active path, one of them makes the nonzero value into zero,...(6/?)

Boyle et al considered that the parties have a secret-shared state and that both parties apply some locally evaluatable operator to their state, with the property that if the secret-shared state becomes zero at a node, then all its descendants become zero. It is invariant that... (5/12)

The main idea builds upon the 2-party DPF construction of Boyle et al. Essentially, we frame the problem as a binary tree with n levels where one secret leaf is the active leaf where the parties are supposed to obtain a shared nonzero value, and should obtain a zero in the other leaves (4/12)

Our construction takes a different approach from those two works. As an upside, we get a construction where the key size of one computing party does not depend on the number of parties, as a downside, our construction depends on some new assumptions, thus making it potentially less secure. (3/12)

We thought that our result was the first multiparty DPF with a polylogarithmic cost, an open problem for ten years, but we did miss a work by Couteau and Kumar (eprint.iacr.org/2025/269), also, a follow-up work that was put to eprint a few days ago (eprint.iacr.org/2025/966) (2/12)

However, in the updated version, we saw that it is sufficient to work with systems on linear equations where the coefficients are just bits, which gives a great speedup to that particular part, and also makes evaluation much faster, as we don't need finite-field multiplications. (2/2)

The thing I have been working the most at for the last month is on overleaf, but today I missed the apparent overleaf-down issues by writing an application for a project instead. There is probably a moral somewhere in this story.