Will large quantum computers be built? If so, what will they do to the cryptographic landscape?

Anyone who can build a large quantum computer can break today's most popular public-key cryptosystems: e.g., RSA, DSA, and ECDSA. But there are several other cryptosystems that are conjectured to resist quantum computers: e.g., the Diffie-Lamport-Merkle signature system, the NTRU encryption system, the McEliece encryption system, and the HFE signature system. Exactly which of these systems are secure? How efficient are they, in theory and in practice?

PQCrypto 2006, the International Workshop on Post-Quantum Cryptography, will look ahead to a possible future of quantum computers, and will begin preparing the cryptographic world for that future.

Update: PQCrypto 2006 is done! The workshop record, except for three papers restricted by the copyright holders, is now online: pqcrypto2006record.pdf

## Speakers

Invited speakers:
• Sean Hallgren, NEC Laboratories, USA. "Quantum algorithms."
• Phong Nguyen, École Normale Supérieure, France. "Post-quantum lattice-based cryptography."
• Oded Regev, Tel-Aviv University, Israel. "More quantum algorithms."
• Nicolas Sendrier, Institut National de Recherche en Informatique et en Automatique, France. "Post-quantum code-based cryptography."
• Jacques Stern, École Normale Supérieure, France. "Post-quantum multivariate-quadratic public key schemes."
• Michael Szydlo, RSA Laboratories, USA. "Post-quantum hash-based cryptography."
• Lieven Vandersypen, Technische Universiteit Delft, the Netherlands. "Can quantum computers be built?"
Contributed talks: See below.

## Organization

PQCrypto 2006 is organized by the European Network of Excellence for Cryptology (ECRYPT), funded within the Information Societies Technology Programme (IST) of the European Commission's Sixth Framework Programme (FP6) under contract number IST-2002-507932. PQCrypto 2006 is an activity of ECRYPT's Asymmetric Techniques Virtual Lab (AZTEC). Program committee:
• Daniel J. Bernstein, University of Illinois at Chicago, USA
• Johannes Buchmann, Technische Universität Darmstadt, Germany
• Jintai Ding, University of Cincinnati, USA
• Louis Goubin, Université de Versailles, France
• Tanja Lange, Danmarks Tekniske Universitet, Denmark
• Phong Nguyen, École Normale Supérieure, France
• Tatsuaki Okamoto, NTT Laboratories, Japan
• Louis Salvail, Aarhus Universitet, Denmark
• Alice Silverberg, University of California at Irvine, USA
• Joe Silverman, Brown University, USA
• Martijn Stam, École Polytechnique Fédérale de Lausanne, Switzerland
• Christopher Wolf, École Normale Supérieure, France
Local assistance is provided by Nessim Kisserli, Ozgul Kucuk, Joseph Lano, Pela Noe, Saartje Verheyen, Christopher Wolf, and Elvira Wouters.

## Location

PQCrypto 2006 will be held at the Katholieke Universiteit Leuven in Belgium from Tuesday 23 May 2006 through Friday 26 May 2006. (Eurocrypt 2006 will begin on Sunday 28 May 2006 in St. Petersburg.)

Alert: PQCrypto 2006 was originally scheduled to start Wednesday 24 May 2006, but the opening talk is now scheduled for Tuesday 23 May 2006.

All lectures will take place in Room 00.54 (Auditorium A) of the ESAT-COSIC building at Kasteelpark Arenberg 10 in Heverlee. Directions appear at the bottom of this page; there is also a separate page of maps and directions.

Lectures will begin no earlier than 17:00 Tuesday 23 May and will end by 17:00 Friday 26 May. The doors of the ESAT-COSIC building will be open 07:30-19:00 each day.

Visas: Please ensure that you have valid travel documents to enter Belgium. Depending on your home country applications might take months. Belgium is a Schengen country, so you can enter Belgium using a visa for another Schengen country (e.g., Germany). However, you cannot enter Belgium using a non-Schengen visa (e.g., a United Kingdom visa). A list of Schengen states and more information about visa requirements for Belgium can be found here.

Space has been reserved in the schedule for contributed lectures. Important dates:
• submission of extended abstracts, 3 April 2006;
• registration, 26 April 2006;
• revised extended abstracts, 4 May 2006;
• workshop, 23-26 May 2006.

Authors interested in contributing a lecture should send an extended abstract in PDF form to

     contributed at postquantum.cr.yp.to

by 3 April 2006. Page limits: at most 20 pages including bibliography and appendices.

Update: The deadline for contributions has passed. The following contributed talks have been accepted:

• A public-key cryptosystem using algebraic surfaces (*Akiyama, Goto)
• Equivalent keys in multivariate quadratic public key systems (*Wolf, Preneel)
• High order linearization equation (HOLE) attack on multivariate public key cryptosystems (*Ding, Hu, Nie, Li, Wagner)
• Implementation of improved "Quantum public-key cryptosystem" (*Miyazawa, Kobayashi, Oda, Nakamura, Kanai)
• l-invertible cycles for multivariate quadratic public key cryptography (Ding, *Wolf, Yang)
• NTRUEncrypt and NTRUSign: efficient public key algorithms for a post-quantum world (Hoffstein, Howgrave-Graham, Pipher, Silverman, *Whyte)
• Polynomial equivalence problems: algorithmic and theoretical aspects (*Faugère, Perret)
• Probabilistic multivariate cryptography (Gouget, *Patarin)
• Proposal for piece in hand matrix ver. 2: general concept for enhancing security of multivariate public key cryptosystems (Tsujii, *Tadaki, Fujita)
• Statistical zero knowledge and quantum one-way functions (Kashefi, *Kerenidis)
• Symplectic lattice reduction and NTRU (*Gama, Howgrave-Graham, Nguyen)
• The limit of XL implemented with sparse matrices (Chen, Yang, Chen); talk given by *Ding
• Zhuang-Zi: a new algorithm for solving multivariate polynomial equations over a finite field (*Ding, Gower, Schmidt)
Speakers are marked with *.

