iiinova — where your digital self keeps evolving

Reposted by Aleksei Udovenko

New paper! Given a Jacobian over Fp, can you easily check supersingularity? If you've worked with these objects in magma, you know how annoying this question can be. Turns out it's very easy: we give efficient probabilistic tests, and conclusive if you need to be absolutely sure. ia.cr/2026/2259

eprint.iacr.org

Supersingularity and Superspeciality Verification of Abelian Surfaces

Supersingular abelian surfaces are essential in isogeny-based cryptography. Despite this, we have no efficient algorithm to verify if a given abelian surface is supersingular. In this work, we initiat...

063

Reposted by Aleksei Udovenko

mccurley.bsky.social @mccurley.bsky.social · 28/09/2026

I'd like to remind IACR members to sign up for discuss.iacr.org so they can participate in the discussion about how to adapt the society to the new world of publishing and conferences. If you don't have an account you can visit iacr.org/discuss/

iacr.org

accounts on discuss.iacr.org

044

Reposted by Aleksei Udovenko

No One Upstairs @nooneupstairs.bsky.social · 27/09/2026

Yes, to all the thread. But government assessment of universities would need to change away from for-profit, quantity & IF. Many times, the rules for assessment are made by academics who enjoy the status quo, and so we continue with these problems.

112

Reposted by Aleksei Udovenko

Total Internal Reflection🇬🇧🇺🇸🇺🇦 @tirscienceblog.bsky.social · 26/09/2026

Great 🧵 from @hansonmark.bsky.social on why all academics should be opting to publish in non-profit journals 👏👏👏👇

054

Reposted by Aleksei Udovenko

John Stott @jpsastro.bsky.social · 24/09/2026

Had a UKRI funded grant proposal rejected at the "AI triage stage". "This AI-based triage was used only to identify approximately 50% of the strongest proposals to take forward to full human review." 🧪 #academicsky

I am writing to let you know that, unfortunately, your application was not successful.

Review process

As part of the initial triage of the 179 proposals submitted to this call, each was assessed using an AI-based review. Every proposal was read independently by several different AI models against the same seven criteria used to shape this call (including cyber security relevance, research quality and novelty, importance of the problem addressed, feasibility of the project plan, likely outputs and impact, value for money, and responsible research practice), with each model asked to give a score and a written justification with supporting quotations from the text. To guard against any one model's idiosyncrasies, we also ran a second, independent process in which different AI models debated the merits and weaknesses of each proposal before reaching a judgement, again against the same criteria. Scores from both processes were combined to produce an overall ranking.

This AI-based triage was used only to identify approximately 50% of the strongest proposals to take forward to full human review. Projects selected for funding were drawn from those that progressed to the full human review stage. We recognise that AI-assisted assessment is a new and evolving part of the review process, and we are continuing to evaluate how well it aligns with the judgements of human reviewers on this call. We will soon produce a document detailing our method, so that others can build upon it and improve it.

Feedback on your application

Your application was not selected to progress beyond the AI triage stage. To provide transparency on the outcome of this assessment, we are sharing below the scores (out of 5) from each of the two AI review processes described above, together with the mean score across the two processes.

40417222

Reposted by Aleksei Udovenko

Clément Canonne @ccanonne.github.io · 22/09/2026

Quite the exciting talk by Ryan O'Donnell (@booleananalysis.bsky.social) at the Simons Institute next week, on Expander Graphs. We'll finally know which ones are his favorites! Livestream option available upon (free) registration: simons.berkeley.edu/events/my-fa... @simonsinstitute.bsky.social

simons.berkeley.edu

My Favorite Expanders | Richard M. Karp Distinguished Lecture

Expander graphs are sparse graphs for which, whenever you split the graph into two parts, the number of edges going between the parts is proportional to the size of the smaller part. There are extreme...

1132

Reposted by Aleksei Udovenko

Emmanuel Thomé @emmanuelthome.bsky.social · 21/09/2026

Forging 1024-bit RSA signatures in nearly SNFS time Hand over your HSM for some time, and we can forge signatures for its key. Arbitrary signatures. Forever. github.com/ucsd-hacc/NS...

github.com

GitHub - ucsd-hacc/NSNFSSSFSFN: Nearly SNFS-Speed Signature Forgery Sans Factoring N

Nearly SNFS-Speed Signature Forgery Sans Factoring N - ucsd-hacc/NSNFSSSFSFN

13013

Reposted by Aleksei Udovenko

Helger Lipmaa @helger.bsky.social · 18/09/2026

A different view. As a cryptographer (or maybe, as me - some cryptographers are in a different camp), I mostly agree with what @wtgowers.bsky.social is saying - my goal is to solve problems, and if AI does it better, then so be it. My problem is ethical. The way (say) OpenAI approaches it is wrong.

031

Reposted by Aleksei Udovenko

Clément Canonne @ccanonne.github.io · 17/09/2026

The Call for Papers for #STOC2027 is up! Importantly, the PC "will place substantial weight on the quality of exposition, and clarity of technical arguments and proofs" Also: - Public posting requirement - Required video submission and more. Deadline: ⏰ Nov 2, AoE acm-stoc.org/stoc2027/sto...

Policy experiments for STOC 2027: In light of rapid advances in generative AI and their impact on research and scientific communication, STOC 2027 is experimenting with several new policies intended to encourage high-quality submissions and promote clear and effective communication of research. The policies below include mandatory public posting and mandatory video submission. Detailed instructions for these two requirements will be released closer to the paper submission deadline.

