Stefano Tessaro
LightNews LightNews
banner
stefanotessaro.bsky.social
Stefano Tessaro
@stefanotessaro.bsky.social
500 followers 250 following 28 posts
Professor at the University of Washington, Paul G. Allen School of Computer Science & Engineering @uwcse.bsky.social

Working on cryptography, theoretical computer science, and computer security.

https://homes.cs.washington.edu/~tessaro/
Posts Replies Media Videos
Reposted by Stefano Tessaro
jonfroehlich.bsky.social
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
Apply - Interfolio {{$ctrl.$state.data.pageTitle}} - Apply - Interfolio
apply.interfolio.com
October 28, 2025 at 8:55 PM
Reposted by Stefano Tessaro
eprint.ing.bot
Tight Security for BBS Signatures (Rutchathon Chairattana-Apirom, Dennis Hofheinz, Stefano Tessaro) ia.cr/2025/1973
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.
October 25, 2025 at 6:20 PM
Reposted by Stefano Tessaro
eprint.ing.bot
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. 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.
October 20, 2025 at 1:40 PM
Reposted by Stefano Tessaro
eprint.ing.bot
Fraud Mitigation in Privacy-Preserving Attribution (Rutchathon Chairattana-Apirom, Stefano Tessaro, Nirvan Tyagi) ia.cr/2025/1891
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.
October 12, 2025 at 9:19 PM
Reposted by Stefano Tessaro
eprint.ing.bot
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. 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.
September 5, 2025 at 11:33 AM
Reposted by Stefano Tessaro
eprint.ing.bot
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. 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.
June 16, 2025 at 9:21 PM
Reposted by Stefano Tessaro
eprint.ing.bot
On the Concrete Security of BBS/BBS+ Signatures (Rutchathon Chairattana-Apirom, Stefano Tessaro) ia.cr/2025/1093
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.
June 12, 2025 at 12:26 PM
Reposted by Stefano Tessaro
eprint.ing.bot
On the Adaptive Security of FROST (Elizabeth Crites, Jonathan Katz, Chelsea Komlo, Stefano Tessaro, Chenzhi Zhu) ia.cr/2025/1061
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.
June 9, 2025 at 3:28 AM
Reposted by Stefano Tessaro
eprint.ing.bot
Everlasting Anonymous Rate-Limited Tokens (Rutchathon Chairattana-Apirom, Nico Döttling, Anna Lysyanskaya, Stefano Tessaro) ia.cr/2025/1030
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.
June 3, 2025 at 8:16 PM
stefanotessaro.bsky.social
Successful escape from PNW weather - Spring Break edition
March 23, 2025 at 8:38 PM
stefanotessaro.bsky.social
New paper!
eprint.ing.bot ePrint Updates @eprint.ing.bot · Mar 21
Server-Aided Anonymous Credentials (Rutchathon Chairattana-Apirom, Franklin Harding, Anna Lysyanskaya, Stefano Tessaro) ia.cr/2025/513
Abstract. This paper formalizes the notion of server-aided anonymous credentials (SAACs), a new model for anonymous credentials (ACs) where, in the process of showing a credential, the holder is helped by additional auxiliary information generated in an earlier (anonymous) interaction with the issuer. This model enables lightweight instantiations of ‘publicly verifiable and multi-use’ ACs from pairing-free elliptic curves, which is important for compliance with existing national standards. A recent candidate for the EU Digital Identity Wallet, BBS#, roughly adheres to the SAAC model we have developed; however, it lacks formal security definitions and proofs. In this paper, we provide rigorous definitions of security for SAACs, and show how to realize SAACs from the weaker notion of keyed-verification ACs (KVACs) and special types of oblivious issuance protocols for zero-knowledge proofs. We instantiate this paradigm to obtain two constructions: one achieves statistical anonymity with unforgeability under the Gap q-SDH assumption, and the other achieves computational anonymity and unforgeability under the DDH assumption. Image showing part 2 of abstract.
March 21, 2025 at 2:32 AM
Reposted by Stefano Tessaro
drl3c7er.bsky.social
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 😎
drl3c7er.bsky.social Daniel Slamanig @drl3c7er.bsky.social · Jan 24
We are organising the International Workshop on Foundations and Applications of Privacy-Enhancing Cryptography (PrivCrypt) - co-located with ACNS 2025 end of June in beautiful Munich.

Submission deadline is March 21, 2025 (AoE).

Please help spread the word! 🙏

