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

**Reynald Lercier**, Centre d'Electronique de L'Armement, France**Ben Lynn**, Stanford University, USA**Victor Miller**, Center for Communications Research, USA**Alice Silverberg**, Ohio State University, USA**Edlyn Teske**, University of Waterloo, Canada**Nicolas Theriault**, University of Essen, Germany**Hugh C. Williams**, University of Calgary, Canada

**D. J. Bernstein**, University of Illinois at Chicago, USA**Iftikhar Burhanuddin**, University of Southern California, USA**Denis Charles**, University of Wisconsin, USA**Michael Jacobson, Jr.**, University of Calgary, Canada**Jon-Lark Kim**, University of Nebraska at Lincoln, USA**Willi More**, University of Klagenfurt, Austria**Siguna Mueller**, University of Calgary, Canada**Rich Schroeppel**, Sandia National Laboratories, USA

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:

- Suanne Au, University of Nebraska at Lincoln, USA, xau@math.unl.edu
- Prof. D. J. Bernstein, University of Illinois at Chicago, USA, djb@cr.yp.to
- Prof. Dick Blahut, University of Illinois at Urbana-Champaign, USA, blahut@uiuc.edu
- Prof. Ian Blake, University of Toronto, Canada, ifblake@comm.utoronto.ca
- Iftikhar Burhanuddin, University of Southern California, USA, burhanud@usc.edu
- O-Yeat Chan, University of Illinois at Urbana-Champaign, USA, ochan@math.uiuc.edu. Other participants (male) should contact about possibly sharing a hotel room.
- Denis Charles, University of Wisconsin, USA, cdx@cs.wisc.edu
- Guy Chasse, Ecole des Mines de Nantes, France, chasse@emn.fr
- Pradeep Kamal Dharmavarapu, USA, pradeep_kamal_d@yahoo.com. Other participants (male) should contact about possibly sharing a hotel room.
- Han Duong, University of Illinois at Urbana-Champaign, USA, han@math.uiuc.edu
- Prof. Iwan Duursma, University of Illinois at Urbana-Champaign, USA, duursma@math.uiuc.edu
- Christina Eubanks-Turner, University of Nebraska at Lincoln, USA, ceubanks@math.unl.edu
- Jennifer Everson, University of Nebraska at Lincoln, USA, jeverson@math.unl.edu
- Randy Fulara, Information Security Corporation, USA
- Prof. Darren Glass, Columbia University, USA, glass@math.columbia.edu
- Dr. Jon Grantham, Center for Computing Sciences, USA, grantham@super.org
- Prof. Michael Jacobson, Jr., University of Calgary, Canada, jacobs@cpsc.ucalgary.ca
- Dr. Jon-Lark Kim, University of Nebraska at Lincoln, USA, jlkim@math.unl.edu
- Negar Kiyavash, University of Illinois at Urbana-Champaign, USA, kiyavash@uiuc.edu
- Eric Landquist, University of Illinois at Urbana-Champaign, USA, landquis@math.uiuc.edu Other participants (male) should contact about possibly sharing a hotel room.
- Reynald Lercier, Centre d'Electronique de L'Armement, France, lercier@club-internet.fr
- Ben Lynn, Stanford University, USA, blynn@stanford.edu
- Dr. Michael Markowitz, Information Security Corporation, USA, markowitz@infoseccorp.com
- Dr. Victor Miller, Center for Communications Research, USA, victor@idaccr.org
- Dr. Willi More, University of Klagenfurt, Austria, willi.more@uni-klu.ac.at
- Siguna Mueller, University of Calgary, Canada, smueller@math.ucalgary.ca
- Patricio Parada, University of Illinois at Urbana-Champaign, USA, paradasa@uiuc.edu
- Nikki Pitcher, University of Illinois at Chicago, USA, pitcher@math.uic.edu
- Prof. Vera Pless, University of Illinois at Chicago, USA, pless@math.uic.edu
- Ricardo Rojas, University of Illinois at Urbana-Champaign, USA, rrojas@uiuc.edu
- Jonathan Schulze-Hewett, Information Security Corporation, USA
- Rich Schroeppel, Sandia National Laboratories, USA, rcs@cs.arizona.edu
- Prof. Alice Silverberg, Ohio State University, USA, silver@math.ohio-state.edu
- Prof. Andreas Stein, University of Illinois at Urbana-Champaign, USA, andreas@math.uiuc.edu
- Dr. Christine Swart, University of Illinois at Chicago, USA, swart@math.uic.edu
- Dr. Edlyn Teske, University of Waterloo, Canada, eteske@uwaterloo.ca
- Dr. Nicolas Theriault, University of Essen, Germany, nicolast@math.toronto.edu
- Limin Wang, University of Illinois at Chicago, USA, limin@math.uic.edu
- Jonathan Webster, University of Illinois at Urbana-Champaign, USA, jewebste@math.uiuc.edu
- Hugh C. Williams, University of Calgary, Canada, williams@math.ucalgary.ca
- Qingquan Wu, University of Illinois at Urbana-Champaign, USA, qwu@uiuc.edu. Other participants (male) should contact about possibly sharing a hotel room.
- Maosheng Xiong, University of Illinois at Urbana-Champaign, USA, xiong@math.uiuc.edu. Other participants (male) should contact about possibly sharing a hotel room.

