|
|
Special day on Mathematics of Cryptology
January 21 2005
|  |
On January 21 we organize a joint meeting with the
RISC
seminar.
The lectures will take place at Room 201 (Huygens Building) of the
Lorentz Center in Leiden.
Program
|
|
10:30−11:00
|
Coffee
|
|
11:00−11:45
|
Carles Padró (Barcelona)
Secret Sharing Schemes, Error Correcting Codes and Matroids
Abstract
Error correcting codes and matroids have been widely used in the study
of secret sharing schemes. This talk deals mainly with the connections
between codes, matroids and a special class of secret sharing schemes,
namely multiplicative linear secret sharing schemes (MLSSS). Such
schemes are known to enable multi-party computation protocols secure
against general (non-threshold) adversaries. Two open problems related
to the complexity of multiplicative linear secret sharing schemes will
be considered.
Hirt and Maurer proved that such a scheme can be costructed whenever
the set of players is not the union of two unqualified subsets.
Cramer, Damgard and Maurer proved that, in this case, a multiplicative
linear secret sharing scheme can be efficiently constructed from any
linear secret sharing scheme by increasing the complexity by a
constant factor of 2. The first open problem we consider is to
determine in which situations a multiplicative scheme can be obtained
without increasing the complexity. We study this problem in an
extremal case. Namely, to determine whether all self-dual vector space
access structures admit an ideal MLSSS. By the aforementioned
connection, this in fact constitutes an open problem about Matroid
Theory, since it can be re-stated in terms of representability of
identically self-dual matroids by self-dual codes. We introduce a new
concept, the flat-partition, that provides a useful classification of
identically self-dual matroids. Uniform identically self-dual
matroids, which are known to be representable by self-dual codes, form
one of the classes. We prove that this property also holds for the
family of matroids that, in a natural way, is the next class in the
above classification: the identically self-dual bipartite matroids.
The second open problem deals with strongly multiplicative linear
secret sharing schemes. As opposed to the case of multiplicative
LSSSs, it is not known whether there is an efficient method to
transform an LSSS into a strongly multiplicative LSSS for the same
access structure with a polynomial increase of the complexity. We
prove a property of strongly multiplicative LSSSs that could be useful
in solving this problem. Namely, using a suitable generalization of
the well-known Berlekamp-Welch decoder, we show that all strongly
multiplicative LSSSs enable efficient reconstruction of a shared
secret in the presence of malicious faults.
|
|
11:45−12:00
|
Coffee break
|
|
12:00−12:45
|
Salil Vadhan (Harvard)
Randomness Extractors and their Cryptographic Applications
Abstract:
Over the past two decades, a rich body of work has developed around
the problem of constructing randomness extractors --- algorithms that
extract high-quality randomness (i.e. nearly uniform and independent
bits) from low-quality randomness (i.e. sources of biased and
correlated bits). Although some of the early results on randomness
extraction came from the cryptography literature, most of the
subsequent theory has been developed in the setting of computational
complexity, where extractors have unified the study of a number of
fundamental objects (such as pseudorandom generators, expander graphs,
and list-decodable error-correcting codes). In the past few years, the
relevance of extractors to cryptography has been re-discovered, with
increasing variety of applications being found. In this talk, I will
survey the basic theory of randomness extractors, give a sense of the
current state-of-the-art, and describe some of their cryptographic
applications.
|
|
12:45−13:45
|
Lunch
|
|
13:45−14:30
|
Rafi Ostrovsky (UCLA)
Survey on Private Information Retrieval
Abstract:
Consider a setting where a user wishes to retrieve an item from a
database, without letting the database administrator know which item
is being retrieved. Of course, a trivial (but expensive) solution is
for the user to request contents of the entire database, thus
concealing from the database administrator which item is of interest
to the user. Can this be done with less communication? Perhaps
somewhat surprisingly, the answer is yes, under various assumptions
and settings. In this talk, I'll survey much progress that has been
achieved on this problem and point our some interesting connections to
other problems in coding theory and several hardness results in
cryptography.
|
|
14:30−15:00
|
Tea break
|
|
15:00−15:45
|
Phong Nguyen (ENS Parijs)
From Euclid to Lenstra-Lenstra-Lovasz: Revisiting Lattice Basis
Reduction
Abstract:
Lattices are simple yet fascinating mathematical objects. Roughly
speaking, they are linear deformations of the n-dimensional grid Z^n.
Lattices have many applications in mathematics and computer science.
Of particular importance is lattice basis reduction, which is the
problem of finding "nice" representations of lattices. For instance,
lattice basis reduction is the most popular tool to attack public-key
cryptosystems. In this talk, we will revisit lattice basis reduction,
from Euclid's gcd algorithm to the celebrated LLL algorithm. We will
also briefly discuss recent results. Curiously, it is possible to
obtain a Euclid-like complexity for lattice basis reduction: in some
sense, one can compute a reduced basis (without fast integer
arithmetic) in essentially the same time as the elementary method to
multiply integers.
|
|
15:45−16:15
|
Tea break
|
|
16:15−17:00
|
Steven Galbraith
(London)
The Eta Pairing
Abstract:
We introduce a new pairing on certain supersingular curves which is
very closely related to the Tate pairing, but which has some
implementation advantages. We interpret the results of Duursma and Lee
in terms of this pairing and we describe a fast pairing on genus 2
curves in characteristic 2.
|
|
17:00−18:00
|
Drinks
|
|
|
February 4
|
Special program in Utrecht on the occasion of Johnny Edwards' PhD defense
The afternoon talks are in room 018 at Kromme Nieuwegracht 66, number 11 on
this map
We can have lunch at "Trans 10", which is number 14 on the
map
|
|
10:30
|
PhD defense of Johnny Edwards in the Academiegebouw, number 1 on
this
map
|
|
13:00−14:00
|
Michael Stoll (Bremen), Proving non-existence of rational
points on curves
Abstract.
Let C be a curve of genus at least two over Q (or, more generally,
over a number field K).
An important problem is to decide whether C has any rational
points. The first step in trying to solve this problem is to check
if C has points everywhere locally (which can be done effectively).
If this is the case, but C
does not appear to have global points, there is the possibility that
the absence of global points can be explained by the Brauer-Manin
obstruction. It turns out that this is equivalent to the existence
of a descent obstruction coming from some abelian covering of C.
We will discuss how we can check for such an obstruction, focussing
on genus 2 curves, and we will give experimental results obtained
by Victor Flynn, Nils Bruin and myself.
|
|
14:15−15:15
|
Andreas Schweizer (KIAS Seoul), Construction of quadratic function
fields whose class groups have m-rank 4.
Abstract.
Fix a finite field Fq of odd characteristic and
an odd integer m that is not divisible by the characteristic
of Fq. We are interested in the m-rank of the
divisor class groups of quadratic extensions L of the rational
function field Fq(T).
First we show: If there is one L with m-rank at least r,
then there are infinitely many L with m-rank at least r.
Then for q = 1 mod 4 we explicitly construct an L with
m-rank at least 4. Similar constructions give slightly weaker
results if q = 3 mod 4 and also for the ideal class group
of the integral closure of Fq[T] in L.
|
|
15:30−16:30
|
Andreas Weiermann (Utrecht/Muenster),
Analytic combinatorics of the transfinite
Abstract:
We consider a natural well-ordered subclass H of Hardy's
1917 orders of infinity.
Let H be the least set of functions from the non negative
integers into the non negative integers such that:
1) the constant zero function belongs to H,
2) with f and g the function idf+g belongs to
H where
id denotes the identity function.
Let < be the ordering of eventual domination on H.
A norm function is a function from H into the non negative
integers such that for any non negative integer n there are
only finitely many elements in H having norm below n.
For a given norm N and a given f in H let
cfN(n)
be the number of elements g in H such that
g<f
and N(g)≤ n.
We are going to classify various of these count functions.
Partition functions appear as special cases of this construction.
We use tools from Tauberian theory and generating function
methodology. Moreover we indicate where the count functions
can be used in logic.
|
|
|
February 18
|
Leiden, room 312 (first talk), 405 (other talks).
|
|
12:00−13:00
|
Robin de Jong (Leiden),
Arakelov geometry and its applications to number
theory
Abstract.
The purpose of this talk is to make popular the idea that Arakelov
geometry can be used to obtain effective results in number theory. We
discuss in this respect the existence of an efficient algorithm to
compute the Ramanujan tau-function at a given prime number, as well as
the effective Shafarevich conjecture trying to make quantitative the
(proven) statement that given a number field K, a positive integer g
and a set S of primes of K, there exist only finitely many
K^alg-isomorphism classes of curves of genus g, defined over K and
having good reduction outside S. The former topic is work in progress
together with Edixhoven and Couveignes, the latter topic is probably
still far out of reach, although recently strong results have been
obtained by Heier in the function field case.
In order to bring Arakelov theory into action, it is essential to
obtain explicit representations of the various objects that occur in
this theory. As an example we discuss an explicit formula for the
Arakelov-Green function of a compact and connected Riemann surface of
positive genus.
|
|
14:00−14:45
|
Eleonora Pellegrini,
Power bases for pure cubic fields
Abstract.
In this talk we will consider the problem of the monogenicity
of a number field, with a particular attention at cubic fields of the
form Q(3√m), where
m is a cubefree positive
integer. After giving a criterion of monogenicity, we will discuss
the
distribution of those m that give rise to monogenic pure cubic
fields.
|
|
15:00−15:45
|
Clemens Fuchs (Leiden),
Polynomial generalisations of a problem of
Diophantus
Abstract.
A Diophantine m-tuple is a set of m positive integers with the
property that theproduct of any two distinct elements plus one is a
square of an integer. In my
talk I will start with a survey on Diophantine m-tuples and possible
generalisations with an emphasis on variants of the problem for
polynomials withinteger coefficients. E.g. I will discuss a recent
joint result with A. Dujella
and G. Walsh: we proved that there does not exist a set of more than
12
polynomials with integer coefficients, not all constant, and with the
property
that the product of any two of them plus a linear polynomial is a
square of a
polynomial with integer coefficients.
|
|
16:00−16:45
|
Capi Corrales Rodrigañez (Madrid),
On the unit group of an order in a non-split quaternion algebra
Abstract.
I will speak on some joint work with E. Jespers, G. Leal and
A. del Río, in which we give an algorithm to determine a finite set
of generators
of the unit group of an order in a non-split classical quaternion
algebra H(K)
over an imaginary quadratic extension K of the rationals.
We then apply this method to obtain a presentation for the unit group
of H(Z[(1+√-7)/2]). As a consequence, we get a
presentation for
the orthogonal group
SO3(Z[(1+√-7)/2]).
These results provide the first examples of a characterization of the
unit group of some group rings that have an epimorphic image that is
an order in a non-commutative division algebra that is not a totally
definite quaternion algebra.
|
|
|
March 4
|
Universtiteit Gent,
building S22 at Galglaan 2, lokaal 14.
On the
map
of Gent
this is between numbers 14 and 18, and on the
Campus
map it is building 40-22
[further info].
| |
13:30-14:30
|
Joost van Hamel (Leuven),
Abelianised Galois cohomology of reductive groups
| |
14:45-15:45
|
Lenny Taelman (Groningen),
On analytic unformization of abelian varieties and Anderson
modules
| |
16:15-17:15
|
Jan Schepers (Leuven),
Introduction to motivic integration
|
|
|
March 18
|
Groningen, room A901 at Broerstraat 9,
next to the Academiegebouw
(see the map)
|
|
11:15−12:00
|
Matthias Schuett (Hannover),
Extremal elliptic K3 fibrations
Abstract.
In this talk we will consider elliptic K3 surfaces. After a brief
introduction we will especially emphasize the extremal fibrations.
With view
to their classification and Frits Beukers' talk, we would like to
discuss how
many of them arise as pull-back from rational elliptic surfaces by a
base
change of low degree.
|
|
12:15−13:00
|
Ronald van Luijk
(Berkeley),
K3 surfaces with Picard number one and infinitely many rational
points
Abstract.
Not much is known about the arithmetic of K3 surfaces in
general. Once the Picard number, which is the rank of the Neron-Severi
group, is high enough, more structure is known and more can be said.
But still we don't know of a single K3 surface whose set of rational
points has been proved to be neither empty, nor Zariski dense.
Also, until recently, not even a single K3 surface was known with
Neron-Severi rank 1 and infinitely many rational points. We will give
an explicit example of such a surface over Q, where even the Picard
number over the algebraic closure is equal to 1. This solves an old
problem, that has been attributed to Mumford. The method used has been
extended by Remke Kloosterman to find elliptic K3 surfaces of rank 15.
|
|
13:45−14:30
|
Frits Beukers (Utrecht),
Computation of extremal elliptic K3 fibrations
Abstract.
In a joint effort with H. Montanus we computed all extremal
semistable elliptic K3 fibrations over P1. Although the subject
matter
is geometrical, this talk will be computational. We focus
our attention on the determination of 188 plane 'dessins d'enfant'
and their associated Belyi maps.
|
|
14:45−15:30
|
Jozef Steenbrink (Nijmegen),
The billiard problem on an ellipse
Abstract.
I will show how one may visualize the solution to the billiard
problem on an ellipse and how this gives rise to a nice deformation of
a double hyperbola. It is a demonstration of the use of the
CABRI-geometry program on academic level (I hope).
|
|
16:15
|
PhD defense of
Remke Kloosterman in the Academiegebouw
|
|
|
April 1
|
Utrecht, room K11
| |
11:00−12:00
|
Roelof Bruggeman (Utrecht),
Period functions and Maass cusp forms
Abstract.
For holomorphic modular cusp forms there is a well established
relation with period polynomials. In the case of modular Maass cusp
forms, Lewis and Zagier have studied the associated period functions.
I'll speak about ongoing work of Lewis, Zagier and me on these period
functions and their cohomological interpretation.
| |
12:15−13:15
|
Yiannis Petridis (Bonn),
Modular symbols and spectral theory
Abstract.
A conjecture of Goldfeld about periods of elliptic curves implies a
weak version of ABC. On the other hand this conjecture is equivalent
with the modular symbol conjecture about their relative growth. The
modular symbols encode geometric information about the cohomology and
the fundamental group of the modular curves. Through trace
type-identities we can relate modular symbols and the spectral theory
of the Laplace operator on the modular curve. The objects to study
are: families of automorphic forms, Eisenstein series twisted by
modular symbols and Selberg-zeta functions. The technique is
perturbation theory of operators. The result is the distribution of
the (normalized) modular symbols: a Gaussian law.
| |
14:15−15:15
| Byoung Ki Seo (Utrecht),
Asymptotic behaviors of the first return time of
translations on a torus
Abstract.
We investigate asymptotic behaviors of the first return time of
translations on a torus using Diophantine approximations. It is known
that the first return time to an element of the equipartition equals
to the 1 over the size of the element asymptotically for almost but
not all irrational translation on a 1 dimensional unit interval. We
expand the results to the case for an irrational translation on a
multidimensional torus.
| |
15:30−16:30
|
Gunther Cornelissen (Utrecht),
Complexity of the rational numbers and conjectures about elliptic
curves
Abstract.
We don't know whether or not there is an algorithm to decide whether
a diophantine equation has a rational solution or not ("Hilbert's
tenth problem for Q", HTP(Q)), but Julia Robinson has proven in 1949
that
one cannot decide the truth of more general statements about the
rationals.
I will discuss conjectures about elliptic curves that allow us to
improve
upon Robinson's result and - in a sense that I will make precise -
closer
to a solution of HTP(Q). The keyword is "Zsigmondy type theorems for
elliptic divisibility sequences with extra conditions". I will present
some heuristics to support the conjectures.
|
|
|
April 15
|
Special day on Lambda rings
Nijmegen, room CZ N7 (=N1004 on the first floor of building N1)
On the
map look for the red dot with green arrow "oudbouw". Enter there
and go up two floors. For parking you might get lucky at the bottom of
the map near "INGANG VANAF BRAKKESTEIN" on the Driehuizerweg, which
is easier to spot on this
map
Speakers: Jim Borger (Max Planck), Frans Clauwens (Nijmegen), Bart de
Smit (Leiden).
| |
12:00−13:00
|
Jim Borger (Max Planck),
Lambda rings for beginners part I
| |
14:00−15:00
|
Jim Borger (Max Planck),
Lambda rings for beginners part II
| |
15:15−16:15
|
Frans Clauwens (Nijmegen),
Natural operations on lambda rings
| |
16:30−17:30
| Bart de Smit (Leiden),
Integral lambda ring structure on finite étale Q-agebras
Abstract.
For a lambda ring K which is
finite étale as a Q-algebra we determine whether
K has a lambda subring R
of finite rank over Z so that
K=R⊗Q.
We also determine the maximal such R if it exists.
This is joint work with Jim Borger.
|
|
|
May 13
|
Leiden, room 412
| |
13:30−14:15
|
Joost Batenburg (Leiden/CWI),
Small, smaller, smallest. Steps toward the atomic resolution
microscope.
Abstract.
Building an electron microscope that can view samples at atomic
resolution is a longstanding goal in the microscopy community. It has
recently become possible to acquire images of projected crystalline
structures in which separate atom columns can be resolved. By
themselves, these images do not provide sufficient information to
determine the positions and types of individual atoms inside the
crystal. However, when projections from several viewpoints are
combined, it is possible to make a full 3D reconstruction of the
crystal by performing a tomographic inversion procedure.
Because the number of measured projections is typically very small,
methods from continuous tomography, which are used in medical imaging,
cannot be used for this application. The young field of discrete
tomography is suited particularly well for computing reconstructions
from few projections. Discrete tomography is an interdisciplinary
field, with links to number theory, combinatorics, operations research
and coding theory.
In this talk I will describe how discrete tomography can be used to
compute atomic resolution 3D reconstructions of crystals and discuss a
variety of problems that still need to be solved.
| |
14:30−15:15
|
Oliver Lorscheid (Utrecht),
Completeness and compactness for varieties over local fields
[math.AG/0410346]
Abstract. For a complex variety it is well known that it is
complete if and only if the rational points form a compact space in
the complex topology. The only essential property of the complex
numbers for this statement to hold is their locally compactness.
One finds the following generalisation: let K be a local field
and X a variety over K, then X is complete if and
only if for every finite field extension L of K,
X(L) is compact in its strong topology.
| |
15:30−17:00
|
Pre-Journées program
Three PhD students from Leiden present their
proposed talks for the
Journées Arithmétiques
Willem Jan Palenstijn,
Computing near-primitive root densities
Abstract.
Artin's primitive root conjecture gives, for an integer x, an
expression for the density of primes q for which x is a
primitive root modulo q. In this talk, we consider the
following generalization: given a number field K, a non-zero
element x of K, and a positive
integer d, what is the density of primes q of K
for which the subgroup of the multiplicative group of the residue
class field of q generated by x has index dividing
d?
Bas Jansen,
Mersenne primes and Lehmer's observation
Abstract.
The Lucas-Lehmer test is an algorithm to check whether a number of the
form M=2p-1, with
p an odd positive integer, is prime.
The algorithm produces a sequence of
p-1 numbers modulo M,
starting with the number 4 and each time squaring
the previous number and subtracting 2.
Then the last number is zero modulo M if and only if
M is prime. Lehmer observed that if the last number is zero
then the penultimate number can be either PLUS or MINUS 2(p+1)/2 modulo M.
Gebre-Egziabher showed that if you start your sequence with 2/3
instead of 4, then the test also works, and the sign will be plus if
and only if p is 1 modulo 4 (p>5). In this talk we
generalize this result.
Reinier Bröker,
Class invariants in a non-archimedean setting
Abstract.
One of the goals of explicit class field theory is to compute a
generating polynomial for the Hilbert class field of a given number
field. For imaginary quadratic fields, the theory of complex
multiplication provides us with an elegant solution. The classical
approach has two improvements. Firstly, one can use `smaller'
functions than the classical j-function, leading to smaller
polynomials. This leads to the theory of class invariants, which was
initiated by Weber. Secondly, one can work in a non-archimedean
setting, avoiding the problem of rounding errors in the classical
approach. In this talk we will combine both improvements, i.e., we
will show how to use class invariants in a non-archimedean setting.
|
|
|
|
