iiinova — where your digital self keeps evolving

Stefano Tessaro @stefanotessaro.bsky.social · 23/09/2026

New paper (ia.cr/2026/2126) with Àlex Rodríguez García. We give polynomial-time (!) adaptive attacks against a number of threshold Schnorr signatures. At the core are the first polynomial-time attacks on LDVR, a problem whose solution yields adaptive attacks on several practical schemes.

ia.cr

Cryptanalysis of LDVR: Polynomial-Time Adaptive Attacks against Threshold Schnorr Signatures

We present the first polynomial-time attacks against certain parameter choices of the low-dimensional vector representation (LDVR) problem, introduced by Crites, Katz, Komlo, Tessaro, and Zhu (CRYPTO ...

1103

Reposted by Stefano Tessaro

Henry Yuen @henryyuen.bsky.social · 01/08/2026

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.

232972

Reposted by Stefano Tessaro

Chris Peikert @chrispeikert.bsky.social · 02/08/2026

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

openai.com

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.

210328

Stefano Tessaro @stefanotessaro.bsky.social · 22/07/2026

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.

itcrypto.github.io

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.

020

Reposted by Stefano Tessaro

mccurley.bsky.social @mccurley.bsky.social · 31/03/2026

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

debrisprint.iacr.org

Craptology debrisPrint Snarkive

1166

Stefano Tessaro @stefanotessaro.bsky.social · 27/03/2026

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

020

Stefano Tessaro @stefanotessaro.bsky.social · 18/03/2026

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

072

Reposted by Stefano Tessaro

ePrint Updates @eprint.ing.bot · 03/03/2026

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.

001

Reposted by Stefano Tessaro

ePrint Updates @eprint.ing.bot · 22/12/2025

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.

021

Stefano Tessaro @stefanotessaro.bsky.social · 22/11/2025

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)

nytimes.com

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

24211

Stefano Tessaro @stefanotessaro.bsky.social · 21/11/2025

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

080

Reposted by Stefano Tessaro

Jon Froehlich @jonfroehlich.bsky.social · 28/10/2025

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

Apply - Interfolio {{$ctrl.$state.data.pageTitle}} - Apply - Interfolio

01911

Reposted by Stefano Tessaro

ePrint Updates @eprint.ing.bot · 25/10/2025

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.

011

Reposted by Stefano Tessaro

ePrint Updates @eprint.ing.bot · 20/10/2025

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.

001

Reposted by Stefano Tessaro

ePrint Updates @eprint.ing.bot · 12/10/2025

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.

001

Reposted by Stefano Tessaro

ePrint Updates @eprint.ing.bot · 05/09/2025

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.

001

Reposted by Stefano Tessaro

ePrint Updates @eprint.ing.bot · 16/06/2025

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.

043

Reposted by Stefano Tessaro

ePrint Updates @eprint.ing.bot · 12/06/2025

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.

002

Reposted by Stefano Tessaro

ePrint Updates @eprint.ing.bot · 09/06/2025

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.

021

Reposted by Stefano Tessaro

ePrint Updates @eprint.ing.bot · 03/06/2025

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.

021

Stefano Tessaro @stefanotessaro.bsky.social · 23/03/2025

Successful escape from PNW weather - Spring Break edition

1110

Reposted by Stefano Tessaro

Daniel Slamanig @drl3c7er.bsky.social · 20/03/2025

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 😎

035

Reposted by Stefano Tessaro

ePrint Updates @eprint.ing.bot · 08/03/2025

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.

021

Reposted by Stefano Tessaro

Ryan Williams @rrwilliams.bsky.social · 21/02/2025

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

1726475

Reposted by Stefano Tessaro

Lance Fortnow @lance.fortnow.com · 02/02/2025

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

094

Stefano Tessaro @stefanotessaro.bsky.social · 30/01/2025

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.

youtube.com

Audio of MID-AIR CRASH into Potomac River | Regional Jet and Black Hawk Helicopter

YouTube video by VASAviation -

000

Stefano Tessaro @stefanotessaro.bsky.social · 27/01/2025

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.

0207

Stefano Tessaro @stefanotessaro.bsky.social · 03/01/2025

Successful escape from the PNW rain

050

Stefano Tessaro @stefanotessaro.bsky.social · 26/12/2024

I guess this is the end of beyond-birthday security research?

151