44014

Reposted by Aleksei Udovenko

Lance Fortnow @lance.fortnow.com · 17/09/2026

STOC call for papers is out. Deadline is November 2. acm-stoc.org/stoc202... New rules for the AI era: limited submissions, public posting and a required video. Is it a coincidence that the camera-ready deadline is April Fools Day?

0125

Reposted by Aleksei Udovenko

Kenny Paterson @kennyog.bsky.social · 13/09/2026

TL;DR: using compression before encryption is much weaker than we thought. Tiny length differences can be amplified - almost without limit - and noise-based or bucketization countermeasures are then easy to bypass. Joint work with @prefix-free.bsky.social and Lenka Mareková, to appear at CCS 2026.

12415

Reposted by Aleksei Udovenko

Eric Schares @eschares.bsky.social · 31/08/2026

🚨Update: Our analysis of global APC expenditure has now been expanded to cover more publishers (7 -> 14) and more years (2019-2025). We estimate $15B in APCs paid over seven years, $3.7B in 2025 alone. Elsevier crosses the $1B threshold by itself in 2025. arxiv.org/abs/2608.16322 #ScholComm

Line chart showing 5 biggest publishers from 2019-2025

6179147

Reposted by Aleksei Udovenko

Jess Miers 🦝 @jmiers230.bsky.social · 13/09/2026

I did a somewhat deep dive into the recent OpenAI and Anthropic "hacks" for an upcoming interview. IMO, the AI companies are better off running with the "rogue AI" story because the real story is actually pretty embarrassing. Like making your Wi-Fi password "wifi" embarrassing. 🧵

341835794

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 13/09/2026

Cryptanalysis of the Alternative Mod-2/Mod-3 Weak PRF (Augustin Bariant, Christina Boura, Baptiste Germon, Rachelle Heim, Charles Meyer-Hilfiger, Tyge Tiessen) ia.cr/2026/1982

$Abstract. The alternative mod-2/mod-3 function is one of the most widely used weak PRF constructions in modern cryptographic protocols. Despite its practical importance, its security has received relatively limited attention, with the main cryptanalytic results consisting of two distinguishing attacks due respectively to Cheon et al. and Johansson et al. In this work, we revisit the cryptanalysis of this primitive by analyzing the output distribution of the weak PRF under fixed Hamming weights for both the secret key and the inputs. This refined analysis allows us to isolate and amplify statistical biases that were averaged out in previous works. Using this approach, we derive a new distinguishing attack with asymptotic data and time complexity 𝒪(2^(0.099n)). We implemented the attack for the original parameter set n = 384, thereby obtaining the first practical attack against this instance of the construction. We then introduce a generic technique, called the splitting strategy, which consists in partially fixing or guessing part of the secret key in order to amplify the biases while introducing an additional computational cost that can be efficiently handled using Fast Fourier Transform-like techniques. This leads to the currently best known attack against the construction, with asymptotic data, time, and memory complexities $\widetilde{\mathcal O}(2^{0.09n})$. This last technique also provides a useful time-memory trade-off for estimating the security of real-world constructions when the available data is bounded: we show that the weak PRF offers less than 128-bit security for n = 510 when the data is limited to 2⁴⁵. Finally, we revisit the attack of Johansson et al. and provide a corrected and refined analysis of the underlying bias, showing that the statistical behavior of the attack differs significantly once the Hamming weight of the secret key is taken into account. This new analysis explains phenomena previously observed experimentally but left unexplained. Thanks to this approach we are able to identify a large class of keys for which the attack performs much better asymptotically than anticipated by Johansson et al.$ Image showing part 2 of abstract.

011

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 14/09/2026

Two-Anchor Holdout/Hermite: Solving the TII-254 McEliece Key Recovery Challenge (Markku-Juhani O. Saarinen) ia.cr/2026/1986

Abstract. We report on the solution to the TII-254 McEliece key recovery challenge – currently the hardest solved challenge under the original brute-force metric (2²⁵⁴). The parameters of TII-254 are (m, t, n) = (8, 12, 223), defining a binary [223, 127] code specified by a full-rank (96 × 223) parity-check matrix. We state the method as a thirteen-step process, separating heuristic and non-heuristic choices. At a high level, we computed two complete 121-dimensional relation kernels conditioned at distinct public coordinates, combined them to isolate a certified 80-dimensional pair core, removed a 64-dimensional common nuisance space, and identified the remaining 16 dimensions as an 𝔽_(2⁸) projective-line geometry. This yielded all 87 visible locators, after which a deterministic completion search recovered the full support and polynomial. The two final Krylov sequences alone used 27.2 GPU-hours on NVIDIA GH200s, excluding GPU reconstruction and CPU processing. We provide a self-contained artifact with compact recovery inputs and code, an independent key verifier, and Lean proofs of the reusable linear-algebraic steps.

022

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 13/09/2026

A Forgery Attack against Frobenius-UOV (Augustin Bariant) ia.cr/2026/1927

