Advances in Cryptology - ASIACRYPT 2000

ASIACRYPT 2000 was the sixth annual ASIACRYPT conference. It was sp- sored by the International Association for Cryptologic Research (IACR) in - operation with the Institute of Electronics, Information, and Communication Engineers (IEICE). The ?rst conference with the name ASIACRYPT took place in 1991, and the series of ASIACRYPT conferences were held in 1994, 1996, 1998, and 1999, in cooperation with IACR. ASIACRYPT 2000 was the ?rst conference in the series to be sponsored by IACR. The conference received 140 submissions (1 submission was withdrawn by the authors later), and the program committee selected 45 of these for presen- tion. Extended abstracts of the revised versions of these papers are included in these proceedings. The program also included two invited lectures by Thomas Berson (Cryptography Everywhere: IACR Distinguished Lecture) and Hideki Imai (CRYPTREC Project - Cryptographic Evaluation Project for the Japanese Electronic Government). Abstracts of these talks are included in these proce- ings. The conference program also included its traditional "rump session" of short, informal or impromptu presentations, kindly chaired by Moti Yung. Those p- sentations are not re?ected in these proceedings. The selection of the program was a challenging task as many high quality submissions were received. The program committee worked very hard to evaluate the papers with respect to quality, originality, and relevance to cryptography. I am extremely grateful to the program committee members for their en- mous investment of time and e?ort in the di?cult and delicate process of review and selection.

Includes supplementary material: sn.pub/extras

Cryptanalysis I.- Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers.- Cryptanalysis of the RSA Schemes with Short Secret Exponent from Asiacrypt '99.- Why Textbook ElGamal and RSA Encryption Are Insecure.- Cryptanalysis of the TTM Cryptosystem.- Attacking and Repairing Batch Verification Schemes.- IACR Distinguished Lecture.- Cryptography Everywhere.- Digital Signatures.- Security of Signed ElGamal Encryption.- From Fixed-Length to Arbitrary-Length RSA Padding Schemes.- Towards Signature-Only Signature Schemes.- A New Forward-Secure Digital Signature Scheme.- Unconditionally Secure Digital Signature Schemes Admitting Transferability.- Protocols I.- Efficient Secure Multi-party Computation.- Mix and Match: Secure Function Evaluation via Ciphertexts.- A Length-Invariant Hybrid Mix.- Attack for Flash MIX.- Distributed Oblivious Transfer.- Number Theoretic Algorithms.- Key Improvements to XTR.- Security of Cryptosystems Based on Class Groups of Imaginary Quadratic Orders.- Weil Descent of Elliptic Curves over Finite Fields of Characteristic Three.- Construction of Hyperelliptic Curves with CM and Its Application to Cryptosystems.- Symmetric-Key Schemes I.- Provable Security for the Skipjack-like Structure against Differential Cryptanalysis and Linear Cryptanalysis.- On the Pseudorandomness of Top-Level Schemes of Block Ciphers.- Exploiting Multiples of the Connection Polynomial in Word-Oriented Stream Ciphers.- Encode-Then-Encipher Encryption: How to Exploit Nonces or Redundancy in Plaintexts for Efficient Cryptography.- Protocols II.- Verifiable Encryption, Group Encryption, and Their Applications to Separable Group Signatures and Signature Sharing Schemes.- Addition of El Gamal Plaintexts.- Improved Methods to Perform Threshold RSA.- Commital Deniable Proofsand Electronic Campaign Finance.- Provably Secure Metering Scheme.- Invited Lecture.- CRYPTREC Project Cryptographic Evaluation Project for the Japanese Electronic Government.- Fingerprinting.- Anonymous Fingerprinting with Direct Non-repudiation.- Efficient Anonymous Fingerprinting with Group Signatures.- Zero-Knowledge and Provable Security.- Increasing the Power of the Dealer in Non-interactive Zero-Knowledge Proof Systems.- Zero-Knowledge and Code Obfuscation.- A Note on Security Proofs in the Generic Model.- Boolean Functions.- On Relationships among Avalanche, Nonlinearity, and Correlation Immunity.- Cryptanalysis II.- Cryptanalysis of the Yi-Lam Hash.- Power Analysis, What Is Now Possible....- Pseudorandomness.- Concrete Security Characterizations of PRFs and PRPs: Reductions and Applications.- Symmetric-Key Schemes II.- The Security of Chaffing and Winnowing.- Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm.- Increasing the Lifetime of a Key: A Comparative Analysis of the Security of Re-keying Techniques.- Proofs of Security for the Unix Password Hashing Algorithm.- Public-Key Encryption and Key Distribution.- Trapdooring Discrete Logarithms on Elliptic Curves over Rings.- Strengthening McEliece Cryptosystem.- Password-Authenticated Key Exchange Based on RSA.- Round-Efficient Conference Key Agreement Protocols with Provable Security.