Toomas Krips

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

Multiparty Homomorphic Secret Sharing and More from LPN and MQ We give the first constructions of multiparty pseudorandom correlation generators, distributed point functions, and (negligible-error) homomorphic secret sharing for constant-degree polynomials for an...

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)

Multi-Party Distributed Point Functions with Polylogarithmic Key Size from Invariants of Matrices Distributed point functions (DPFs), introduced in 2014, are a widely used primitive in secure computation for a wide variety of applications. However, until now, constructions for DPFs with polylogari...

Me and Pille Pullonen-Raudvere uploaded a paper to ePrint called Multi-Party Distributed Point Functions with Polylogarithmic Key Size from Invariants of Matrices. (eprint.iacr.org/2025/978). It is a candidate solution for multiparty distributed point functions with a polylogarithmic cost. (1/12)

Abstract. Distributed point functions (DPFs), introduced in 2014, are a widely used primitive in secure computation for a wide variety of applications. However, until now, constructions for DPFs with polylogarithmic-size keys have been known only for the two-party setting. We propose a scheme for a polylogarithmic-size DPF for an arbitrary number of parties. We use a technique where a secret-shared vector is mapped to collinear vectors by public matrices serves as an invariant for off-path leaves. We show, using a technique by Shamir, that when we work over Z_pq , these vectors are hard to compute if factoring is hard. We also show that our scheme is a secure DPF, provided that two new assumptions hold, one of which is related to Generic Group Model and the other to MinRank. The output of our scheme is in the exponent in some group where Diffie-Hellman type problems are hard. Although this limits the usability of our scheme, we believe that our scheme is the first distributed point function for more than two parties with a key size that is polylogarithmic in the size of the domain and that does not use fully homomorphic encryption.

Image showing part 2 of abstract.

Multi-Party Distributed Point Functions with Polylogarithmic Key Size from Invariants of Matrices (Toomas Krips, Pille Pullonen-Raudvere) ia.cr/2025/978

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)

SLAMP-FSS: Two-Party Multi-Point Function Secret Sharing from Simple Linear Algebra Multi-point function secret sharing (FSS) is a building block for pseudo- random correlation generators used in the novel silent correlation generation methods for various secure multiparty computatio...

We updated our eprint "SLAMP-FSS: Two-Party Multi-Point Function Secret Sharing from Simple Linear Algebra" on eprint recently. Our previous construction for multipoint FSS required solving systems of linear equations over finite fields which is somewhat costly. (1/2) eprint.iacr.org/2024/1394

Just submitted a paper to CRYPTO with Pille Pullonen-Raudvere. If the new assumption we made is legitimate, this is a solution to a problem that I have been working with since 2021, and to which I have about 250 solutions that do not work. Fingers crossed that this paper won't be the 251th one.

Abstract. The Fiat-Shamir (FS) transform is a prolific and powerful technique for compiling public-coin interactive protocols into non-interactive ones. Roughly speaking, the idea is to replace the random coins of the verifier with the evaluations of a complex hash function. The FS transform is known to be sound in the random oracle model (i.e., when the hash function is modeled as a totally random function). However, when instantiating the random oracle using a concrete hash function, there are examples of protocols in which the transformation is not sound. So far all of these examples have been contrived protocols that were specifically designed to fail. In this work we show such an attack for a standard and popular interactive succinct argument, based on the GKR protocol, for verifying the correctness of a non-determinstic bounded-depth computation. For every choice of FS hash function, we show that a corresponding instantiation of this protocol, which was been widely studied in the literature and used also in practice, is not (adaptively) sound when compiled with the FS transform. Specifically, we construct an explicit circuit for which we can generate an accepting proof for a false statement. We further extend our attack and show that for every circuit C and desired output y, we can construct a functionally equivalent circuit C^(*), for which we can produce an accepting proof that C^(*) outputs y (regardless of whether or not this statement is true). This demonstrates that any security guarantee (if such exists) would have to depend on the specific implementation of the circuit C, rather than just its functionality. Lastly, we also demonstrate versions of the attack that violate non-adaptive soundness of the protocol – that is, we generate an attacking circuit that is independent of the underlying cryptographic objects. However, these versions are either less practical (as the attacking circuit has very large depth) or make some additional (reasonable) assumptions on the underlying cryptographic primitives.

Image showing part 2 of abstract.

How to Prove False Statements: Practical Attacks on Fiat-Shamir (Dmitry Khovratovich, Ron D. Rothblum, Lev Soukhanov) ia.cr/2025/118

We are hiring a PhD student to work on applied cryptographic protocol design at Aarhus University: phd.nat.au.dk/for-applican...

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.

Joke about environmentally friendly cryptography. "Sustainable Cryptography Initiative Reduce: use less different keys Reuse: key pairs are still usable after the expiration date Recycle: publish your private key so less key mining is needed"