$Abstract. Frobenius-UOV (F-UOV) is a multivariate signature scheme by Macario-Rat over 𝔽_(p^(e)) whose public equations are quadratic over 𝔽_(p) but have high degree over 𝔽_(p^(e)). A message can be forged by solving a six-term univariate equation in 𝔽_(p^(e)), which can be reduced to a univariate equation containing three monomials with exponents p^(a_(k)) + p^(b_(k)) for k = 0, 1, 2 and a constant term, where the constants a_(k) and b_(k) are fixed by the specification. We show that the choice of constants a_(k), b_(k) of F-UOV allows one to solve the univariate equation efficiently without knowledge of the secret key, leading to a forgery attack. The attack introduces a variable representing a Frobenius power of x, derives two low-degree bivariate equations, and solves them using a so-called linearized resultant. Under heuristics assumptions on the success probabilities, the average complexity is $\tilde{\mathcal{O}}(ep^6)$ field operations. For the 128-, 192-, and 256-bit security instances, our estimates are approximately 2⁴⁵, 2⁵², and 2⁵³ field operations, respectively. This attack may be mitigated by changing the choice of the exponents a_(k) and b_(k).$ Image showing part 2 of abstract.

011

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 13/09/2026

SoK: Zero-Knowledge Friendly Hash Functions over Prime Fields (Clémence Bouvier, Lorenzo Grassi, Katharina Koschatko, Christian Rechberger, Fabian Schmid, Matthias Johann Steiner, Zhuo Wu, Hailun Yan) ia.cr/2026/1931

Abstract. Zero-Knowledge (ZK) proof systems have become a cornerstone of privacy-preserving technologies and blockchain scalability. However, traditional hash functions are often inefficient within ZK protocols due to their high constraint complexity in arithmetic circuits. While various ZK-friendly hash functions have been proposed to address this bottleneck, their diverse algebraic structures and varying security margins make it difficult for practitioners to select the optimal primitive.

We conduct a systematic survey of ZK-friendly hash functions, covering both algorithmic design paradigms and modes of operation. We consolidate the relevant algebraic cryptanalysis techniques and review the third-party cryptanalysis of each design. For parameter sets broken by the best known attacks, we estimate the minimum number of rounds needed to withstand them - not as new recommendations, but to bring all constructions to a comparable level. On this basis, we analyze each construction across different arithmetization styles (R1CS, AIR, PLONK), both theoretically, by deriving the underlying constraint or gate counts, and empirically, through extensive benchmarks.

This paper comes with a fully open-source implementation suite comprising a SageMath/Python reference framework, native Rust implementations, in-circuit implementations, and a reusable TikZ figure library.

013

Reposted by Aleksei Udovenko

TCS+ @tcsplus.bsky.social · 12/09/2026

📢 Our first TCS+ talk of the season will be Wednesday, Sep 16 (10am PT, 1pm ET, 19:00 CEST): Tselil Schramm, from Stanford, will give a survey of "10 years of the low-degree framework in average-case complexity" RSVP to receive the link (one day prior to the talk): docs.google.com/forms/d/e/1F...

docs.google.com

TCS+ RSVP: Tselil Schramm (2026/09/16)

10 years of the low-degree framework in average-case complexity

064

Reposted by Aleksei Udovenko

Ryan O'Donnell @booleananalysis.bsky.social · 10/09/2026

Am teaching grad complexity theory at CMU; about 1/3 of the lectures will be new (vs. last time), 'modern' results. Videos are going onto www.youtube.com/@ComplexityT... which will later also feature student videos. We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.

youtube.com

Complexity Theory At Carnegie Mellon

05717

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 10/09/2026

Nothing Up My Matrix: Kleptographic Backdoors in ZK-friendly Hash Functions (Hyunsik Jeong, Malte Sander Leip, Mincheol Son) ia.cr/2026/1901

Abstract. ZK-friendly hash functions are often built from algebraic SPN permutations. The matrix provides diffusion by mixing the state elements after the S-box layer. However, there is no uniform convention for selecting matrices for the linear layer across primitives. Matrix selection may follow a transparent nothing-up-my-sleeve procedure or prioritize implementation efficiency. Some specifications instead treat any MDS matrix as admissible. This parameter-selection freedom also persists in practice, as some deployed implementations replace the concrete matrix proposed in the original specification with an alternative instantiation. We show that adversarial use of this freedom can create a kleptographic attack surface.

In this paper, we study kleptographic backdoors embedded in the matrices of ZK-friendly hash functions. Assuming that a malicious designer controls matrix selection, the designer can choose a matrix that maps a chosen input to a chosen output under appropriate round and parameter conditions. The resulting matrix is MDS and passes the additional matrix security checks required by the target primitive.

Three case studies show that such a backdoor could have critical security consequences in real-world deployments. In Plonky3, it would allow a prover to control a Fiat–Shamir challenge and make the verifier accept an invalid claim. In Neptune Cash, it would permit creating a digest collision between the program that checks whether a transaction is valid and one that omits this check, enabling counterfeit currency. Finally, in Plonky2, it would enable a forged Merkle-tree membership proof for an attacker-chosen element. Our results show that satisfying the MDS condition and other security requirements is insufficient to establish that a matrix is trustworthy. Its generation process must also be transparent and verifiable.

011

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 10/09/2026

A Better Bivariate Resultant Attack on Round-Reduced Poseidon (Antoine Bak, Maël Hostettler) ia.cr/2026/1905

Abstract. Poseidon is one of the most popular arithmetization-oriented (AO) hash function, due to its good performances both in evaluation and in Zero-knowledge proof protocols. It is for instance used in the Plonky3 library, and has been considered for use in the Ethereum protocol.