Contributors:

• Koichiro Akiyama, Toshiba Corporation, Japan
• Chia-Hsin Owen Chen, National Taiwan University, Taiwan
• Jiun-Ming Chen, National Taiwan University / Chinese Data Security, Inc., Taiwan
• Jintai Ding, University of Cincinnati, USA
• Jean-Charles Faugère, LIP6, France
• Ryou Fujita, Institute of Information Security, Japan
• Nicolas Gama, École Normale Supérieure, France
• Yasuhiro Goto, Hokkaido University of Education, Japan
• Aline Gouget, Gemplus, France
• Jason Gower, University of Cincinnati, USA
• Jeff Hoffstein, Brown University / NTRU Cryptosystems, USA
• Nick Howgrave-Graham, NTRU Cryptosystems, USA
• Lei Hu, Chinese Academy of Sciences, China
• Atsushi Kanai, NTT Information Sharing Platform Laboratories, Japan
• Elham Kashefi, Institute for Quantum Computing, Canada
• Iordanis Kerenidis, Greece; affiliated to CNRS, Universite Paris-Sud, France
• Tetsutaro Kobayashi, NTT Information Sharing Platform Laboratories, Japan
• Jianyu Li, Chinese Academy of Sciences, China
• Toshiyuki Miyazawa, NTT Information Sharing Platform Laboratories, Japan
• Ichizo Nakamura, NTT Information Sharing Platform Laboratories, Japan
• Phong Nguyen, École Normale Supérieure, France
• Xuyun Nie, Chinese Academy of Sciences, China
• Satoshi Oda, NTT Information Sharing Platform Laboratories, Japan
• Jacques Patarin, University of Versailles, France
• Ludovic Perret, Université Catholique de Louvain, Belgium
• Jill Pipher, Brown University / NTRU Cryptosystems, USA
• Bart Preneel, Katholieke Universiteit Leuven, Belgium
• Dieter Schmidt, University of Cincinnati, USA
• Joseph H. Silverman, Brown University / NTRU Cryptosystems, USA
• Kohtaro Tadaki, Chuo University, Japan
• Shigeo Tsujii, Institute of Information Security, Japan
• John Wagner, University of Cincinnati, USA
• William Whyte, NTRU Cryptosystems, USA / Ireland
• Christopher Wolf, École Normale Supérieure, France
• Bo-Yin Yang, Tamkang University, Taiwan

A record of the workshop containing all accepted papers will be provided to the participants. There will be no formal proceedings; papers may be submitted to other conferences.

## Registration

All participants are required to register. The registration fee covers
• the welcome reception on Tuesday;
• lunch on Wednesday, Thursday, and Friday;
• the conference dinner on Thursday; and
• coffee during the morning and afternoon breaks.
In addition, all participants will receive a hardcopy of the papers presented, a map of Leuven, and a password to use the wireless network facilities of K.U.Leuven.

The registration fees are as follows:

• 160€ on or before 26 April 2006
• 210€ after 26 April 2006
The registration form is on a separate web page.

There is a limited number of stipends available to Ph.D. students and recent post-docs from the EU and associated states who cannot afford to attend otherwise. Please send applications to europeanstipends at postquantum.cr.yp.to including

• a short motivation (max. 10 lines),
• a CV, including the titles of your recent publications, and
• an estimate of your travel and hotel expenses.
If you have applied for a scholarship but want to register beforehand, please make sure to state in the registration form's comment field that you have applied for a stipend, and please do not supply a credit-card number.

Stipends are issued on a first come first serve basis depending on qualification, so please apply as soon as possible. Update: The deadline for stipend applications has passed.

Please note that we cannot fund applicants from other countries.

## Participants

