MPKC 2003: Mathematics of Public-Key Cryptography

MPKC 2003 will cover the latest developments in the mathematics of public-key cryptography. MPKC 2003 will be held Friday 7 November 2003 through Sunday 9 November 2003 at the University of Illinois at Chicago.

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 as soon as possible. Participants with other questions about the conference should contact


Invited speakers: Speakers contributing talks: All lectures will take place in Room 613 of the Chicago Circle Center (CCC) at 750 S. Halsted Street. Lectures will begin at 09:00 Friday 7 November and end midday Sunday 9 November. The doors of CCC will be open 07:00-22:00 each day. Titles and abstracts appear at the bottom of this page.

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


All participants are required to register. (Refreshments aren't free!) Registration fees will double on 17 October 2003. The registration form is on a separate web page.


Registered participants can send updates to

Campus and near-campus facilities

Email and web browsing. A conference account will be set up on the computers in a nearby computer lab, CCC 401. The login name will be xpguest. Hours 09:00-21:00 Thursday, 09:00-21:00 Friday, 08:00-20:00 Saturday, 08:00-14:00 Sunday.

Connecting laptops to the Internet. Conference participants who

will be allowed to plug their laptops into the ``UIC Network Access Stations'' in CCC 401. Sorry, no wireless access.

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:

  1. Giordano's, 815 W. Van Buren, 10:00-00:00. $. Pizza etc. 773-421-1221.
  2. Costa's, 340 S. Halsted, 11:00-00:00 SMTWR, 11:00-01:00 FS. $$. Greek. 312-263-9700.
  3. Nine Muses, 315 S. Halsted, 11:00-02:00 MTWRF, 14:00-03:00 S, 14:00-02:00 S. $. Greek. 312-902-9922.
  4. Byzantium, 232 S. Halsted, 16:00-04:00. $$. Greek. No non-smoking section. 312-454-1227.
  5. Athena, 212 S. Halsted, 11:00-00:00 SMTWR, 11:00-01:00 FS. $$. Greek. 312-665-0000.
  6. Greek Islands, 200 S. Halsted, 11:00-00:00 SMTWR, 11:00-01:00 FS. $$. Greek. 312-782-9855.
  7. Pegasus, 130 S. Halsted, 11:00-00:00 MTWRF, 12:00-00:45 SS. $$. Greek. 312-226-3377.
  8. 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.
  9. 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.
  10. La Sardine, 111 N. Carpenter, 11:30-14:30 17:00-23:00 MTWRF, 17:00-23:30 FS. French. $$$. 312-421-2800.
  11. One Sixty Blue, 160 N. Loomis, 17:00-22:00 MTWR, 17:00-22:30 FS. $$$. American. 312-850-0303.
  12. Chez Joel, 1119 W. Taylor. 17:00-22:00 MTWR, 17:00-23:00 FS, 16:30-22:00 S. $$$. French. 312-226-6479.
  13. Che Cafe, 1058 W. Taylor. $. 312-850-4665.
  14. Thai Bowl, 1049 W. Taylor. 11:00-20:30. $. Thai. 312-226-5865.
  15. 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.
Explorers can find more restaurant information at, and may find the train/bus maps useful.


The weather in Chicago is hard to predict. Examples: Participants are advised to check weather reports the day before travelling.

Travel and lodging

Chicago's O'Hare airport (10000 Bessie Coleman Drive) serves about 40 airlines. O'Hare has a Blue Line train connection to downtown and UIC every 10 minutes; inside the airport, look for signs saying Trains To City.

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:
HotelRate for double roomGetting to hotelGetting 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.
UIC offers visitor parking for $9.50/day in three large garages: 751 S. Halsted (directly across Halsted from CCC), 915 S. Paulina (two blocks from the Marriott), and 1100 W. Harrison.


Tentative lecture schedule:
Fri 7 Nov08:00-09:00Morning coffee
Fri 7 Nov09:00-09:05R. Michael Tanner, ProvostWelcome
Fri 7 Nov09:05-10:05Victor MillerThe 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 Nov10:05-10:30Coffee break
Fri 7 Nov10:30-11:30Reynald LercierA 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 Nov11:30-13:45Lunch
Fri 7 Nov13:45-14:45Ben 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 Nov15:00-15:30Iftikhar BurhanuddinOn 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 Nov15:30-16:00Coffee break
Fri 7 Nov16:00-16:30Jon-Lark KimCode-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 Nov16:45-17:00Rich SchroeppelAccelerating elliptic-curve computations
Sat 8 Nov08:00-09:00Morning coffee
Sat 8 Nov09:00-10:00Hugh 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 Nov10:00-10:30Coffee break
Sat 8 Nov10:30-11:30Nicolas TheriaultCryptographically 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 Nov11:30-14:00Lunch
Sat 8 Nov14:00-15:00Edlyn TeskeWeak 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 Nov15:10-15:30D. J. BernsteinNews from the Rabin-Williams front. Abstract: "Key compression; reducing randomness."
Sat 8 Nov15:30-16:00Coffee break
Sat 8 Nov16:00-16:30Willi MoreFermat 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 Nov16:40-17:00D. J. BernsteinMore news from the Rabin-Williams front. Abstract: "Signature compression; generating verification primes."
Sat 8 Nov17:00-17:30Siguna MuellerOn 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 Nov08:00-09:00Morning coffee
Sun 9 Nov09:00-10:00Alice SilverbergApplications 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 Nov10:00-10:30Coffee break
Sun 9 Nov10:30-11:30Michael JacobsonApplications 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 Nov11:45-12:15Denis CharlesTesting 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."