The security of Arithmetization-oriented hash functions is commonly evaluated through the CICO-k problem, which consists in controlling simultaneously k coordinates in the input and output of the permutation. This problem is in particular relevant to finding preimages in sponge or compression mode and solving zero-test problems. Depending on the size of the underlying field, different values of k may be relevant. In this paper, we focus on the case of k=2, that was the subject of the recent bounty program by the Ethereum foundation.

In this setting, one can model the CICO-2 problem as a bivariate system P(X, Y) = Q(X, Y) = 0 where the polynomials have total degree delta = d^(RF +RP). The best known methods for solving bivariate systems are algorithms for computing bivariate resultants. Over a generic system with coefficients over a finite field, the best algorithms achieve an asymptotic bit complexity that is linear in delta^(2+eps) log(q)^(1+eps), which is close to optimal, given that the input and output of the algorithm have bit size delta^2 log (q).

However, the polynomial systems that stem from Poseidon are more structured, leading to a resultant that has degree DI = d^(2RF + RP), which is much less than what one would expect from a random bivariate system of degree d^(RF + RP). This fact has already been exploited in a previous work that used an evaluation-interpolation approach to compute the bivariate resultant in time that is quasi-linear in d^(3 RF + 2 RP).

In this work, we exploit this fact by adapting another bivariate resultant algorithm to the special setting where the degree of the resultant of the equations is much lower than delta^2. By doing a careful analysis of the algorithm for systems with such property, we show that under some heuristics, the CICO-2 problem on Poseidon can be solved in time that is quasi-linear in DI delta^(1-1/w), where 2 <= w < 2.38 is the exponent of matrix multiplication. We validate our approach by implementing our attack on reduced versions of the Poseidon permutation, and show a practical speedup compared to the previous approaches.

011

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 10/09/2026

Cryptanalysis of a knot-based key exchange (Simon-Philipp Merz) ia.cr/2026/1898

Abstract. We present an efficient attack on a knot-based Diffie–Hellman key exchange proposed by Sconza and Wildi. In the proposal, the two parties exchange oriented knots, combine them under connected sum to obtain a common knot, and derive the shared secret by evaluating a finite type invariant of degree m on it. We show the scheme is insecure for every choice of finite type invariant. The shared secret can be computed from the public transcript at roughly three times the cost of running the scheme honestly. The attack maps knots into a truncated Polyak space 𝒫_(m), in which connected sum becomes multiplication and every element of the image is invertible, so the public knot can simply be divided out. This bypasses all countermeasures put in place by the proposed protocol.

Independently of the attack, we show that the key space is too small for the parameters proposed. A degree-m invariant takes O(c^(m)) values on knots represented with diagrams consisting of c crossings. For the suggested crossing number, reaching the 128 bits claimed would require m ≥ 10, at which point a single evaluation of the invariant costs in the order of 2⁵⁰ operations.

031

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 07/09/2026

Rogue: Updatable Matrix Lookup Arguments and Applications to Verifiable Databases (Christodoulos Pappas, Zhuo Cai, Dimitrios Papadopoulos) ia.cr/2026/1890

$Abstract. Proving the correctness of computations over a large dataset via succinct non-interactive arguments of knowledge (SNARKs) entails the large overhead of “loading” the dataset in the SNARK. However, certain computations may only need to access a small fraction of the dataset (e.g., a database query that only accesses a subset of table rows and then computes an aggregation function). The standard way of proving such computations is to use to load only necessary data to the SNARK. Unfortunately, all prior schemes are : even a single change to the dataset forces the prover to re-run an expensive pre-processing step, linear to the dataset size. The only exemption is the recent work of Dutta et al., (CCS’24) that proposed a lookup argument with sublinear updates—based on re-running the pre-processing phase periodically, when too many changes have been accumulated. In this work, we present Rogue, the first lookup argument with sublinear prover time and updates that take time proportional only to the number of incurred changes. Indeed, Rogue is actually a , supporting entire row lookups in time proportional to the number of rows (and independent of their size)! It has very good practical performance, e.g., for a 2²⁰ × 2⁷ matrix and 2¹⁰ row accesses, Rogue achieves ×21-942 and ×76-30000 faster lookups and updates, respectively, compared to prior works. We then use Rogue to build RogueDB, the first verifiable database system for arbitrary SQL queries that supports authenticated indexes, hence achieves prover time sublinear to the database. Compared with prior schemes with succinct proofs, vSQL (Zhang et al., IEEE S&P’17) and PoneglyphDB (Gu et al., SIGMOD’25), we get ×42.8-×8624.1 and ×149.6-×11362.4 faster prover times, for various SQL queries from the TPC-H benchmark.$ Image showing part 2 of abstract.

001

Reposted by Aleksei Udovenko

Pedro Beltrao @pedrobeltrao.bsky.social · 03/09/2026

8.8% success rate for the ERC Starting Grant is not acceptable. It is a lottery at this point with so many great scientists and ideas left to be funded. We keep talking about the competitiveness of Europe and we can't agree to properly fund our best instrument for scientific innovation.

37722

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 04/09/2026

Finding a Shortest Vector and More in 2^(n/2 + o(n)) Time using q-ary Coset Difference Tree (Minki Hhan) ia.cr/2026/1859