There are 71 participants registered so far:
• Koichiro Akiyama (TOSHIBA Corp.), Japan
• Pierre Barthelemy (CNRS-IML), France
• Daniel Bernstein (U. Illinois at Chicago), USA
• Johannes Buchmann (Darmstadt University of Technology), Germany
• Pierre-Louis Cayrel (Xlim), France
• Manuel Charlemagne (UVSQ), France
• Erik Dahmen (TU Darmstadt), Germany
• Yvo Desmedt (University College London), United Kingdom
• Jintai Ding (University of Cincinnati), USA
• Philippe Elbaz-Vincent (U. Montpellier II), France
• Jean-Charles Faugere (CNRS), France
• Ryou Fujita (Institute of Information Security, Japan), Japan
• Nicolas Gama (ENS), France
• Craig Gentry (Stanford University), USA
• Yasuhiro Goto (Hokkaido Univ. of Edu.), Japan
• Aline Gouget (Gemplus), France
• Sean Hallgren (NEC Labs), USA
• Hendrik Hubrechts (K.U.Leuven), Belgium
• Ilknur Inam (SSM / Project Manager), Turkey
• Iordanis Kerenidis (CNRS), France
• Eike Kiltz (CWI), Netherlands
• Woo-Hwan Kim (NSRI), Korea
• Brad Lackey (U.S. Dept of Defense), USA
• Andreas Lang (University of Magdeburg), Germany
• Tanja Lange (Technical University of Denmark), Denmark
• Richard Lindner (TU Darmstadt), Germany
• Manfred Lochter (BSI), Germany
• Ignacio Luengo (U. Complutense de Madrid), Spain
• Matthew McKague (IQC University of Waterloo), Canada
• Andre Allan Methot (Universite de Geneve), Switzerland
• Toshiyuki Miyazawa (NTT Information Sharing Platform Laboratories), Japan
• Moesfa Soeheila Mohamad (Mimos), Malaysia
• Michele Mosca (IQC and PI, Waterloo), Canada
• Phong Nguyen (ENS), France
• Tatsuaki Okamoto (NTT), Japan
• Alp Oztarhan (TUBITAK-UEKAE), Turkey
• Jacques Patarin (University of Versailles), France
• Bart Preneel (COSIC, K.U.Leuven), Belgium
• Christine Priplata (EDIZONE GmbH), Germany
• Oded Regev (Tel-Aviv University), Israel
• Maike Ritzenhofen (TU Darmstadt), Germany
• Reihaneh Safavi-Naini (University of Wollongong), Australia
• Nicolas Sendrier (INRIA), France
• Abhi Shelat (IBM Zurich), Switzerland
• Daniel James Shepherd (Univ Bristol), UK
• Benjamin Smith (RHUL), UK
• Jerry Solinas (NSA), USA
• Colin Stahlke (EDIZONE GmbH), Germany
• Martijn Stam (EPFL), Switzerland
• Douglas Stebila (IQC, University of Waterloo), Canada
• Jacques Stern (ENS), France
• Michael Szydlo (RSA Labs), USA
• Kohtaro Tadaki (Chuo University), Japan
• Edlyn Teske (University of Waterloo and CWI Amsterdam), Canada
• Lieven Vandersypen (TU Delft), The Netherlands
• Ulrich Vollmer (TU Darmstadt), Germany
• William Whyte (NTRU), Ireland / USA
• Andreas Winter (University of Bristol), United Kingdom
• Christopher Wolf (ENS), France
• Song Yan (Coventry University), UK
• 11 unlisted participants

## Campus and near-campus facilities

Connecting laptops to the Internet. Wireless access is provided to all participants. Upon registration, you get a login and a password.

Some Internet cafes in Leuven:

• Cafe Apero, Oude Markt 52, 3000 Leuven, phone +32 (0) 16 22 37 76.
• Spacebar, Naamsestraat 66, 3000 Leuven, email info at spacebar.be, hours 12:00-02:00.

Campus dining facilities. Lunches on Wednesday and Friday will be at Alma 3, close to the conference venue.

Near-campus dining facilities. There are plenty of restaurants and pubs in Leuven, so it is impossible to give a general overview of all possible places to go. As a rule of thumb, you can find cheap places in Naamsestraat, close to the city hall (stadhuis). More elaborate cuisine can be found in Muntstraat (first street on the left if you go from the city hall to Naamsepoort). A variety of pubs (most of them also serving food) can be found at the Oude Markt. Starting at the stadhuis, you walk on Naamsestraat, and take the second on the right.

## Weather

Some historical data for nearby Brussels:
• 24 May 2005: low 7, high 17, humidity 48-93, wind speed 10 km/h, rain;
• 24 May 2004: low 3, high 17, humidity 45-93, wind speed 3 km/h;
• 24 May 2003: low 10, high 15, humidity 82-100, wind speed 8 km/h, rain;
• 24 May 2002: low 8, high 13, humidity 67-94, wind speed 8 km/h, rain;
• 24 May 2001: low 10, high 23, humidity 38-88, wind speed 6 km/h;
• 24 May 2000: low 12, high 18, humidity 68-100, wind speed 19 km/h, rain;
• 24 May 1999: low 11, high 17, humidity 64-94, wind speed 8 km/h, rain;
• 24 May 1998: low 10, high 15, humidity 67-100, wind speed 3 km/h, rain;
• 24 May 1997: low 3, high 13, humidity 51-100, wind speed 6 km/h.
Bottom line: Bring an umbrella.

Update: Here are the Monday 22 May 2006 weather predictions. Tuesday 23 May: 14, wind speed 21 km/h, 40% chance of rain. Tuesday night: 6, wind speed 14 km/h, low chance of rain. Wednesday 24 May: 15, wind speed 32 km/h, 50% chance of rain. Wednesday night: 8, wind speed 21 km/h, 30% chance of rain. Thursday 25 May: 13, wind speed 21 km/h, 80% chance of rain. Thursday night: 10, wind speed 14 km/h, low chance of rain. Friday 26 May: 14, wind speed 18 km/h, 80% chance of rain. Friday night: 13, wind speed 25 km/h, 90% chance of rain.

## Lodging

Other events are taking place in Leuven at this time of the year. Participants are advised to book early.

