Plenary talks

1. Daniel Bernstein,
   „Slow-boiled frogs”
   
   Abstract. In 2013, I introduced a name for cryptography that simply works, solidly resists attacks, and never needs any upgrades: I called it boring cryptography. This talk is about the opposite extreme, which is called lattice-based cryptography. I’ll talk about some general context and some number-theoretic issues that appear in the area.
   
   
2. Philippe Michel,
   „Recent examples of equidistribution in number theory”
   
   Abstract. Since the seminal work of H. Weyl (whop established that if \alpha is irrational the sequence (\alpha n)_{n\geq 1} is equidistributed modulo 1), equidistribution has played a central role in number theory and its applications. In this talk will discuss recent examples of equidistribution for various sequences of arithmetic objects, the techniques used to establish these as well as some (number theoretic) applications with the hope that these will trigger further ideas from cryptographers.
   
   
3. Jacek Pomykała,
   „Elliptic-curve factorization, witnesses and oracles”
   
   Abstract. The survey talk concerns the selected approaches to integer factorization problem of positive integer N, with the aid of elliptic curves E over \Z_N. I will mainly focus on the investigation of various oracles related to EC-based factorization in one approach and on the investigation of so-called decomposition witnesses in the other. The second approach covers two aspects – first dealing with the extension of the classical Fermat factoring method for elliptic curves and the second inspired by familiar Lenstra’s results based on the distribution of B-smooth local orders \#E(F_r) for prime r\mid N. Here the more detailed analysis concerns the investigation of parameters \beta and \sigma allowing to simultaneously control the B-smooth factor and the squarefree divisor of non B-smooth factor of \#E(F_r) in the suitable ranges. They are responsible for the choice the admissible elliptic curve E over \Z_N and the deterministic time of factorization of N with the aid of witness (u,v)\in \Z_N^2.
   
   
4. Damien Robert,
   „On the efficient representation of isogenies”
   
   Abstract. We survey different representations of isogenies between elliptic curves. Notably, we focus on the novel representation obtained via the techniques in the SIDH attacks, which showed that every isogeny admits an efficient representation by embedding it into a higher dimensional smooth degre isogeny. We explain how to work in practice with this representation (equality testing, division, push forwards and splittings), and discuss some applications, both in number theory (computation of endomorphism rings of ordinary elliptic curves, canonical lifts, deformations) and isogeny based cryptography (new signature schemes, class group action).
   
   
5. Igor E. Shparlinski,
   „Integers of prescribed arithmethic structure in residue classes”
   
   Abstract. We give an overview of recent results about the distribution of some special integers in residues classes modulo a large integer q. Questions of this type were introduced by Erdos, Odlyzko and Sarkozy (1987), who considered products of two primes as a relaxation of the classical question about the distribution of primes in residue classes. Since that time, numerous variations have appeared for different sequences of integers. The types of numbers we discuss include smooth, square-free, square-full and almost primes integers. We also expose, without going into technical details, the wealth of different techniques behind these results: sieve methods, bounds of short Kloosterman sums, bounds of short character sums and many others.
   
   

Contributed talks

1. George Teseleanu,

   „The Case of Small Prime Numbers Versus the Okamoto-Uchiyama Cryptosystem”

   Abstract. In this paper we study the effect of using small prime numbers within the Okamoto-Uchiyama public key encryption scheme. We introduce two novel versions and prove their security. Then we show how to choose the system’s parameters such that the security results hold. Moreover, we provide a practical comparison between the cryptographic algorithms we introduced and the original Okamoto-Uchiyama cryptosystem.