Abstract. This paper presents a new randomized algorithm for solving the exact shortest vector problem. For the n-dimensional lattice ℒ, our algorithm runs in time and space 2^(n/2 + o(n)).

Our algorithm can be viewed as a q-ary analogue of the midpoint Hessian for an odd prime q; more precisely, we use the fact that, for a shortest vector v, the gradient (rather than Hessian) of the periodic Gaussian function at v/q is nearly proportional to v (up to sign), even after aggregation over a relatively large random affine coset. We compute the relevant coset gradient along a chain of intermediate lattices using a combinatorial procedure inspired by Wagner’s generalized birthday algorithm, yielding the 2^(n/2 + o(n)) time and space complexity.

A variant of the algorithm solves the exact closest vector problem on every input (y, ℒ) with a distance guarantee dist (y, ℒ) ≤ 1.039λ₁(ℒ) within the same time and space complexity. This guarantee holds for a random target and a random lattice drawn according to the Haar-Siegel measure. Thus, this algorithm solves a closest vector problem on such random instances in time and space 2^(n/2 + o(n)).

021

Reposted by Aleksei Udovenko

Maria Corte-Real Santos @maria.isogeny.club · 03/09/2026

Rise and shine, it's time for the Isogeny Club Season Nine! isogeny.club

isogeny.club

The Isogeny Club

185

Reposted by Aleksei Udovenko

Giacomo Fenzi @giacomofenzi.bsky.social · 02/09/2026

New work out! We (royally) show that Fiat-Shamir transformation is insecure for a class of proof systems for *generated* relations (including variants of commonly deployed protocols for R1CS). A thread to explain where this applies ia.cr/2026/1838

151

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 01/09/2026

How to prove more false statements: Fiat–Shamir limitations on (generated) R1CS (Giacomo Fenzi) ia.cr/2026/1838

Abstract. The Fiat–Shamir (FS) transformation is a technique that converts interactive protocols into non-interactive ones. FS is secure in idealized models such as the random oracle model (ROM) (if the interactive protocol satisfies a condition known as state-restoration soundness).

It is known that there are protocols whose FS transformation is secure in the ROM, yet insecure when instantiated with any concrete hash function. Historically, these protocols were contrived (as in, they were designed so their FS transformation would be unsound). Khovratovich, Rothblum and Soukhanov (CRYPTO 2025) showed that a class of natural (and practically deployed) protocols based on a protocol of Goldwasser, Kalai and Rothblum (JACM 2015) was also unsound when compiled with FS and any concrete hash function.

We extend the attack to a different class of protocols: those whose instances are generated by running a program.

This setting covers concrete trends in modern proof systems, in which the computation to be proven is described by a program (often adversarialy generated) which is then either compiled or autonomously converted into an instance of target relation such as rank-1 constraint satisfaction (R1CS). We show that, when the conversion process is “expressive enough”, an adversary controlling the program code can break soundness of the non-interactive proof system.

The attacks generalize to a wide class of protocols: any protocol in which a cheating prover can prepare an accepting transcript before the statement is bound. We show that variants of the Spartan (CRYPTO 2020) and Aurora (EUROCRYPT 2019) proof systems for R1CS fall in this class.

Complementing the attacks, we formalize a mitigation: deriving the first Fiat–Shamir challenge from the generated statement, rather than from the program that generates it, provably reduces the soundness of the compiled protocol to that of the underlying protocol for the non-generated relation.

021

Reposted by Aleksei Udovenko

Deirdre Connolly¹ ² @durumcrustulum.com · 01/09/2026

SQIsign has been updated for Round 3 of the NIST PQC signatures on-ramp: - updated params re: eprint 2026/1486 - new full fixed-precision arithmetic with tight size bounds - no more floating point in lattice reduction - new ideal-to-isogeny, gluing algs, speedups sqisign.org/spec/sqisign...

1145

Reposted by Aleksei Udovenko

Nigel Smart @smartcryptology.bsky.social · 31/08/2026

Super interesting blog on how one leading Oxford physicist thinks that quantum computers will never break RSA.... profwoodward.substack.com/p/quantum-co...

profwoodward.substack.com

Quantum Computers Will Never Break RSA, Says Oxford Physicist. But I Say Migrate Anyway

A serious new theory predicts a hard limit on qubits. Here's why it doesn't change your PQC plans

161

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 30/08/2026

The Extended Wedge Attack (John Baena, Javier Verbel, Luis Villota) ia.cr/2026/1830

Abstract. The wedge attack of Ran (EUROCRYPT 2026) recovers the secret oil space of a UOV public key over fields of characteristic two by exploiting the fact that the polar forms of the public map are alternating. It has since been generalized in several directions, each carrying its own algebraic tools, e.g., Jin et al. (PKC 2026). Working directly with the polynomials of an oil and vinegar map, we give a simpler description of the attack, based on a dual decomposition of oil-vinegar polynomials, and we recover the original wedge attack and its odd-characteristic analogue as special cases. This framework leads to a generalization, which we call the extended wedge attack. We identify two explicit conditions on the parameters that guarantee that the attack terminates with the recovery of the secret space. We also prove that the matrix of the extended wedge attack is permutation equivalent to the truncated Macaulay matrix in the attack by Furue-Ikematsu (CRYPTO 2026).

011

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 28/08/2026

Concrete Security Assessment of Isogeny-based Cryptography with the new Isogeny-Path algorithm (Maher Mamah) ia.cr/2026/1821

