International Association for Cryptologic Research
EUROCRYPT 2001
PREFACE by Birgit Pfitzman
May 6 -- 10, 2001, Innsbruck (Tyrol), Austria
Sponsored by the
International Association for Cryptologic Research (IACR)
in cooperation with the
Austrian Computer Society (OCG)
Reinhard Posch, Institute for Applied Information Processing and Communications (IAIK), Austria
Program Chair
Birgit Pfitzmann, Saarland University, Saarbrücken, Germany
| Josh Benaloh | Microsoft Research, USA |
| Carlo Blundo | Università di Salerno, Italy |
| Jan Camenisch | IBM Zürich Research Laboratory, Switzerland |
| Matt Franklin | UC Davis, USA |
| Shai Halevi | IBM T. J. Watson Research Center, USA |
| Martin Hirt | ETH Zürich, Switzerland |
| Thomas Johansson | Lund University, Sweden |
| Neal Koblitz | Univ. of Washington, USA |
| Hugo Krawcyk | Technion, Israel |
| Kaoru Kurosawa | Tokyo Institute of Technology, Japan |
| Arjen Lenstra | Citicorp, USA |
| Willi Meier | Fachhochschule Aargau, Switzerland |
| David Naccache | Gemplus, France |
| Kaisa Nyberg | Nokia, Finland |
| Torben Pryds Pedersen | Cryptomathic, Denmark |
| Guillaume Poupard | DCSSI Crypto Lab, France |
| Tal Rabin | IBM T. J. Watson Research Center, USA |
| Vincent Rijmen | K. U. Leuven, Belgium |
| Amit Sahai | Princeton University, USA |
| Kazue Sako | NEC, Japan |
| Louis Salvail | BRICS, University of Århus, Denmark |
| Claus-Peter Schnorr | University of Frankfurt, Germany |
| David Wagner | UC Berkeley, USA |
| Michael Waidner | IBM Zürich Research Laboratory, Switzerland |
Table of Contents
- Elliptic Curves
- A Memory Efficient Version of Satoh's Algorithm, page 1
by Frederik Vercauteren (K. U. Leuven, Belgium)
Bart Preneel (K. U. Leuven, Belgium)
Joos Vandewalle (K. U. Leuven, Belgium) - Finding Secure Curves with the Satoh-FGH Algorithm and an Early-Abort Strategy, page 14
by Mireille Fouquet (LIX, école polytechnique, France)
Pierrick Gaudry (LIX, école polytechnique, France)
Robert Harley (ArgoTech, France) - How Secure are Elliptic Curves over Composite Extension Fields?, page 30
by Nigel P. Smart (University of Bristol, UK)
- A Memory Efficient Version of Satoh's Algorithm, page 1
- Commitments
- Efficient and Non-Interactive Non-Malleable Commitment, page 40
by Giovanni Di Crescenzo (Telcordia Technologies Inc., USA)
Jonathan Katz (Telcordia Technologies Inc. and Columbia University, USA)
Rafail Ostrovsky (Telcordia Technologies Inc., USA)
Adam Smith (Massachusetts Institute of Technology, USA) - How to Convert the Flavor of a Quantum Bit Commitment, page 60
by Claude Crépeau (McGill University, Canada)
Frédéric Légaré (Zero-Knowledge Systems Inc., Canada)
Louis Salvail (BRICS, University of Århus, Denmark)
- Efficient and Non-Interactive Non-Malleable Commitment, page 40
- Anonymity
- Cryptographic Counters and Applications to Electronic Voting, page 78
by Jonathan Katz (Telcordia Technologies Inc. and Columbia University, USA)
Steven Myers (University of Toronto, Canada)
Rafail Ostrovsky (Telcordia Technologies Inc., USA) - An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation, page 93
by Jan Camenisch (IBM Zürich Research Laboratory, Switzerland)
Anna Lysyanskaya (Massachusetts Institute of Technology, USA) - Priced Oblivious Transfer: How to Sell Digital Goods, page 118
by Bill Aiello (AT&T Labs -- Research, USA)
Yuval Ishai (DIMACS and AT&T Labs -- Research, USA)
Omer Reingold (AT&T Labs -- Research, USA)
- Cryptographic Counters and Applications to Electronic Voting, page 78
- Signatures and Hash Functions
- A Secure Three-move Blind Signature Scheme for Polynomially Many Signatures, page 135
by Masayuki ABE (NTT Laboratories, Japan) - Practical Threshold RSA Signatures Without a Trusted Dealer,page 151
by Ivan Damgård (BRICS, University of Århus, Denmark)
Maciej Koprowski (BRICS, University of Århus, Denmark) - Hash Functions: From Merkle-Damgård to Shoup, page 165, by Ilya Mironov (Stanford University, USA)
- A Secure Three-move Blind Signature Scheme for Polynomially Many Signatures, page 135
- XTR and NTRU
- Key Recovery and Message Attacks on NTRU-Composite, page 181,
by Craig Gentry (DoCoMo Communications Laboratories Inc., USA) - Evidence that XTR is more Secure than Supersingular Elliptic Curve Cryptosystems, page 194,
by Eric R. Verheul (PricewaterhouseCoopers, The Netherlands) - NSS: An NTRU Lattice-Based Signature Scheme, page 210,
by Jeffrey Hoffstein (NTRU Cryptosystems Inc., USA)
Jill Pipher (NTRU Cryptosystems Inc., USA)
Joseph H. Silverman (NTRU Cryptosystems Inc., USA)
- Key Recovery and Message Attacks on NTRU-Composite, page 181,
- Assumptions
- The Bit Security of Paillier's Encryption Scheme and its Applications, page 228,
by Dario Catalano (University of Catania, Italy)
Rosario Gennaro (IBM T. J. Watson Research Center, USA)
Nick Howgrave-Graham (IBM T. J. Watson Research Center, USA) - Assumptions Related to Discrete Logarithms: Why Subtleties Make a Real Difference, page 243
by Ahmad-Reza Sadeghi (Saarland University, Germany)
Michael Steiner (Saarland University, Germany)
- The Bit Security of Paillier's Encryption Scheme and its Applications, page 228,
- Multiparty Protocols
- On Adaptive vs. Non-adaptive Security of Multiparty Protocols, page 261
by Ran Canetti (IBM T. J. Watson Research Center, USA)
Ivan Damgård (BRICS, University of Århus, Denmark)
Stefan Dziembowski (BRICS, University of Århus, Denmark)
Yuval Ishai (DIMACS and AT&T Labs -- Research, USA)
Tal Malkin (AT&T Labs -- Research, USA) - Multiparty Computation from Threshold Homomorphic Encryption, page 279
by Ronald Cramer (BRICS, University of Århus, Denmark)
Ivan Damgård (BRICS, University of Århus, Denmark)
Jesper B. Nielsen (BRICS, University of Århus, Denmark) - On Perfect and Adaptive Security in Exposure-Resilient Cryptography, page 299
by Yevgeniy Dodis (University of New York, USA)
Amit Sahai (Princeton University, USA)
Adam Smith (Massachusetts Institute of Technology, USA)
- On Adaptive vs. Non-adaptive Security of Multiparty Protocols, page 261
- Block Ciphers
- Cryptanalysis of Reduced-Round MISTY, page 323
by Ulrich Kühn (Dresdner Bank AG, Germany) - The Rectangle Attack -- Rectangling the Serpent, page 338
by Eli Biham (Technion, Israel)
Orr Dunkelman (Technion, Israel)
Nathan Keller (Technion, Israel)
- Cryptanalysis of Reduced-Round MISTY, page 323
- Primitives
- Efficient Amplification of the Security of Weak Pseudo-Random Function Generators, page 356
by Steven Myers (University of Toronto, Canada) - Min-Round Resettable Zero-Knowledge in the Public-Key Model, page 371
by Silvio Micali (Massachusetts Institute of Technology, USA)
Leonid Reyzin (Massachusetts Institute of Technology, USA)
- Efficient Amplification of the Security of Weak Pseudo-Random Function Generators, page 356
- Symmetric Ciphers
- Structural Cryptanalysis of SASAS, page 392
by Alex Biryukov (The Weizmann Institute, Israel)
Adi Shamir (The Weizmann Institute, Israel) - Hyper-Bent Functions, page 404
by Amr M. Youssef (University of Waterloo, Canada)
Guang Gong (University of Waterloo, Canada) - New Method for Upper Bounding the Maximum Average Linear Hull Probability for SPNs, page 418
by Liam Keliher (Queen's University at Kingston, Canada)
Henk Meijer (Queen's University at Kingston, Canada)
Stafford Tavares (Queen's University at Kingston, Canada)
- Structural Cryptanalysis of SASAS, page 392
- Key Exchange and Multicast
- Lower Bounds for Multicast Message Authentication, page 435
by Dan Boneh (Stanford University, USA)
Glenn Durfee (Stanford University, USA)
Matt Franklin (University of California, USA) - Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels, page 451
by Ran Canetti (IBM T. J. Watson Research Center, USA)
Hugo Krawczyk (Technion, Israel) - Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords, page 473
by Jonathan Katz (Telcordia Technologies Inc. and Columbia University, USA)
Rafail Ostrovsky (Telcordia Technologies Inc., USA)
Moti Yung (CertCo Inc., USA)
- Lower Bounds for Multicast Message Authentication, page 435
- Authentication and Identification
- Identification Protocols Secure Against Reset Attacks, page 493
by Mihir Bellare (University of California at San Diego, USA)
Marc Fischlin (University of Frankfurt, Germany)
Shafi Goldwasser (Massachusetts Institute of Technology, USA)
Silvio Micali (Massachusetts Institute of Technology, USA) - Does Encryption with Redundancy Provide Authenticity?, page 509
by Jee Hea An (University of California at San Diego, USA)
Mihir Bellare (University of California at San Diego, USA) - Encryption Modes with Almost Free Message Integrity, page 525
by Charanjit S. Jutla (IBM T. J. Watson Research Center, USA)
- Identification Protocols Secure Against Reset Attacks, page 493