**Connecting laptops to the Internet.**
Conference participants who

- bring laptops,
- bring Ethernet cables, and
- request a temporary UIC account on their registration forms

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:

- Giordano's, 815 W. Van Buren, 10:00-00:00. $. Pizza etc. 773-421-1221.
- Costa's, 340 S. Halsted, 11:00-00:00 SMTWR, 11:00-01:00 FS. $$. Greek. 312-263-9700.
- Nine Muses, 315 S. Halsted, 11:00-02:00 MTWRF, 14:00-03:00 S, 14:00-02:00 S. $. Greek. 312-902-9922.
- Byzantium, 232 S. Halsted, 16:00-04:00. $$. Greek. No non-smoking section. 312-454-1227.
- Athena, 212 S. Halsted, 11:00-00:00 SMTWR, 11:00-01:00 FS. $$. Greek. 312-665-0000.
- Greek Islands, 200 S. Halsted, 11:00-00:00 SMTWR, 11:00-01:00 FS. $$. Greek. 312-782-9855.
- Pegasus, 130 S. Halsted, 11:00-00:00 MTWRF, 12:00-00:45 SS. $$. Greek. 312-226-3377.
- Jaks Tap, 901 W. Jackson, 11:00-00:00 MTW, 11:00-02:00 RF, 16:00-00:00 S. Cost depends primarily on alcohol consumption. 312-666-1700.
- Sushi Wabi, 842 W. Randolph, 11:30-14:00 17:00-23:00 M, 11:30-14:00 17:00-00:00 TWRF, 12:00-17:00 17:00-00:00 S, 17:00-23:00 S. $$$. Japanese. 312-563-1224.
- La Sardine, 111 N. Carpenter, 11:30-14:30 17:00-23:00 MTWRF, 17:00-23:30 FS. French. $$$. 312-421-2800.
- One Sixty Blue, 160 N. Loomis, 17:00-22:00 MTWR, 17:00-22:30 FS. $$$. American. 312-850-0303.
- Chez Joel, 1119 W. Taylor. 17:00-22:00 MTWR, 17:00-23:00 FS, 16:30-22:00 S. $$$. French. 312-226-6479.
- Che Cafe, 1058 W. Taylor. $. 312-850-4665.
- Thai Bowl, 1049 W. Taylor. 11:00-20:30. $. Thai. 312-226-5865.
- Tuscany, 1014 W. Taylor. 11:30-23:00 MTWR, 11:30-00:00 F, 17:00-00:00 S, 14:00-21:30 S. $$$. Italian. 312-829-1990.

- 8 November 2002, 46.4-64.4 deg F, 16.0mph winds;
- 8 November 2001, 35.6-57.2 deg F, 13.3mph winds;
- 8 November 2000, 36.0-50.0 deg F, 6.8mph winds;
- 8 November 1999, 44.1-73.9 deg F, 8.1mph winds;
- 8 November 1998, 33.8-39.9 deg F, 3.5mph winds, rain;
- 8 November 1997, 39.2-46.4 deg F, 9.4mph winds;
- 8 November 1996, 32.0-46.4 deg F, 10.1mph winds, rain;
- 8 November 1994, 46.9-61.9 deg F, 13.8mph winds, rain.

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