Purpose of the workshop
An overall purpose is to help
further strengthening and extending the ties between the cryptology community
and that part of the mathematics community with an interest in cryptology,
especially from algebra, number theory and geometry. An international workshop
is an appropriate vehicle for this.
Several leading researchers
from these communities are invited to deliver key-note presentations on the
most recent developments in mathematics of cryptology, an area that we
would like to define very loosely as consisting of cryptologic problems that
can be shown to reduce to clean and crisp mathematical questions that can be
understood and studied independently from the original cryptologic context.
This will cast a fresh look
on what has been traditionally perceived as common grounds, and will help to
map out new territory that is in fact considerably bigger.
Concretely, this is a
tentative list of topics to be discussed at the workshop, along with some key
references.
·
It has
recently been shown [1, 2] that Weil- and Tate-pairings on certain classes of
elliptic curves can be exploited to construct cryptographic systems with
desirable added functionalities.
The
computational hardness of the mathematical problems upon which the security of these
systems is based, requires critical study by the algorithmic algebraic geometry
community.
·
Faster
or more general algorithms for counting the number of points on certain
algebraic varieties defined over finite fields.
In
the last few years there has been much progress concerning algorithms for
counting points on elliptic curves and more general algebraic varieties over
finite fields of small characteristic [3, 4, 5, 6, 7]. All methods here are
based on p-adic geometry or cohomology. This has positive practical
applications to cryptography based on elliptic curves or more general algebraic
curves.
·
Lattice-based
cryptology: application of integer lattice basis reduction algorithms to
cryptanalysis [8], as well as the construction of crypto systems based on
computationally hard problems in lattices [9, 10].
·
Recent
advances in cryptanalysis, in particular integer factorization with the number
field sieve [11].
·
Hard
sub-group membership problems; it has been shown recently [12] that a
combination of a large group containing a sub-group that is computationally
indistinguishable from the entire group, together with a sufficiently
well-behaved group of homomorphisms, gives rise to potentially very efficient
public key encryption schemes that withstand the strongest type of attack,
i.e., adaptive chosen ciphertext attack.
There
are several concrete realizations known, where security is based on variations
of the integer factorization problem and the discrete logarithm problem.
In
view of possible future cryptanalytic advances in algebraic number theory or
advances in the physics of computation, it is interesting and important to
identify alternative candidates.
·
Information
theoretic secret-key exchange in the bounded storage model and combinatorial
constructions of strong entropy extractors [13].
·
Quantum
error-correcting codes and applications to secure quantum key-exchange [14].
·
Information
theoretically secure multi-party computation and its linear algebraic and
number theoretical aspects [15, 16].
Invited Speakers
Here is a
list of invited speakers. Those who have already made a commitment to
participate are identified with a *.
·
Andries
Brouwer (TU Eindhoven, NL)
·
Joe
Buhler (Portland, USA)
·
Ronald
Cramer (BRICS, Aarhus, DK)
·
Ivan
Damgaard (Aarhus University, DK)*
·
Hans
Dobbertin (Bochum University, DE)
·
Bas
Edixhoven (Leiden, NL)
·
Gerhard
Frey (University of Essen, DE)*
·
Alan
Lauder (Oxford, UK)*
·
Hendrik
Lenstra (Leiden, NL)
·
Ueli
Maurer (ETH Zurich, CH)*
·
Phong
Nguyen (École Normale Supérieure, FR)*
·
Berry
Schoenmakers (Technical University Eindhoven, NL)*
·
René
Schoof (University of Amsterdam, NL)
·
Igor
Shparlinski (Macquarie University, AUS)*
·
Jacques
Stern (École Normale Supérieure, FR)*
·
Peter
Stevenhagen (Leiden, NL)
·
Henk van
Tilborg (TU Eindhoven, NL)*
·
Frederik
Vercauteren (Bristol, UK)*
References:
[1] Antoine Joux: A
one round protocol for tripartite Diffie-Hellman. Proc. Fourth
Algorithmic Number Theory Symposium, Lecture Notes in Computer Science, Vol.
1838, Springer-Verlag, pp. 385-394, 2000.
[2] Dan Boneh,
Matt Franklin: Identity based encryption from the Weil pairing. To
appear in SIAM J. of Computing. Extended abstract in Proc. IACR CRYPTO
'01, Lecture Notes in Computer Science, vol. 2139, Springer-Verlag, pp. 213-229,
2001.
[3] J. Denef
and F. Vercauteren. Computing zeta functions of hyper-elliptic curves
over finite fields of characteristic 2. Preprint, 2002.
[4] K. Kedlaya.
Counting points on hyper-elliptic curves using Monsky-Washnitzer cohomology.
J. Ramanujan Math. Soc. 16 (2001), no. 4, 323-338.
[5] A.G.B. Lauder.
Computing zeta functions of Kummer curves via multiplicative characters.
Preprint, 2002,
Available at: http://web.comlab.ox.ac.uk/oucl/work/alan.lauder
[6] A.G.B. Lauder
and D. Wan. Counting points on varieties over finite fields of small
characteristic. Preprint, 2001,
Available at: http://web.comlab.ox.ac.uk/oucl/work/alan.lauder
[7] T. Satoh.
The canonical lift of an ordinary elliptic curve over a finite field and its
point counting. J. Ramanujan Math. Soc. 15 (2000),
no. 4, 247-270.
[8] Phuong
Q. Nguyen, Jacques Stern: Lattice Reduction in Cryptology: An Update.
Proc. Fourth Algorithmic Number Theory Symposium, Lecture Notes in
Computer Science, Vol. 1838, Springer-Verlag, 2000.
[9] Miklos Ajtai,
Cynthia Dwork: A public-key crypto-system with worst-case/average-case
equivalence. Proc. ACM STOC '97.
[10] Miklos Ajtai: The
shortest vector problem in L_{2} is NP-hard for randomized reductions.
Proc. ACM STOC '98.
[11] Arjen
K. Lenstra, Hendrik W. Lenstra, Jr.: The Development of the
Number Field Sieve. Lecture Notes in Mathematics, vol. 1554, Springer
Verlag, 1993.
[12] Ronald Cramer,
Victor Shoup: Universal Hash Proofs and a Paradigm for Adaptive Chosen
Cipher-Text Secure Public-Key Encryption. Proc. IACR EUROCRYPT '02,
Lecture Notes in Computer Science, vol. 2332, Springer Verlag,
pp. 45-64, 2002.
[13] Stefan
Dziembowski, Ueli Maurer: Optimal Randomizer Efficiency in the
Bounded-Storage Model. submitted manuscript, conference version appeared
in Proc. ACM STOC'02, 2002.
[14] Peter W. Shor,
John Preskill: Simple Proof of Security of the BB84 Quantum key
Distribution Protocol. Phys. Rev. Lett. 85 (2000) 441-444.
[15] Ronald Cramer,
Serge Fehr: Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups.
Proc. IACR CRYPTO '02, Lecture Notes in Computer Science, vol. 2442,
Springer-Verlag, pp. 272-287, 2002.
[16] Ronald Cramer,
Serge Fehr, Yuval Ishai, Eyal Kushilevitz: Multi-Party Computations over
Rings. Proc. IACR EUROCRYPT '03, Lecture Notes in Computer Science,
Springer-Verlag. To appear, 2003.