Crypto '96, the Sixteenth Annual Crypto Conference, is sponsored by the International Association for Cryptologic Research (IACR), in cooperation with the IEEE Computer Society Technical Committee on Security and P- vacy and the Computer Science Department of the University of California at Santa Barbara (UCSB). It takes place at UCSB from August 18 to 22, 1996. The General Chair, Richard Graveman, is responsible for local organization and registration. The scientific program was organized by the 16-member Program C- mittee. We considered 115 papers. (An additional 15 submissions had to be summarily rejected because of lateness or major noncompliance with the c- ditions in the Call for Papers.) Of these, 30 were accepted for presentation. In addition, there will be five invited talks by Ernest Brickell. Andrew Clark, Whitfield Diffie, Ronald Rivest, and Cliff Stoll. A Rump Session will be chaired by Stuart Haber. These proceedings contain the revised versions of the 30 contributed talks. least three com- The submitted version of each paper was examined by at mittee members and/or outside experts, and their comments were taken into account in the revisions. However, the authors (and not the committee) bear full responsibility for the content of their papers.

Hashing and Authentication I.- Keying Hash Functions for Message Authentication.- Universal Hashing and Multiple Authentication.- Universal Hash Functions from Exponential Sums over Finite Fields and Galois Rings.- New Systems.- Asymmetric Cryptography with a Hidden Monomial.- Anonymous Communication and Anonymous Cash.- Asymmetric Systems.- Weaknesses in Some Threshold Cryptosystems.- Hidden Collisions on DSS.- The Dark Side of "Black-Box" Cryptography or: Should We Trust Capstone?.- Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems.- Hard Bits.- All Bits in ax + b mod p are Hard.- Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes.- Signatures.- Security of 2t-Root Identification and Signatures.- Robust and Efficient Sharing of RSA Functions.- New Generation of Secure and Practical RSA-Based Signatures.- Zero Knowledge.- Proving Without Knowing: On Oblivious, Agnostic and Blindfolded Provers.- Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing.- Symmetric Systems.- Improved Differential Attacks on RC5.- Improving Implementable Meet-in-the-Middle Attacks by Orders of Magnitude.- More on Symmetric Systems.- Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES.- How to Protect DES Against Exhaustive Key Search.- Diffie-Hellman Oracle.- Diffie-Hellman Oracles.- Algorithms for Black-Box Fields and their Application to Cryptography.- Hashing and Authentication II.- Fast Hashing on the Pentium.- On Fast and Provably Secure Message Authentication Based on Universal Hashing.- Quantum Crypto.- Quantum Cryptography over Underground Optical Fibers.- Quantum Key Distribution and String Oblivious Transfer in Noisy Channels.- Stream Ciphers.- LinearComplexity of Periodic Sequences: A General Theory.- Generalization of Siegenthaler Inequality and Schnorr-Vaudenay Multipermutations.- Secret Sharing.- Trade-offs Between Communication and Storage in Unconditionally Secure Schemes for Broadcast Encryption and Interactive Key Distribution.- New Results on Visual Cryptography.