Advances in Cryptology – EUROCRYPT ’95: International Conference on the Theory and Application of Cryptographic Techniques, Saint-Malo, France, May ... (Lecture Notes in Computer Science, 921)

EUROCRYPT '95. Sponsored by the International Association for Cryp- logic Research (IACR), in cooperation with the Centre Commun d'Etudes de T616vision et T61Qcommunications (CCETT), a workshop on the theory and - plications of cryptographic techniques takes place at the Palais du Grand Large, Saint Malo, France, May 21-25, 1995. The General Chair of EUROCRYPT '95 is Franqoise Scarabin. The Or- nization Committee was helped by Maryvonne Lahaie and her communication team. Moreover, the CCETT has generously provided the help of a young - glish lady, Miss Virginia Cooper, for the secretariat of both the Organization arid Program Committees. They all did an excellent job in preparing the conference. It is our pleasure to thank them for their essential work. IACR and EUROCRYPT. According to a very good suggestion expressed during CRYPTO '82, the Association was established at CRYPTO '83. Today, the Association has approximately 600 members and the mailing file managed by its Secretariat consists of more than 2 000 names. The main goal of the Association is the sponsoring of two annual conferences: CRYPTO, every summer at the University of California, Santa Barbara (UCSB), and EUROCRYPT, every spring in a different European country. Moreover, the Association edits quarterly the Journal of Cryptology (JoC). front-matter Lecture Notes in Computer Science Advances in Cryptology - EUROCRYPT '95 PREFACE EUROCRYPT '95 CONTENTS fulltext Introduction and Summary Basic concepts or efficient lattice reduction Pruning the enumeration Solving subset sum problems Attacks on the Chor-Rivest cryptosystem Attacks on Damgird’s knapsack hash function General subset sum problems References fulltext_001 Introduction Rcsiilts Finite Markov Chaiiis Differentially uniform mappings Raildoin Graph Theory Convergence and Rapid Mixing Bounding eigenvalues Conclusion Acknowledgement References fulltext_002 Introduction Preliminaries Attacks by the Generalization of Linear Cryptanalysis Success of the Generalization of Linear Cryptanalysis Random Keys and Threefold Sums Finding Effective Threefold Sunis Applicability of Matsui's "Piling-Up Lemma" A Procedure for Finding Effective “Homomorphic” Threefold Sums Discussion of the Given Procedure Application to DES Some Examples The QRweak Cipher Cryptanalysis of IDEA Cryptanalysis of SAFER K-64 Conclusion Acknowledgments References fulltext_003 Introduction Related Work Results and Contents Definitions Security Against Forgeries Anonymity Signer Identification Secure Group Signatures Lower Bounds Secret Keys Auxiliary Information Comparison with Upper Bound Conclusion References fulltext_004 Introduction Related Work Model and Definitions t- Resilience Secret Sharing VES for Exponentiation Based Signatures RSA Signatures Rabin Signatures VCS for Discrete Log Based Signatures Verifiable Discrete Log Sharing ElGamal Signatures Schnorr Signatures VES for the DSA with Heuristic Secrecy Performance Conclusions References fulltext_005 Introduction Prover-Aided Verification of Identity PAV Protocol for Schnorr's Identification Scheme PAV Protocol for Brickell-McCurley’s Scheme PAV Protocol for Okamoto’s Scheme Signer-Aided Verification of Signatures SAV Protocol for Schnorr’s Signature Scheme Batch SAV Protocol for Schnorr’s Scheme Server-Aided Verification of General Functions Summary and Conclusion References fulltext_006 Introduction Elliptic curves over finite fields Counting the nuiiiber of points Torsion points Schoof's algorithin An overview of the iinprovemcnt,s of Atkin and Elkies Couveigncs's algoritliiii A synthetic description of the algorithm A more elaborate strategy Implemeiitatioii and results General reinarks Basic arithmetic Polyiioiiiial arithnietic Timings Comparison with the case GF(p) Records Conclusion Acknowledgments References fulltext_007 Introduction The Discrete Logarithm Problem in IF, The General Number Field Sieve (GNFS) The Sieving Stage Constructing q-th powers in Of - 5 round protocol Conclusion References fulltext_013 Introduction Prior work Our definition of VSS Comparison with previous definitions of VSS A VSS protocol that satisfies our definition Conclusion References Appendix fulltext_014 Introduction Access Structure Domination Mutually Trusted Authority free Schemes The Base Access Structure Measures of Efficiency The Private Access Structures Mutually Trusted Authority free Threshold Schemes References fulltext_015 Introduction Perfect Secret Sharing (PSS) Information Dispersal Algorithms (IDA) A Simple Information Dispersal Algorithm The Size of Pieces General Information Dispersal Algorithms How to Optimize the Information Rate How to Optimize the Average Information Rate Comparison of the Techniques Modified Schemes Computational Secret Sharing Schemes Conclusions References A Information theory fulltext_016 Introduction The Concept of Fair Blind Signatures Fair Blind Signatures using Cut-and-Choose Type I Fair Blind Signatures using Oblivious Transfer A Variation of the Fiat-Shamir Signature Scheme Fair one-out-of-two Oblivious Transfer Fair Blind Fiat-Shamir Signatures Fair Blind Signatures with Registration Conclusions Acknowledgement References fulltext_017 Introduction Our Requirements Intuition Coin-Ripping for a Specific Protocol The General Solution Conclusion Acknowledgements References Appendix: Another Approach for Fairness fulltext_018 Introduction Background Digital Signatures Blind Signature Issuing Protocols Secret-Key Certificate Schemes Restrictive Blinding of Secret-Key Certificates Restrictive Blinding for the Guillou-Quisquater Secret-Key Certificate Scheme Proof of Correctness Proof of the Primary Purpose Proof of the Property of Restrictive Blinding Sequential Executions of the Issuing Protocol Parallel Executions of the Issuing Protocol Relation to Blind Signature Issuing Protocols Conclusion References fulltext_019 Introduction Linear Statistical Weakness Feedback Polynomial Reconstruction Initial State Reconstruction Conclusion References fulltext_020 Introduction Feedback with Carry Shift Registers Finding L-Sequences for Prime Powers Initial Loading of a FCSR Distributional Properties Arithmetic Correlations Conclusions References fulltext_021 Introduction Preliminaries Properties of Resilient Functions Related Work Constructing New Resilient Functions from Old Transforming Linear Resilient Functions to Nonlinear Ones Remarks on Algebraic Degree Conclusion Acknowledgment References fulltext_022 Introduction Preliminaries Authentication code (A-code) Authentication code with arbitration (A’-code) Combinatorial bounds for A2-codes without secrecy Lower bound on PI and Ps Lower bound on PT Lower bound on PR, and PR, Tightness Lower bound on IERI, JERo ErI and l Er|| Combinatorial bounds for general A2-codes Another definition of Pne and PR1| References fulltext_023 Introduction Technical Background Toeplitz matrices E -balanced hashing and authentication E-biased distributions Discrete Fourier Transform Main Result Proof of Theorem 9 Proof of Theorem 5 Explicit Constructions Acknowledgments References fulltext_024 Introduction Enclosed and disclosed arrays JIC-systems The Wegman&Carter-effect References fulltext_025 Introduction Problems The Perceptrons Problem The Permuted Perceptrons Problem Size of the problem Making the problem practical How to get the keys ? Finite field Possible attacks The majority vector Simulated annealing Practical values Protocols Three pass identification protocol (3p zk) Properties Five pass identification protocol (5p zk) Properties Light versions Performances Conclusion Acknowledgements References fulltext_026 Introduction Singular Cubic Curves Key Generation of Scheme 1 and Scheme 2 Scheme 1 Scheme 2 Efficiency Comparison of Proposed Schemes and Other Schemes Encryption Efficiency of Scheme 1 and Scheme 2 Security Security in One-to-one Communication Security in Broadcast Applications Conclusion Acknowledgement References fulltext_027 Introduction Motivation Summary of Results Computational Complexity, Communication Complexity, and Cryptographic Mechanisms Preliminaries Cryptosystems based on DLP Definitions of Problems Reducibilit Main Results Relationships among the Cryptosysterns The Case of Certified Discrete Logarithms The Case of Elliptic Discrete Logarithms Languages Associated with the Cryptosystems Single-Use versus Multiple-Use in Cryptosystems Concluding Remarks Acknowledgments References fulltext_028 Introduction Preliminaries Hash functions given by linear functions on GF[P] Notation Security of lsb(A(t)X(t) + B(t)) Simultaneous security Hash functions given by linear functions in Zp Notation Security of uz + b (mod p ) Security of other bits Open problems Acknowledgements References fulltext_029 Introduction Background and Definitions Quadratic residuosity and Blum integers Perfect Zero-Knowledge Proof Systems Quadratic non-residuosity OR of many statements on a single random string A multi-bit commitment scheme Many statements on a single random string Acknowledgements References fulltext_030 Introduction Matsumoto and Imai’s Human Identification Scheme Notations and Definitions Matsumoto and Imai’s Scheme An Example The Attacks on Matsumoto and Imai’s Scheme The passive attack The Replay Challenge Attack Modified Identification Scheme The passive attack The Replay Challenge Attack Modified Identification Scheme The Scheme Security Analysis Conclusions Acknowledgement References fulltext_031 Introduction Receipt-Free Voting Schemes Results of This Paper Techniques Used Outline of the Rest of the Paper Universally Verifiable Mix-Net A Scheme with Individual Verifiability Achieving Universal Verifiability Processing Multiple Messages Together Remarks on Vote Duplication Proposed Receipt-Free Scheme Overview The Main Protocol Confirming the Voter Knows his Secret Key References fulltext_032 Introduction, Context and Basic Bricks Fischer-Micali-Rackoff‘s Protocol The Brugia-di Porto-Filipponi (BPF) Number Representation System Randomized Modular Multiplication The Protocol Implementation and Performances Further Extensions : Two-way Authentication Acknowledgments Note References fulltext_033 The result The observations by Pfitzmann et al. References back-matter Author Index Attacking The Chor-rivest Cryptosystem By Improved Lattice Reduction / Claus P. Schnorr And H.h. Horner -- Convergence In Differential Distributions / Luke O'connor -- A Generalization Of Linear Cryptanalysis And The Applicability Of Matsui's Piling-up Lemma / Carlo Harpes, Gerhard G. Kramer And James L. Massey -- On The Efficiency Of Group Signatures Providing Information-theoretic Anonymity / Lidong Chen And Torben P. Pedersen -- Verifiable Signature Sharing / Matthew K. Franklin And Michael K. Reiter -- Server (prover / Signer)-aided Verification Of Identity Proofs And Signatures / Chae Hoon Lim And Pil Joong Lee -- Counting The Number Of Points On Elliptic Curves Over Finite Fields: Strategies And Performances / Reynald Lercier And Francois Morain -- An Implementation Of The General Number Field Sieve To Compute Discrete Logarithms Mod P / Damian Weber -- A Block Lanczos Algorithm For Finding Dependencies Over Gf(2) / Peter L. Montgomery. Louis C. Guillou, Jean-jacques Quisquater, Eds. Sponsored By The International Association For Cryptologic Research (iacr) In Cooperation With The Centre Commun D'études De Télévision Et Télécommications (ccett)--p. [ix]. Includes Bibliographical References And Indexes. Drawing on the proceedings of EUROCRYPT '95, the theory and application of cryptographic techniques is discussed in this text. Revised versions of the 33 papers address aspects of cryptologic research and advanced applications.