Seminar

Zero-knowledge proofs of set membership underpin privacy-preserving constructions such as ring signatures and anonymous credentials. Existing succinct constructions rely mainly on the Fiat–Shamir transform in the Random Oracle Model (ROM), while standard-model non-interactive proofs from post-quantum assumptions remain either generic and inefficient or asymptotically compact yet concretely impractical.

This talk introduces a compact lattice-based NIZK arguments for set membership in the standard model with proof size logarithmic in the set cardinality. The construction matches the logarithmic proof size of accumulator-based ROM constructions while achieving post-quantum security without random oracles. The main technical tool is a new trapdoor Σ-protocol (Canetti et al., STOC’19) supporting linear relations modulo multiple heterogeneous moduli, allowing such relations to be handled at their native moduli without homogenization. This yields a modular approach to compact proofs compatible with lattice accumulators. A direct application is a logarithmic-size lattice-based ring signature scheme with provable security under standard lattice assumptions.

Post-quantum cryptography aims to develop cryptographic schemes secure against quantum adversaries. One promising class of digital signature schemes is based on multivariate quadratic equations, of which Unbalanced Oil and Vinegar (UOV) is a leading example. UOV has been extensively studied since its introduction in 1998, and it has remained secure. It offers very small signatures but suffers from very large public keys. To address this issue, some variants, such as MAYO, QR-UOV, and SNOVA, introduce additional structure to reduce the size of the public key. These four multivariate signature schemes are among the candidates in the Third round of NIST’s Additional Call for Post-Quantum Digital Signature Schemes. In this talk, we revisit recent cryptanalytic efforts targeting UOV and its variants, in particular the wedge attack [1] and subsequent extensions [2, 3, 4]. We will discuss the main ideas behind these attacks and their implications for multivariate cryptography.

Since the Stone Age, people have already known that any polynomial of degree d has at most d real solutions, but over finite fields, everything is still chaos. It takes a long time until the Age of Enlightenment, that Lagrange sets his first steps onto the land of finite fields with his theorem, stating that a polynomial of degree d over any finite field still has at most d roots (Lagrange does not even know what is finite field at the time!). Building on this crucial property of polynomials, Irving Reed and Gustave Solomon bring its influence from number theory all the way to information theory, by inventing the Reed-Solomon code. They also did not know at the time that this code became so influential in a field called Zero Knowledge Proofs, especially its list decoding property. Most parameter regimes for list decoding have been explored, by famous algorithms from Berlekamp-Welch to Guruswami-Sudan, but there is still one unknown range, that is from the Johnson Bound 1 − √R to the code capacity 1 − R. This talk acts as a small survey to introduce the techniques of these algorithms, and also introduce the list decoding (open) problem beyond the Johnson bound. There also happens to have a prize tag by the Ethereum Foundation for solving it.

Bilinear groups, also known as pairing groups, are a versatile tool that enables many efficient cryptographic constructions. Among bilinear groups, those with a composite order (𝑁 = 𝑝 ∙ 𝑞 for two large, secret primes 𝑝, 𝑞) offer an additional algebraic structure which is advantageous in many applications. They are however dramatically less efficient than their prime-order counterparts, so multiple translation frameworks for constructions from composite- to prime-order groups have been introduced in the literature.

Motivated by the recent construction of Batch Arguments for NP (BARGs) with linear-size CRS by Chen, Elias and Wu [Asiacrypt ’25], based on composite-order groups, we notice that these previous frameworks fail to transfer their scheme to the prime-order setting. In this work, we identify and close this gap by introducing a new translation framework based on a new abstraction called dual encodings. The crucial feature of these objects is a security property called indistinguishability that allows embedding hidden subgroups, emulating composite-order groups more faithfully and thus enabling more powerful translations. Then, we realize dual encodings using functional encryption for function-hiding inner products. Finally, we apply our framework to build the first BARG with linearsize CRS from prime-order groups, while preserving the (statistical) somewhere extractability of previous constructions. Our result represents a significant step toward practically efficient BARGs and showcases a surprising application of functional encryption which we find of independent interest.

This is a joint work with David Balbás (ETH Zurich) and Dario Fiore (IMDEA Software Institute).

We present RoKoko, a new lattice-based succinct argument system that achieves a linear-time prover alongside polylogarithmic communication and verifier complexity. Asymptotically, our construction improves upon RoK and Roll (ASIACRYPT 2025), the first post-quantum SNARK with \(\tilde{O}(\lambda)\) proof size, by a multiplicative factor of \(\Theta(\log \lambda)\). Practically, our system yields proofs of roughly 200 KB, while outperforming the state-of-the-art polynomial commitment scheme Greyhound (CRYPTO 2024) with a 100× faster verification time, similar prover time, and competitive proof size. Our framework natively supports (tensor-)structured relations, such as polynomial evaluation and sumcheck relations.

At a high level, our construction follows the recursive split-and-fold paradigm: the prover first splits the witness into \(\rho\) sub-witnesses, sends the corresponding cross-terms, and then folds them into a single witness that is shorter by a factor of \(\rho\) using verifier challenges. Prior works typically restrict \(\rho = O(1)\) to preserve succinct verification and maintain the optimal \(\tilde{O}(\lambda)\) proof size. We overcome this “constant barrier”, which enables larger \(\rho\) and thereby reduces the proof size. To achieve this, we introduce the following technical contributions.

