Skip to main content
main-content

Über dieses Buch

This book presents interesting, important unsolved problems in the mathematical and computational sciences. The contributing authors are leading researchers in their fields and they explain outstanding challenges in their domains, first by offering basic definitions, explaining the context, and summarizing related algorithms, theorems, and proofs, and then by suggesting creative solutions.

The authors feel a strong motivation to excite deep research and discussion in the mathematical and computational sciences community, and the book will be of value to postgraduate students and researchers in the areas of theoretical computer science, discrete mathematics, engineering, and cryptology.

Inhaltsverzeichnis

Frontmatter

About Open Problems

A small group of computer scientists and mathematicians from industry and academia convened in a historical home (“Said Halim Pasha Palace”) overlooking the Bosphorus Straits to discuss several difficult problems they and others in similar fields are tackling. The motivation of the

Open Problems in Mathematical and Computational Sciences Conference

was to enable and encourage the academic community, particularly young researchers and Ph.D. candidates, to hear about unsolved, open problems in mathematical and computation sciences, directly from the scientists who are rigorously investigating them.

Çetin Kaya Koç

The Past, Evolving Present, and Future of the Discrete Logarithm

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.

Antoine Joux, Andrew Odlyzko, Cécile Pierrot

Isogenies in Theory and Praxis

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.

Gerhard Frey

Another Look at Security Theorems for 1-Key Nested MACs

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.

Neal Koblitz, Alfred Menezes

Non-extendable ?? q $$\mathbb{F}_{q}$$ -Quadratic Perfect Nonlinear Maps

Let

q

be a power of an odd prime. We give examples of non-extendable

??

q

$$\mathbb{F}_{q}$$

-quadratic perfect nonlinear maps. We also show that many classes of

??

q

$$\mathbb{F}_{q}$$

-quadratic perfect nonlinear maps are extendable. We give a short survey of some related results and provide some open problems.

Ferruh Özbudak, Alexander Pott

Open Problems for Polynomials over Finite Fields and Applications

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.

Daniel Panario

Generating Good Span n Sequences Using Orthogonal Functions in Nonlinear Feedback Shift Registers

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

n

− 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

n

− 2 − 3

n

(near optimal) and 2

n

− 2 (optimal). Two conjectures on the linear span of new sequences are presented and are valid for

n

 ≤ 20.

Kalikinkar Mandal, Guang Gong

Open Problems on the Cross-correlation of m-Sequences

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.

Tor Helleseth

Open Problems on With-Carry Sequence Generators

Pseudorandom sequences are used in a wide range of applications in computing and communications, including cryptography. It is common to use linear feedback shift registers (LFSRs) to generate such sequences, either directly or as components in more complex structures. Much of the analysis of such sequences is done using the algebra of polynomials and power series over finite fields. The subjects of this chapter are feedback with carry shift registers (FCSRs) and algebraic feedback shift registers (AFSRs, generalizations of both LFSRs and FCSRs), sequence generators that are analogous to LFSRs, but whose state update involves arithmetic with a carry. Their analysis is based on algebraic structures with carry, such as the integers and the

N

-adic numbers. After a brief review of the basics on LFSRs, FCSRs, and AFSRs, we describe several open problems. These include: given part of a sequence, how to find an optimal generator of the sequence; how to construct sequences that cannot be generated by short LFSRs, FCSRs, or AFSRs; and the analysis of various statistical properties related to these generators.

Andrew Klapper

Open Problems on Binary Bent Functions

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.

Claude Carlet

On Semi-bent Functions and Related Plateaued Functions Over the Galois Field ?? 2 n $$\mathbb{F}_{2^{n}}$$

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

??

2

n

$$\mathbb{F}_{2^{n}}$$

(

n

even). We review what is known in this framework and investigate constructions.

Sihem Mesnager

True Random Number Generators

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.

Mario Stipčević, Çetin Kaya Koç

How to Sign Paper Contracts? Conjectures and Evidence Related to Equitable and Efficient Collaborative Task Scheduling

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 4

N

− 6 messages and provide computational evidence in favor of this conjecture. We also explore the most equitable commutative task protocols.

Eric Brier, David Naccache, Li-yao Xia

Theoretical Parallel Computing Models for GPU Computing

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

(

n

w

+

n

l

p

+

l

log

n

)

$$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

Ω

(

n

w

+

n

l

p

+

l

log

n

)

$$\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

(

n

log

n

w

+

n

l

log

n

p

+

l

log

n

)

$$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

(

n

w

+

n

l

p

+

l

log

n

)

$$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.

Koji Nakano

Membrane Computing: Basics and Frontiers

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.

Gheorghe Păun

A Panorama of Post-quantum Cryptography

In 1994, Peter Shor published a quantum algorithm capable of factoring large integers and computing discrete logarithms in Abelian groups in polynomial time. Since these computational problems provide the security basis of conventional asymmetric cryptosystems (e.g., RSA, ECC), information encrypted under such schemes today may well become insecure in a future scenario where quantum computers are a technological reality. Fortunately, certain classical cryptosystems based on entirely different intractability assumptions appear to resist Shor’s attack, as well as others similarly based on quantum computing. The security of these schemes, which are dubbed

post-quantum cryptosystems

, stems from hard problems on lattices, error-correcting codes, multivariate quadratic systems, and hash functions. Here we introduce the essential notions related to each of these schemes and explore the state of the art on practical aspects of their adoption and deployment, like key sizes and cryptogram/signature bandwidth overhead.

Paulo S. L. M. Barreto, Felipe Piazza Biasi, Ricardo Dahab, Julio César López-Hernández, Eduardo M. de Morais, Ana D. Salina de Oliveira, Geovandro C. C. F. Pereira, Jefferson E. Ricardini
Weitere Informationen

Premium Partner

Neuer Inhalt

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Product Lifecycle Management im Konzernumfeld – Herausforderungen, Lösungsansätze und Handlungsempfehlungen

Für produzierende Unternehmen hat sich Product Lifecycle Management in den letzten Jahrzehnten in wachsendem Maße zu einem strategisch wichtigen Ansatz entwickelt. Forciert durch steigende Effektivitäts- und Effizienzanforderungen stellen viele Unternehmen ihre Product Lifecycle Management-Prozesse und -Informationssysteme auf den Prüfstand. Der vorliegende Beitrag beschreibt entlang eines etablierten Analyseframeworks Herausforderungen und Lösungsansätze im Product Lifecycle Management im Konzernumfeld.
Jetzt gratis downloaden!

Bildnachweise