Mathematics of Cryptology

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

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