Russell W. F. Lai
LightNews LightNews
russell-lai.bsky.social
Russell W. F. Lai
@russell-lai.bsky.social
70 followers 51 following 0 posts
Assistant professor in cryptography at Aalto University, Finland

https://russell-lai.hk
https://research.cs.aalto.fi/crypto/
https://algorithms.fi
Posts Replies Media Videos
Reposted by Russell W. F. Lai
eprint.ing.bot
SALSAA – Sumcheck-Aided Lattice-based Succinct Arguments and Applications (Shuto Kuriyama, Russell W. F. Lai, Michał Osadnik, Lorenzo Tucci) ia.cr/2025/2124
Abstract. We present SALSAA, a more efficient and more versatile extension of the state-of-the-art lattice-based fully-succinct argument frameworks, “RoK, paper, SISsors (RPS)’’ and”RoK and Roll (RnR)’’ [Klooß, Lai, Nguyen, and Osadnik; ASIACRYPT’24, ’25], integrating the sumcheck technique as a main component. This integration enables us to design an efficient norm-check protocol (controlling the norm during witness extraction) with a strictly linear-time prover while reducing proof sizes by 2-3× compared to the previous quasi-linear-time norm-check in RPS/RnR, eliminating a central performance bottleneck. The sumcheck integration also allows us to natively support a wider class of relations, including rank-1 constraint systems (R1CS), which are widely used to express real-world computations. To demonstrate the versatility and efficiency of our framework, we showcase three impactful applications achieved by different RoKs (Reductions of Knowledge) compositions: (i) a lattice-based succinct argument of knowledge with a linear-time prover, achieving a verifier time of 41 ms, prover runtime of 10.61 s, and proof size of 979 KB for a witness of 2²⁸ ℤ_(q) elements; (ii) a polynomial commitment scheme with matching performance; and (iii) the first lattice-based folding scheme natively operating on ℓ₂-norm-bounded witnesses, achieving highly efficient verification in 2.28 ms and producing a proof of just 73 KB for a witness of 2²⁸ Z_(q) elements, outperforming prior works for the family of linear relations. We provide a modular, concretely efficient Rust implementation of our framework, benchmarked over cyclotomic rings with AVX-512-accelerated NTT-based arithmetic, demonstrating the practical efficiency of our approach. Image showing part 2 of abstract.
November 21, 2025 at 2:28 PM
Reposted by Russell W. F. Lai
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
Reposted by Russell W. F. Lai
eprint.ing.bot
A Gaussian Leftover Hash Lemma for Modules over Number Fields (Martin R. Albrecht, Joël Felderhoff, Russell W. F. Lai, Oleksandra Lapiha, Ivy K. Y. Woo) ia.cr/2025/1852
Abstract. Leftover Hash Lemma (LHL) states that X ⋅ v for a Gaussian v is an essentially independent Gaussian sample. It has seen numerous applications in cryptography for hiding sensitive distributions of v. We generalise the Gaussian LHL initially stated over ℤ by Agrawal, Gentry, Halevi, and Sahai (2013) to modules over number fields. Our results have a sub-linear dependency on the degree of the number field and require only polynomial norm growth: ∥v∥/∥X∥. To this end, we also prove when X is surjective (assuming the Generalised Riemann Hypothesis) and give bounds on the smoothing parameter of the kernel of X. We also establish when the resulting distribution is independent of the geometry of X and establish the hardness of the k-SIS and k-LWE problems over modules (k-MSIS/k-MLWE) based on the hardness of SIS and LWE over modules (MSIS/MLWE) respectively, which was assumed without proof in prior works.
October 8, 2025 at 4:39 AM
Reposted by Russell W. F. Lai
eprint.ing.bot
Papercraft: Lattice-based Verifiable Delay Function Implemented (Michał Osadnik, Darya Kaviani, Valerio Cini, Russell W. F. Lai, Giulio Malavolta) ia.cr/2025/879
Abstract. A verifiable delay function (VDF) requires a specified number of sequential steps to compute, yet the validity of its output can be verified efficiently, much faster than recomputing the function from scratch. VDFs are a versatile cryptographic tool, with many industrial applications, such as blockchain consensus protocols, lotteries and verifiable randomness. Unfortunately, without exceptions, all known practical VDF constructions are broken by quantum algorithms. In this work, we investigate the practicality of VDFs with plausible post-quantum security. We propose Papercraft, a working implementation of a VDF based entirely on lattice techniques and thus plausibly post-quantum secure. Our VDF is based on new observations on lattice-based succinct argument systems with many low-level optimisations, yielding the first lattice-based VDF that is implementable on today’s hardware. As an example, our Papercraft implementation can verify a computation of almost 6 minutes in just 7 seconds. Overall, our work demonstrates that lattice-based VDFs are not just a theoretical construct, paving the way for their practical deployment. Image showing part 2 of abstract.
May 19, 2025 at 10:10 AM
Reposted by Russell W. F. Lai
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 Russell W. F. Lai
eprint.ing.bot
Pilvi: Lattice Threshold PKE with Small Decryption Shares and Improved Security (Valerio Cini, Russell W. F. Lai, Ivy K. Y. Woo) ia.cr/2025/1691
Abstract. Threshold public-key encryption (tPKE) enables any subset of t out of K parties to decrypt non-interactively, while any ciphertext remain secure if less that t decryption shares are known. Despite recent progress, existing lattice-based tPKEs face at least one of the following drawbacks: (1) having large decryption share size – polynomial in K and some even exponential in t, (2) proven secure only against relaxed security models where the adversary is not allowed to see decryption shares of challenge ciphertexts, and (3) lack of concrete efficiency, in particular due to the requirement of super-polynomial modulus for noise flooding. We present Pilvi, a new thresholdised variant of Regev’s public-key encryption scheme, which achieves both small decryption shares and a strong form of simulation-based security under the Learning with Errors (LWE) assumption. Our construction has decryption share size t ⋅ log K ⋅ poly(λ) and allows the use of a polynomial-size modulus assuming an a priori bound on the number of queries Q. It remains secure even when an adaptive adversary requests partial decryptions of both challenge and non-challenge ciphertexts, as long as for each ciphertext the number of corrupt parties plus the number of shares obtained is less than t. We provide concrete parameter suggestions for 128-bit security for a wide range of (t, K, Q), including cases where t ≈ K/2 for up to K ≤ 32 users and Q ≤ 2⁶⁰ partial decryption queries. The ciphertext size ranges from 14 to 58 KB and the partial decryption share size ranges from 1 to 4 KB. Along the way, we abstract out a general purpose tool called the threshold-LWE assumption, which we prove to follow from LWE. The threshold-LWE assumption captures the core steps in security proofs of schemes involving Shamir’s secret-sharing the LWE secret with carefully chosen evaluation points, the algebraic structures from the latter being what enabling the efficiency of our tPKE scheme. As an additional application, we also show how to construct distributed pseudorandom functions (dPRFs) from the threshold-LWE assumption. Image showing part 2 of abstract.
September 18, 2025 at 1:51 PM
Reposted by Russell W. F. Lai
tjesi.bsky.social
The EU Parliament has published a new proposal for Chat Control to mass-surveil all digital communication in Europe. The proposal is ineffective, weakens secure communication, and violates basic human privacy. This must be stopped immediately. #ChatControl
csa-scientist-open-letter.org/Sep2025
csa-scientist-open-letter.org
September 9, 2025 at 11:11 AM
Reposted by Russell W. F. Lai
icthiit.bsky.social
🚨 Job Alert! 🚨
We are #hiring Postdoctoral Fellows (3 years) or Research Fellows (5 years) for researchers in ICT. Find out more information in the 🔗 www.hiit.fi/hiit-postdoc... #AcademicSky #HigherEd #EduSky #Research #postdocjobs #postdoc
July 3, 2025 at 12:23 PM
Reposted by Russell W. F. Lai
eprint.ing.bot
Lattice-based Obfuscation from NTRU and Equivocal LWE (Valerio Cini, Russell W. F. Lai, Ivy K. Y. Woo) ia.cr/2025/1129
Abstract. Indistinguishability obfuscation (iO) turns a program unintelligible without altering its functionality and is a powerful cryptographic primitive that captures the power of most known primitives. Recent breakthroughs have successfully constructed iO from well-founded computational assumptions, yet these constructions are unfortunately insecure against quantum adversaries. In the search of post-quantum secure iO, a line of research investigates constructions from fully homomorphic encryption (FHE) and tailored decryption hint release mechanisms. Proposals in this line mainly differ in their designs of decryption hints, yet all known attempts either cannot be proven from a self-contained computational assumption, or are based on novel lattice assumptions which are subsequently cryptanalysed. In this work, we propose a new plausibly post-quantum secure construction of iO by designing a new mechanism for releasing decryption hints. Unlike prior attempts, our decryption hints follow a public Gaussian distribution subject to decryption correctness constraints and are therefore in a sense as random as they could be. To generate such hints efficiently, we develop a general-purpose tool called primal lattice trapdoors, which allow sampling trapdoored matrices whose Learning with Errors (LWE) secret can be equivocated. We prove the security of our primal lattice trapdoors construction from the NTRU assumption. The security of the iO construction is then argued, along with other standard lattice assumptions, via a new Equivocal LWE assumption, for which we provide evidence for plausibility and identify potential targets for further cryptanalysis. Image showing part 2 of abstract.
June 17, 2025 at 2:52 AM
Reposted by Russell W. F. Lai
malb.bsky.social
Rerandomising LWE martinralbrecht.wordpress.com/2025/03/01/r...
Drake No: A(s,e) + A(t,d) Drake Yes: UAO
March 1, 2025 at 12:58 PM
Reposted by Russell W. F. Lai
eprint.ing.bot
Hollow LWE: A New Spin, Unbounded Updatable Encryption from LWE and PCE (Martin R. Albrecht, Benjamin Benčina, Russell W. F. Lai) ia.cr/2025/340
Abstract. Updatable public-key encryption (UPKE) allows anyone to update a public key while simultaneously producing an update token, given which the secret key holder could consistently update the secret key. Furthermore, ciphertexts encrypted under the old public key remain secure even if the updated secret key is leaked – a property much desired in secure messaging. All existing lattice-based constructions of UPKE update keys by a noisy linear shift. As the noise accumulates, these schemes either require super-polynomial-size moduli or an a priori bounded number of updates to maintain decryption correctness. Inspired by recent works on cryptography based on the lattice isomorphism problem, we propose an alternative way to update keys in lattice-based UPKE. Instead of shifting, we rotate them. As rotations do not induce norm growth, our construction supports an unbounded number of updates with a polynomial-size modulus. The security of our scheme is based on the LWE assumption over hollow matrices – matrices which generate linear codes with non-trivial hull – and the hardness of permutation code equivalence. Along the way, we also show that LWE over hollow matrices is as hard as LWE over uniform matrices, and that a leftover hash lemma holds for hollow matrices. Image showing part 2 of abstract.
February 25, 2025 at 7:28 PM