Advances in Cryptology – EUROCRYPT ’92: Workshop on the Theory and Application of Cryptographic Techniques, Balatonfüred, Hungary, May 24–28, 1992 Proceedings (Lecture Notes in Computer Science, 658)

"A series of workshops devoted to modern cryptography began in Santa Barbara, California in 1981 and was followed in 1982 by a European counterpart in Burg Feuerstein, Germany. The series has been maintained with summer meetings in Santa Barbara and spring meetings somewhere in Europe. At the 1983 meeting in Santa Barbara the International Association for Cryptologic Research was launched and it now sponsors all the meetings of the series. This volume presents the proceedings of Eurocrypt '92, held in Hungary. The papers are organized into the following parts: Secret sharing, Hash functions, Block ciphers, Stream ciphers, Public key I, Factoring, Trapdoor primes and moduli (panel report), Public key II, Pseudo-random permutation generators, Complexity theory and cryptography I, Zero-knowledge, Digital knowledge and electronic cash, Complexity theory andcryptography II, Applications, and selected papers from the rump session. Following the tradition of the series, the authors produced full papers after the meeting, in some cases with revisions."--PUBLISHER'S WEBSITE front-matter Advances in Cryptology - Preface Contents fulltext Introduction Secret Sharing Schemes Basic Results Graph Decomposition Constructions Optimal Information Rates A Linear Programming Probleiii Illformation Rate for Trees Optimal Average Information Rates A Linear Programming Problem Vertex Covers and Secret Sharing Schemes Average Information Rate for Paths and Cycles Average Information Rate for Dees The Connected Graphs on at Most Five Vertices Acknowledgements References fulltext_001 Introduction Background and notation Structure of shares Classification A general homomorphic sharing scheine Conclusion REFERENCES fulltext_002 The FFT Hashing Function The FFT Hashing Function Notations Preliminary remarks Construction or two colliding messages Construction of a partial collision Construction of a full collision wing a partial collision Implementation details Conclusions Acknowledgements References fulltext_003 The hash algorithm Provable properties of the function g fulltext_004 Introduction Iterated hash functions and attacks Hash round functions based on block ciphers Some rn-bit hash round functions Construction of 2m-bit hash round functions A principle for evaluating hash round functions and four attacks on three 2m-bit hash round functions Complexity of known attacks on 2m-bit hash functions Proposed schemes for block ciphers with k = 2m Acknowledgements References fulltext_005 Introduction The MD5 Message Digest Algorithm Overall Structure Block Processing The Cryptanalytic Problem Differential Cryptanalysis of the Add Function Differential Cryptanalysis of the Circular Shift Differential Cryptanalysis of the Step Feedback Functions Cryptanalysis of the Rounds References fulltext_006 Intrwductioii Preliminaries Principle of the attack Attack of FEAL-4 Attack of FEAL-6 Attack of FEAL-7 Attack of FEAL-8 Conclusion Acknowledgement References fulltext_007 Introductioii The nonlinearity ineasure Quadratic functions Let The coiistructioii REFERENCES fulltext_008 Introduction Notations 3 The 3-Transitivity of the Group G Proof of the main Theorem Conclusions Acknowledgement References fulltext_009 INTRODUCTION GENERAL BINARY COMBINER WITH WEHORY 111. CORRELATION PROPERTY OF A GENERAL COHBINER WITH HEHORY LINEAR APPROXIHATION OF A GENERAL BINARY COHBINER TITH HEHORY CORRELATION ATTACK CONCLUSION REFERENCES fulltext_010 INTRODUCTION PROBLEW STATEHENT SELF-COHPOSITION OF THE BAYES ERROR PROBABILITY CONVERGENCE ANALYSIS ALTERNATIVE APPROACH TO THE CONVERGENCE AHALYSIS fulltext_011 Introduction Computing the span of a sequence Previous work Pattern-matching algorithms Properties of feedback polynomials Experimental results Conclusion ACKNOWLEDGEMENTS References fulltext_012 Introduction The Modd Overview over Protocols and Attacks Other Security Considerations The RSA Protocols MAS1 WAS2 other variants Passive Attacks Passive Attack on MAS1 Passive Attack on RSAS2 Passive Attacks on Other Variants Active Attacks Description of Attacks Discussion of Countermeasures Attacks on ReIated Protocols Conclusion Acknowledgement References fulltext_013 Introduction Elliptic Curve Cryptosystems Pollard p-Method Field Arithmetic Normal Basis Representation Polynomial Basis Representation Timings Implementation of an Elliptic Curve Cryptosystem Conclusions References fulltext_014 Introduction Exponcntiation and Addition Chains Known methods for the application of addition chains Effects on operation count and memory demand Opcration count and memory requirements of different exponentiation methodsOpcration count and memory requirements of different exponentiation Conclusion References fulltext_015 Introduction The hardware Elliptic curve method Block-wise modular arithmetic A second implementation and resuIts References fulltext_016 Introduction Rainer A. Rueppel Arjen K. Lenstra Miles E. Smid DSA 'Trapdooi' Kevin S. McCurley Yvo Desmedt Andrew Odlyzko Progress in factoring and discrete logarithms Trapdoor primes and moduli Peter Landrock fulltext_017 Introduction Basic strategies Other number systems Parallelizing the algorithm References fulltext_018 Introduction Batch-RSA Batch Diffie-Hellman Security System Considerations for Batch-Diffie-Hellman Why not Batch-RSA? Conclusions Acknowledgement References fulltext_019 Introduction An Efficient Implementation for RSA Scheme An Efficient Modular Multiplication Circuit Circuit Scale and Processing Speed Systolic Arrays for RSA Scheme An Approach to Design Systolic Arrays for Modular Multiplica- tion A Systolic Array for Modular Multiplication arid Compensating Carry Bits Circuit Scale and Processing Speetl Chip Implementation Using the Systolic-Array Approach Another Utility of the Systolic- Array Approacli Conclusion References Appendix fulltext_020 Introduction Terminology Luby-Rackoff Pseudorandom Permutation Random Functions and Locally Random Func- t ions Complexity-theoretic Applications of Locally Concluding Discussion Acknowledgment References fulltext_021 Introduction Notations Definition of the “spreading” of a permutation 5 4 A “basic property” of $(f, f, f o o f) $(f, f, f o o f) is pseudorandom, if C is well chosen Reinarks A basic “property” of $(f, f, f, f o ( o f) @(f, f, f, f o c o f ) is super pseudorandom, if ( is well Generators with two functions Conclusion Refer e 11 c e s fulltext_022 Introduction Notations Preliminaries Construction of Super Pseudorandom Permutations Super Pseudorandonmess of $(h, 1, f, h, 1, f) Super Pseudorandomness of $(f2, 1, f, f2, 1, f) Conclusions and Open Problems ACKNOWLEDGMENT References fulltext_023 Introduction Oblivious Transfer: the Tradit ioiial Approach Oblivious Transfer in an Ideal World Oblivious Transfer: Background Notes on Cryptography An Early Iinpleineiitatioii Breaking an Oblivious Transfer Protocol Why OT Has Always Been Defined Incorrectly Defining and Proving Security Finding and Fixing Security Holes How to Fix den Boer’s Protocol Yet Another Protocol Conclusion References fulltext_024 Introduction Uniform vs. non-uniform algorithms Security schemes Obtaining uniform results Bibliography fulltext_025 Introduction Definitions and proof techniques Background mechanics Security Proof techniques and now-provable folk theorems Achieving security against dynamic adversaries Open Questions References Appendix fulltext_026 Introduction Problems in Divertible Scenario Undeniable Signature Abuse of Undeniable Signature Discussion Divertible Scenario and Divert ible-freeness Secure Bit Commitment in Divertible Sce- nario Definition of Security An Application of Secure Bit Commitment Function Properties of Functions Naor's Bit Commitment is Secure against Di- vert ibility Naor's Bit Commitment Function Conclusion and Remarks Acknowledgments References fulltext_027 Introduction Notation and Definitions Non-Interactive Proof System for SAT PROVER’S ALGORITHM Perfect and Statistical Zero-Knowledge Arguments With Preprocessing The protocol by Shamir and Lapidot An Improvement Based on Hash Functions Perfect Zero-Knowledge Arguments in the Shared String Model Conclusion and Open Problems References fulltext_028 Introduction Probabilistic Turing Machines Probabilistic Circuits Indistinguishability The Main Theorems References fulltext_029 Introduction Fail-stop Signatures Notation Signature Scheme Acknowledgements References fulltext_030 Introduction Notation The Protocol and Problem under Consideration Algebraic Strategies A Special Case of Protocol 2 Generalizations References fulltext_031 Introduction The Model How to Transfer Electronic Money Unconditionally Untraceable Money Computationally Untraceable Money Applications to Secret Sharing Conclusion Acknowledgements References fulltext_032 Introduction and Summary Statistical Local Randomness Statistical Local Randomness Random Function Generators that Provide Statistical Local Randomness References fulltext_033 Introduction Preliminaries Main Result Related Open Problems Conclusion Acknowledgments References fulltext_034 Intro'duction Preliminaries The Oracle Factoring Algorithm Analysis of the Algorithm Acknowledgments References fulltext_035 Introduction The Problem Digital Audio and Bridging Previously Suggested Solutions The New Solution Tools Max-Bridging Secure-Sum and Secure-Max Calculations The Proposed System and Its Security A Concrete Design Open Problems Acknowledgements References fulltext_036 Introduction Improved Conference Key Distribution Schemes Shimbo and Kawamura’s Attacking Method Security of New Schemes Conclusion References fulltext_037 Introduction Rephrasing Shanks’ Method Applications Concluding Remarks Acknowledgement References fulltext_038 Acknowledgments References fulltext_039 Introduction Protocols with Controlable Security Bound Connections to Other Definitions of Security Discussion References fulltext_040 Introduction Fraud schemes Applications References fulltext_041 Introduction Probabilistic Constrained Edit Distance REFERENCES fulltext_042 Introduction A Novel Algorithm for Modular Exponentiation Systolic-Arrays for Montgomery's Modular Multiplication Array-B Array-C Conclusion RRfere nces fulltext_043 Abslract introduction A llardware Irepleiiienlation Throughput Calculations Sunimary References fulltext_044 ABSTRACT INTRODUCTION THE NEW FIAT-SHAMIR-LIKE PROTOCOL. THE NEW PROTOCOL CONCLUSION AND IMREMENTATION DETAILS. REFERENCES back-matter Author Index