2. Andrew Mendelsohn and Cong Ling,

   „Algebraic Equipage for Learning with Errors in Cyclic Division Algebras”

   Abstract. In `Noncommutative Ring Learning With Errors From Cyclic Algebras’, a variant of Learning with Errors from cyclic division algebras, dubbed ‘Cyclic LWE’, was developed, and security reductions similar to those known for the ring and module case were given, as well as a Regev-style encryption scheme. In this work, we make a number of improvements to that work: namely, we describe methods to increase the number of cryptographically useful division algebras, demonstrate the hardness of CLWE from ideal lattices obtained from non-maximal orders, and study Learning with Rounding in cyclic division algebras.

3. Semira Einsele and Gerhard Wunder,

   „From Worst to Average Case to Incremental Search Bounds of the Strong Lucas Test”

   Abstract. The strong Lucas test is a widely used probabilistic primality test in cryptographic libraries. When combined with the Miller-Rabin primality test, it forms the Baillie-PSW primality test, known for its absence of false positives, undermining the relevance of a complete understanding of the strong Lucas test. In primality testing, the worst-case error probability serves as an upper bound on the likelihood of incorrectly identifying a composite as prime. For the strong Lucas test, this bound is 4/15 for odd composites, not products of twin primes. On the other hand, the average-case error probability indicates the probability that a randomly chosen integer is inaccurately classified as prime by the test. This bound is especially important for practical applications, where we test primes that are randomly generated and not generated by an adversary. The error probability of 4/15 does not directly carry over due to the scarcity of primes, and whether this estimate holds has not yet been established in the literature. This paper addresses this gap by demonstrating that an integer passing t consecutive testing rounds, alongside additional standard tests of low computational cost, is indeed prime with a probability greater than 1-(4/15)^t for all t\geq 1. Furthermore, we introduce error bounds for the incremental search algorithm based on the strong Lucas test, as there are no established bounds up to date either. Rather than independent selection, in this approach, the candidate is chosen uniformly at random, with subsequent candidates determined by incrementally adding 2. This modification reduces the need for random bits and enhances the efficiency of trial division computation further.

4. Maciej Grześkowiak,

   „On chains of pairing-friendly elliptic curves”

   Abstract. Recently, many constructions of curves aim to implement different kinds of proof systems efficiently. For the protocol to be efficient, one must generate particular forms of prime numbers. This article presents an algorithm that finds desired prime numbers in polynomial time.

5. Michel Seck and Abderrahmane Nitaj,

   „A New Public Key Cryptosystem Based on the Cubic Pell Curve”

   Abstract. Since its invention in 1978 by Rivest, Shamir and Adleman, the public key cryptosystem RSA has become a widely popular and a widely useful scheme in cryptography. Its security is related to the difficulty of factoring large integers which are the product of two large prime numbers. For various reasons, several variants of RSA have been proposed, and some have different arithmetics such as elliptic and singular cubic curves. In 2018, Murru and Saettone proposed another variant of RSA based on the cubic Pell curve with a modulus of the form N=pq. In this paper, we present a new public key cryptosystem based on the arithmetic of the cubic Pell curve with a modulus of the form N=p^rq^s. Its security is based on the hardness of factoring composite integers, and on Rabin’s trapdoor one way function. In the new scheme, the arithmetic operations are performed on a cubic Pell curve which is known only to the sender and the recipient of a plaintext.

6. Ahmet Ramazan Ağırtaş and Oğuz Yayla,

   „Compartment-based and Hierarchical Threshold Delegated Verifiable Accountable Subgroup Multi-signatures”

   Abstract. In this paper, we study the compartment-based and hierarchical delegation of signing power of the verifiable accountable subgroup multi-signature (vASM). ASM is a multi-signature in which the participants are accountable for the resulting signature, and the number of participants is not fixed. After Micali et al.’s and Boneh et al.’s ASM schemes, the verifiable-ASM (vASM) scheme with a verifiable group setup and more efficient verification phase was proposed recently. The verifiable group setup in vASM verifies the participants at the group setup phase. In this work, we show that the vASM scheme can also be considered as a proxy signature in which an authorized user (original signer, designator) delegates her signing rights to a single (or a group of) unauthorized user(s) (proxy signer). Namely, we propose four new constructions with the properties and functionalities of an ideal proxy signature and a compartment-based / hierarchical structure. In the first construction, we apply the vASM scheme recursively; in the second one, we use Shamir’s secret sharing (SSS) scheme; in the third construction, we use SSS again but in a nested fashion. In the last one, we use the hierarchical threshold secret sharing (HTSS) scheme for delegation. Then, we show the affiliation of our constructions to proxy signatures and compare our constructions with each other in terms of efficiency and security. Finally we compare the vASM scheme with the existing pairing-based proxy signature schemes.

7. Shiping Cai, Mingjie Chen and Christophe Petit,

   „Faster algorithms for isogeny computations over extensions of finite fields”

   Abstract. Any isogeny between two supersingular elliptic curves can be defined over \mathbb{F}_p^2, however, this does not imply that computing such isogenies can be done with field operations in \mathbb{F}_p^2. In fact, the kernel generators of such isogenies are defined over extension fields of \mathbb{F}_p^2, generically with extension degree k linear to the isogeny degree. Most algorithms related to isogeny computations are only efficient when the extension degree k is small. This leads to efficient algorithms used in isogeny-based cryptographic constructions, but also limits their parameter choices at the same time. In this paper, we consider three computational subroutines regarding isogenies such as computing a basis of \ell-torsion points, computing the kernel generator of an isogeny given the corresponding quaternion ideal under the Deuring correspondence, and computing the kernel polynomial given a kernel generator, with an emphasis on the cases when k is large. We facilitate these subroutines for certain parameter choices. Finally, we discuss the implications of our new algorithms on isogeny-based cryptography.

8. Marios Adamoudis, Konstantinos Draziotis and Eirini Poimenidou,

   „Message Recovery in NTRU Encryption based on CVP”

   Abstract. In the present paper, we implement a message recovery attack on the NTRU-HPS cryptosystem using its state-of-the-art parameters. We make the assumption that the first and second most significant bits (MSB) of the polynomial u(x), which is a multiple of the public key h(x), are known and using Babai’s nearest plane algorithm we successfully recover the message. Additionally, we discuss a possibility of a side-channel attack method designed to extract the necessary bit information from the cryptographic operations.

9. Robert Dryło,

   „Integral solutions of some systems of polynomial equations and constructing families of pairing-friendly elliptic curves with small \rho-value”

   Abstract. The Brezing-Weng algorithm allows to construct complete families a pairing-friendly elliptic curves. This algorithm can be extended to construct also complete with variable discriminant and sparse families of such curves. This algorithm returns an output, which is a triple of polynomials (r(x),t(x),q(x))\in Q[x]^3 (also called a family) such that if the values on integers of these polynomial satisfy suitable conditions, then this triple is used to obtain parameters of pairing-friendly curves as values (r(x_0),t(x_0),q(x_0)) for some x_0\in\N, and \rho-values of these curves tend to the \rho-value the family \rho = \deg q(x)/\deg r(x) for large x_0. To apply the Brezing-Weng algorithm a suitable number field K is chosen, and one obtains families (r(x),t(x),q(x)) such that K \cong Q[x]/(r(x)). For K and an upper bound \rho_0 on \rho-values we give a correspondence between integral solutions of some systems of polynomial equations and families (r(x),t(x), q(x)) returned by the Brezing-Weng algorithmfor which \rho\leq \rho_0 and K\cong Q[x]/(r(x)). We also give such correspondence for the extended Brezing-Weng and arbitrary families. We give examples which show that these correspondendces can be used to obtain families of pairing-friendly elliptic curves.