Relating Novel Lattice Assumptions

While lattice-based constructions have historically relied on the hardness of SIS, LWE, NTRU, or their ring-versions directly, the cryptographic community began diverging from this path in 2022, introducing a wealth of novel lattice-based assumptions. These novel assumptions enable the construction of several advanced primitives such as broadcast encryption. While some of these assumptions are backed by reductions from standard assumptions, others rely on entirely on cryptanalytic efforts. The development in this area is captured and tracked via the Lattice Assumption Zoo (LAZ).

To establish a more sound foundation for advanced constructions, cryptographers actively search for new reductions between these novel assumptions and standard lattice problems. As the rapidly growing body of work in this area is too large to summarise here – and will be comprehensively systematised in the LAZ – this page focusses on a high-level summary of my key contributions. It assumes the reader is either familiar with these assumptions or willing to explore the linked LAZ entries.

Tight Reductions for SIS-with-Hints Assumptions with Applications to Anonymous Credentials

In a collaboration with Ngoc Khanh Nguyen (Nguyen & Siemer, 2026), we explore the ISIS$_f$ and One-More-ISIS assumption families, which are both related to the construction of anonymous credentials. The main contributions of this work are:

• A reduction from ISIS$_f$ to Generalised ISIS$_{f_\kappa}$ (GenISIS$_{f_\kappa}$) with properly chosen keys $\kappa$.
• An adoption of the MP12-signature to reduce SIS to GenISIS$_{f_\kappa}$ for a specific choice of $f_\kappa$. This provides the first reduction from a standard assumption to a GenISIS$_{f_\kappa}$ instance in the standard model. However, because the function $f_\kappa$ utilises lattice-mixing, it should not be considered for practical use.
• A tight reduction from GenISIS$_{f_\kappa}$ to its interactive version, improving upon prior work by a polynomial factor. Evidently, this reduction also applies to ISIS$_f$ and its interactive version.
• Proving that Randomised One-More-ISIS (rOM-ISIS) is at least as hard as One-More-ISIS (OM-ISIS); a lower bound for the robustness of rOM-ISIS claimed in the original work introducing this variant.
• An equivalence result for different domains of rOM-ISIS, specifically demonstrating equivalence between the domains $\{-1,1\}$ and $\{0,1\}$.

Ultimately, our tight reduction successfully bridges the gap between the static and interactive versions of GenISIS$_{f_{\kappa}}$. In practice, this enables the construction of proof-friendly signatures without incurring the significant efficiency loss observed in prior works. This allows constructions such as the anonymous credential scheme proposed by Bootle et al. to base their security directly on the more extensively studied and easier to analyse assumption GenISIS$_{f_\kappa}$, circumventing the previous 4x blow-up in credential size accompanying this decision.