Tessera

Russell W. F. Lai

@russell-lai.bsky.social

Assistant professor in cryptography at Aalto University, Finland https://russell-lai.hk https://research.cs.aalto.fi/crypto/ https://algorithms.fi

0 Posts83 Follower 52 Folgt

Martin R. Albrecht @malb.bsky.social · 2mo ago

Hardness of hinted ISIS from the space-time hardness of lattice problems martinralbrecht.wordpress.com/2026/06/12/h...

Morpheus (from the movie The Matrix) asking: "What if I told you that ISIS is hard even given a trapdoor"

ePrint Updates @eprint.ing.bot · 6mo ago

Hardness of hinted ISIS from the space-time hardness of lattice problems (Martin R. Albrecht, Russell W. F. Lai, Eamonn W. Postlethwaite) ia.cr/2026/187

Abstract. We initiate the study of basing the hardness of hinted ISIS problems (i.e. with trapdoor information, or ‘hints’) on the previously conjectured space-time hardness of lattice problems without hints. We present two main results.

1. If there exists an efficient algorithm for hinted ISIS that outputs solutions a constant factor longer than the hints, then there exists a single-exponential time and polynomial memory zero-centred spherical Gaussian sampler solving hinted SIS with norm a constant factor shorter than the hints.

2. Assume the existence of a chain of algorithms for hinted ISIS each taking as input Gaussian hints whose norms decrease by a constant factor at each step in the chain, then there exists a single-exponential time and polynomial memory algorithm for SIS with norm a quasilinear factor from optimal.

The existence of such hinted ISIS solvers implies single-exponential time and polynomial memory algorithms for worst-case lattice problems, contradicting a conjecture by Lombardi and Vaikuntanathan (CRYPTO’20) and all known algorithms. This suggests that hinted ISIS is hard.

Apart from advancing our understanding of hinted lattice problems, an immediate consequence is that signing the same message twice in GPV-style [Gentry–Peikert–Vaikuntanathan, STOC’08] schemes (without salting or derandomisation) likely does not compromise unforgeability. Also, cryptanalytic attempts on the One-More-ISIS problem [Agrawal–Kirshanova–Stehlé-Yadav, CCS’22] likely will need to overcome the conjectured space-time hardness of lattices.

Diego F. Aranha @dfaranha.bsky.social · 8mo ago

If you believe that smart people cannot do utterly dumb things, just look at the Eurocrypt'26 rebuttal process.

ePrint Updates @eprint.ing.bot · 9mo ago

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.

Helger Lipmaa @helger.bsky.social · 9mo ago

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

ePrint Updates @eprint.ing.bot · 10mo ago

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.

ePrint Updates @eprint.ing.bot · last yr.

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.

ePrint Updates @eprint.ing.bot · last yr.

RoK and Roll – Verifier-Efficient Random Projection for Õ(λ)-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 Õ(λ) 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 Õ(λ) while maintaining a succinct verification time. These two techniques, combined with existing RoKs from RPS, yield a succinct argument system with communication complexity Õ(λ) and succinct verification for structured linear relations.

ePrint Updates @eprint.ing.bot · 11mo ago

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.

Tjerand Silde @tjesi.bsky.social · 11mo ago

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

Helsinki Institute for Information Technology @icthiit.bsky.social · last yr.

🚨 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

ePrint Updates @eprint.ing.bot · last yr.

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.

Martin R. Albrecht @malb.bsky.social · last yr.

Rerandomising LWE martinralbrecht.wordpress.com/2025/03/01/r...

Drake No: A(s,e) + A(t,d)
Drake Yes: UAO

ePrint Updates @eprint.ing.bot · last yr.

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.