Open Problems in Mathematics and Computational Science

The first practical public key cryptosystem ever published, the Diffie–Hellman key exchange algorithm, relies for its security on the assumption that discrete logarithms are hard to compute. This intractability hypothesis is also the foundation for the security of a large variety of other public key systems and protocols.

Since the introduction of the Diffie–Hellman key exchange more than three decades ago, there have been substantial algorithmic advances in the computation of discrete logarithms. However, in general the discrete logarithm problem is still considered to be hard. In particular, this is the case for the multiplicative groups of finite fields with medium to large characteristic and for the additive group of a general elliptic curve.

This chapter presents a survey of the state of the art concerning discrete logarithms and their computation.

We want to give an overview on arithmetical aspects of abelian varieties and their torsion structures, isogenies, and resulting Galois representations. This is a wide and deep territory with a huge amount of research activity and exciting results ranging from the highlights of pure mathematics like the proof of Fermat’s last theorem to stunning applications to public-key cryptography. Necessarily we have to be rather superficial, and thus specialists in the different aspects of the topics may be disappointed. But I hope that for many, and in particular for young researchers, the chapter may serve as an appetizer and will raise interest for a fascinating area of mathematics with many open problems (some are very hard and worth a Fields Medal but others are rather accessible).

The first section of the chapter gives basic notions, definitions, and properties of abelian varieties. Disguised as examples one will find their theory over the complex numbers \(\mathbb{C}\) and the special case of elliptic curves. The second section discusses the situation over finite fields, in particular the role of the Frobenius endomorphism, and over number fields where the most interesting results and challenging conjectures occur. Finally we discuss algorithmic aspects of isogenies, mostly of elliptic curves, and relations to cryptography.

We prove a security theorem without collision resistance for a class of 1-key hash function-based MAC schemes that includes HMAC and Envelope MAC. The proof has some advantages over earlier proofs: it is in the uniform model, it uses a weaker related-key assumption, and it covers a broad class of MACs in a single theorem. However, we also explain why our theorem is of doubtful value in assessing the real-world security of these MAC schemes. In addition, we prove a theorem assuming collision resistance. From these two theorems, we conclude that from a provable security standpoint, there is little reason to prefer HMAC to Envelope MAC or similar schemes.

Let q be a power of an odd prime. We give examples of non-extendable \(\mathbb{F}_{q}\)-quadratic perfect nonlinear maps. We also show that many classes of \(\mathbb{F}_{q}\)-quadratic perfect nonlinear maps are extendable. We give a short survey of some related results and provide some open problems.

We survey open problems for univariate polynomials over finite fields. We first comment in some detail on the existence and number of several classes of polynomials. The open problems in that part of the survey are of a more theoretical nature. Then, we center on classes of low-weight (irreducible) polynomials. The conjectures here are more practically oriented. Finally, we give brief descriptions of a selection of open problems from several areas including factorization of polynomials, special polynomials (APN functions, permutations), and relations between rational integers and polynomials.

A binary span n sequence generated by an n-stage nonlinear feedback shift register (NLFSR) is in a one-to-one correspondence with a de Bruijn sequence and has the following randomness properties: period 2 ⁿ − 1, balance, and ideal n-tuple distribution. A span n sequence may have a high linear span. However, how to find a nonlinear feedback function that generates such a sequence constitutes a long-standing challenging problem for about 5 decades since Golomb’s pioneering book, Shift Register Sequences, published in the middle of the 1960s. In hopes of finding good span n sequences with large linear span, in this chapter we study the generation of span n sequences using orthogonal functions in polynomial representation as nonlinear feedback in a nonlinear feedback shift register. Our empirical study shows that the success probability of obtaining a span n sequence in this technique is better than that of obtaining a span n sequence in a random span n sequence generation method. Moreover, we analyze the linear span of new span n sequences, and the linear span of a new sequence lies between 2 ⁿ − 2 − 3n (near optimal) and 2 ⁿ − 2 (optimal). Two conjectures on the linear span of new sequences are presented and are valid for n ≤ 20.

Pseudorandom sequences are important for many applications in communication systems, in coding theory, and in the design of stream ciphers. Maximum-length linear sequences (or m-sequences) are popular in sequence designs due to their long period and excellent pseudorandom properties. In code-division multiple-access (CDMA) applications, there is a demand for large families of sequences having good correlation properties. The best families of sequences in these applications frequently use m-sequences in their constructions. Therefore, the problem of determining the correlation properties of m-sequences has received a lot of attention since the 1960s, and many interesting theoretical results of practical interest have been obtained. The cross-correlation of m-sequences is also related to other important problems, such as almost perfect nonlinear functions (APN) and almost bent functions (AB), and to the nonlinearity of S-boxes in many block ciphers including AES. This chapter gives an updated survey of the cross-correlation of m-sequences and describes some of the most important open problems that still remain in this area.

