Stefano Tessaro

Abstract. This paper gives the first lattice-based two-round threshold signature scheme that tolerates the adaptive corruption of up to T − 1 out of N signers. Our construction is based on the MLWE and MSIS assumptions. We substantially improve upon the only existing adaptively secure lattice-based construction, recently given by Katsumata, Reichle, and Takemure (CRYPTO ’24), which requires five rounds.

Tweed: Adaptively Secure Lattice-Based Two-Round Threshold Signatures (Kaijie Jiang, Stefano Tessaro, Hoeteck Wee, Chenzhi Zhu) ia.cr/2026/417

Abstract. Over the past two decades, several works have used (almost) k-wise independence as a proxy for pseudorandomness in block ciphers, since it guarantees resistance against broad classes of statistical attacks. For example, even the case k = 2 already implies security against differential and linear cryptanalysis. Hoory, Magen, Myers, and Rackoff (ICALP ’04; TCS ’05) formulated an appealing conjecture: if the sequential composition of T independent local randomized permutations is (close to) four-wise independent, then it should also be a pseudorandom permutation. Here, “local” means that each output bit depends on only a constant number of input bits. This conjecture offers a potential strong justification for analyses of block ciphers that establish (almost) k-wise independence of this type of constructions. In this work, we disprove the conjecture in full generality by presenting an explicit local randomized permutation whose sequential composition is four-wise independent, but not a pseudorandom permutation. Our counterexample in fact extends to k-wise independence for any constant k.

Image showing part 2 of abstract.

When Simple Permutations Mix Poorly: Limited Independence Does Not Imply Pseudorandomness (Jesko Dujmovic, Angelos Pelecanos, Stefano Tessaro) ia.cr/2025/2282

Their job is to write stories people click on so that their advertisers get to show their ads. This one worked better on that front than writing something positive about our community.

And now we are famous: www.nytimes.com/2025/11/21/w... - congratulations to all colleagues who made the NYT (both through quotes, by playing a role, or by being on this picture)

PSA: A 2-out-3 access structure is not necessarily better than a 3-out-3 access structure.

Join us at the UW Paul G. Allen School of Computer Science & Engineering. We are hiring tenure-track faculty positions. Apply here: apply.interfolio.com/174303

Abstract. This paper studies the concrete security of BBS signatures (Boneh, Boyen, Shacham, CRYPTO ’04; Camenisch and Lysyanskaya, CRYPTO ’04), a popular algebraic construction of digital signatures which underlies practical privacy-preserving authentication systems and is undergoing standardization by the W3C and IRTF. Sch"age (Journal of Cryptology ’15) gave a tight standard-model security proof under the q-SDH assumption for a less efficient variant of the scheme, called BBS+–here, q is the number of issued signatures. In contrast, the security proof for BBS (Tessaro and Zhu, EUROCRYPT ’23), also under the q-SDH assumption, is tight. Nonetheless, this recent proof shifted both standardization and industry adoption towards the more efficient BBS, instead of BBS+, and for this reason, it is important to understand whether this tightness gap is inherent. Recent cryptanalysis by Chairattana-Apirom and Tessaro (ASIACRYPT ’25) also shows that a tight reduction to q-SDH is the best we can hope for. This paper closes this gap in two different ways. On the positive end, we show a novel tight reduction for BBS in the case where each message is signed at most once–this case covers in particular the common practical use case which derandomizes signing. On the negative end, we use a meta-reduction argument to prove that if we allow generating multiple signatures for the same message, then {} algebraic reduction to q-SDH (and its variants) can be tight.

Image showing part 2 of abstract.

Tight Security for BBS Signatures (Rutchathon Chairattana-Apirom, Dennis Hofheinz, Stefano Tessaro) ia.cr/2025/1973

Abstract. Very recently, Crites et al. (CRYPTO 2025) gave a proof for the full adaptive security of FROST (Komlo and Goldberg, SAC 2020), the state-of-the-art two-round threshold Schnorr signature scheme, which is currently used in real-world applications and is covered by an RFC standard. Their security proof, however, relies on the computational hardness of a new search problem they call “low-dimensional vector representation” (LDVR). In fact, the authors show that hardness of LDVR is necessary for adaptive security of a large class of threshold Schnorr signatures to hold, including FROST and its two-round variants. Given that LDVR is a new assumption and its hardness has not been seriously scrutinized, it remains an open problem whether a two-round threshold Schnorr signature with full adaptive security can be constructed based on more well-established assumptions. In this paper, we resolve this open problem by presenting ms-FROST. Our scheme is partially non-interactive and supports any t - 1 < n adaptive corruptions, where n is the number of signers and t is the signing threshold. Its security relies on the algebraic one-more discrete logarithm (AOMDL) assumption, the algebraic group model (AGM), and the random oracle model (ROM). Further, it achieves the strongest security notion (TS-UF-4) in the security hierarchy of Bellare et al. (CRYPTO 2022). To justify our use of the algebraic group model, we show an impossibility result: We rule out any black-box algebraic security reduction in the ROM from AOMDL to the adaptive TS-UF-0 security of ms-FROST.