Abstract. Very recently, Wesolowski (ePrint 2026/1486) proposed a heuristic algorithm for solving the supersingular isogeny-path problem in time and memory p^(1/3 + o(1)), where p is the characteristic of the underlying field. Although this constitutes an asymptotic improvement over the previous best-known complexity of p^(1/2)log^(O(1))(p), its concrete impact on the security of isogeny-based cryptographic schemes, particularly SQIsign, remains unclear due to the superpolynomial overhead hidden in the p^(o(1)) factor and the algorithm’s exponential memory requirement.

In this work, we assess the concrete cost of Wesolowski’s attack, study its time–memory tradeoffs, and investigate optimizations based on the van Oorschot–Wiener (vOW) technique. Our analysis shows that, over the practical memory ranges considered, neither the optimized full-list attack nor its vOW variants outperform the previous state-of-the-art low-memory algorithm for computing supersingular endomorphism rings. We further study quantum claw-finding improvements. While Grover search can essentially remove the large memory requirement, it offers little improvement in running time, whereas Tani’s algorithm provides a stronger gate–memory tradeoff at the cost of substantial coherent quantum memory. Overall, our results show that the asymptotic p^(1/3 + o(1)) improvement does not directly translate into a comparable reduction in concrete security.

043

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 28/08/2026

HyperSolver: Asymptotically and Concretely Accelerating the Delfs–Galbraith Attack using Isogeny Ladders (Lorenz Panny, Ryan Rueger, Alessandro Sferlazza, Aleksei Udovenko) ia.cr/2026/1823

Abstract. We present a new variant of the memoryless Delfs-Galbraith algorithm for finding an isogeny path from any given supersingular elliptic curve to a curve with known endomorphism ring. Through existing polynomial-time reductions, our algorithm allows one to solve the supersingular endomorphism-ring problem which lies at the heart of isogeny-based cryptography.

For arbitrary characteristics p our algorithm asymptotically outperforms the previous best Delfs-Galbraith variant by a logarithmic factor; and matches the best previous asymptotic for characteristics with favourable structure.

In addition to the asymptotic analysis, we also calculate a concrete cost estimate for our algorithm in terms of finite-field operations, which indicates that our expected cost is lower than all previous Delfs-Galbraith variants, even concretely. By substituting bit-operation counts for the cost of arithmetic, we can deduce concrete bit-security estimates for isogeny-based cryptographic primitives, including (but not limited to) SQIsign.

As part of the calculation of the expected cost, we also provide a novel analysis of the probability of encountering “distinguished” subgraphs in an expander graph when relying various modes of graph exploration, whose potentially counterintuitive behaviour had apparently remained unnoticed thus far.

Finally, we provide a complete implementation of our algorithm(s), with the asymptotic bottleneck being attacked on GPUs, and the easier post-processing done on CPU using C++ as well as SageMath. Preliminary experimental results suggest that we can solve 100-bit instances of the problem within less than 100 GPU hours.

For comparison, the current cryptanalytic record for ECDLP (which has a comparable classical attack complexity) stands at 114 bits, achieved using significantly more hardware and time.

032

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 26/08/2026

Beyond Linear Subspace Trails: Nonlinear Subspaces for Gr"obner Basis Attacks on Poseidon/Poseidon2 and Neptune (Enyan Li, Fukang Liu, Gaoli Wang) ia.cr/2026/1792

Abstract. Poseidon/Poseidon2 and Neptune are prominent primitives for zero-knowledge proof systems. Their arithmetic circuit cost is reduced mainly through partial S-box layers and low-degree finite field operations. Algebraic attacks are therefore a central part of their security analysis, and Gr"obner basis methods are a main tool for studying such attacks. For such attacks, controlling the algebraic degree of the polynomial systems induced by partial rounds is a central issue. Previous work has shown that linear subspace trails can reduce the algebraic degree of partial rounds in constrained-input-constrained-output (CICO) problems. Therefore, subspace analysis has become an important tool for evaluating the algebraic security of Poseidon-like permutations.

The main contribution of this paper is to extend the existing linear subspace trail framework to nonlinear subspaces. More precisely, we first introduce a parametric Macaulay matrix method. This method transforms the search for algebraic constraints that reduce degree growth into the problem of solving a parametric system. It provides a general algebraic approach for constructing longer nonlinear subspace trails that suppress degree growth over more internal partial rounds. Second, for the CICO problem with Ec extra constraints, we give a concrete constraint pattern that extends a linear subspace trail into a nonlinear one. In this nonlinear construction, the first Ec subspace constraints generate an ideal, and further compatible subspace constraints can be added along the chain without enlarging this ideal. As a result, the nonlinear subspace trail can cover up to 2Ec internal rounds, whereas the previous linear subspace trail can cover up to Ec rounds. We further show that the balancing matrix required by this construction is generically nonsingular. Furthermore, we propose subspace modeling variants without variable substitution. These variants impose linear or nonlinear constraints directly on high-degree intermediate states.

For the Poseidon/Poseidon2 and Neptune instances proposed by Grassi et al. in ToSC 2025, our experiments show that, under the same complexity bound and the same Gr"obner basis cost model, the nonlinear subspace model can analyze approximately twice as many internal partial rounds as the linear subspace model considered in ToSC 2025. For several concrete instances, our method reaches or even exceeds the recommended number of internal rounds given by the designers in sponge mode or compression mode.