privcryptworkshop.github.io
PrivCrypt 2025
privcryptworkshop.github.io
March 20, 2025 at 8:12 AM
Reposted by Stefano Tessaro
edlazowska.bsky.social
www.theatlantic.com/ideas/archiv...
The Cost of the Government’s Attack on Columbia
American universities have given the country prosperity and security. The Trump administration’s attack on academic freedom endangers all of that.
www.theatlantic.com
March 19, 2025 at 3:59 PM
Reposted by Stefano Tessaro
eprint.ing.bot
The Algebraic One-More MISIS Problem and Applications to Threshold Signatures (Chenzhi Zhu, Stefano Tessaro) ia.cr/2025/436
Abstract. This paper introduces a new one-more computational problem for lattice-based cryptography, which we refer to as the Algebraic One-More MISIS problem, or AOM-MISIS for short. It is a modification of the AOM-MLWE problem recently introduced by Espitau et al. (CRYPTO ’24) to prove security of new two-round threshold signatures. Our first main result establishes that the hardness of AOM-MISIS is implied by the hardness of MSIS and MLWE (with suitable parameters), both of which are standard assumptions for efficient lattice-based cryptography. We prove this result via a new generalization of a technique by Tessaro and Zhu (EUROCRYPT ’23) used to prove hardness of a one-more problem for linear hash functions assuming their collision resistance, for which no clear lattice analogue was known. Since the hardness of AOM-MISIS implies the hardness of AOM-MLWE, our result resolves the main open question from the work of Espitau et al., who only provided a similar result for AOM-MLWE restricted to selective adversaries, a class which does not cover the use for threshold signatures. Furthermore, we show that our novel formulation of AOM-MISIS offers a better interface to develop tighter security bounds for state-of-the-art two-round threshold signatures. We exemplify this by providing new proofs of security, assuming the hardness of MLWE and MSIS, for two threshold signatures, the one proposed in the same work by Espitau et al., as well as a recent construction by Chairattana-Apirom et al. (ASIACRYPT 2024). For the former scheme, we also show that it satisfies the strongest security notion (TS-UF-4) in the security hierarchy of Bellare et al. (CRYPTO ’22), as a result of independent interest. Image showing part 2 of abstract.
March 8, 2025 at 1:37 AM
Reposted by Stefano Tessaro
rrwilliams.bsky.social
New paper: Simulating Time With Square-Root Space

people.csail.mit.edu/rrw/time-vs-...

It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}].

To appear in STOC. Comments are very welcome!
people.csail.mit.edu
February 21, 2025 at 10:19 PM
Reposted by Stefano Tessaro
carlbergstrom.com
1. Today the NIH director issued a new directive slashing overhead rates to 15%.

I want to provide some context on what that means and why it matters.

grants.nih.gov/grants/guide...
NOT-OD-25-068: Supplemental Guidance to the 2024 NIH Grants Policy Statement: Indirect Cost Rates
NIH Funding Opportunities and Notices in the NIH Guide for Grants and Contracts: Supplemental Guidance to the 2024 NIH Grants Policy Statement: Indirect Cost Rates NOT-OD-25-068. OD
grants.nih.gov
February 8, 2025 at 12:18 AM
Reposted by Stefano Tessaro
lance.fortnow.com
NSF is getting back to business due to a court order.

Order: nsf-gov-resources.ns...

Details: new.nsf.gov/executiv...
February 2, 2025 at 9:31 PM
stefanotessaro.bsky.social
I found this video (www.youtube.com/watch?v=CiOy...) more informative than any news article this morning. Not an expert, but sadly this appears to be a significant failure in designing procedures meant to be fault-tolerant.
Audio of MID-AIR CRASH into Potomac River | Regional Jet and Black Hawk Helicopter
YouTube video by VASAviation -
www.youtube.com
January 30, 2025 at 3:50 PM
stefanotessaro.bsky.social
I wonder if we can attack more examples where (1) circuits are adaptively chosen by the adversary, and (2) security proof is in the ROM. It always felt like playing with fire (because ROM does not model potential circuit dependence on the hash function), and this work nicely confirms the concern.
eprint.ing.bot ePrint Updates @eprint.ing.bot · Jan 27
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:40 PM
stefanotessaro.bsky.social
Successful escape from the PNW rain
A view on a valley near Sedona, AZ.
January 3, 2025 at 4:34 AM
stefanotessaro.bsky.social
I guess this is the end of beyond-birthday security research?
colmmacc.bsky.social Colm MacCarthaigh @colmmacc.bsky.social · Dec 25
Great to see NIST take up a wide block cipher mode! At AWS we have to carefully engineer around the 128-bit safety limits. Otherwise hyper-scale systems like VPC, S3, and EBS would exceed those limits in seconds! 256-bits is much more misuse-proof.
csrc.nist.gov/News/2024/ni...
NIST Proposes to Standardize a Wider Variant of AES | CSRC
NIST indicated its interest in vetting another Rijndael variant for approval: Rijndael with 256-bit blocks (i.e., Rijndael-256) with a single key size of 256-bits. NIST plans to develop a draft standa...
csrc.nist.gov
December 26, 2024 at 12:40 AM