Toomas Krips
LightNews LightNews
toomaskrips.bsky.social
Toomas Krips
@toomaskrips.bsky.social
120 followers 62 following 16 posts
Lecturer in Cryptography in University of Tartu. Secure Multiparty Computation, Zero-Knowledge.
Posts Replies Media Videos
toomaskrips.bsky.social
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)
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...
eprint.iacr.org
June 2, 2025 at 10:40 AM
Reposted by Toomas Krips
eprint.ing.bot
Multi-Party Distributed Point Functions with Polylogarithmic Key Size from Invariants of Matrices (Toomas Krips, Pille Pullonen-Raudvere) ia.cr/2025/978
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.
June 2, 2025 at 2:52 AM
toomaskrips.bsky.social
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
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...
eprint.iacr.org
April 16, 2025 at 7:08 PM
toomaskrips.bsky.social
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.
February 14, 2025 at 11:39 AM
Reposted by Toomas Krips
eprint.ing.bot
How to Prove False Statements: Practical Attacks on Fiat-Shamir (Dmitry Khovratovich, Ron D. Rothblum, Lev Soukhanov) ia.cr/2025/118
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.
January 27, 2025 at 1:59 AM
Reposted by Toomas Krips
dfaranha.bsky.social
We are hiring a PhD student to work on applied cryptographic protocol design at Aarhus University: phd.nat.au.dk/for-applican...
SCI: Secure Computing Infrastructures
phd.nat.au.dk
January 14, 2025 at 9:45 PM
Reposted by Toomas Krips
1bitofentropy.bsky.social
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"
November 27, 2024 at 8:17 AM