Image showing part 2 of abstract.

Adaptively Secure Partially Non-Interactive Threshold Schnorr Signatures in the AGM (Renas Bacho, Yanbo Chen, Julian Loss, Stefano Tessaro, Chenzhi Zhu) ia.cr/2025/1953

Abstract. Privacy-preserving advertisement attribution allows websites selling goods to learn statistics on which advertisement campaigns can be attributed to converting sales. Existing proposals rely on users to locally store advertisement history on their browser and report attribution measurements to an aggregation service (instantiated with multiparty computation over non-colluding servers). The service computes and reveals the aggregate statistic. The service hides individual user contributions, but it does not guarantee integrity against misbehaving users that may submit fraudulent measurements. Our work proposes a new cryptographic primitive, “secret share attestation”, in which secret shares input into a multiparty computation protocol are accompanied by an attestation of integrity by a third party: advertisers include signature attestations when serving ads that are later included in contributed measurements. We propose two constructions based on the standards-track BBS signatures and efficient signatures over equivalence classes, respectively. We implement and evaluate our protocols in the context of the advertising application to demonstrate their practicality.

Image showing part 2 of abstract.

Fraud Mitigation in Privacy-Preserving Attribution (Rutchathon Chairattana-Apirom, Stefano Tessaro, Nirvan Tyagi) ia.cr/2025/1891

I still don’t understand this deranged game, but judging by the citywide scream, it must have ended well.

Abstract. We consider FB-PRF, one of the key derivation functions defined in NIST SP 800-108 constructed from a pseudorandom function in a feedback mode. The standard allows some flexibility in the specification, and we show that one specific instance of FB-PRF allows an efficient distinguishing attack.

A Note on Feedback-PRF Mode of KDF from NIST SP 800-108 (Ritam Bhaumik, Avijit Dutta, Tetsu Iwata, Ashwin Jha, Kazuhiko Minematsu, Mridul Nandi, Yu Sasaki, Meltem Sönmez Turan, Stefano Tessaro) ia.cr/2025/1586

Abstract. This paper studies the security of key derivation functions (KDFs), a central class of cryptographic algorithms used to derive multiple independent-looking keys (each associated with a particular context) from a single secret. The main security requirement is that these keys are pseudorandom (i.e., the KDF is a pseudorandom function). This paper initiates the study of an additional security property, called key control (KC) security, first informally put forward in a recent update to NIST Special Publication (SP) 800-108 standard for KDFs. Informally speaking, KC security demands that, given a known key, it is hard for an adversary to find a context that forces the KDF-derived key for that context to have a property that is specified a-priori and is hard to satisfy (e.g., that the derived key consists mostly of 0s, or that it is a weak key for a cryptographic algorithm using it). We provide a rigorous security definition for KC security, and then move on to the analysis of the KDF constructions specified in NIST SP 800-108. We show, via security proofs in the random oracle model, that the proposed constructions based on XOFs or hash functions can accommodate for reasonable security margins (i.e., 128-bit security) when instantiated from KMAC and HMAC. We also show, via attacks, that all proposed block-cipher based modes of operation (while implementing mitigation techniques to prevent KC security attacks affecting earlier version of the standard) only achieve at best 72-bit KC security for 128-bit blocks, as with AES.

Image showing part 2 of abstract.

Cryptographic Treatment of Key Control Security – In Light of NIST SP 800-108 (Ritam Bhaumik, Avijit Dutta, Akiko Inoue, Tetsu Iwata, Ashwin Jha, Kazuhiko Minematsu, Mridul Nandi, Yu Sasaki, Meltem Sönmez Turan, Stefano Tessaro) ia.cr/2025/1123

Abstract. BBS/BBS+ signatures are the most promising solution to instantiate practical and lightweight anonymous credentials. They underlie standardization efforts by the W3C and the IRTF. Due to their potential for large scale deployment, it is paramount to understand their concrete security, but a number of questions have been left open by prior works. To this end, the security proofs by Au et al. (SCN ’06), Camenisch et al. (TRUST ’16), and Tessaro and Zhu (EUROCRYPT ’23) show reductions from q-SDH in groups of prime order p, where q is the number of issued signatures. However, these prior works left the possibility open that BBS/BBS+ is “even more secure” than what can be guaranteed by such proofs. Indeed, while the q-SDH assumption is subject to an attack that uses $O(\sqrt{p/q})$ group exponentiations (Cheon, EUROCRYPT ’06) for several choices of q, no attack with a similar complexity appears to affect either of BBS+ and “deterministic” BBS, for which the best known attacks amount to recovering the secret key by breaking the discrete logarithm problem. The assumption that this attack is best possible also seemingly justifies the choice of parameters in practice. Our result shows that this expectation is not true. We show new attacks against BBS+ and deterministic BBS which, after seeing q signatures, allow us to recover the secret key with the same complexity as solving the Θ(q)-Discrete Logarithm problem, which in turn is proportional to $O(\sqrt{p/q})$ for many choices of q. Further, we also extend the attack to a reduction showing that the security of BBS+ and deterministic BBS implies the Θ(q)-SDH assumption.

