Tessera

Folgen

Toomas Krips

@toomaskrips.bsky.social

Lecturer in Cryptography in University of Tartu. Secure Multiparty Computation, Zero-Knowledge.

16 Posts123 Follower 63 Folgt

Toomas Krips @toomaskrips.bsky.social · last yr.

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

ePrint Updates @eprint.ing.bot · last yr.

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.

Toomas Krips @toomaskrips.bsky.social · 2y ago

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

Toomas Krips @toomaskrips.bsky.social · 2y ago

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.

ePrint Updates @eprint.ing.bot · 2y ago

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.

Diego F. Aranha @dfaranha.bsky.social · 2y ago

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

Mike Agrenius Kushner @1bitofentropy.bsky.social · 2y ago

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"