MPKC 2003 is sponsored by the National Science Foundation; the Illinois Center for Cryptography and Information Protection at the University of Illinois at Urbana-Champaign; and the Coordinated Science Lab at the University of Illinois at Urbana-Champaign. It is organized by Dan Bernstein, Dick Blahut, Iwan Duursma, and Andreas Stein.
This is version 2003.11.06 of the MPKC 2003 web page. Before travelling to Chicago, participants should print this web page and the separate map. Browsers that have trouble fitting the map onto a printed page may do better with the pre-shrunk map. There is also a map covering a larger area for participants scrolling through maps on their laptops.
Participants who would like to contribute talks should send a title and abstract to contributed@mpkc2003.mwisc.org as soon as possible. Participants with other questions about the conference should contact organizers@mpkc2003.mwisc.org.
Information for speakers: The lecture room will have two projector screens, two transparency projectors, and at least one computer projector. You are encouraged to prepare a talk that will make good use of both screens simultaneously. As a backup in case of computer problems, please send a PDF version of your talk to pdfslides@mpkc2003.mwisc.org.
Participants:
Connecting laptops to the Internet. Conference participants who
Starbucks has wireless access for a fee. There are Starbucks in the area at 550 W. Van Buren, 55 E. Jackson, 130 S. Canal, 1001 W. Madison, and 1430 W. Taylor.
Campus dining facilities. Some of the dining facilities in CCC, and in adjacent SRC, will be open at various times during the weekend.
Near-campus dining facilities. There are many restaurants within a several-minute walk of CCC in Greektown (north of campus) and Little Italy (immediately west of campus). For example:
Chicago's Midway airport (5700 S. Cicero) serves about 10 airlines, notably Southwest. Midway has an Orange Line train connection to downtown every 10 minutes. The Orange Line connects to the Blue Line at the Clark/Lake stop; adventurous travellers can consult maps to find faster connections.
There are many hotels in Chicago, but there are also many tourists in Chicago, so participants are encouraged to book rooms as soon as possible. Some rooms have been reserved at the following hotels:
| Hotel | Rate for double room | Getting to hotel | Getting to CCC |
|---|---|---|---|
| Marriott, 625 S. Ashland | $145, valet parking available for $22; call 312-491-1234 and mention UIC | By train: Blue Line to Medical Center or Polk. By car from O'Hare: Take 190 East to 90 East (Kennedy); exit to I-290 (Eisenhower) towards West Suburbs; exit 28B (Ashland); turn left on Ashland. By car from Midway: Take 55 North (Stevenson); exit 292A (Ryan/I-90 W/I-94 W) towards Wisconsin; exit 53A towards Wisconsin; exit to I-290 (Eisenhower) towards West Suburbs; exit 28B (Ashland); turn left on Ashland. Shorter routes are available on surface streets. | By foot: Walk 1 mile east on Harrison to Halsted; turn right; walk half block; CCC is on the right. By train: Blue Line in O'Hare direction to UIC/Halsted. By shuttle: Ask hotel. |
| Rodeway Inn, 1 S. Halsted (officially 1 Midcity Plaza; in Greektown) | $89, hotel parking available for $13; call 877-424-6423 and mention MPKC | By train from O'Hare: Blue Line to Grand; 8 bus south on Halsted to Madison. By train from Midway: Orange Line to Washington; 20 bus west on Madison to Halsted. By car from O'Hare: Take 190 East to 90 East (Kennedy); exit 51D (Madison); turn right onto Madison. By car from Midway: Take 55 North (Stevenson); exit 292A (Ryan/I-90 W/I-94 W) towards Wisconsin; exit 53A towards Wisconsin; exit 51E (Monroe); turn left onto Monroe. | By foot: Walk 0.7 miles south on Halsted past Harrison; CCC is on the right. |
| Hotel Burnham, 32 N. State (center of downtown) | $179, valet parking available for $31; call 877-294-9712 and mention MPKC UIC Department of Mathematics | By train: Blue Line to Washington, or Orange Line to Madison. By car from O'Hare: Take 190 East to 90 East (Kennedy); exit 51C (Washington); turn left onto Washington; east 1 mile on Washington to State. By car from Midway: Take 55 North (Stevenson); exit 292A (Ryan/I-90 W/I-94 W) towards Wisconsin; exit towards right to I-290 East (Eisenhower); east 1 mile to State; turn left; north 0.5 miles to Madison. | By train: Blue Line from Washington in Cermak/Forest Park direction to UIC/Halsted. By cab: Cabs readily available outside the hotel. |
| Fri 7 Nov | 08:00-09:00 | Morning coffee | |
| Fri 7 Nov | 09:00-09:05 | R. Michael Tanner, Provost | Welcome |
| Fri 7 Nov | 09:05-10:05 | Victor Miller | The Weil pairing and its efficient computation. Abstract: "The Weil Pairing was introduced by Andre Weil in 1940, and has become quite important in the arithmetic theory of elliptic curves and abelian varieties. More specifically, let E be an elliptic curve over a field K. For each integer n relatively prime to the characteristic of K, there is a skew-symmetric non-degenerate pairing, denoted by e_n, on the points of order n on E. We describe efficient algorithms for calculating the value of the pairing e_n with complexity O(log n) field operations in K. We then give two applications: reduction of the elliptic-curve discrete-logarithm problem for E(K) to the multiplicative-group discrete-logarithm problem in an extension of K (almost always of exponential degree), and a fast algorithm for calculating the group structure of E(K)." |
| Fri 7 Nov | 10:05-10:30 | Coffee break | |
| Fri 7 Nov | 10:30-11:30 | Reynald Lercier | A quasi-quadratic-time algorithm for hyperelliptic-curve point counting (joint work with D. Lubicz). Abstract: "We describe an algorithm to compute the cardinality of Jacobians of ordinary hyperelliptic curves of small genus over finite fields F_{2^n} with cost O(n^{2+o(1)}). This algorithm is derived from ideas due to Mestre. More precisely, we state the mathematical background behind Mestre's algorithm and develop from it a variant with quasi-quadratic time complexity. Among others, we present an algorithm to find roots of a system of generalized Artin-Schreier equations and give results that we obtain with an efficient implementation. Especially, we were able to obtain the cardinality of curves of genus one, two or three in finite fields of huge size." |
| Fri 7 Nov | 11:30-13:45 | Lunch | |
| Fri 7 Nov | 13:45-14:45 | Ben Lynn | Applications of bilinear maps. Abstract: "Pairing-based cryptography has become a very active research area. Many novel cryptosystems have been proposed, each one depending on properties of bilinear maps such as the Tate pairing. In this talk we will discuss how the bilinear maps are used in cryptography. We also investigate methods for constructing pairing-friendly elliptic curves, and outline various optimizations for the pairing. Lastly we will mention several open problems." |
| Fri 7 Nov | 15:00-15:30 | Iftikhar Burhanuddin | On computing discrete logarithms in formal groups and its applications. Abstract: "Given x,y in G an (additive) abelian group and y in <x> to compute n in Z such that y = [n]x is called the discrete logarithm problem. The supposed computational intractability of this problem in certain groups forms the core of many cryptographic systems. We will provide efficient algorithms to compute discrete logarithms in certain formal groups and show how inparticular this helps us to compute discrete logarithms in elliptic curves over local fields. We will discuss the motivation for the problem and its cryptographic applications." |
| Fri 7 Nov | 15:30-16:00 | Coffee break | |
| Fri 7 Nov | 16:00-16:30 | Jon-Lark Kim | Code-based public-key cryptosystems. Abstract: "In this talk we survey code-based public-key cryptosystems. We describe various such cryptosystems as well as code-based digital signature systems." |
| Fri 7 Nov | 16:45-17:00 | Rich Schroeppel | Accelerating elliptic-curve computations |
| Sat 8 Nov | 08:00-09:00 | Morning coffee | |
| Sat 8 Nov | 09:00-10:00 | Hugh Williams | Number theory inspired by cryptography. Abstract: "It is common knowledge that most of the constructions of public-key cryptography--and many of the constructions of modern private key cryptography--are based on difficult problems in number theory. There is, however, a constantly expanding flow in the opposite direction, from cryptography to number theory. In this largely expository talk I will describe several techniques, which owe their origin to the application of number theory to cryptography, that have been successfully applied to classical problems arising in computational number theory. In particular, I will discuss the integer factoring problem, the discrete logarithm problem, the problem of solving the Pell equation, and the primality testing problem." |
| Sat 8 Nov | 10:00-10:30 | Coffee break | |
| Sat 8 Nov | 10:30-11:30 | Nicolas Theriault | Cryptographically weak hyperelliptic curves. Abstract: "We describe some types of hyperelliptic curves that should be avoided in hyperelliptic cryptosystems and we discuss the reasons for these weaknesses, namely the index calculus attack and the Weil descent attack." |
| Sat 8 Nov | 11:30-14:00 | Lunch | |
| Sat 8 Nov | 14:00-15:00 | Edlyn Teske | Weak fields for elliptic-curve cryptography. Abstract: "We demonstrate that some finite fields, including GF(2^210), are weak for elliptic-curve cryptography in the sense that any instance of the elliptic-curve discrete-logarithm problem for any elliptic curve over these fields can be solved in significantly less time than it takes Pollard's rho method to solve the hardest instances. We discuss the implications of our observations to elliptic-curve cryptography, and list some open problems." |
| Sat 8 Nov | 15:10-15:30 | D. J. Bernstein | News from the Rabin-Williams front. Abstract: "Key compression; reducing randomness." |
| Sat 8 Nov | 15:30-16:00 | Coffee break | |
| Sat 8 Nov | 16:00-16:30 | Willi More | Fermat factorisation for n=pq. Abstract: "Using a conjecture by Schinzel and Sierpinski we will show that there exist infinitely many primes p, q related in the form f(p)=d q by an arbitrary irreducible polynomial f(x) in Z[x] with positive leading coefficient and an almost arbitrary integer d>0. So we can conclude that there exist infinitely many such n which will be factored by Fermat's method in step k >= k_0 for any given natural number k_0." |
| Sat 8 Nov | 16:40-17:00 | D. J. Bernstein | More news from the Rabin-Williams front. Abstract: "Signature compression; generating verification primes." |
| Sat 8 Nov | 17:00-17:30 | Siguna Mueller | On pseudocubes and primality testing. Abstract: "The concept of pseudosquares has been successfully applied to obtain fast primality testing algorithms. A pseudosquare behaves locally like a square while it nevertheless is not a perfect square. The question of extending this concept to more general type of numbers has been an unsolved problem for many years. Very recently, we have finally managed to extend the theory to pseudocubes." |
| Sun 9 Nov | 08:00-09:00 | Morning coffee | |
| Sun 9 Nov | 09:00-10:00 | Alice Silverberg | Applications of algebraic tori to cryptography. Abstract: "We apply the theory of algebraic tori to cryptography. We show how to use the rationality of algebraic tori to give discrete log based cryptosystems with shorter transmission sizes. We also give a mathematical interpretation of LUC, XTR, and conjectured generalizations in terms of algebraic tori. Further, we disprove conjectures given in the paper 'Looking Beyond XTR'. This is joint work with Karl Rubin." |
| Sun 9 Nov | 10:00-10:30 | Coffee break | |
| Sun 9 Nov | 10:30-11:30 | Michael Jacobson | Applications of NUCOMP. Abstract: "Recently, Jacobson and van der Poorten demonstrated that Dan Shanks' NUCOMP algorithm for composing binary quadratic forms can be applied to a number of other settings including divisor addition on hyperelliptic curves and computations in the infrastructure of a real quadratic number or function field. In this talk, we give an introduction to NUCOMP and report on recent work towards improving NUCOMP in these settings." |
| Sun 9 Nov | 11:45-12:15 | Denis Charles | Testing elliptic curves for complex multiplication. Abstract: "We describe some work in progress on checking when an elliptic curve defined over a number field has complex multiplication. We describe two polynomial time algorithms for this problem, one randomized and the other deterministic. The proof of correctness of these algorithms presents some interesting and challenging problems." |
