Advances in Cryptology ― CRYPTO ’96: 16th Annual International Cryptology Conference, Santa Barbara, California, USA, August 18–22, 1996, Proceedings (Lecture Notes in Computer Science (1109))

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. front-matter Advances in Cryptology-CRYPTO'96 Preface CRYPTO'96 Contents fulltext 1 Introduction 1.1 Authenticity and MACs 1.2 MACing with cryptographic hash functions 1.3 This work 1.4 A closer look 1.5 Related work 2 Basic Notions 3 The Nested Construction NMAC 4 HMAC: A fixed IV variant 5 Attacks and Comparison to other Proposals 6 Implementation considerations for HMAC Acknowledgments References fulltext_001 1 Introduction 2 Authentication Codes 3 Universal Hashing 3.1 Comparison of Authentication Codes 4 Counter-based Multiple Authentication 5 Multiple Authentication without Counters 6 Composition Constructions 7 Multiple Authentication without Counters 8 Summary Acknowledgements References fulltext_002 1 Introduction 2 Authentication codes and universal hash functions 3 Exponential sums over finite fields 4 Universal hash functions from exponential sums over finite fields 5 Exponential sums over Galois rings 6 Universal hash functions from exponential sums over Galois rings 7 Conclusions References fulltext_003 1 Introduction PART 1 : Description of the 1iicldr.n monomial schemes 2 “Dragon”: a new family of algorithms for asymmetriccryptography 3 The algorithm MIIP-3 4 Implementations and public key lengt 11s PART 2: Cryptanalysis results 5 Cryptanalysis of extended Matsumoto-Iniai Algorithms with small branches 6 Cryptanalysis of two compositions of C* algorithms 7 Cryptanalysis of the little Dragon Algorithm 8 Cryptanalysis of the Dragons of paragraph 2 9 Cryptanalysis of MIIP-3 10 Unclear cases PART 3: A candidate for 64 bits signatures andc o II c 1 1 1 s i o n 11 A candidate Dragon algorithm for extremelyshort signat iires 12 Conclusion Acknowledgments References fulltext_004 1 Introduction 1.1 The problem 1.2 A solution 1.3 Security 2 The Model 2.1 The Anonymous Communication Nctwork 2.2 Electronic Cash Protocols 3 The Protocol 3.1 Description 4 Conclusions and Open Problems 5 Acknowledgements References fulltext_005 1 Introduction 2 Undeniable Signatures 2.1 Chaum’s Undeniable Signature Scheme 2.2 Group Public Key Generation Phase 2.3 Signature Creation 2.4 Forging Signatures 3 Threshold Signatures 3.1 n-out-of-n Share Generation 3.2 k-out-of-n Share Generation 3.3 Non-anonymous Members 3.4 Preventing The Attack 4 Generalized Threshold Cryptosystem 4.1 Generalized Threshold Scheme 4.2 Access Structures 5 Conclusion References fulltext_006 1 Signatures based on discrete logarithm 2 Collision for DSS 3 The public parameters generation of DSS 4 On the g parameter 5 Conclusion References fulltext_007 1 Introduction 2 Definitions and Background Definition 1: Definition 2: Related Work 3 SETUP in RSA Key Generation 3.1 Security of PAP 4 An Application: Auto-Escrowing-Keys in Hardware 5 SETUPS in ElGamal, DSA, and Kerberos SETUP in ElGamal Key Generation SETUP in ElGamal Signature SchexnP SETUP in DSA: SETUP from subliminal channels SETUP in Kerberos Kerberos Table of Abbreviations 6 Conclusion Acknowledgement References fulltext_008 1 Introduction 2 Cryptanalysis of a Simple Modular Exponentiator 3 Error Correctioii 4 The General Attack 5 Simplifying the Attack 6 Experimental Results 7 Montgomery Multiplication and the CRT 8 Timing Cryptanalysis of DSS 9 Masking Timing Characteristics 10 Preventing the Attack 11 Further Work 12 Conclusions 13 Acknowledgements References fulltext_009 1. Introduction 2. Preliminaries 3. Previous Work 4. Proof Outline 5. Security of Non Leftmost Bits 5.1. Some Results on Uniform Distribution of Sequences. 5.2. Generalizing the Two-point Based Sampling. 5.3. Good Primes. 5.4. Finding Good Intervals and Shifts. 6. Security of the Leftmost Bits 7. Discussion and Open Problems 8. Acknowledgment References Appendix A. Proof Sketch to Lemma 5.5 fulltext_010 1 Introduction 2 Discovering a number given an MSB oracle 3 Main Results 3.1 Related schemes 4 Proofs 4.1 Proof of hardness of Diffie-Hellman MSB’s 4.2 Proofs for DH-Related Schemes 5 The case of a small generator 5.1 A variant of Diffie-Hellman and its bit security 6 Concluding Remarks Acknowledgments References fulltext_011 1 Introduction and Summary 2 0 ng- S chnorr ident ificat, ion 3 Passive impersonation attacks for m 2 t 4 Passive impersonation attacks for m < t 5 Security of Ong-Schnorr signatures 6 Ong-Schnorr ID is secure against active inipersoiiatiori References Erra turn fulltext_012 1 Introduction 2 Our results 3 Preliminaries 3.1 Threshold Sharing of RSA functions 3.2 Notation 4 Non-Interactive Robust Threshold RSA 4.1 Extensions of Information Checking 4.2 Generation of Verification Data (Dealing Phase) 4.3 Partial Signatures Veritication (Signature Phase) 5 Interactive Robust Threshold RSA 5.1 Generation of Verification Data (Dealing Phase) 5.2 Verification of Partial Signatures (Signature Phase) 6 Conclusions and Further Applications References fulltext_013 1 Introduction 2 Basic Ideas 3 Description of the Scheme 4 Generating the List of Primes L 5 Performance of the Scheme 6 Proof of Security 7 Optimizations References fulltext_014 1 Introduction 2 Definitions 2.1 Uses of the above kiiowledge restrictioiis 3 sOblivious and Agnostic Decisioii Proofs for Undeniable Signature 3.1 Uiideniable Sigiiatures: a short Expos6 3.2 The Oblivious Protocol 3.3 The Agnostic Protocol 4 A c kn ow 1 e d g em e 11 t s References fulltext_015 1 Introduction 1.1 Previous Work 1.2 Our result 1.3 A False Solution 1.4 Our Coiistruction in a Nutshell 2 Preliminaries 2.1 Universal Hashing 2.2 Statistical Difference 2.3 Negligible Functioris 2.4 Feasible Algorithms 2.5 Collision-F'rac Hashing 2.6 Comniitrrient Schemes 3 The First Scheme 3.1 Analysis of the Scheme 4 Getting an O(k)-Bit Commitment String 5 Open Problems References fulltext_016 1 Introduction 2 Differential Attacks 3 Our Differential Attacks 3.1 A Basic Key Detection Algoritlirri 3.2 Extensions of the key detcction algorithm 3.3 Improved Differential Attack 3.4 RC5 with 64 bit words 4 Differentially Weak Keys 5 Concluding remarks References fulltext_017 1. Introduction 2. Forniulating Meet-in-the-Middle Attacks as Collision Search Problems 3. Solving the Collision Search Problem 4. Comparison to Previous Techniques 5. Conclusion Acknowledgments References fulltext_018 1 Introduction 2 Attacks 011 Key Schedules 2.1 Meet-in-the-Middle Attacks 2.2 Linear Factors 2.3 Weak Keys 2.4 Detectable Key Classes 2.5 Simple Relations and Equivalent Keys 2.6 Attacks on One-Wayiiess 3 Introduction to Related-Key Cryptanalysis 3.1 Overview of General Techniques 3.2 Motivation and Impact 3.3 Attacks on Key Exchange Protocols 3.4 Attacks on Hash Functions 4 New Related-Key Attacks 4.1 GOST 4.2 IDEA 4.3 SAFER K-64 4.4 DES with Independent Round Siibkcys 4.5 G-DES 4.6 Three-Kcy Triple-DES 4.7 ECB+OFB 5 Designing Strong Key Schedules 6 Conclusions References fulltext_019 1 Introduction 1.1 Our model 1.2 Our main result 1.3 Related work 1.4 Discussion 1.5 Outline of the paper 2 Preliminaries 3 Security of the DESX Construction 4 Discussion 5 Our Bound is Tight 5.1 Preliminaries 5.2 The basic attack 5.3 Analysis of the attack 6 Open Problems and Conclusions Acknowledgments References fulltext_020 1 Introduction 2 Various Types of Diffie-Hellman Oracles and Their Equivalence 2.1 E-DH-Oracles 2.2 The Squaring Oracle 2.3 The Security of Subgroups 3 Conditions for Equivalence Between the Diffie-Hellman Problem and Computing Discrete Logarithms 3.1 Computing with Implicit Representations 3.2 Auxiliary Groups 3.3 Elliptic Curves as Auxiliary Groups 3.4 Subgroups of Finite Fields as Auxiliary Groups 3.5 The Main Equivalence Result 4 Construction of Secure Diffie-Hellman Groups 5 Concluding Remarks Acknowledgments References fulltext_021 1 Introduction 2 Black-box fields 3 Applications 3.1 Algebraically homomorphic encryption schemes 3.2 The Difie-Hellman protocol 4 Algorithms for black-box fields 4.1 A sub-exponential algorithm for BBFP 4.2 A two step algorithm 5 Security of the Diffie-Hellman protocol 6 Black-box fields in characteristic 0 7 Conclusions and open problems Acknowledgments References fulltext_022 1 Introduction 2 Comparative description of the MD4-family 3 Pentium architecture overview 4 Pairing in MD4-like hash functions 5 Performance figures 6 Effects of data cacheing and representation 7 Conclusion References fulltext_023 1 Introduction 2 Using a Pseudo-Random Family of Permutations 3 Using a Random Tag 4 Three Types of Hash F'unctioiis 5 The Evaluation Hash 6 The Division Hash 6.1 Hash Function Application 6.2 Generating an Irrcducihle Polynomial 7 The Generalized Division Hash 7.1 Hash Function Application 7.2 Generating an Irreducible Polynomial 8 Conclusion Appendix A: Proof of Theorems 2 and 3 Appendix B: Proof of Theorem 4 References fulltext_024 1. Introduction 2. Quantum cryptography: theory 3. Quantum cryptography: experimental realization 4. Summary References fulltext_025 1 Introduction and Brief History 2 Related results 3 Some algebra 6 Bob’s view 7 The small distance property 8 Using the small distance property 9 The density matrices 10 Proving the small distance property References fulltext_026 1 Introductioii 2 Linear Complexity of Periodic Sequences 3 Hasse Derivatives and Hasse Matrices 4 A Generalized Discrete Fourier Transform (GDFT) 5 Applicatioiis of the Generalized DFT 5.1 The Games-Chan Algorithm arid its gerir:ralization 5.2 Application to Hadainard prodiicts of seqiiences 6 Acknowledgernent References fulltext_027 1 Introduction 2 Correlation immune functions and orthogonal arrays 3 Algebraic normal form and nonlinear order of correlation immune functions over any finite field 4 Construction of t-resilient functions with optimal nonlinearity over any finite field 4.1 Combining LFSRS 4.2 Construction of resilient functions with optimal non-linearity 5 Algebraic Normal Form of q-ary functions which are correlation immune with respect to F: 6 Application to the design of cryptographic primitives References fulltext_028 1 Introduction 2 Mathematical Models 2.1 Key Predistribution Schemes 2.2 Broadcast Encryption Schemes 3 The Blundo ct a1 KPS and its Properties 4 One-time Broadcast Encryption Schemes 4.1 A Construction using Resolvable Designs 4.2 Security of the Scherne 5 Entropy Bounds for OTBES 5.1 Lower Bounds on Entropy 5.2 The Entropy of our Schemes 6 The Model for Interactive Key Distribution Schemes 7 Constructions for Key Distribution Schemes 8 The Entropy of our Key Distribution Schemes 9 Comments Acknowledgments References fulltext_029 1 Introduction 2 The Basic Model 3 Basic Results 4 A New Construction Principle for k out of n Schemes 5 Structural Results 6 New Bounds on the Values of a and m 7 S-Extended n out of n Schemes Acknowledgements References Appendix back-matter Author Index "This book constitutes the refereed proceedings of the 16th Annual International Cryptology Conference, CRYPTO '96, held in Santa Barbara, California, USA, in August 1996 under the sponsorship of the International Association for Cryptologic Research (IACR). The 30 revised full papers presented in the volume were selected from a total of 130 submissions; they are organized in topical sections on hashing and authentication, new systems, cryptoanalysis, hard bits, signatures, zero knowledge, symmetric systems, Diffie-Hellman oracle, quantum cryptography, stream ciphers, and secret sharing. All in all, this book is a current report on the state-of-the-art in the field."--PUBLISHER'S WEBSITE