Joint MPIM and B-IT workshop on Number Theory and Cryptography
Organizers:
- Joachim von zur Gathen, B-IT
- Pieter Moree, MPIM
- Igor Shparlinski, UNSW
The purpose of this two-day workshop is to bring together (analytic) number theorists and cryptographers. A good part of public-key cryptography makes use of number-theoretic concepts and algorithms. This, in turn, has led to new challenges in number theory. Some of these connections are among the topics to be discussed in the workshop.
Wednesday, 20 November 2013, MPIM
Location: Hörsaal MPI
9.30 coffee
10.00-11.00 Florian Luca, On the counting function of the range of the Carmichael lambda-function
Abstract: The Carmichael function associates to n the exponent lambda(n) of the multiplicative group modulo n. In my talk, I will describe the main ideas behind the proof that the counting function #{lambda(n)<=x} of the range of the Carmichael function lambda(n) below x is x(log x)^{-eta+o(1)} as x tends to infinity, where eta= 1-(1 + log log 2)/log 2 = 0.08607... is the Erdős-Tenenbaum-Ford constant. The proof uses sieve methods. This is joint work with Kevin Ford and Carl Pomerance.
11.15-12.15 Par Kurlberg, On the period of some pseudo-random number generators and "number-theoretical turbulence"
Abstract: Given coprime integers b and n, let ord(b,n) be the multiplicative order of b modulo n. The length of the periods of some popular pseudorandom number generators (e.g., the linear congruential generator, and the Blum-Blum-Shub generator) turns out to be related to ord(b,n) for appropriately chosen b and n. We will investigate some conclusions by V.I. Arnold (based on numerics by F. Aicardy as well as analogies with the physical principle of turbulence) on the average of ord(b,n), as n ranges over integers. We will also give lower bounds on ord(b,n) for b fixed and n ranging over certain subsets of the integers, e.g., the set of primes, the set of "RSA moduli" (i.e., products of two primes), the full set of integers, and the images of these sets under the Carmichael lambda function. (The lower bounds in the case of RSA moduli shows that certain "cycling attacks" on the RSA crypto system are ineffective.) Time permitting we will discuss similar questions regarding exponents of elliptic curves mod p, and p varying.
14.45-15.45 Cameron Stewart, A refinement of the abc conjecture
Abstract: We shall discuss joint work with Robert and Tenenbaum on a proposed refinement of the well known abc conjecture.
16.00 tea
16.30-17.30 Peter Stevenhagen, Complex multiplication in cryptography
Abstract: Algorithms going under the name `complex multiplication' typically have a run time that is exponential in the size of the input data. We will show that nevertheless such algorithms may sometimes be profitably used in cryptographic settings.
Thursday, 21 November 2013, B-IT
Location: B-IT Bitmax
13.00-13.55 Ronald Rietman, HIMMO: A collusion-resistant identity-based scheme for symmetric key generation
Abstract: We describe HIMMO, a new scheme for identity-based symmetric key generation. Like the scheme of Blundo et al, HIMMO employs symmetric polynomials, which lead to very efficient implementations, but it is much less vulnerable against collusion attacks. HIMMO employs mixing modular operations over different rings and hiding part of the result of polynomial evaluation by only considering its least significant bits, which relates HIMMO to Noisy Polynomial Interpolation. We discuss the collusion resistance properties of HIMMO based on lattice-based cryptanalysis.
14.00-14.55 Konstantin Ziegler, Fast and uniform generation of safe RSA moduli
Abstract: Several cryptographic schemes require safe RSA moduli. These are composite numbers of the form pq, where p and q are distinct safe primes. Usually, a prime p is called safe if it is of the form p = 2 ℓ + 1, where ℓ is prime as well. Then ℓ is called a Sophie-Germain prime. It is conjectured that many such primes exist, but not even known whether there are infinitely many of them so that they could be generated algorithmically. Von zur Gathen & Shparlinski (2013) suggest a more general notion of "safe prime." The resulting moduli can be generated in polynomial time and are suitable for all popular cryptographic applications, where safe RSA moduli are required.
We outline this method and study variations of the resulting prime-generating algorithms with respect to the generated distributions and the required costs. This is joint work with Joachim von zur Gathen and Johannes Zollmann.
15.00 tea
Location: B-IT Rheinsaal
15.30-16.30 Francesco Pappalardi, Groups of points of elliptic curves over finite fields and related questions
Abstract: We will report on joint work with W. Banks and I. Shparlinski on groups realizable as groups of points of elliptic curves over finite fields and in particular we will review some improvements due to V. Chandee, C. David, D. Koukoulopoulos and E. Smith with extensions to Abelian varieties.
We will also consider the related problems of estimating the exponent of the group of points of elliptic curves over finite fields.
16.40-17.40 Lillian Pierce, Burgess bounds for short mixed character sums
Abstract: A celebrated result of Burgess proves nontrivial bounds for short multiplicative character sums. This talk presents new work, joint with Roger Heath-Brown, on nontrivial bounds for short mixed character sums in which the additive character is evaluated at a real-valued polynomial. Our approach, via the Burgess method, includes a novel application of the recent results of Wooley and Ford on the Vinogradov mean value theorem.
Registration
If you want to attend this meeting please write a message with your Full Name, Affiliation, Day(s) of participation (20 and 21) and whether you would like to attend the conference dinner on Nov. 20 (typical German food, cost: around 30 euro) to: