Advances in Cryptology ― CRYPTO ’94: 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21–25, 1994. Proceedings (Lecture Notes in Computer Science, 839)

The CRYPTO ’94 conference is sponsored by the International Association for Cryptologic Research (IACR), in co-operation with the IEEE Computer Society Technical Committee on Security and Privacy. It has taken place at the Univ- sity of California, Santa Barbara, from August 21-25,1994. This is the fourteenth annual CRYPTO conference, all of which have been held at UCSB. This is the first time that proceedings are available at the conference. The General Chair, Jimmy R. Upton has been responsible for local organization, registration, etc. There were 114 submitted papers which were considered by the Program Committee. Of these, 1 was withdrawn and 38 were selected for the proce- ings. There are also 3 invited talks. Two of these are on aspects of cryptog- phy in the commercial world. The one on hardware aspects will be presented by David Maher (AT&T), the one on software aspects by Joseph Pato (Hewlett- Packard). There will also be a panel discussion on “Securing an Electronic World: Are We Ready?” The panel members will be: Ross Anderson, Bob Blakley, Matt Blaze, George Davida, Yvo Desmedt (moderator), Whitfield Diffie, Joan Feig- baum, Blake Greenlee, Martin Hellman, David Maher, Miles Smid. The topic of the panel will be introduced by the invited talk of Whitfield Diffie on ”Securing the Information Highway. ” These proceedings contain revised versions of the 38 contributed talks. Each i paper was sent to at least 3 members of the program committee for comments. front-matter Lecture Notes in Computer Science Advances in Cryptology-CRYPTO '94 PREFACE CRYPTO '94 CONTENTS fulltext Introduction Preliminaries Principle of the New Attack Algorithm for breaking 16-round DES (I) Data Counting Phase Key Counting Phase Algorithm for breaking l6-rou11d DES (11) Exhaustive Search Phase Success Rate and Complexity The Computer Experiment Concluding Remarks References fulltext_001 Introduction Linear Cryptanalysis Notations and Preliminaries Principle Implementation Techniques Algorithm 1 (Counter Technique) Linear Approximation of FEAL What are the Problems Linear Expressions of F-function Linear Expressions of Reduced Round FEAL Algorithm 2 (Search Algorithm of 7-Round Linear Expression) Discussion Attack Strategy Comparison with DES Experimentation Results Concluding Remarks References fulltext_002 Summary Notation Review of Differential and Linear Cryptanalysis Differential Cryptanalysis Linear Cryptanalysis Differential-Linear Cryptanalysis Structures Additional Bits of Key Work in Progress References fulltext_003 Introduction Linear Cryptanalysis Multiple Linear Approximations Analysis of Algorithm 1M Algorithm LM Experimental Results Coiifiriiiing the assumptions and Alyorathm IM Coiifiriiiiiig Algo~ilhin 2M Effectiveness and Extensions Implications Conclusions References A Proof of Lemmas 1 and 2 Proof of Lemma 1 Proof of Lemma 2 fulltext_004 Introduction A Design Strategy. Graph-theoretic Issues The General Construction The Choice of SLZ. On the Difficulty of Finding Collisions. A Specific Hash Function The Set of Hashcodes Protection Against Local Modifications Protection Against Density Attacks Concluding Remarks References fulltext_005 Introduction Current Design Methods of Curves [Koblitz’s algorithm] [Atkin, Morain’s algorithm] Design of Curves with Controlled Lower Boundary of Extension Degree against Reduction Attack Algorithm] [Example] References fulltext_006 Introduction Motivation Discrete Logarithms in Real-quadratic Orders Computing Powers Cryptographic Applications of EXP References fulltext_007 Introduction Theoretical Results Definitions Equivalence of Designated Confirmer Signature and Publie-Key Enceryption Practical Constructions Basic Protocol Example Based on Schnorr Example Based on the Extended Fiat-Shamir Conclusion Acknowledgments References fulltext_008 Introduction One-time signature schemes based on directed acyclic graphs Optimal graphs and signature schemes Concluding remarks Acknowledgements References fulltext_009 Introduction Bounded Life-span Signatures Initialization of the System First Step Second Step The Scheme The Underlying Guillou-Quisquater Zero-Knowledge Proof The Scheme Analysis and Remarks What Happens if a Signature is Replayed ? Refreshment Delegation Scheme General Remarks Applications Pre-payment Cards Electronic Cash Pay-TV Conclusion Acknowledgments References fulltext_010 Introduction Review of Previous Work : BGMW Method The Proposed Method Speeding up Identification and Signature Verifications Parallel Processing Conclusion References fulltext_011 Introduction Principles of multiplication in parallel Implementation details Conclusions References fulltext_012 Introduction Turbulence in Disk Drives Converting Access-Times to Random Numbers Statistical Analysis References fulltext_013 Introduction The Gemmell and Naor protocol An impersonation attack A substitution attack Example Conclusion Acknowledge 111 e nt s References fulltext_014 Introduction Hash Functions and Message Authentication Hash Functions Message Authentication Constructions Cryptographic CRC LFSR-based Toeplitz References fulltext_015 Introduction Preliminaries Notation Authentication code (A-code) Basic results on A-code New bound for Az-code Authentication code with arbitration (Az-code) Johansson's bound Generalization of basic results on A-code New bound Proof Construction of Az-code Further work References fulltext_016 Introduction The Models The First Model The Second Model The Equivalence of the Two Models Sharing Two and Three Secrets The Case of Two Secrets The Case of Three Secrets Bounds on the Size of the Shares Multi-Secret Schemes for Threshold Structures References fulltext_017 The Underlying Problem Key Generation A Three Pass Identification Protocol A Five Pass Identification Protocol Security of the Scheme Performances of the Scheme. An Additive Variant Conclusion Acknowledgements References fulltext_018 Introduction Related Work Proofs of Knowledge An Example Secret Sharing Main Result Application to Identification and Signatures Open Problems References fulltext_019 Introduction Preliminaries Examples Opaque/Transparent Bit Commitments Transparent/Opaque Bit Commitments Concluding Remarks References fulltext_020 Introduction The Fiat-Shamir scheme Description Too short (or ill-chosen) hash-values decrease the level of security The level of security of the h-variant The Schnorr scheme Description Too short hash-values decrease the level of security The level of security of the h-variant An interesting optimization The Stern identification scheme Description Too short hash-values decrease the level of security The level of security The Shamir identification scheme Description Too short hash-values decrease the level of security The level of security Conclusion References fulltext_021 Introduction A wide range of applications Problems considered in this absitract Incremental collision-free hashing Incremental digital signatures Practical issues An interesting open question Preliminaries Incremental collision-free hashing Families of hash functions Incrementality Collision-freeness An incremental hash family Incremental Signing Signature schemes Incrementality Basic security Incremental signature schemes achieving basic security Security against substitution attacks A successful substitution attack Work in progress Acknowledgments References fulltext_022 Introduction Related Work The Scheme Outline Detailed Description Computational Requirements: Remarks on Implementation Security of the Scheme Application to Signing Faxed Documents When the Receiver is a CFAX 5.2 The Procedure for CFAX to FAX References fulltext_023 Introduction Orthogonal Arrays Bounds Based on Linear Programming Explicit Bounds Optimal Resilient Functions Related Results Acknowledgements References fulltext_024 Introduction An Examplo Definitions Construction of Traceability Schemes A Simple Sctienie An Open Two Level Schenie A Secret One Level Scheiiic Lower Bounds Acknowledginents References fulltext_025 Introduction Computing discrete logarithms and breaking the Diffie-Hellman protocol Towards an equivalence proof for all groups Concluding remarks Acknowledgment References fulltext_026 Introduction Outline of the Algorithm Optinial Trial Division and Run Time Analysis Analysis of the Algorithm Cryptographic Security and Related Topics Performance Conclusions Acknowledgement References fulltext_027 Introduction The NIB-TAS Scheme Public information common for all entities Public information for a single entity Center Secrets common for all entities Individual secrets kept in center Individual secrets distributed to each entity Key Sharing Algorithm The Attack Example References fulltext_028 In t r o duct i o 11 Cryptanalysis of the Yacobi System The Yacobi System Cryptanalysis of the Yacobi System The Triangle Attack Hiding the Attack Cryptanalysis of Other Key Distribution Systems The Goss System The Attack The Guiither System The Attack COMSET (the Key Exchange Version) The Attack Repairing the Systeiiis Conclusion Acknowledgements References fulltext_029 Introduction Coiitiiiuous Tiine Chaos Synchronization in Chaotic Dynamical Systems Cryptosystenis based on Remote Chaos Replication Cryptanalysis of Cryptosystems based on Remote Chaos Replication Conclusions Acknowledgements Refer e iic es fulltext_030 Introduction Period and Linear Complexity of Sequences The Discrete Fourier Transform (DFT) Definition of the DFT Properties of the DFT The Shifting Property The Corivoliition Property The Conjugacy Constraints Property Blahut's Theorem PN-Sequences and their linearized polyno- mials-mials Second Order Nonlinear Filterings of PN-sequencessequences Conclusion References fulltext_031 Introduction The problem: Is the CBC MAC secure? Our approach Main result Extensions and corollaries History and related work Discussion and open questions Preliminaries The CBC Lemma: Information-theoretic case Statement Proof The CBC Lemma: The computational case Length Variability From PRFs to MACs Acknowledgments References fulltext_032 Description of Khufu Differential properties used in our attack An attack of the 16-round Khufii A k ii ow 1 e d genie lit s Conclusion Refer en ces fulltext_033 Introduction One-way function of the MAP MAP Algorithm Function S-BOX Function f Proposed Ciphertext Only Attack Outline of Attack Simplification of the MAP Algorithm Calculation of plaintext Example of computation Concluding Remarks References fulltext_034 Basic Definitions Nonexistence of Certain Quadratic S-boxes On Quadratie S-boxes with a UHODDT An Extension Columns of a UHODDT On Methods for Synthesizing S-boxes Chopping Permutations Linear Transforms Applied on Inputs Linear 'Ik.aiisforrns Applied on Outputs Connecting Permutations in Parallcl EIilarging Inputs or Reducing Outputs by Modulo Operations Hadamard Matrices Embodied in Difference Distribution Table Difference Distribution Tables arid Incidence Functions Hadamard Matrices in Difference Distribution Tables Chopping Quadratic Permutations Acknowledgments References fulltext_035 Introduction Preliminaries Upper Bound Lower Bounds Preliminaries A Lemma on Sensitivity Lower Bound on the Number of Rounds Lower Bounds on the Expected Number of rounds Weakly Correct Protocols References fulltext_036 Introduction Techniques Used Comparison to Related Work The Basic Scheme Preliminaries and Initial Preparation The Election Procedure Proving x1 + x2 E (1, -1) Many Centers and Many Votes Proving X(’) + X(’) + - - - + X(”) = A + B Proving Equations Simultaneously Efficiency Communication Cost Computation Cost for Voters Computation Cost for Verifying Other Voters Efficiency Comparisons with Previous Work Acknowledgments References fulltext_037 Introduction Reconstructability and its Application to Secure Sign-On Related Works Definitions The Protocol Analysis Insecure Links On the Application to Secure Sign-On Conclusions and Open Problems Acknowledgments References Appendix A: An alternative definition of PP back-matter Author Index "This volume constitutes the proceedings of CRYPTO '94, the 14th International Cryptology Conference, held at Santa Barbara, CA, USA in August 1994 under the sponsorship of the International Association for Cryptologic Research (IACR). The proceedings contains revised versions of the 38 papers selected for presentation at the conference from a total of 114 submissions. All aspects of cryptologic research and advanced applications are addressed; in particular there are sections on block ciphers, signatures, implementation and hardware aspects, authentication and secret sharing, zero-knowledge, combinatorics, number theory, cryptanalysis and protocol failures, and secure computations and protocols."--PUBLISHER'S WEBSITE