Hotel accommodations are not included in the workshop registration fee. Participants must make their own arrangements. The first four hotels in the following list offer special prices for conference participants:
Hotel Rates Internet access Directions to hotel Directions to ESAT
IBIS Leuven. Brusselsestraat 52, 3000 Leuven. Phone: +32.16.29.31.11. Fax: +32.16.23.87.92. Email: H1457 at accor.com. Single: 79 €. Double: 89 €. Breakfast included. Call before 5 May 2006 and mention PQCrypto 2006. Orange WiFi hotspot. 10€ for 2 hours. From the Leuven train station, follow Bondgenotenlaan until Fochplein. There, continue to the city hall (stadhuis), and then turn right into Brusselsestraat. Follow Brusselsestraat until you reach the city hall (stadhuis). Enter Naamsestraat and walk until the next bus stop (about 50m). Then take the bus to the ESAT building.
Hotel Industrie. Martelaerenplein 7, 3000 Leuven. Phone: +32.16.22.13.49. Fax: +32.16.20.82.85. Email: info at industriehotel.be. Single: 55 €. Double: 65 €. Breakfast included. Call before 8 April 2006, mention PQCrypto 2006, and supply credit-card number. No Internet access. However, the Hotel Mille Colonnes next door offers Internet for passersby. From the Leuven train station, cross the street. As the hotel is directly at the train station, simply take the bus to the ESAT building.
Hotel de Biestpoort, formerly Hotel Jackson's. Brusselsestraat 110-112, 3000 Leuven. Phone: +32.16.20.24.92 or +32.16.20.81.43. Fax: +32.16.23.13.29. Email: info at hotelbiestpoort.be. Single: 65 €. Double: 80 €. Breakfast included. Call before 8 April 2006, mention PQCrypto 2006, and supply credit-card number. Cancellation policy: 2 days before arrival = no expenses charged. No Internet access. From the Leuven train station, follow Bondgenotenlaan until Fochplein. There, continue to the city hall (stadhuis), and then turn right into Brusselsestraat. Follow Brusselsestraat until you reach the city hall (stadhuis). Enter Naamsestraat and walk until the next bus stop (about 50m). Then take the bus to the ESAT building.
Hotel La Royale. Martelaerenplein 5, 3000 Leuven. Phone: +32.16.22.12.52. Fax: +32.16.29.52.52. Email: info at laroyale.be. Single: 57 €. Double: 69 €. Breakfast included. Call before 12 May 2006, mention PQCrypto 2006, supply credit-card number, and state arrival time. No Internet access. However, the Hotel Mille Colonnes next door offers Internet for passersby. From the Leuven train station, cross the street. As the hotel is directly at the train station, simply take the bus to the ESAT building.
Hotel Binnenhof. Maria-Theresiastraat 65, 3000 Leuven. Phone: +32.16.20.55.92. Fax: +32.16.23.69.26. Email: info at hotelbinnenhof.be. Single: 115 - 130 €. Double: 130 - 145 €. Breakfast included. One PC in the lobby which can be used free of charge for guests. From the Leuven train station, cross the street, turn left and then walk 20 metres until you reach the Maria-Theresia-Street. From the hotel, go to the train station. From there, take the bus to the ESAT building.
Hotel Boardhouse. Jules Vandenbemptlaan 6, 3001 Leuven-Heverlee. Phone: +32.16.31.44.44. Fax: +32.16.21.44.45. Email: info at boardhouse.be. Rooms: 80 - 110 €. Breakfast: 11 €. WiFi, free of charge for guests. From the Leuven train station, take the bus to the Kantineplein. Turn left and enter Jules Vandenbemptenlaan. At the hotel, turn right and follow Jules Vandenbemptenlaan until you reach Kantineplein. Cross Kantineplein to reach the conference venue.
Hotel The Lodge Heverlee. Kantineplein 3, 3001 Leuven-Heverlee. Phone: +32.16.50.95.09. Fax: +32.16.50.95.08. Email: heverlee at lodge-hotels.be. Single: 105 €. Double: 115 - 145 €. Breakfast included. WiFi, free of charge for guests. From the Leuven train station, take the bus to the Kantineplein. You find the hotel there. Cross Kantineplein to reach the conference venue.
Hotel Mille Colonnes. Martelarenplein 5, 3000 Leuven. Phone: +32.16.22.86.21. Fax: +32.16.22.04.34. Email: Mille.colonnes at pandora.be. Single: 35 - 45 €. Double: 55 - 60 €. Breakfast included. In the bar, there is a computer which can be used by guests. Guests of other hotel can also use this computer against a (reasonable) fee. From the Leuven train station, cross the street. As the hotel is directly at the train station, simply take the bus to the ESAT building.
De Blauwput. Martelarenlaan 11A, 3000 Leuven. Phone: +32.16.63.90.62. Fax: +32.16.63.90.64. Email: leuven@vjh.be. This is the Leuven youth hostel; it does not take advance bookings. Bed in dorm: 16.30 €. Bed in twin room: 20.50 €. Breakfast included. One PC, connected to broad band, is available to guests for 1 € per half hour. Exit the train station in direction Kessel-Lo, cross the Martelarenlaan, and enter the youth hostel. Cross Martelarenlaan, enter the station and then take the bus to the ESAT building.
Using the official Leuven tourism site you can look for other hotels.

Warning for drivers: Make sure that your hotel has a parking lot. In particular for hotels in the Leuven city centre, this is not always the case. In addition, Leuven is not at all designed to drive around in the city by car (plenty of one-way streets). However, going there is easy as it is situated at the two high-ways E40 and E314.

