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
Information for speakers: Please send your PDF presentation by email to pdfslides at postquantum.cr.yp.to at least two days before your presentation, or bring it to the lecture room on a USB stick. Please contact your session chair before your session and check that your presentation can be displayed well on the COSIC laptop. The lecture room also has a blackboard. If you need any special equipment, please contact us beforehand.
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.
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:
Contributors:
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.
The registration fees are as follows:
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
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.
Some Internet cafes in Leuven:
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.
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.
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. |
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.
| 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.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. |
| 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. |
| 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) | |