011

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 22/08/2026

Notes on Short-Limb Modular Multiplication Techniques: Barrett, Montgomery, Plantard, and the Explicit CRT (Bo-Yin Yang) ia.cr/2026/1743

Abstract. This note collects, in compressed form, some techniques for modular multiplication with word-size (“short-limb”), or at most a-handful-of-words sized moduli as they are used in implementations of lattice-based cryptography: Barrett reduction and multiplication (in signed and unsigned flavors, with exact error, range, and canonicality analyses), Montgomery reduction and multiplication (including the folded-constant form, the precise equivalence with Barrett multiplication, even moduli, the multi-limb case, and the k-reduction), Plantard multiplication (the original unsigned algorithm, the signed variant, and a variant taking signed inputs to the canonical unsigned representative in [0,q)), and modular multiplication via the explicit Chinese remainder theorem. These are compressed out of my lecture slides in the class Post-Quantum Cryptography at National Taiwan University 2020–2025 (EE 5176/921 U2540). All numerical examples, ranges, and windows stated here have been verified by exhaustive or randomized machine search; several constants and ranges correct typos and miscalculations that circulated after lectures.

011

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 24/08/2026

A Practical Optimization for Wiedemann XL (Tung Chou, Ruben Niederhagen) ia.cr/2026/1787

Abstract. Wiedemann XL is a variant of the XL algorithm that has been widely used in algebraic attacks. Usually, the cost of applying Widemann XL is estimated as 3N^2 ω, where N is the width of the Macaulay matrix, and ω is the average row weight of the Macaulay matrix. Among 3N^2 ω, 2N^2 ω is from the 1st phase of the algorithm, while N^2 ω is from the 3rd phase of the algorithm. This paper shows a practical optimization that reduces the cost of the 3rd phase by a huge factor so that its cost becomes essentially negligible compared to that of the 1st phase. Our optimization makes use of the fact that to obtain a solution of the multivariate system, only a small part of the kernel vectors is needed.

011

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 18/08/2026

Lumora: A Family of Permutation-Based Wide-Block Ciphers for Post-Quantum zkSNARK Applications (Susanta Samanta, Martin Grenouilloux, Guang Gong, Chunlei Li) ia.cr/2026/1653

$Abstract. The deployment of advanced cryptographic protocols such as zero-knowledge proofs (ZKPs) requires symmetric primitives optimized for fast verification inside proof systems. In frameworks based on Rank-1 Constraint Systems (R1CS), prover performance and proof size are dominated by the cost of arithmetization, specifically, by the number of nonlinear multiplication constraints. Traditional bit-oriented designs are typically inefficient under this metric. In this paper, we introduce Lumora, a family of arithmetization-oriented, permutation-based wide-block ciphers designed for efficient use inside zkSNARK circuits and for applications in post-quantum digital signatures. Each instance of Lumora follows a unified AES-like SPN structure defined over the binary extension field 𝔽_(2^(n)) for n ∈ {16, 32, 64}. The underlying permutation is instantiated as a block cipher via the Even-Mansour paradigm, which eliminates the R1CS constraint overhead of a separate key schedule, ensuring the prover’s workload remains strictly focused on evaluating the public permutation. Finally, we provide a detailed security analysis of the Lumora family, together with implementation results and a comparison within the FAEST-EM-256 framework.$ Image showing part 2 of abstract.

011

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 18/08/2026

A decrementally-improved algorithm for Boolean MQ (Charles Bouillaguet, Julia Sauvage) ia.cr/2026/1704

Abstract. The MQOM signature scheme is currently a third-round candidate in the NIST competition for additional signatures. It is based on the “MPC-in-the-Head” paradigm and relies on the hardness of the MQ problem. Some of its parameter sets expose a Boolean quadratic system in the public key. While the situation for MQ over larger fields has been relatively quiescent over the last decade, Boolean MQ has seen active progress, culminating with Dinur’s algorithms at SODA 2021 and Eurocrypt 2021.

We propose yet another algorithm for Boolean MQ. It is a hybrid between the “polynomial-method” of Lokshtanov, Paturi, Tamaki, Williams and Yu from SODA 2017 and Dinur’s “second algorithm” from Eurocrypt 2021. We remove some machinery from the latter to obtain a modest improvement of 1–4 bits in performance for MQOM parameters (“decremental improvement”).

MQOM optionally uses the “correlated GGM trees” technique to shorten signatures; in that case, its security also relies on the hardness of the “Partial-Guessing One-Wayness” problem for MQ (PGOW-MQ): given an MQ system supposed to offer λ bits of security, the adversary has to find the first λ bits of a solution, and they have access to an oracle that enables them to check candidate prefixes. The designers of MQOM implicitly assumed that PGOW-MQ is as hard as MQ itself. Our algorithm can exploit the availability of the solution-testing oracle to solve PGOW-MQ 2 to 4 times faster than it solves MQ, thus showing that the two problems are marginally different. This yields attacks against MQOM that are 3–4 bits below the expected security level, but that suffer from huge memory complexities.

Lastly, we survey old and new techniques to find an invertible linear change of variables that puts a few arbitrary polynomials in UOV shape. This leads to a small acceleration of our algorithm, and also incidentally improves upon the Thomae-Wolf and Furue-Nakamura-Takagi algorithms to solve underdetermined Boolean systems. A new idea based on matrix pencils was used to solve the largest underdetermined Boolean Fukuoka MQ challenges and may be of independent interest.