## Schedule

 Session chair: Phong Nguyen Tue 23 May 17:20-17:30 Opening (in room 00.24) Tue 23 May 17:30-18:20 Speaker: Lieven Vandersypen "Can quantum computers be built?" Abstract: TBA. Tue 23 May 18:20-19:00 Registration and reception (in room 00.62) Tue 23 May 19:00-20:00 Reception continues Wed 24 May 09:00-09:40 Registration (in room 01.57) Session chair: Christopher Wolf Wed 24 May 09:40-09:50 Essential information (in room 00.54) Wed 24 May 09:50-10:40 Speaker: Sean Hallgren "Quantum algorithms." Abstract: TBA. Wed 24 May 10:40-11:10 Coffee Wed 24 May 11:10-12:00 Speaker: Michael Szydlo "Post-quantum hash-based cryptography." Abstract: The Merkle-tree construction promises to offer authentication and digital signatures which are resistant to quantum attacks. One of the first proposals in public key cryptography (1979), this construction relies only on a hash function for its security. While RSA and other number theory based algorithms will succumb to efficient quantum algorithms, a hash function need not have a "number-theoretic" basis. Without this structure, a quantum Fourier transform based algorithm seems less likely to appear. In this talk we will review the Merkle tree constructions and focus on recent advances which make the Merkle-tree construction more efficient and practical. We explain the space-time tradeoffs inherent in the Merkle construction, which historically made them less appealing than other authentication and digital signature schemes. However, we suggest that recent efficiency improvements render Merkle trees more practical today, and the threat of quantum algorithms makes this well accepted construction even more appealing. Wed 24 May 12:00-14:00 Lunch (in Alma 3); registration (in room 01.57) Session chair: Jintai Ding Wed 24 May 14:00-14:30 Speaker: Iordanis Kerenidis "Statistical zero knowledge and quantum one-way functions." (Kashefi, Kerenidis) Abstract: One-way functions are a fundamental notion in cryptography, since they are the necessary condition for the existence of secure encryption schemes. Most examples of such functions, including factoring, discrete Logarithm or the RSA function, can be, however, inverted with the help of a quantum computer. Hence, it is very important to study the possibility of quantum one-way functions, i.e. functions which are easily computable by a classical algorithm but are hard to invert even by a quantum adversary. In this paper, we provide for the first time a set of problems that are good candidates for quantum one-way functions. These problems include Graph Non-Isomorphism, approximate Closest Lattice Vector and Group Non-Membership. More generally, we show that any hard instance of Circuit Quantum Sampling gives rise to a quantum one-way function. By the work of Aharonov and Ta-Shma, this implies that any language in Statistical Zero Knowledge which is hard-on-average for quantum computers, leads to a quantum one-way function. Moreover, extending the result of Impagliazzo and Luby to the quantum setting, we prove that quantum distributionally one-way functions are equivalent to quantum one-way functions. Wed 24 May 14:30-14:45 Discussion Wed 24 May 14:45-15:35 Speaker: Jacques Stern "Post-quantum multivariate quadratic public key schemes." Abstract: Since the invention of public key cryptography by Diffie and Hellman in 1976, very few public key schemes have been deployed in applications, besides the celebrated RSA algorithm designed by Rivest, Shamir, and Adleman. While millions of RSA keys are used in WEB browsers, most public key cryptosystems are only present in textbooks, despite the fact that, if ever it happens, the advent of quantum computers would render RSA insecure. There are however, several challenging lines of research proposing public key schemes of a different flavour. Among these is multivariate cryptography, which stems from considering the mathematical formula describing RSA as a univariate modular polynomial, and attempts to use multivariate polynomials instead, hoping that the cost of encryption and/or decryption will be lower. While the original proposals based on this idea have been shown insecure, many further schemes have been designed. In turn, these have been subject to active cryptanalytic work. The aim of the talk is to review some of the schemes, to explain some of the methods that have been used to attack them, and to assess their level of security. In other words, is multivariate cryptography now ready for practical applications? Or do we have to wait until quantum computers are built? PPT slides Wed 24 May 15:35-16:05 Coffee Session chair: Johannes Buchmann Wed 24 May 16:05-16:35 Speaker: Jacques Patarin "Probabilistic multivariate cryptography." (Gouget, Patarin) Abstract: In public key schemes based on multivariate cryptography, the public key is a finite set of $m$ (generally quadratic) polynomial equations and the private key is a trapdoor allowing the owner of the private key to invert the public key. In existing schemes, a signature or an answer to an authentication is valid if all the m equations of the public key are satisfied. In this paper, we study the idea of probabilistic multivariate cryptography, i.e., a signature or an authentication value is valid when at least $\alpha$ equations of the $m$ equations of the public key are satisfied, where $\alpha$ is a fixed parameter of the scheme (or more generally when at least $\alpha_1$ of the first $m_1$ equations of the public key are satisfied, and at least $\alpha_2$ of the $m_2$ next equations of the public key are satisfied, etc., and at least $\alpha_\ell$ of the last $m_\ell$ equations are satisfied, where $\alpha_1,\ldots,\alpha_\ell,m_1,\ldots,m_\ell$ are well chosen integers with $m_1 + \cdots + m_\ell = m$). We show that many new public key signature and authentication schemes can be built using this concept. We apply this concept on some known multivariate schemes and we show how it can improve the security of the schemes. Wed 24 May 16:35-16:50 Discussion Wed 24 May 16:50-17:20 Speaker: Jean-Charles Faugère "Polynomial equivalence problems: algorithmic and theoretical aspects." (Faugère, Perret) Abstract: The Isomorphism of Polynomials (IP), which is the main concern of this paper, originally corresponds to the problem of recovering the secret key of a C* scheme. Besides, the security of various other schemes (signature, authentication, traitor tracing, ... also depends on the practical hardness of IP. Due to its numerous applications, the Isomorphism of Polynomials is thus one of the most fundamental problems in multivariate cryptography. In this paper, we address two complementary aspects of IP, namely its theoretical and practical difficulty. We present an upper bound on the theoretical complexity of "IP-like" problems, i.e. a problem consisting in recovering a particular transformation between two sets of multivariate polynomials. We prove that these problems are not NP-Hard (provided that the polynomial hierarchy does not collapse). Concerning the practical aspect, we present a new algorithm for solving IP. In a nutshell, the idea is to generate a suitable algebraic system of equations whose zeroes correspond to a solution of IP. From a practical point of view, we employed a fast Groebner basis algorithm, namely F5, for solving this system. This approach is efficient in practice and obliges to modify the current security criteria for IP. We have indeed broken several challenges proposed in literature. For instance, we solved a challenge proposed by O. Billet and H. Gilbert at Asiacrypt'03 in less than one second. Wed 24 May 17:20-17:35 Discussion Wed 24 May 17:35-18:05 Speaker: Christopher Wolf "l-invertible cycles for multivariate quadratic public key cryptography." (Ding, Wolf, Yang) Abstract: We propose a new basic trapdoor $\ell$IC ($\ell$-Invertible Cycles) for Multivariate Quadratic public key cryptosystems of the mixed field type. While IC is distantly related to the well-known $C^*$ or Matsumoto-Imai Scheme A (MIA) trapdoor, and share some features of the stagewise triangular systems, it has distinctive properties that sets it apart as a new basic trapdoor in the context of Multivariate Quadratic public key systems. This is the first new basic trapdoor since the invention of Unbalanced Oil and Vinegar in 1997, nearly a decade ago. In practice, IC is much faster than MIA, and can even match the speed of single-field Multivariate Quadratic schemes. We also introduce formally a new modifier, the so-called embedding'', which can be used to construct mixed field schemes without decryption failure. Session chair: Daniel J. Bernstein Thu 25 May 09:30-10:20 Speaker: Oded Regev "More quantum algorithms." Abstract: In this talk I will describe some attempts to construct quantum algorithms to deal with problems not addressed by Shor's algorithms and subsequent developments. A particular emphasis will be put on quantum algorithms for lattice problems, as those are one of our best candidates for post-quantum cryptography. Among other things, I will describe the connection to the dihedral hidden subgroup problem, and show how the ability to create certain quantum states implies interesting quantum algorithms. Thu 25 May 10:20-10:50 Coffee Thu 25 May 10:50-11:20 Speaker: Jintai Ding "High order linearization equation (HOLE) attack on multivariate public key cryptosystems." (Ding, Hu, Nie, Li, Wagner) Abstract: In the CT-track of the 2006 RSA conference, a new multivariate public key cryptosystem, which is called the Medium Field Equation (MFE) multivariate public key cryptosystem, is proposed by Wang, Yang, Hu and Lai. We use the second order linearization equation attack method by Patarin to break MFE. Given a ciphertext, we can derive the plaintext within $2^{23}$ ${\bf F}_{2^{16}}$-operations, after performing once for any public key a computation of complexity less than $2^{52}$. We also propose a high order linearization equation (HOLE) attack on multivariate public key cryptosystems, which is a further generalization of the (first and second order) linearization equation (LE). This method can be used to attack extensions of the current MFE. Thu 25 May 11:20-11:35 Discussion Thu 25 May 11:35-12:05 Speaker: Kohtaro Tadaki "Proposal for piece in hand matrix ver. 2: general concept for enhancing security of multivariate public key cryptosystems." (Tsujii, Tadaki, Fujita) Abstract: We proposed the concept, piece in hand (soldiers in hand) matrix and have developed the framework based on the concept so far. The piece in hand (PH, for short) matrix is a general concept which can be applicable to any type of multivariate public key cryptosystems to enhance their security. In this paper, we make improvements in the PH matrix method as follows. (i) In the PH matrix method, an arbitrary number of additional variables can be introduced to the random polynomial term in the public key, which is eliminated by the multiplication of the public key by the PH matrix during the decryption. Thus these additional variables enables the public key to have more than one solution, and therefore increases the difficulty to solve the public key. We show, in an experimental manner, that the PH matrix method improved in this way is secure even against the Gr\"obner basis attack. (ii) In the nonlinear PH matrix method proposed previously, the degree of polynomials in the public key is more than two, and this may cause an undesirable increase in the size of the public key. In this paper, we propose a nonlinear PH matrix method, where the degree of polynomials in the public key is kept the same as the degree of polynomials in the public key of the original cryptosystem, which is normally two. Thu 25 May 12:05-14:00 Lunch (in room 01.57); registration (in room 01.57) Session chair: Martijn Stam Thu 25 May 14:00-14:30 Speaker: Koichiro Akiyama "A public-key cryptosystem using algebraic surfaces." (Akiyama, Goto) Abstract: In this paper, we present a new type of public-key cryptosystem whose security is based on a decision randomizing polynomial problem which is related to a problem of finding sections on fibered algebraic surfaces. This section finding problem has no known efficient algorithm to solve. It can be reduced to solving a multivariable equation system and this problem is known to be NP-complete. The multivariable equation system associated with the section finding problem can be more general than that of Hidden Field Equations'' (HFE); with respect to the key size, our cryptosystem requires a key size of order $O(n)$, whereas HFE requires one of order $O(n^3)$, where n denotes the number of variables. We prove the IND-CCA security of our cryptosystem within the framework of the random oracle model. Thu 25 May 14:30-14:45 Discussion Thu 25 May 14:45-15:35 Speaker: Phong Nguyen "Post-quantum lattice-based cryptography." Abstract: TBA. Thu 25 May 15:35-16:05 Coffee Session chair: Tatsuaki Okamoto Thu 25 May 16:05-16:35 Speaker: William Whyte "NTRUEncrypt and NTRUSign: efficient public key algorithms for a post-quantum world." (Hoffstein, Howgrave-Graham, Pipher, Silverman, Whyte) Abstract: We provide an overview of the algorithms NTRUEncrypt and NTRUSign. These algorithms have attractive operating speed and keysize and are based on hard problems that are not known to have polynomial-time quantum algorithms. We discuss the state of current knowledge about the security of both algorithms and identify areas of research where progress could help the algorithms to gain acceptance. Thu 25 May 16:35-16:50 Discussion Thu 25 May 16:50-17:20 Speaker: Nicolas Gama "Symplectic lattice reduction and NTRU." (Gama, Howgrave-Graham, Nguyen) Abstract: NTRU is a very efficient public-key cryptosystem based on polynomial arithmetic. Its security is related to the hardness of lattice problems in a very special class of lattices. This article is motivated by an interesting peculiar property of NTRU lattices. Namely, we show that NTRU lattices are proportional to the so-called symplectic lattices. This suggests to try to adapt the classical reduction theory to symplectic lattices, from both a mathematical and an algorithmic point of view. As a first step, we show that orthogonalization techniques (Cholesky, Gram-Schmidt, QR factorization, etc.) which are at the heart of all reduction algorithms known, are all compatible with symplecticity, and that they can be significantly sped up for symplectic matrices. Surprisingly, by doing so, we also discover a new integer Gram-Schmidt algorithm, which is faster than the usual algorithm for all matrices. Finally, we study symplectic variants of the celebrated LLL reduction algorithm, and obtain interesting speed ups. Thu 25 May 17:20-17:35 Discussion Thu 25 May 17:35-18:05 Speaker: Toshiyuki Miyazawa "Implementation of improved "Quantum public-key cryptosystem"." (Miyazawa, Kobayashi, Oda, Nakamura, Kanai) Abstract: In 2000, Okamoto, Tanaka, and Uchiyama proposed the concept of the "quantum public-key cryptosystem" and a concrete scheme called OTU2000. OTU2000 is secure against attacks using quantum computers and uses these computers to generate a key pair. Thus, it is thought that OTU2000 will be actualized after quantum computers are actualized. We improve the original OTU2000 scheme so that it can be executed using current computers and show implementation results, using the multiplicative group of the ring of integers modulo a 640-bit composite number. The key generation procedure requires less than 2 hours, the encryption procedure requires approximately 4.4 msec, and the decryption procedure requires approximately 7.6 msec on a PC (Pentium 4 3.2 GHz). These results show that the OTU2000 can be implemented using current computers. Thu 25 May 18:05-19:30 Free time. Update: Rump session during this time! Contact Christopher Wolf if you have a rump-session presentation. Thu 25 May 19:30-22:00 Conference dinner (in Wok Dynasty) Session chair: Tanja Lange Fri 26 May 09:30-10:20 Speaker: Nicolas Sendrier "Post-quantum code-based cryptography." Abstract: Cryptographic primitives based on error correcting codes allow the construction of various kind of cryptographic schemes: encryption, authentication, digital signature and even hash functions. We will first review some of those systems and examine how their security is reduced to well identified difficult problems of algorithmic coding theory. We will then examine some of the most attractive features of those systems: the McEliece encryption scheme has a very fast encryption procedure the code-based digital signature scheme allows an extremely short signature size the syndrome primitive is a linear function acting on a non linear domain; it allows the construction of efficient hash functions with an interesting security reduction Finally we will examine some open problems related to parameter improvements or security assessments. Fri 26 May 10:20-10:50 Coffee Fri 26 May 10:50-11:20 Speaker: Christopher Wolf "Equivalent keys in multivariate quadratic public key systems." (Wolf, Preneel) Abstract: Multivariate Quadratic public key schemes have been suggested back in 1985 by Matsumoto and Imai as an alternative for the RSA scheme. Since then, several other schemes have been proposed, for example Hidden Field Equations, Unbalanced Oil and Vinegar schemes, and Stepwise Triangular Schemes. All these schemes have a rather large key space for a secure choice of parameters. Surprisingly, the question of equivalent keys has not been discussed in the open literature until recently. In this article, we show that for all basic classes mentioned above, it is possible to reduce the private --- and hence the public --- key space by several orders of magnitude. For the Matsumoto-Imai scheme, we are even able to show that the reductions we found are the only ones possible, i.e., that these reductions are tight. While the theorems developed in this article are of independent interest themselves as they broaden our understanding of Multivariate Quadratic public key systems, we see applications of our results both in cryptanalysis and in memory efficient implementations of MQ-schemes. Fri 26 May 11:20-11:35 Discussion Session chair: Christopher Wolf Fri 26 May 11:35-12:05 Speaker: Jintai Ding "The limit of XL implemented with sparse matrices." (Chen, Yang, Chen) Abstract: System-solving algorithms attracted a lot of attention when Jean-Charles Faugère solved the HFE Challenge 1 using his F5 algorithm. Today, they are the centerpiece of what is known as algebraic attacks and very much a vital technique in cryptology. Methods that find a Groebner Bases through the manipulation of extended Macaulay matrices are called Lazard-Faugère solvers. The state-of-the-art F5 as well as its predecessor F4, and XL (eXtended Linearization) variants are Groebner Basis Solvers of the Lazard-Faugère family, which solve a polynomial system by manipulating extended Macaulay matrices. We explore their uses in cracking some multivariate public-key cryptosystems and try to learn how to optimize system-solving in some cryptologically significant situations. In the process, we try to implement and evaluate XL using sparse matrices, and arrive at the conclusion that for generic mid-sized field and systems in the practical range, FXL can potentially outperform more sophisticated F4-F5 based methods. Fri 26 May 12:05-12:20 Discussion Fri 26 May 12:20-12:50 Speaker: Jintai Ding "Zhuang-Zi: a new algorithm for solving multivariate polynomial equations over a finite field." (Ding, Gower, Schmidt) Abstract: We present the Zhuang-Zi algorithm, a new method for solving multivariate polynomial equations over a finite field. We describe the algorithm and present examples, some of which cannot be solved with the fastest known algorithms. Fri 26 May 12:50-13:00 Closing Fri 26 May 13:00-14:15 Lunch (in Alma 3)

## Directions

Bus from the Leuven train station to the ESAT building: At the train station, board a number 2 bus direction Heverlee Campus. Stay on the bus for about 20 minutes and leave at Kantineplein. (Previous stops: Fochplein, Naamsestraat, Naamsesteenweg.) You are now in front of Kasteel Arenberg. Go towards the castle. The first building on the right is the Department of Electrical Engineering.

We want to stress that there are four (!) different number 2 buses, but only one them will bring you to the conference venue, namely Heverlee Campus. Do not confuse this with Heverlee Boskant; that bus requires you to get off at Heverlee station and then walk for about 5 minutes to the ESAT building, taking the Jules-Vandenbemptlaan until it ends.

One ride within Leuven costs 1.5€ when bought on the bus. If you buy your ticket in advance at one of these shops you get it for 1.20€. There are blocks of 10 rides (usable also for multiple people) called Lijnkaarten. You can buy them directly from the bus-driver for 12€, from vending machines for 10€ and from shops for as little as 8€.

In case you are travelling regularly with a group of at least 5 people the Lijnkaart %, only 6€ in shops, is attractive; this is the price reduced version for children, elderly people and groups. For more information on prices and the public transportation system visit De Lijn-Priceinformation (Flemish only).

Walking from the Leuven train station to the ESAT building: Walking from the station will take you about one hour. We describe the whole way from the station, as it is an attractive option to see the city. In addition, if your hotel is situated close to Naamseport, walking to the venue is actually a very attractive option. From the station, you follow the Bondgenotenlaan until Fochplein (big bus station). There, you go until the city hall (stadhuis) / tourist information, and then follow Naamsestraat until Naamsepoort. There you cross the ring. Right after, the Naamsestraat splits in two and also changes its name: the left part is called Naamsesteenweg, the right part Kardinaal Mercierlaan. You take the latter and keep on walking until you reach the Kantineplein. There you turn right. The first building on the right is the Department of Electrical Engineering.

Getting to Leuven by train: Leuven is well situated in the Belgium train system. Hence, you have trains going to Leuven every half hour or every hour, depending from where you come. Notice that Belgium is a bilingual country, and depending on the part of the country you are in, names of places change. The French name of Leuven is Louvain. So in the French speaking part, you have to catch a train to Louvain (not Louvain-la-neuve!) instead of Leuven.

The German railway company provides a user-friendly search page in English, French, Italian, and German. The search page knows about Belgian train connections and is far more user-friendly than the Belgian railway site.

Both Luik/Liège/Lüttich and Brussels are reachable by ICE and Thalys. In either city, you can take an IC train directly to Leuven/Louvain.

Brussels has a direct Eurostar connection to London.

Getting to Leuven by plane+train: Many airlines fly to Brussels International Airport in Zaventem. From the airport, you can take a direct train to Leuven for approximately 5 €. For comparison, a taxi costs approximately 50-60 € (90 after midnight).

As an alternative, Ryanair has flights to the Charleroi airport. From the airport, you can take the coach bus to Brussels (around 11 €, goes to Brussels-Midi/Brussels-Zuid), and then a train from Brussels-Midi/Brussels-Zuid to Leuven (around 5 €). For comparison, a taxi will cost you around 100-120 €.

## Driving directions

Driving from Leuven to the ESAT building: In general, going by car is a bad idea in Leuven. Hence, only use a car after you are absolutely sure that your hotel has parking and that you do not have to navigate through too many one-way streets to go there.

However, if you do want to use a car, you need to get on the ring and drive until Naamsepoort. Here you go out-bound, choose the right lane (Kardinaal Mercierlaan), and continue by car until Kantineplein. You turn right, follow the street until the stream, and then turn right at the parking lot. Good luck finding a free spot to park your car!

Driving from Brussels to Leuven and the ESAT building: Take the outer ring and go to E40, direction Leuven/Louvain and continue until E314. Take E314 and use the first exit on E314 (no. 15). Turn right at the second traffic lights (direction Campus Arenberg, this is the Celestijnenlaan). Drive on for about 500 m, until the bridge over the river Dijle. Just past the bridge, on the left, you can drive into the Arenberg park. Continue on the road parallel to the river until past the Arenberg castle. About 50 m downstream from the castle a public parking lot is available. The building towering above the parking lot is the Department of Electrical Engineering.

Driving from Aachen/Eindhoven/Hasselt to Leuven and the ESAT building: Take the highway E314 (Aachen - Leuven). Take the exit "Leuven" (no. 15). This is the last exit before the E40. Turn right at the second traffic lights (direction Campus Arenberg, this is the Celestijnenlaan). Drive on for about 500 m, until the bridge over the river Dijle. Just past the bridge, on the left, you can drive into the Arenberg park. Continue on the road parallel to the river until past the Arenberg castle. About 50 m downstream from the castle a public parking lot is available. The building towering above the parking lot is the Department of Electrical Engineering.

## Maps

There is a separate page of maps and directions.

## Contact

Submissions (PDF, 3 April 2006, at most 20 pages): contributed at postquantum.cr.yp.to.

Slides (PDF, at least two days before talk): pdfslides at postquantum.cr.yp.to.

Questions about Leuven: local at postquantum.cr.yp.to.

Other questions about PQCrypto 2006: questions at postquantum.cr.yp.to.

## Version

This is version 2006.10.30 of the PQCrypto 2006 web page.