Tessera

Stefano Tessaro

@stefanotessaro.bsky.social

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/

35 Posts574 Follower 255 Folgt

Henry Yuen @henryyuen.bsky.social · 4d ago

Some initial thoughts, and a complicated mix of feelings. Wow. I mean, Erdos problems are cool (I genuinely mean that), I didn't know about the Jacobian conjecture before it got disproved. But this newest batch from OpenAI hits home in a way the previous announcements did not.

Chris Peikert @chrispeikert.bsky.social · 4d ago

1/ Initial reactions after some hours with this groundbreaking result proving the NP-hardness of poly-approx CVP/NCP: It is most likely correct, but more importantly, it is original, elegant, and beautiful! (Also: it is easy to improve, quantitatively.) openai.com/index/ten-ad...

Ten advances in mathematics and theoretical computer science

OpenAI shares new results on long-standing open problems in mathematics and theoretical computer science, including advances in geometry, cryptography, and complexity.

openai.com

Stefano Tessaro @stefanotessaro.bsky.social · 2w ago

ITC 2026 is co-located with CRYPTO 2026, with a great program and a wonderful lineup of invited speakers! itcrypto.github.io/2026/2026pro... - consider attending, especially if you are already in Santa Barbara for CRYPTO.

ITC 2026 Program

Preliminary program for ITC 2026, August 15–16 at UC Santa Barbara, with publication-track papers, invited spotlight talks, highlights talks, abstracts, breaks, meals, and receptions.

itcrypto.github.io

@mccurley.bsky.social · 4mo ago

In honor of April Fool's Day (which has already started in Australia), I offer you debrisprint.iacr.org for AI-generated cryptology content.

Craptology debrisPrint Snarkive

debrisprint.iacr.org

Stefano Tessaro @stefanotessaro.bsky.social · 4mo ago

Is EUROCRYPT '26 the first joint IACR-ATP-WTA event in history?

Stefano Tessaro @stefanotessaro.bsky.social · 5mo ago

Huge congrats to Bennett and Brassard for the well-deserved award, but the highlighted sentence from the ACM announcement (www.acm.org/media-center...) is a rather odd take on PQC ...

"Quantum cryptography, alongside emerging, hopefully quantum-resistant classical approaches for which no proofs of security are known, represents one pathway toward securing digital communications in the decades ahead."

ePrint Updates @eprint.ing.bot · 5mo ago

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

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.

ePrint Updates @eprint.ing.bot · 8mo ago

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

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.

Stefano Tessaro @stefanotessaro.bsky.social · 9mo ago

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)

Cryptographers Held an Election. They Can’t Decrypt the Results.

nytimes.com

Stefano Tessaro@stefanotessaro.bsky.social · 9mo ago

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

Stefano Tessaro @stefanotessaro.bsky.social · 9mo ago

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

Jon Froehlich @jonfroehlich.bsky.social · 9mo ago

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

ePrint Updates @eprint.ing.bot · 9mo ago

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.

ePrint Updates @eprint.ing.bot · 10mo ago

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.

ePrint Updates @eprint.ing.bot · 10mo ago

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.

ePrint Updates @eprint.ing.bot · 11mo ago

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.

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

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.

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

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.

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

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.

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

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.

Stefano Tessaro @stefanotessaro.bsky.social · last yr.

Successful escape from PNW weather - Spring Break edition

Stefano Tessaro @stefanotessaro.bsky.social · last yr.

New paper!

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

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.

Daniel Slamanig @drl3c7er.bsky.social · last yr.

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 😎

Daniel Slamanig@drl3c7er.bsky.social · 2y ago

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

Ed Lazowska @edlazowska.bsky.social · last yr.

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.

theatlantic.com

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

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.

Ryan Williams @rrwilliams.bsky.social · last yr.

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

Carl T. Bergstrom @carlbergstrom.com · last yr.

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

Lance Fortnow @lance.fortnow.com · 2y ago

NSF is getting back to business due to a court order. Order: nsf-gov-resources.ns... Details: new.nsf.gov/executiv...

Stefano Tessaro @stefanotessaro.bsky.social · 2y ago

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 -

youtube.com

Stefano Tessaro @stefanotessaro.bsky.social · 2y ago

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

Stefano Tessaro @stefanotessaro.bsky.social · 2y ago

Successful escape from the PNW rain