Helger Lipmaa
LightNews LightNews
banner
helger.bsky.social
Helger Lipmaa
@helger.bsky.social
530 followers 250 following 160 posts
Cryptography professor at the University of Tartu, Estonia. Zero-Knowledge. SNARKs.
Posts Replies Media Videos
helger.bsky.social
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
Professor of Cybersecurity
iacr.org
November 3, 2025 at 10:24 AM
helger.bsky.social
(accepted to TCC)
eprint.ing.bot ePrint Updates @eprint.ing.bot · Sep 26
Plonk is Simulation Extractable in ROM Under Falsifiable Assumptions (Helger Lipmaa) ia.cr/2025/1759
Abstract. Solving a long-standing open problem, Faonio, Fiore, and Russo proved that the widely used Plonk zk-SNARK is simulation extractable. However, their proof assumes both the random oracle model (ROM) and the algebraic group model. We prove that the same holds in the ROM under falsifiable assumptions. We combine the template of Faust et al., who proved that simulation extractability follows from knowledge soundness, (weak) unique response, and trapdoorless zero-knowledge, with the recent result of Lipmaa, Parisella, and Siim (Crypto 2025), who proved that Plonk has knowledge soundness in the ROM under falsifiable assumptions. For this, we prove that Plonk satisfies new variants of the weak unique response and trapdoorless zero-knowledge properties. We prove that several commonly used gadgets, like the linearization trick, are not trapdoorless zero-knowledge when considered as independent commit-and-prove zk-SNARKs.
September 26, 2025 at 2:44 AM
Reposted by Helger Lipmaa
cosic.bsky.social
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
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.
www.standaard.be
September 24, 2025 at 8:59 AM
Reposted by Helger Lipmaa
eprint.ing.bot
The Syndrome-Space Lens: A Complete Resolution of Proximity Gaps for Reed-Solomon Codes (Russell Okamoto) ia.cr/2025/1712
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.
September 21, 2025 at 12:28 AM
Reposted by Helger Lipmaa
durumcrustulum.com
not again

arxiv.org/pdf/2509.12341
September 17, 2025 at 10:03 PM
Reposted by Helger Lipmaa
eprint.ing.bot
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
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.
July 7, 2025 at 2:34 AM
Reposted by Helger Lipmaa
ccanonne.github.io
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.
September 16, 2025 at 3:56 PM
Reposted by Helger Lipmaa
thejonullman.bsky.social
📢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!
September 15, 2025 at 12:41 PM
helger.bsky.social
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)
theorydays2025.quantum.lu.lv
September 10, 2025 at 12:00 AM
Reposted by Helger Lipmaa
tomgur.bsky.social
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
September 3, 2025 at 8:48 AM
Reposted by Helger Lipmaa
ec.europa.eu
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
💰💰💰💰💰💰💰💰💰💰💰💰💰💰💰💰💰💰
August 5, 2025 at 6:55 AM
Reposted by Helger Lipmaa
ccanonne.github.io
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...
Front cover: Differential Privacy in Artificial Intelligence: From Theory to Practice, now Publishers
August 25, 2025 at 10:45 PM
Reposted by Helger Lipmaa
teorth.bsky.social
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...
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.
newsletter.ofthebrave.org
August 18, 2025 at 3:45 PM
helger.bsky.social
Really happy to have Jens Groth visiting us in Tartu and giving a seminar on ZK, zkVMs, and AI on Tuesday
August 17, 2025 at 3:41 PM
Reposted by Helger Lipmaa
mccurley.bsky.social
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.
International Association for Cryptologic Research
A place to discuss matters related to IACR
discuss.iacr.org
August 14, 2025 at 4:28 AM
Reposted by Helger Lipmaa
giacomofenzi.bsky.social
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...
August 14, 2025 at 2:36 PM
helger.bsky.social
The depth was probably zero
mkskeller.bsky.social Marcel Keller @mkskeller.bsky.social · Aug 13
USENIX chair report: "six individuals appear as co-authors on 20 or more submissions, with two authors appearing on 36 and 39 submissions respectively. At such volume, it becomes difficult not to question the nature and depth of the contributions" www.usenix.org/sites/defaul...
www.usenix.org
August 13, 2025 at 9:55 PM
helger.bsky.social
haha :D
eprint.ing.bot ePrint Updates @eprint.ing.bot · Aug 12
zip: Reducing Proof Sizes for Hash-Based SNARGs (Giacomo Fenzi, Yuwen Zhang) ia.cr/2025/1446
Abstract. The argument size of succinct non-interactive arguments (SNARG) is a crucial metric to minimize, especially when the SNARG is deployed within a bandwidth constrained environment. We present a non-recursive proof compression technique to reduce the size of hash-based succinct arguments. The technique is black-box in the underlying succinct arguments, requires no trusted setup, can be instantiated from standard assumptions (and even when P = NP!) and is concretely efficient. We implement and extensively benchmark our method on a number of concretely deployed succinct arguments, achieving compression across the board to as much as 60% of the original proof size. We further detail non-black-box analogues of our methods to further reduce the argument size.
August 12, 2025 at 9:57 PM
Reposted by Helger Lipmaa
teorth.bsky.social
#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
www.ipam.ucla.edu
August 8, 2025 at 12:48 AM
helger.bsky.social
www.thebulwark.com/p/terence-ta...
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
August 7, 2025 at 12:15 PM
helger.bsky.social
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
July 25, 2025 at 11:50 PM
helger.bsky.social
Crypto 2025 has a session for the Back of the Future fans :)
July 25, 2025 at 1:16 PM
Reposted by Helger Lipmaa
algorithms.fi
Helsinki Algorithms & Theory Days on 28–29 August, 2025, keynote talk by Andris Ambainis
algorithms.fi/theory-days-...
Helsinki Algorithms & Theory Days
algorithms.fi
July 24, 2025 at 8:51 PM
Reposted by Helger Lipmaa
marialep.bsky.social
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...
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...
research-and-innovation.ec.europa.eu
July 23, 2025 at 7:49 PM
Reposted by Helger Lipmaa
gil-kalai.bsky.social
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...
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 …
gilkalai.wordpress.com
July 23, 2025 at 12:33 PM