Helger Lipmaa

We are looking for a cybersecurity professor to strengthen Estonia's existing expertise. We are looking for an ambitious researcher (with a steady presence at big four security conferences) with demonstrated leadership skills who can build a larger team. iacr.org/jobs/item/4075

(accepted to TCC)

Europa test leeftijdscontroles op het internet: is dit het einde van online anonimiteit? Europa test een app waarmee we ons in de toekomst moeten aanmelden op het internet, om te bewijzen dat we meerderjarig zijn. Critici waarschuwen dat het systeem makkelijk te omzeilen is en ongewenste neveneffecten zal hebben, onder meer voor onze privacy.

Europe is testing a digital age verification app to protect minors online. Bart Preneel warns it risks privacy, can be bypassed, and may exclude users. Could this be the end of online anonymity?
www.standaard.be/media-en-cul...
#ageverification #anonyimity #privacy

earlier it was more difficult to write ai-generated papers

Abstract. We resolve the Correlated Agreement (CA) problem for Reed-Solomon codes up to the information-theoretic capacity limit by introducing a fundamental change of basis: from the traditional evaluation domain to the syndrome space. Viewed through this “Syndrome-Space Lens,” the problem of proximity testing transforms into a transparent question of linear-algebraic geometry: a single affine line of syndromes traversing a family of low-dimensional subspaces. This new perspective makes a sharp phase transition at the capacity boundary visible, allowing for a complete characterization of the problem’s behavior across all parameter regimes, yielding short, self-contained proofs. Classification. We establish a precise trichotomy organized by the rank margin Δ := t − d. At the capacity boundary (Δ = 0), the CA premise is information-theoretically vacuous, and we prove that no rigidity can be concluded without imposing additional structure. One step beyond capacity (Δ = 1), the problem enters a “knife-edge” regime where unconditional rigidity does not hold; soundness is recovered either through a combinatorial witness (such as a repeated error support or a small union of supports) or by adding protocol-level structure (such as independent two-fold MCA checks, DEEP/STIR out-of-domain sampling, or a global error locator). For stricter gaps (Δ ≥ 2), unconditional rigidity holds under a simple algebraic condition ((r + 1)k < m + 1), with explicit quantitative bounds. MCA and Practical Implications. Below capacity (δ < 1 − ρ), the strengthened mutual correlated agreement (MCA) problem reduces to ordinary correlated agreement. MCA holds under the same hypotheses as CA. When folds are generated with independent challenges (e.g., via domain-separated Fiat-Shamir), the per-round security margins add. The model-scoped soundness law is Pr [FA] ≤ q^(−(∑Δ_(i))s), providing a clear and complete rulebook for selecting safe and efficient parameters in FRI/STARK systems. This work bypasses the complex machinery of list-decoding algorithms entirely and resolves the long-standing open problem concerning the gap between the Johnson bound and capacity.

Image showing part 2 of abstract.

Image showing part 3 of abstract.

The Syndrome-Space Lens: A Complete Resolution of Proximity Gaps for Reed-Solomon Codes (Russell Okamoto) ia.cr/2025/1712

not again

arxiv.org/pdf/2509.12341

Abstract. Succinct non-interactive arguments of knowledge (SNARKs) based on lattice assumptions offer a promising post-quantum alternative to pairing-based systems, but have until now suffered from inherently quadratic proof sizes in the security parameter. We introduce RoK and Roll, the first lattice-based SNARK that breaks the quadratic barrier, achieving communication complexity of Õ(λ) together with a succinct verification time. The protocol significantly improves upon the state of the art of fully-succinct argument systems established by “RoK, Paper, SISsors” (RPS) [ASIACRYPT’24] and hinges on two key innovations, presented as reductions of knowledge (RoKs): - Structured random projections: We introduce a new technique for structured random projections that allows us to reduce the witness dimensions while approximately preserving its ℓ₂ norm and maintaining the desired tensor structure. In order to maintain succinct communication and verification, the projected image is further committed and adjoined to the original relation. This procedure is recursively repeated until dimension of the intermediate witness becomes poly(λ), i.e. independent of the original witness length. - Unstructured random projection: When the witness is sufficiently small, we let the unstructured projection (over coefficients ℤ_(q)) be sent in plain, as in LaBRADOR [CRYPTO’23]. We observe, however, that the strategy from prior works to immediately lift the projection claim to ℛ_(q), and into our relation, would impose a quadratic communication cost. Instead, we gradually batch-and-lift the projection a the tower of intermediate ring extensions. This reduces the communication cost to Õ(λ) while maintaining a succinct verification time. These two techniques, combined with existing RoKs from RPS, yield a succinct argument system with communication complexity Õ(λ) and succinct verification for structured linear relations.

Image showing part 2 of abstract.

RoK and Roll – Verifier-Efficient Random Projection for Õ(λ)-size Lattice Arguments (Michael Klooß, Russell W. F. Lai, Ngoc Khanh Nguyen, Michał Osadnik) ia.cr/2025/1220