This chapter gives a survey of the recent results on Boolean bent functions and lists some open problems in this domain. It includes also new results. We recall the definitions and basic results, including known and new characterizations of bent functions; we describe the constructions (primary and secondary; known and new) and give the known infinite classes, in multivariate representation and in trace representation (univariate and bivariate). We also focus on the particular class of rotation symmetric (RS) bent functions and on the related notion of bent idempotent: we give the known infinite classes and secondary constructions of such functions, and we describe the properties of a recently introduced transformation of RS functions into idempotents.

Plateaued functions were introduced in 1999 by Zheng and Zhang as good candidates for designing cryptographic functions since they possess desirable various cryptographic characteristics. They are defined in terms of the Walsh–Hadamard spectrum. Plateaued functions bring together various nonlinear characteristics and include two important classes of Boolean functions defined in even dimension: the well-known bent functions and the semi-bent functions. Bent functions (including their constructions) have been extensively investigated for more than 35 years. Very recently, the study of semi-bent functions has attracted the attention of several researchers. Much progress in the design of such functions has been made. The chapter is devoted to certain plateaued functions. The focus is particularly on semi-bent functions defined over the Galois field \(\mathbb{F}_{2^{n}}\) (n even). We review what is known in this framework and investigate constructions.

Random numbers are needed in many areas: cryptography, Monte Carlo computation and simulation, industrial testing and labeling, hazard games, gambling, etc. Our assumption has been that random numbers cannot be computed; because digital computers operate deterministically, they cannot produce random numbers. Instead, random numbers are best obtained using physical (true) random number generators (TRNG), which operate by measuring a well-controlled and specially prepared physical process. Randomness of a TRNG can be precisely, scientifically characterized and measured. Especially valuable are the information-theoretic provable random number generators (RNGs), which, at the state of the art, seem to be possible only by exploiting randomness inherent to certain quantum systems. On the other hand, current industry standards dictate the use of RNGs based on free-running oscillators (FRO) whose randomness is derived from electronic noise present in logic circuits and which cannot be strictly proven as uniformly random, but offer easier technological realization. The FRO approach is currently used in 3rd- and 4th-generation FPGA and ASIC hardware, unsuitable for realization of quantum RNGs. In this chapter we compare weak and strong aspects of the two approaches. Finally, we discuss several examples where use of a true RNG is critical and show how it can significantly improve security of cryptographic systems, and discuss industrial and research challenges that prevent widespread use of TRNGs.

This chapter explores ways of performing a kind of commutative task by N parties, of which a particular scenario of contract signing is a canonical example. Tasks are defined as commutative if the order in which parties perform them can be freely changed without affecting the final result. It is easy to see that arbitrary N-party commutative tasks cannot be completed in less than N − 1 basic time units.

We conjecture that arbitrary N-party commutative tasks cannot be performed in N − 1 time units by exchanging less than 4N − 6 messages and provide computational evidence in favor of this conjecture. We also explore the most equitable commutative task protocols.

The latest GPUs are designed for general purpose computing and attract the attention of many application developers. The main purpose of this chapter is to introduce theoretical parallel computing models, the Discrete Memory Machine (DMM) and the Unified Memory Machine (UMM), that capture the essence of CUDA-enabled GPUs. These models have three parameters: the number p of threads and the width w of the memory and the memory access latency l. As examples of parallel algorithms on these theoretical models, we show fundamental algorithms for computing the sum and the prefix-sums of n numbers. We first show that the sum of n numbers can be computed in \(O( \frac{n} {w} + \frac{\mathit{nl}} {p} + l\log n)\) time units on the DMM and the UMM. We then go on to show that \(\varOmega ( \frac{n} {w} + \frac{\mathit{nl}} {p} + l\log n)\) time units are necessary to compute the sum. We also present a simple parallel algorithm for computing the prefix-sums that runs in \(O(\frac{n\log n} {w} + \frac{nl\log n} {p} + l\log n)\) time units on the DMM and the UMM. Clearly, this algorithm is not optimal. We present an optimal parallel algorithm that computes the prefix-sums of n numbers in \(O( \frac{n} {w} + \frac{\mathit{nl}} {p} + l\log n)\) time units on the DMM and the UMM. We also show several experimental results on GeForce Titan GPU.

Membrane computing is a branch of natural computing inspired by the structure and the functioning of the living cell, as well as by the cooperation of cells in tissues, colonies of cells, and neural nets. This chapter briefly introduces the basic notions and (types of) results of this research area, also discussing open problems and research topics. Several central classes of computing models (called P systems) are considered: cell-like P systems with symbol objects processed by means of multiset rewriting rules, symport/antiport P systems, P systems with active membranes, spiking neural P systems, and numerical P systems.