NuTMiC 2026: Abstracts

TBA

Computing class groups and unit groups is a famous problem in algorithmic number theory, with many cryptographic applications. We will first provide some motivation for studying this problem, arising from lattice-based cryptography. In a second part, we will review the existing quantum and classical algorithms that compute class groups and unit groups in fields of arbitrary large degree. Finally, we will comment on the heuristics that are used in the classical algorithm, and we will see how these heuristics can be proven (assuming only the Generalized Riemann Hypothesis).

TBA

TBA

A multiple base $(g_1,\ldots,g_n)$ discrete logarithm problem in an abelian group $G$ concerns solutions to the equation $g_1^{x_1}\cdot\ldots\cdot g_n^{x_n}=g$ for $(x_1,\ldots,x_n)\in\Z^n$, where $g_1,\ldots,g_n,g\in G$. In this paper, we show that the local to global multiple base discrete logarithm problem in the group $\mathbb{G}_m^{\;2}(\mathcal{O}_{F,S})=(\mathcal{O}_{F,S}^\times)^{2}$, for a number field $F$, has counterexamples for arbitrary large bases, including infinite bases.

This paper deals with the hardness of finding short vectors in module lattices. Let K be a number field of degree d and OK its ring of integers. We show that if a module lattice M of rank n in OK^n has some Galois-symmetries, namely if it is fixed coordinate-wise (as a set) by a group G of automorphisms of K, then M can actually be seen as a module of rank n over a subfield K' of K (K' is the fixed-field of G), whose degree is |G| times smaller than the degree of K. When one wants to find short vectors in M, this translates into the observation that the module lattice M, which is a priori a lattice of rank nd can in fact be seen as a lattice of rank only nd/|G|. Hence, finding short vectors in M is easier than what one could have expected by forgetting about the algebraic structure of M.
This result is a generalization of a similar result by Boudgoust, Gachon and Pellet-Mary (Crypto'22), which was restricted to ideal lattices (i.e., modules of rank 1).

We shall present an approach applying the notion of polynomial time reduction of Integer Factoring of Composite numbers (IFC) to problem ECNSOSGC. Moreover we investigate the factoring algorithms with oracles OrdEll and DecOrdEll of positive integers having the fixed number of prime divisors. These results apply the Coppersmith method of factorization developed before in the case of the oracle Sigma.

In this paper, we present a new attack against search-LWE instances with a small secret key. The method consists of lifting the public key to $\mathbb Z$ and finding a good Diophantine approximation of the public key divided by the modulus $a$. This is done using lattice reduction algorithms. The lattice considered, and the approximation quality needed is similar to known decision-LWE attacks for small keys. However, we do not require an in-depth analysis of the reduction algorithm (any reduction algorithm giving small enough vectors is sufficient for us), and our method solves the search problem directly, which is harder than the decision problem.

Abelian varieties with complex multiplication (CM) play a central role in several areas of modern public-key cryptography. For example, ECC and its higher-dimensional generalizations, such as HCC, rely on the group structure of Jacobians of algebraic curves over finite fields.
In this paper, we consider two families (dependent on the parameter a) of hyperelliptic curves defined over Q whose Jacobians have CM by the quartic field Q(√(-5+√5)). For an odd prime p∤55a, we obtain types of reduction (supersingular, superspecial, ordinary) at p in terms of congruences modulo 40 and the exact formulae for the zeta function over F_{p} for p not congruent to 1,19,29,31(mod40). We deduce as conclusions the complete characterization of the torsion subgroup and some information about the rank of the Mordell-Weil group.

We study multi-issuer blind issuance schemes in the lattice setting and present a construction that incorporates entropy recycling techniques to improve efficiency in the multi-issuer setting. Our construction adapts standard lattice-based blind signature techniques to the multi-issuer setting, while enabling partial reuse of randomness across protocol components.
We prove that the resulting scheme satisfies blindness and multi-issuer query-bounded unforgeability in the random oracle model, based on the hardness of the underlying M-LWE and \M-SIS problems, as well as the properties of the employed zero-knowledge proof systems. Our results show that entropy recycling can be leveraged to optimize lattice-based blind issuance schemes.

Computing the endomorphism ring $\mathrm{End}(E)$ of a supersingular elliptic curve $E$ is a fundamental challenge in computational algebra and is central to the security of isogeny-based cryptography. In this paper, we present practical improvements to the cycle-finding algorithm proposed by Eisentr\"{a}ger \textit{et al.} for efficiently finding isogeny cycles through $E$. Let $\mathcal{V}$ be the set of $j$-invariants of supersingular elliptic curves defined over a finite field of characteristic $p \geq 5$. For a set of primes $L$, we define an enlarged target subset $\mathcal{S}_L \subseteq \mathcal{V}$ consisting of elements $j \in \mathcal{V}$ that satisfy $\Phi_r(j, j^p) = 0$ for some $r \in L$, where $\Phi_r$ denotes the $r$-th modular polynomial. Our approach accelerates the search by generating a sequence of random $\ell$-isogenies for $\ell \in \{ 2, 3\}$ while performing a membership test for $\mathcal{S}_L$ at each step to facilitate the folding of the sequence into an isogeny cycle. Based on complexity analysis, we provide an asymptotically optimal set $L$ to minimize the search cost. We also present a stable and fast implementation in SageMath to report running times for computing $\mathrm{End}(E)$ with primes $p$ of up to \textbf{50} bits. In particular, we determine an optimal set $L$ in both theory and practice.

The CGL hash function, introduced by Charles et al. in 2009, is defined as a non-backtracking walk through a Ramanujan graph. An upper bound on the non-backtracking mixing time of such a graph is given by Basso et al. (2023). However, usually, CGL ignores one edge in the first step, so that this bound does not provide an accurate analysis in this case. We take this into account and use the result by Basso et al. to give a modified bound. In the second part, we introduce some natural generalizations of CGL, by considering two distinct prime isogeny degrees at the same time. We provide upper bounds on the mixing time and discuss collision resistance. Here, we take into account both the usual definition of mixing time and the one where one edge is ignored in the first step. The final version turns out to have mixing time comparable to CGL in terms of bit-length and is collision resistant, while allowing for parallelization in a natural way.

The Ring Learning with Errors (RLWE) problem is widely believed to be computationally hard and underpins many modern lattice-based cryptographic constructions. Its security rests on a worst-case to average-case reduction from the approximate Shortest Vector Problem (SVP) on ideal lattices to average-case instances of RLWE, established by Lyubashevsky, Peikert, and Regev.
In this work we study the influence of the algebraic structure of cyclotomic fields $K$ on the hardness of Ideal-SVP and hence on the security of RLWE-based schemes. We investigate how the ideal class group of cyclotomic fields, and specifically $h^+(K)$ and $h^-(K)$, influence the efficiency of algorithms that find mildly short vectors in ideal lattices, following the approach of Cramer, Ducas, and Wesolowski.
We provide a detailed analysis of class number growth: the real class numbers $h^+(K)$ exhibit slow polynomial growth, while the relative class numbers $h^-(K)$ grow slightly faster than exponentially.
Using these results, we critically examine standard power-of-two RLWE parameter choices and propose prime cyclotomic fields as alternative parameter rings. Fields with large class groups impose additional computational cost on known class-group-based attacks, potentially strengthening the underlying Ideal-SVP hardness. We present concrete parameter tables and discuss efficiency tradeoffs.

This article present a new, direct and simple formula for constructing Mignotte sequences.
Note: There will be more done with the paper - some additions and expansion of the subject that are not shown in the paper yet, but will be contained in the lecture.

In recent years, various RSA variants based on diverse algebraic structures have been proposed with the aim of enhancing its security. In this paper, we focus on type-A and type-B variants, which generalize RSA-type constructions over the ring of Gaussian integers modulo $N = pq$ and constructions based on the cubic Pell equation, respectively. First, we present a lattice-based method for finding, in polynomial time, solutions to the equation $xH(y)+cz\equiv 0 \bmod \beta$, where $H(y)$ is a monic polynomial, thereby generalizing previously established bounds. We then apply this method to factor the modulus in both type-A and type-B cryptosystems under multiple attack scenarios, such as partial key information attacks. Therefore, we provide certain bounds for the secret exponent under which these cryptosystems can be compromised.

A multi-signature scheme is a digital signature protocol in which a set of n signers, each possessing their own distinct private key, jointly generate a single, verifiable signature on a common message. In addition, an aggregate signature scheme allows multiple signatures on different messages from different signers to be combined into a single compact signature. Although these techniques improve efficiency, verification still requires access to all original messages, which can be limiting in terms of scalability and accessibility. For aggregate signature schemes, Goyal and Vaikuntanathan introduced the notion of local verification, which allows a verifier to check whether a particular message m is included in an aggregate signature using auxiliary information, without requiring access to the full set of signed messages. In this paper, we propose a locally verifiable aggregated multi-signature (LVAMS) scheme that supports aggregation from a non-fixed set of signers, allowing each signing session to involve different participants. It produces a compact final signature by aggregating multiple multi-signatures, and enables efficient local verification of individual or multiple message-signature pairs (via auxiliary values), without requiring access to the entire message set. We also provide a theoretical performance analysis and prove the security of the scheme in the random oracle model.