Got my first "official AI review" today from AAAI. Amazing! Very detailed, with very specific technical comments. A shame the most crucial and confidently stated ones are deeply incorrect, though.

Well you can't get everything I guess.

also can't you just get an AI review yourself without even submitting to AAAI?

📢Adam Smith, @gautamkamath.com, and I are putting together a list of job market candidates in Foundations of Responsible Computing! Last year's list was a great success so we're keeping it going!

If you want to be included, or nominate someone, see link in the replies!

Estonian-Latvian theory days this October: theorydays2025.quantum.lu.lv
(local groups work in cryptography, type theory, quantum algorithms, complexity theory, automata theory, error-correcting codes and lately also in database theory)

New arXiv preprint: we show algorithmic versions of the polynomial Freiman–Ruzsa (PFR) theorem of Gowers, Green, Manners, and Tao. Interestingly, our proof draws on quantum information and stabilizer learning algorithms, which we dequantize into classical algorithms.

arxiv.org/pdf/2509.02338

Double the discovery, double the momentum 🚀

Europe doubles down on research competitiveness with a major boost to #HorizonEurope:

€95.5 billion foreseen for 2021-2027
💰💰💰💰💰💰💰💰💰

€175 billion proposed for 2028-2034
💰💰💰💰💰💰💰💰💰💰💰💰💰💰💰💰💰💰

Front cover: Differential Privacy in Artificial Intelligence: From Theory to Practice, now Publishers

New differential #privacy textbook in town: "DP in Artificial Intelligence: From Theory to Practice", by @nandofioretto.bsky.social and @vanhentenryck.bsky.social. Open access, w/ chapters by @jubaz.bsky.social, @grahamrc.bsky.social, and @stein.ke!

www.nowpublishers.com/article/Book...

Louis XIV "the binomials is me" Multinoulli

I’m an award-winning mathematician. Trump just cut my funding. The “Mozart of Math” tried to stay out of politics. Then it came for his research.

I wrote an op-ed on the world-class STEM research ecosystem in the United States, and how this ecosystem is now under attack on multiple fronts by the current administration: newsletter.ofthebrave.org/p/im-an-awar...

Really happy to have Jens Groth visiting us in Tartu and giving a seminar on ZK, zkVMs, and AI on Tuesday

International Association for Cryptologic Research A place to discuss matters related to IACR

Anyone who has been an IACR member in 2023-2026 should have received a link to respond to a survey about conferences and publishing. So far over 500 people have responded, but it will remain open for responses until Sept 12, 2025. I would also encourage people to use their forum invitations.

Back to actual research…
We present a family of space-efficient sumcheck algorithms, and show that they are optimal! 🍹

Joint work with Anubhav, Ale, Elisabetta, @zkproofs.bsky.social, Tushar and Andrew

📚: ia.cr/2025/1473
🧑🏻‍💻: github.com/compsec-epfl...

The depth was probably zero

haha :D

#IPAM (the institute for pure and applied mathematics) is facing a critical shortfall for operating expenses due to an unexpected suspension of NSF funding www.ipam.ucla.edu/news/nsf-fun... . Donations for emergency continuity of operations funding can be made at

giving.ucla.edu/Campaign/Donat

He’s the ‘Mozart’ of Math and Trump Killed His Funding The latest casualty in the administration’s assault on higher education is a legendary researcher who embodies the best of America.

www.thebulwark.com/p/terence-ta...

Crypto 2025 program is online. Five sessions on proof systems, one on Fiat-Shamir, one on Polynomial Commitments. I hope we can cool down the audience after the LatticeFold+ talk

Crypto 2025 has a session for the Back of the Future fans :)

Helsinki Algorithms & Theory Days on 28–29 August, 2025, keynote talk by Andris Ambainis
algorithms.fi/theory-days-...

Horizon Europe 2028 - 2034: twice bigger, simpler, faster and more impactful Research and innovation news alert: As part of the next long-term EU budget 2028-2034, the Commission is proposing to double the budget of the research and innovation framework programme to €175 billi...

Very promising news on the next seven-year EU budget, with a proposed substantial increase for Horizon Europe including the ERC.

We are analysing the other parts of this proposal in more detail.

@Vonderleyen @EZaharievaEU

research-and-innovation.ec.europa.eu/news/all-res...

you should thank yourself, nobody else is more deserving ;)

Amazing: Jie Ma, Wujie Shen, and Shengjie Xie Gave an Exponential Improvement for Ramsey Lower Bounds h/t Benny Sudakov The Ramsey number R(ℓ,k) is the smallest integer n such that in any two-coloring of the edges of the complete graph on n vertices, $latex K_n$, by red and blue, there is either a …

After 78 years, an exponential improvement for Ramsey numbers were found by Jie Ma, Wujie Shen, and Shengjie Xie.
gilkalai.wordpress.com/2025/07/23/a...

congratulations!