011

Reposted by Aleksei Udovenko

COSIC @cosic.bsky.social · 17/08/2026

We’re excited to announce the 7th edition of the Leuven Isogeny Days (Sept 16–18, 2026)! Registration is open until 22 August, join us! More info & signup: www.esat.kuleuven.be/cosic/projec... #LID #Isogeny #IsogenyDays

033

Reposted by Aleksei Udovenko

Samuel Moore @samuelmoore.org · 17/08/2026

Helpful reminder from Elsevier that they have the "legal power" to do what they want with your journals. You have the collective power to take your editorial work elsewhere.

16843

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 10/08/2026

Quasipolynomial Cryptanalysis of the McEliece Cryptosystem (or: PIR Meets McEliece) (Ashrujit Ghoshal, Yuval Ishai, Aayush Jain, Nuozhou Sun) ia.cr/2026/1630

Abstract. The McEliece code-based cryptosystem, utilizing binary Goppa codes, is the earliest public-key encryption scheme that is still considered post-quantum secure. We present a simple, classical quasipolynomial-time distinguisher for Goppa–McEliece in the asymptotic “Classic McEliece” regime: for code length n, extension degree m = Θ(log n), Goppa degree t = Θ(n/log n), and public-code dimension k = Θ(n), the algorithm runs in time n^(𝒪(log n)) and distinguishes the McEliece public key from the uniform distribution over 𝔽₂^(k × n) with advantage 1 − o(1). The distinguisher is not merely asymptotic: it applies to all Classic McEliece parameter sets considered in the NIST process and yields improved (though not yet practical) concrete attack estimates.

Our distinguishing attack originated from a failed attempt to construct doubly efficient private information retrieval (PIR) protocols from algebraic locally decodable codes, and can be intuitively explained from the PIR perspective. We extend this provable algorithm to a heuristic n^(𝒪(log n))-time ciphertext-decryption attack that recovers the message from a noisy codeword.

02512

Reposted by Aleksei Udovenko

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

Solving the supersingular isogeny problem in time p^(2/5 + o(1)) using bivariate multipoint evaluation (Aleksei Udovenko) ia.cr/2026/1575

Abstract. This note presents a new unconditional attack on the supersingular isogeny problem, with time and memory complexity p^(2/5 + o(1)). It builds on the approach by Eisenträger-Hallgren-Leonardi-Morrison-Park (2020) and Fuselier-Iezzi-Kozek-Morrison-Namoijam (2025), and is related to the recent heuristic attack with complexity p^(1/3 + o(1)) by Wesolowski (ePrint 2026/1486): all of these search for a separable isogeny from a curve to its Galois conjugate to form a non-scalar endomorphism.

Our attack is based on highly theoretical multivariate multipoint evaluation algorithms from Kedlaya-Umans (2008, 2011), Bhargava-Ghosh-Guo-Kumar-Umans (2022), and Ghosh-Harsha-Herdade-Kumar-Saptharishi (2023), and therefore does not threaten isogeny cryptosystems in practice; it is of theoretical interest.

012

Reposted by Aleksei Udovenko

ePrint Updates @eprint.ing.bot · 07/08/2026

AES-Based Grinding for MPC-in-the-Head Signatures (Matthieu Rivain) ia.cr/2026/1625

$Abstract. Grinding is a technique which introduces a proof of work into the Fiat-Shamir transform: by constraining the challenge to satisfy a w-bit condition, forging a proof requires about 2^(w)/ε evaluations of the hash function instead of 1/ε, where ε is the soundness error of the underlying protocol. This allows one to select reduced parameters, yielding shorter proofs and signatures. Grinding is used in FAEST, MQOM and SDitH, the three MPC-in-the-Head schemes selected for the third round of the NIST additional post-quantum signature standardization process, where it is instantiated with Keccak. In this short paper, we investigate grinding schemes in which the proof of work is expressed in terms of block cipher computations, specifically AES, which is significantly faster than Keccak on modern CPUs, is already a building block of these schemes, and underlies the very definition of the NIST security categories. We formalize the notion of grinding scheme together with a protocol-agnostic security notion, we propose a construction performing two cipher calls per iteration, and we prove, in the ideal cipher and random oracle models, that an adversary making Q_(E) cipher queries breaks it with probability at most $\frac{4}{3} \cdot \varepsilon\, Q_E / 2^w$, up to negligible terms. We further generalize the scheme to use more cipher calls per iteration, which makes the constant $\frac43$ tend to 1.$ Image showing part 2 of abstract.

011

Reposted by Aleksei Udovenko

Nigel Smart @smartcryptology.bsky.social · 04/08/2026

The IACR just published Volume 3, Issue 2 of the IACR Communications in Cryptology See cic.iacr.org/i/3/2. This issue consists of 41 papers.

cic.iacr.org

Volume 3, Issue 2

051

Reposted by Aleksei Udovenko

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 Aleksei Udovenko

Martin R. Albrecht @malb.bsky.social · 01/08/2026

OpenAI claim a proof that CPV is NP-hard for polynomial approximation factors. openai.com/index/ten-ad...

Screenshot of the text: "Closest vector problem. Polynomial-factor hardness of approximation for the closest vector problem, a foundational lattice question related to post-quantum cryptography."

084