Image showing part 2 of abstract.

On the Concrete Security of BBS/BBS+ Signatures (Rutchathon Chairattana-Apirom, Stefano Tessaro) ia.cr/2025/1093

Abstract. FROST and its variants are state-of-the-art protocols for threshold Schnorr signatures that are used in real-world applications. While static security of these protocols has been shown by several works, the security of these protocols under adaptive corruptions—where an adversary can choose which parties to corrupt at any time based on information it learns during protocol executions—has remained a notorious open problem that has received renewed attention due to recent standardization efforts for threshold schemes. We show adaptive security (without erasures) of FROST and several variants under different corruption thresholds and computational assumptions. Let n be the total number of parties, t+1 the signing threshold, and t_c an upper bound on the number of corrupted parties. 1. We prove adaptive security when t_c = t/2 in the random oracle model (ROM) based on the algebraic one-more discrete logarithm assumption (AOMDL)—the same conditions under which FROST is proven statically secure. 2. We introduce the low-dimensional vector representation (LDVR) problem, parameterized by t_c, t, and n, and prove adaptive security in the algebraic group model (AGM) and ROM based on the AOMDL assumption and the hardness of the LDVR problem for the corresponding parameters. In some regimes (including some t_c >t/2) we show the LDVR problem is unconditionally hard, while in other regimes (in particular, when t_c = t) we show that hardness of the LDVR problem is necessary for adaptive security to hold. In fact, we show that hardness of the LDVR problem is necessary for proving adaptive security of a broad class of threshold Schnorr signatures.

Image showing part 2 of abstract.

On the Adaptive Security of FROST (Elizabeth Crites, Jonathan Katz, Chelsea Komlo, Stefano Tessaro, Chenzhi Zhu) ia.cr/2025/1061

Abstract. Anonymous rate-limited tokens are a special type of credential that can be used to improve the efficiency of privacy-preserving authentication systems like Privacy Pass. In such a scheme, a user obtains a “token dispenser” by interacting with an issuer, and the dispenser allows the user to create up to a pre-determined number k of unlinkable and publicly verifiable tokens. Unlinkable means that one should not be able to tell that two tokens originate from the same dispenser, but also they cannot be linked to the interaction that generated the dispenser. Furthermore, we can limit the rate at which these tokens are created by linking each token to a context (e.g., the service we are authenticating to), and imposing a limit N ≤ k such that seeing more than N tokens for the same context will reveal the identity of the user. Constructions of such tokens were first given by Camenisch, Hohenberger and Lysyanskaya (EUROCRYPT ’05) and Camenisch, Hohenberger, Kohlweiss, Lysyanskaya, and Meyerovich (CCS ’06). In this work, we present the first construction of anonymous rate-limited tokens, for which unlinkability holds against computationally unbounded adversaries, whereas other security properties (e.g., unforgeability) remain computational. Our construction relies on pairings. While several parameters in our construction unavoidably grow with k, the key challenge we resolve is ensuring that the complexity of dispensing a token is independent of the parameter k. We are motivated here by the goal of providing solutions that are robust to potential future quantum attacks against the anonymity of previously stored tokens. A construction based on post-quantum secure assumptions (e.g., based on lattices) would be rather inefficient—instead, we take a pragmatic approach dispensing with post-quantum security for properties not related to privacy.

Image showing part 2 of abstract.

Everlasting Anonymous Rate-Limited Tokens (Rutchathon Chairattana-Apirom, Nico Döttling, Anna Lysyanskaya, Stefano Tessaro) ia.cr/2025/1030

I feel G1 arithmetic speed up would make it much more interesting. But arguably, this is subjective, and depends on what you are working on. Cool either way.

I am worried about my reputation …

Knowing you, 3:20/km 5 x 800m on your first try.

Intervals (mostly) is not cardio 🤔

Congratulations!

The context was that this would maintain the rotation. Of course without that, Europe works just fine

Also, I think Mexico City would be an amazing location :-)

Of course. All I am saying is that someone needs to do it and submit a proposal. One word of caution is that South America is very easy for Europeans/Americans, but for others who need a visa could be very painful.

The obvious barrier is that you need to find a place with local organizers wanting to do it. For example, it wouldn't be easy for someone in the US to organize it in Mexico. So Canada becomes the obvious choice, with several visa issues even worse than the US.

But in all fairness, this just happened. I did not attend RWC due to a temporary effort to reduce travel costs. The point is that RWC is rotating exactly for this reason.

To be clear, I am not involved … (nobody at UW is)

Oh … sorry! But the PNW can be very beautiful in the rain, too. Just need the occasional escape…

Successful escape from PNW weather - Spring Break edition

New paper!

We have extended the submission deadline for the International Workshop on Foundations and Applications of Privacy-Enhancing Cryptography (PrivCrypt) by two weeks to April 4, 2025, AoE. Please help spread the word and consider submitting your work to join us in Munich in Summer 😎