(i) Committed folding. Instead of sending \(O(\rho)\) cross-terms in the clear, the prover commits to the messages and later proves that the committed vector satisfies the verification relations. This enables the use of a larger shrinking factor, thereby reducing the number of recursion rounds. While this strategy has been successfully used in LaBRADOR (CRYPTO 2023), additional care is required here to preserve succinct verification.

(ii) Recursive commitments. We generalise the double-commitment technique from LaBRADOR into a framework for recursive commitments, yielding further compression in commitment size. This results in concrete improvements in communication within each recursion round.

(iii) Sumcheck-driven structured recursion. We extend the sumcheck framework from SALSAA (ePrint 2025/2124) to prove substantially more complex constraints arising in our construction (and open for future extensions), including correctness of random projections, inner-product claims and well-formedness of recursive commitments. While expressing these constraints as sumcheck relations requires considerable technical effort, the resulting protocols compose seamlessly with the structured recursion, yielding both linear-time proving and succinct verification.

In this work, we present Hachi, a concretely efficient multilinear polynomial commitment scheme that offers succinct proof sizes of \(\mathrm{poly}(\ell, \lambda)\) and achieves a “square-root” verifier time complexity of \(\tilde{O}(\sqrt{2^{\ell}\lambda})\) for \(\ell\)-variate polynomials under the Module-SIS assumption. Compared to the current state-of-the-art scheme, Greyhound (CRYPTO 2024), Hachi provides an asymptotic improvement of \(\tilde{O}(\lambda)\) in verification time, which translates into a practical 12.5-fold speedup, while maintaining compact proofs of approximately 55 KB.

To improve the verification time, we adopt the sumcheck protocol. Note that the standard sumcheck has efficiency bottlenecks for lattice-based constructions, since lattice operations are usually performed over power-of-two cyclotomic rings \(\mathbf{R}_q := \mathbb{Z}_q[X]/(X^d + 1)\). To address this challenge, we provide a novel approach that integrates Greyhound with the ring-switching idea proposed by Huang, Mao and Zhang (ePrint 2025). Surprisingly, under this approach, the verifier does not need to perform any multiplication over \(\mathbf{R}_q\), enabling a much faster verification time. This technique could be of independent interest for building lattice-based SNARKs, particularly for achieving faster verification.

As a separate contribution, we introduce a generic reduction that converts polynomial evaluation proofs over extension fields \(\mathbb{F}_{q^k}\) (under suitable parameter regimes) into equivalent statements over cyclotomic rings \(\mathbf{R}_q\). This reduction is compatible with existing lattice-based polynomial commitment schemes and can be integrated as a modular enhancement to broaden applicability to statements over extension fields.

Since the invention of public key cryptography in 1976, a lot of mathematics has been used in the area of cryptography. However, no proof has ever been given that secure public key cryptography is possible at all. Moreover, no attempt has been made to develop the tools to prove or disprove the conjecture of their existence. Thousands, of papers have been published based on unproven assumptions. This is in sharp contrast to the approach that was used to prove Fermat’s Last Theorem. New mathematics was developed, in particular elliptic curves, which eventually lead to the desired proof.

The 50 years anniversary of the invention of public key cryptography is the right time to reflect back on what has been achieved, and what not, in these 50 years. Giving a survey of the area is impossible. Therefore the focus will be on what is used in the practical world, which is only a small fraction of all the work. We will also briefly explain the concept of unconditional security.

To better understand the importance of mathematics in the analysis of cryptosystems, we briefly explain the breaking of the Merkle-Hellman basic knapsack scheme, which was the fastest public key cryptosystem in the 1970s.

Zero-knowledge simulators, initially developed for proving the security of proof systems, turned out to be also useful in constructing advanced protocols from simple three-move interactive proofs. However, in the context of multi-round public-coin protocols, the interfaces of these auxiliary algorithms become more complex, introducing a range of technical challenges that hinder the generalization of these constructions.

We introduce a framework to enhance the usability of zero-knowledge simulators in multi-round argument systems for protocol designs. Critical-round zero-knowledge relies on the ability to perform complete zero-knowledge simulations by knowing the challenge of just one specific round in advance. We show that these notions are satisfied by diverse protocols based on MPC-in-the-Head, interactive oracle proofs, and split-and-fold arguments.

We demonstrate the usefulness of the critical round framework by constructing proofs of partial knowledge (Cramer, Damgård, and Schoenmakers, CRYPTO’94) and trapdoor commitments (Damgård, CRYPTO’89) from critical-round multi-round proofs.

The work will be presented in IACR Eurocrypt 2026 conference.

A classical computer uses Boolean circuits and can only operate on one input at a time. Quantum computers compute on a superposition of states, but need a measurement to extract the result. In this presentation we propose the use of Weyl Algebra to perform computations on N inputs at once. We also need a generalization of a “measurement” to obtain a useful result. Although this new type of computation is inspired by quantum computers, we do not need to follow the laws of quantum physics. We look at the computational complexity of certain computation when using this new approach. In particular at (i) the potential impact on porting Shor’s quantum algorithm to a classical computer while maintaining polynomial running time, and (ii) whether co-NP=P, which would imply NP=P.